Logic Guide

User Manual:

Open the PDF directly: View PDF .
Page Count: 3

Download
Open PDF In Browser	View PDF

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 → P means (P ∧ (¬Q)) → P .
¬(¬p)
p∧p
p∨p
p∧T
p∨F
p∧F
p∨T
p∧q
p∨q
p ∨ ¬p
p ∧ ¬p
p ∧ (q ∧ z)
p ∨ (q ∨ z)
p ∨ (p ∧ q)
p ∧ (p ∨ q)
p ∨ (q ∧ z)
p ∧ (q ∨ z)
¬(p ∧ q)
¬(p ∨ q)
p→q
p↔q

≡
≡
≡
≡
≡
≡
≡
≡
≡
≡
≡
≡
≡
≡
≡
≡
≡
≡
≡
≡
≡

p
p
p
p
p
F
T
q∧p
q∨p
T
F
(p ∧ q) ∧ z
(p ∨ q) ∨ z
p
p
(p ∨ q) ∧ (p ∨ z)
(p ∧ q) ∨ (p ∧ z)
(¬p) ∨ (¬q)
(¬p) ∧ (¬q)
¬p ∨ q
(p → q) ∧ (q → p)

double negation
idempotent laws
identity elements
zero elements (’domination laws’)
commutativity
negation laws (excluded middle and contradiction)
associativity
absorption
distributive laws
De Morgan’s laws
definition of →
definition of ↔

Connection between laws and tautologies:
p ≡ q is a valid law if, and only if, p ↔ q is a tautology.

1

Inference rules for propositional logic
Rule

Corresponding tautology

Name of rule

p

p→q
q

(p ∧ (p → q)) → q

Modus ponens

p

p↔q
q

(p ∧ (p ↔ q)) → q

Equivalence rule

p
q
p∧q

Conjunction rule

p→q
q→r
p→r

(p→q)∧(q→r)→(p→r)

Hypothetical syllogism

[p]
..
.
q
p→q

Discharge hypothesis

∀x P (x)
P (c)

(∀x P (x)) → P (c)

Universal instantiation
(c is any expression)

P (x)

(x is arbitrary)
∀x P (x)

P (c)
∃x P (x)
P (x)

Universal Generalization

P (c) → ∃x P (x)

x=e
P (e)

P (0)

P (0 ())

Existential Generalization

Substitution of equals

∀n. (n 6= 0 → (P (n − 1) → P (n))
∀n ∈ N P (n)))
∀lst. (lst 6=0 () → (P ((cdr lst)) → P (lst)))
∀lst P (lst)

Induction (on naturals)

Induction (on lists)

For Universal Generalization “x is arbitrary” means the proof of P (x) makes no
assumptions about x. By comparison, for Existential Generalization you choose
an expression c and 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
2. P ∨ Q
3. P ∨ Q ≡ Q ∨ P
4. Q ∨ P
5. P → Q ∨ P

assumption
from 1 by Addition rule
commutativity law for ∨ (and Univ. Instantiation!)
from 2 and 3 by Equivalence rule
from 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



---

Source Exif Data:

File Type                       : PDF
File Type Extension             : pdf
MIME Type                       : application/pdf
PDF Version                     : 1.5
Linearized                      : No
Page Count                      : 3
Producer                        : pdfTeX-1.40.15
Creator                         : TeX
Create Date                     : 2015:10:12 11:16:53-04:00
Modify Date                     : 2015:10:12 11:16:53-04:00
Trapped                         : False
PTEX Fullbanner                 : This is pdfTeX, Version 3.14159265-2.6-1.40.15 (TeX Live 2014) kpathsea version 6.2.0

EXIF Metadata provided by EXIF.tools