Cheatsheet

Propositional Logic

Logical Equivalence

• Double Negation (1) $\phi \equiv \neg \neg \phi$
• (2) if $\phi \equiv \neg \psi$ then $\neg \phi \equiv \psi$
• Material Implication 3. $(\phi \to \psi )\equiv (\neg \phi \vee \psi )$ 4. $(\phi \vee \psi )\equiv (\neg \phi \to \psi )$
• • (5A) $\neg (\phi \to \neg \psi )\equiv (\phi \wedge \psi )$
  • (5B) $\neg (\phi \to \psi )\equiv (\phi \wedge \neg \psi )$
• De Morgan
  • (6A) $\neg (\phi \vee \psi )\equiv (\neg \phi \wedge \neg \psi )$
  • (6B) $(\phi \vee \psi )\equiv \neg (\neg \phi \wedge \neg \psi )$
  • (7A) $\neg (\phi \wedge \psi )\equiv (\neg \phi \vee \neg \psi )$
  • (7B) $(\phi \wedge \psi )\equiv \neg (\neg \phi \vee \neg \psi )$
• Distributivity
  • (8) $(\phi \vee (\psi \wedge \theta ))\equiv ((\phi \vee \psi )\wedge (\phi \vee \theta ))$
  • (9) $(\phi \wedge (\psi \vee \theta ))\equiv ((\phi \wedge \psi )\vee (\phi \wedge \theta ))$
• Contraposition
  • (10) $(\neg \phi \to \neg \psi )\equiv (\psi \to \phi )$
• Biconditional
  • (11) $(\phi \leftrightarrow \psi )\equiv ((\phi \to \psi )\wedge (\psi \to \phi ))$
• Exclusive OR
  • (12) $(\phi \leftrightarrow \psi )\equiv ((\phi \wedge \psi )\vee (\neg \phi \wedge \neg \psi ))$

Proof Claculus

Logical Axioms in Propositional Language $L_{\to }$

1. $(\phi \to (\psi \to \theta ))$
2. $(\phi \to (\psi \wedge \theta ))\to ((\phi \to \psi )\to (\phi \to \theta ))$
3. $(\neg \phi \to \neg \psi )\to (\psi \to \phi )$

Additional Logical Axioms in propositional language $L$

4. (a) $((\alpha \wedge \beta )\to \alpha )$ (conjunction elimination)
5. (b) $((\alpha \wedge \beta )\to \beta )$ (conjunction elimination)
6. $(\alpha \to (\beta \to (\alpha \wedge \beta )))$ (conjunction introduction)
7. (a) $((\beta \to (\alpha \vee \beta ))$ (disjunction introduction)
8. (b) $((\alpha \to (\alpha \vee \beta ))$ (disjunction introduction)
9. $(\neg \alpha \to ((\alpha \vee \beta )\to \beta ))$ (modus tollens)
10. (a) $((\alpha \leftrightarrow \beta )\to (\alpha \to \beta ))$ (biconditional elimination)
11. (b) $((\alpha \leftrightarrow \beta )\to (\beta \to \alpha ))$ (biconditional elimination)
12. $((\alpha \to \beta )\wedge ((\beta \to \alpha )\to (\alpha \leftrightarrow \beta )))$ (biconditional introduction)

Rules of Inference (Modus Ponens)

$\frac{\phi ,(\phi \to \psi )}{\psi }$ (modus ponens)

Predicate Logic

Additional L. Axioms in Predicate Language

Axioms of $\forall$
$\forall x\phi \to \phi [t/x]$	if no variable occur in $t$ become bonud
$\forall x(\phi \to \psi )\to (\phi \to \forall x\psi )$	if $x$ is not occur freely in $\phi$

• $\frac{\phi }{\forall x\phi }$ (generalization)

Natural Deduction

$\frac{\phi \alpha }{\exists x\phi x}$
$\frac{\exists x\phi x}{\phi \alpha }$
$\frac{\phi x}{\forall y\phi y}$ (where $x$ is a var., and $y$ isn’t free in $\phi x$todo)
$\frac{\forall y\phi y}{\phi a}$ (where $y$ is a variable, and $a$ is a constant)

Logical Validity (אמיתות לוגיות)

• $(\forall x\phi )\leftrightarrow (\neg \exists x\neg \phi )$
• $(\neg \forall x\phi )\leftrightarrow (\exists x\neg \phi )$
• $(\exists x\phi )\leftrightarrow (\neg \forall x\neg \phi )$
• $(\neg \exists x\phi )\leftrightarrow (\forall x\neg \phi )$

where $x$ is not free in $\psi$, then the following formulas are logical valid:

• $[(\forall x\phi )\wedge \psi ]\leftrightarrow \forall x(\phi \wedge \psi )$

• $[(\forall x\phi )\vee \psi ]\leftrightarrow \forall x(\phi \vee \psi )$

• $[(\exists x\phi )\wedge \psi ]\leftrightarrow \exists x(\phi \wedge \psi )$

• $[(\exists x\phi )\vee \psi ]\leftrightarrow \exists x(\phi \vee \psi )$

• $\forall x(\psi \to \phi )\leftrightarrow [\psi \to (\forall x\phi )]$

• $\exists x(\psi \to \phi )\leftrightarrow [\psi \to (\exists x\phi )]$

• $\forall x(\phi \to \psi )\leftrightarrow [(\exists x\phi )\to \psi ]$

• $\exists x(\phi \to \psi )\leftrightarrow [(\forall x\phi )\to \psi ]$