<aside> 💡 Proposition: building block of logic
</aside>
<aside> 💡 Declarative sentence: either True or False ( Truth Value )
</aside>
| Connectives | |||
|---|---|---|---|
| Negation | $\neg P$ | ||
| Conjunction | $p\wedge q$ | “and” | |
| Disjunction | $p \vee q$ | “or” | Inclusive |
| Exclusive OR | $p\oplus q$ | ||
| Implication | $p\rarr q$ | $\neg{p}\ \vee\ q$ | |
| Biconditional | $p\lrarr q$ | “if and only if” | “iff” |
| Contradiction | never be true |
|---|---|
| Tautology | alway true |
| Contingencies | … |
| Converse | $q\rarr p$ |
| Inverse | $\neg p \rarr \neg q$ |
| Contrapositive | $\neg q \rarr p$ |
| Equivalence | Name |
|---|---|
| $p \wedge T \equiv p \\ p\vee F \equiv p$ | Identity laws |
| $p \vee T \equiv T\\p\wedge F \equiv F$ | Domination laws |
| $p \wedge p \equiv p \\ p\vee p \equiv p$ | Idempotent laws |
| $\neg(\neg p) \equiv p$ | Double negation law |
| $p\vee q \equiv q \vee p\\ p\wedge q \equiv q\wedge p$ | Commutative laws |
| $(p \vee q )\vee r \equiv p \vee (q \vee r) \\ (p \wedge q )\wedge r \equiv p \wedge (q \wedge r)$ | Associative laws |
| $p \vee (q \wedge r) \equiv (p \vee q)\wedge (p \vee r) \\ p \wedge (q \vee r) \equiv (p \wedge q)\vee (p \wedge r)$ | Distributive laws |
| $\neg (p \wedge q ) \equiv \neg p \vee \neg q\\\neg (p \vee q ) \equiv \neg p \wedge \neg q$ | De Morgan’s laws |
| $p \vee (p \wedge q) \equiv p \\ p \wedge (p \vee q) \equiv p$ | Absorption laws |
| $\neg (p \wedge q ) \equiv \neg p \vee \neg q\\\neg (p \vee q ) \equiv \neg p \wedge \neg q$ | Negation laws |
| $p\rarr q \equiv \neg p \vee q$ | |
| “Conditional Disjunctive Equivalence” |
$$ \neg(\exist xP(x))\equiv\forall x(\neg P(x))\\\text{while} \\ \neg(\forall x Q(x))\equiv\exist x(\neg Q(x)) $$
$$ \text{universal modus tollens: }\\ ∀x(P(x) → Q(x))\\
¬Q(a), \text{where a is a particular element in the domain}\\
∴ ¬P(a) $$
| Union | $A\cup B$ |
|---|---|
| Intersection | $A\cap B$ |
| Difference | $A \setminus B$ |
| Complement | $\overline{A}=U\setminus A$ |
| Cartesian Product | $A\times B=\{(a,b) |
$$ \empty \sube S\\ S\sube S\\ \text{proper subset:} A\sube B \wedge A\ne B $$
$$ |\mathcal{P}(A)|=2^{|A|} $$