User:Arthur Rubin/Rules

From

• Rubin, Jean E. (1990). Mathematical Logic: Applications and Theory. Saunders College Publishing. ISBN 0-03-012808-0.

• Note: I'm going to skip rules of identity
• Note: Even if this is a potentional copyright violation, does anyone doubt I can get permission?

• Tautology:

  If $\vDash P_{1}\land P_{2}\land \cdots \land P_{n}\rightarrow Q$ ($P_{1}\land P_{2}\land \cdots \land P_{n}\rightarrow Q$ is a tautology), then $P_{1},P_{2},\cdots ,P_{n}\vdash Q$

  (note that n may equal 0.)

• Tautologically Equivalent Formulas

  If $\vDash \psi _{1}\leftrightarrow \psi _{2}$ and $\varphi _{2}$ is obtained from $\varphi _{1}$ by substituing some occurences of $\psi _{1}$ by $\psi _{2}$, then $\vDash \varphi _{1}\leftrightarrow \varphi _{2}$

• (Implict rule of proof)

  If

  $\Gamma _{1}\vdash P_{1}$,

  $\Gamma _{2}\vdash P_{2}$,

  .

  .

  .

  $\Gamma _{n}\vdash P_{n}$,

  $P_{1},P_{2},\cdots ,P_{n}\vdash Q$, then

  $\Gamma _{1}\cup \Gamma _{2}\cup \cdots \cup \Gamma _{n}\vdash Q$

Specific tautologies:

1. $P\land (P\rightarrow Q)\rightarrow Q$ Rule of Detachment, Modus Ponens
2. $\neg Q\land (P\rightarrow Q)\rightarrow \neg P$ (Modus Tollendo Tollens)
3. $\neg P\land (P\lor Q)\rightarrow Q$ (Modus Tollendo Ponens)
4. $P\land Q\rightarrow P$ (Rule of Simplification)
5. $P\rightarrow P\lor Q$ (Rule of Addition)
6. Rule of Adjunction
   • $P\rightarrow (Q\rightarrow P\land Q)$
   • $(P\rightarrow Q)\land (P\rightarrow R)\rightarrow (P\rightarrow Q\land R)$
7. $(P\rightarrow Q)\land (Q\rightarrow R)\rightarrow (P\rightarrow R)$ (Rule of Hypothetical Syllogism)
8. Rules of Alternative Proof
   • $(P\rightarrow Q)\land (\neg P\rightarrow Q)\rightarrow Q$
   • $(P\lor Q\rightarrow R)\leftrightarrow (P\rightarrow R)\land (Q\rightarrow R)$
9. Rule of Absurdity
   • $(P\rightarrow Q\land \neg Q)\rightarrow \neg P$
   • $P\land \neg P\rightarrow Q$
10. $P\lor \neg P$ (Rule of the Excluded Middle)
11. $\neg (P\land \neg P)$ (Rule of Contradiction)
12. Communtative Rules
    • $P\lor Q\leftrightarrow Q\lor P$
    • $P\land Q\leftrightarrow Q\land P$
13. Associative Rules
    • $P\lor (Q\lor R)\leftrightarrow (P\lor Q)\lor R$
    • $P\land (Q\land R)\leftrightarrow (P\land Q)\land R$
14. Distributive Rules
    • $P\lor (Q\land R)\leftrightarrow (P\lor Q)\land (P\lor R)$
    • $P\land (Q\lor R)\leftrightarrow (P\land Q)\lor (P\land R)$
15. De Morgan's Rules
    • $\neg (P\lor Q)\leftrightarrow \neg P\land \neg Q$
    • $\neg (P\land Q)\leftrightarrow \neg P\lor \neg Q$
16. $\neg \neg P\leftrightarrow P$ (Rule of Double Negation)
17. Rules for the Conditional
    • $(P\rightarrow Q)\leftrightarrow \neg P\lor Q$
    • $\neg (P\rightarrow Q)\leftrightarrow P\land \neg Q$
18. Rules for the Biconditional
    • $(P\leftrightarrow Q)\leftrightarrow (P\rightarrow Q)\land (Q\rightarrow P)$
    • $(P\leftrightarrow Q)\leftrightarrow (P\land Q)\lor (\neg P\land \neg Q)$
    • $(P\leftrightarrow Q)\leftrightarrow (\neg P\lor Q)\land (P\land \neg Q)$
19. Idempotency Rules
    • $P\lor P\leftrightarrow P$
    • $P\land P\leftrightarrow P$
20. Rules of Contraposition
    • $(P\rightarrow Q)\leftrightarrow (\neg Q\rightarrow \neg P)$
    • $(P\rightarrow \neg Q)\leftrightarrow (Q\rightarrow \neg P)$
    • $(\neg P\rightarrow Q)\leftrightarrow (\neg Q\rightarrow P)$
21. $(P\rightarrow (Q\rightarrow R))\leftrightarrow (P\land Q\rightarrow R)$ (Rule of Exportation-Importation)
22. Rules of Absorption
    • $P\lor (P\land Q)\leftrightarrow P$
    • $P\land (P\lor Q)\leftrightarrow P$

(non-tautological rules)

• Conditional Proof

  If $\Gamma ,P\vdash Q$ then $\Gamma \vdash P\rightarrow Q$

• Indirect proof

  If $\neg P,\Gamma \vdash Q\land \neg Q$, then $\Gamma \vdash P$

(non-tautological rules of the predicate calculus)

• Existential generalization

  $\varphi [t|v]\vdash (\exists v)\varphi$ if the substitution of t for v in $\varphi$

• Existential Proof

  If $\Gamma ,\psi [v|u]\vdash \varphi$, then $\Gamma ,(\exists u)\psi \vdash \varphi$, provided that

  1. The substitution of v for u in $\psi$ is valid
  2. v is not free in $\varphi$
  3. v is not free in $\Gamma$

• Universal Generalization

  If $\Gamma \vdash \varphi$, then $\Gamma \vdash (\forall v)\varphi$,

  if v is not free in $\Gamma$.

• Universal Specification

  $(\forall v)\varphi \vdash \varphi [t|v]$,

  if the substitution of t for v is valid.