1 Propositional Logic - Axioms and Inference Rules

[Pages:22]1 Propositional Logic - Axioms and Inference Rules

Axioms

Axiom 1.1 [Commutativity] (p q) = (q p) (p q) = (q p) (p = q) = (q = p)

Axiom 1.2 [Associativity] p (q r) = (p q) r p (q r) = (p q) r

Axiom 1.3 [Distributivity] p (q r) = (p q) (p r) p (q r) = (p q) (p r)

Axiom 1.4 [De Morgan] ?(p q) = ?p ?q ?(p q) = ?p ?q

Axiom 1.5 [Negation] ??p = p

Axiom 1.6 [Excluded Middle] p ?p = T

1

Axiom 1.7 [Contradiction] p ?p = F

Axiom 1.8 [Implication] p q = ?p q

Axiom 1.9 [Equality] (p = q) = (p q) (q p)

Axiom 1.10 [or-simplification] pp = p pT = T pF = p

p (p q) = p

Axiom 1.11 [and-simplification] pp = p pT = p pF = F

p (p q) = p

Axiom 1.12 [Identity] p=p

2

Inference Rules

p1 = p2 , p2 = p3 p1 = p3

Transitivity

p1 = p2

Substitution

E(p1) = E(p2) , E(p2) = E(p1)

q1 , q2 , . . . , qn , q1 q2 . . . qn (p1 = p2) E(p1) = E(p2) , E(p2) = E(p1)

Conditional Substitution

3

2 Propositional Logic - Derived Theorems

Equivalence and Truth Theorem 2.1 [Associativity of = ] ((p = q) = r) = (p = (q = r))

Theorem 2.2 [Identity of = ] (T = p) = p

Theorem 2.3 [Truth] T

Negation, Inequivalence, and False Theorem 2.4 [Definition of F ] F = ?T

Theorem 2.5 [Distributivity of ? over = ] ?(p = q) = (?p = q) (?p = q) = (p = ?q)

Theorem 2.6 [Negation of F ] ?F = T

4

Theorem 2.7 [Definition of ?] (?p = p) = F

?p = (p = F )

Disjunction Theorem 2.8 [Distributivity of over = ]

(p (q = r)) = ((p q) = (p r)) ((p (q = r)) = (p q)) = (p r)

Theorem 2.9 [Distributivity of over ] p (q r) = (p q) (p r)

Conjunction Theorem 2.10 [Mutual definition of and ]

(p q) = (p = (q = (p q))) (p q) = ((p = q) = (p q)) ((p q) = p) = (q = (p q)) ((p q) = (p = q)) = (p q) (((p q) = p) = q) = (p q)

Theorem 2.11 [Distributivity of over ] p (q r) = (p q) (p r)

5

Theorem 2.12 [Absorption] p (?p q) = p q p (?p q) = p q

Theorem 2.13 [Distributivity of over = ] (p q) = ((p ?q) = ?p)

((p q) = (p ?q)) = ?p p (q = p) = (p q)

Theorem 2.14 [Replacement] (p = q) (r = p) = (p = q) (r = q)

Theorem 2.15 [Definition of = ] (p = q) = (p q) (?p ?q)

Theorem 2.16 [Exclusive or] ?(p = q) = (?p q) (p ?q)

Implication Theorem 2.17 [Definition of Implication]

(p q) = ((p q) = q) ((p q) = (p q)) = q

(p q) = ((p q) = p) ((p q) = (p q)) = p

6

Theorem 2.18 [Contrapositive] (p q) = (?q ?p)

Theorem 2.19 [Distributivity of over = ] p (q = r) = ((p q) = (p r))

Theorem 2.20 [Shunting] p q r = p (q r)

Theorem 2.21 [Elimination/Introduction of ] p (p q) = p q p (q p) = p p (p q) = T p (q p) = ?q p

(p q) (p q) = (p = q) p F = ?p F p = T

Theorem 2.22 [Right Zero of ] (p T ) = T

Theorem 2.23 [Left Identity of ] (T p) = p

7

Theorem 2.24 [Weakening/Strengthening] p pq

pq p pq pq p (q r) p q p q p (q r)

Theorem 2.25 [Modus Ponens] p (p q) q

Theorem 2.26 [Proof by Cases] (p r) (q r) = (p q r)

(p r) (?p r) = r

Theorem 2.27 [Mutual Implication] (p q) (q p) = (p = q)

Theorem 2.28 [Antisymmetry] (p q) (q p) (p = q)

Theorem 2.29 [Transitivity] (p q) (q r) (p r) (p = q) (q r) (p r) (p q) (q = r) (p r)

Theorem 2.30 [Monotonicity of ] (p q) (p r q r)

8

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download