Logic Guide
User Manual:
Open the PDF directly: View PDF 
.
Page Count: 3
CS135 Spring 2015 logic guide, version 0
Some laws of propositional logic
Binding power: ∧,∨bind more tightly than →, less tightly than ¬. For example,
P∧ ¬Q→Pmeans (P∧(¬Q)) →P.
¬(¬p)≡pdouble negation
p∧p≡pidempotent laws
p∨p≡p
p∧T≡pidentity elements
p∨F≡p
p∧F≡Fzero elements (’domination laws’)
p∨T≡T
p∧q≡q∧pcommutativity
p∨q≡q∨p
p∨ ¬p≡Tnegation laws (excluded middle and contradiction)
p∧ ¬p≡F
p∧(q∧z)≡(p∧q)∧zassociativity
p∨(q∨z)≡(p∨q)∨z
p∨(p∧q)≡pabsorption
p∧(p∨q)≡p
p∨(q∧z)≡(p∨q)∧(p∨z) distributive laws
p∧(q∨z)≡(p∧q)∨(p∧z)
¬(p∧q)≡(¬p)∨(¬q) De Morgan’s laws
¬(p∨q)≡(¬p)∧(¬q)
p→q≡ ¬p∨qdefinition of →
p↔q≡(p→q)∧(q→p) definition of ↔
Connection between laws and tautologies:
p≡qis a valid law if, and only if, p↔qis a tautology.
1
Inference rules for propositional logic
Rule Corresponding tautology Name of rule
p p →q
q(p∧(p→q)) →qModus ponens
p p ↔q
q(p∧(p↔q)) →qEquivalence rule
p q
p∧qConjunction rule
p→q q →r
p→r(p→q)∧(q→r)→(p→r) Hypothetical syllogism
[p]
.
.
.
q
p→qDischarge hypothesis
∀x P (x)
P(c)(∀x P (x)) →P(c) Universal instantiation
(cis any expression)
P(x) (xis arbitrary)
∀x P (x)Universal Generalization
P(c)
∃x P (x)P(c)→ ∃x P (x) Existential Generalization
P(x)x=e
P(e)Substitution of equals
P(0) ∀n. (n6= 0 →(P(n−1) →P(n))
∀n∈NP(n))) Induction (on naturals)
P(0()) ∀lst. (lst 6=0() →(P((cdr lst)) →P(lst)))
∀lst P (lst)Induction (on lists)
For Universal Generalization “xis arbitrary” means the proof of P(x) makes no
assumptions about x. By comparison, for Existential Generalization you choose
an expression cand prove P(c).
2
When doing a proof in step-by-step style, these rules justify that one line
follows from previous lines. For example, here is a proof of P→Q∨P.
1. P assumption
2. P ∨Qfrom 1 by Addition rule
3. P ∨Q≡Q∨Pcommutativity law for ∨(and Univ. Instantiation!)
4. Q ∨Pfrom 2 and 3 by Equivalence rule
5. P →Q∨Pfrom 1 and 4 by Discharge hypothesis
A complete proof shouldn’t have any assumptions that were not discharged.
When doing a proof in equational style, we are implicitly using one the
following rule:
P≡Q Q ≡R
P≡R
and similarly for equality (=) for numeric expressions etc.
3
