ch01s4

Formal Logic: 

Formal Logic Mathematical Structures for Computer Science Chapter 1 Copyright © 2006 W.H. Freeman & Co. MSCS Slides Formal Logic

Predicate Logic: 

Predicate Logic Similar to propositional logic for solving arguments, build from quantifiers, predicates and logical connectives. A valid argument for predicate logic need not be a tautology. The meaning and the structure of the quantifiers and predicates determines the interpretation and the validity of the arguments Basic approach to prove arguments: Strip of quantifiers Manipulate the unquantified wffs Reinsert the quantifiers Four new inference rules Note to remember: P(x) could be (y) (z) Q(x,y,z)

Inference Rules: 

Inference Rules

Examples: Proofs using Predicate Logic: 

Examples: Proofs using Predicate Logic Prove the following argument: All flowers are plants. Sunflower is a flower. Therefore, sunflower is a plant. P(x) is “ x is a plant” a is a constant symbol (Sunflower) Q(x) is “x is a flower” The argument is (x)[P(x)  Q(x)] Λ P(a)  Q(a) The proof sequence is as follows: (x)[P(x)  Q(x)] hyp P(a) hyp P(a)  Q(a) 1, ui Q(a) 2, 3, mp

Examples: Proofs using Predicate Logic: 

Examples: Proofs using Predicate Logic Prove the argument (x)[P(x)  Q(x)] Λ [Q(y)]  [P(y)] Proof sequence: (x)[P(x)  Q(x)] hyp [Q(y)] hyp P(y)  Q(y) 1, ui [P(y)] 2, 3, mt Prove the argument (x)P(x)  (x)P(x) Proof sequence: (x)P(x) hyp P(x) 1, ui (x)P(x) 2, eg

Examples: Proofs using Predicate Logic: 

Examples: Proofs using Predicate Logic Prove the argument (x)[P(x)  Q(x)] Λ (x)P(x)  (x)Q(x) Proof sequence: (x)[P(x)  Q(x)] hyp (x)P(x) hyp P(x)  Q(x) 1, ui P(x) 2, ui : no restriction on ui about reusing a name Q(x) 3, 4, mp (x)Q(x) 5, ug Note: step 6 is legitimate since x is not a free variable in any hypothesis nor was ei used before

Examples: Proofs using Predicate Logic: 

Examples: Proofs using Predicate Logic Prove the argument (x)[P(x) Λ Q(x)]  (x)P(x) Λ (x)Q(x) Proof sequence: (x)[P(x) Λ Q(x)] hyp P(x) Λ Q(x) 1, ui P(x) 2, sim Q(x) 2, sim (x)P(x) 3, ug (x)Q(x) 4, ug (x)P(x) Λ (x)Q(x) 5, 6, con

Examples: Proofs using Predicate Logic: 

Examples: Proofs using Predicate Logic Prove the argument (y)[P(x)  Q(x,y)]  [P(x)  (y)Q(x,y)] Using the deduction method, we can derive (y)[P(x)  Q(x,y)] Λ P(x)  (y)Q(x,y) Proof sequence: (y)[P(x)  Q(x,y)] hyp P(x) hyp P(x)  Q(x,y) 1, ui Q(x,y) 2, 3, mp (y)Q(x,y) 4, ug

Temporary hypotheses: 

Temporary hypotheses A temporary hypothesis can be inserted into a proof sequence. If T is inserted as a temporary hypothesis and eventually W is deduced from T and other hypotheses, then the wff T  W has been deduced from other hypotheses and can be reinserted into the proof sequence Prove the argument [P(x)  (y)Q(x,y)]  (y)[P(x)  Q(x,y)] Proof sequence: P(x)  (y)Q(x,y) hyp P(x) temporary hypothesis (y)Q(x,y) 1, 2, mp Q(x,y) 3, ui P(x)  Q(x,y) temp. hyp discharged (y)[P(x)  Q(x,y)] 5, ug

More Examples: 

More Examples Prove the sequence [(x)A(x)]  (x)[A(x)] To prove equivalence, implication in each direction should be proved Proof sequence for [(x)A(x)]  (x)[A(x)] [(x)A(x)] hyp A(x) temp. hyp (x)A(x) 2, eg A(x)  (x)A(x) temp. hyp discharged [A(x)] 1, 4, mt (x)[A(x)] 5, ug Proof sequence for (x)[A(x)]  [(x)A(x)] (x)[A(x)] hyp (x)A(x) temp. hyp A(a) 2, ei [A(a)] 1, ui [(x)[A(x)]] 3, 4, inc (x)A(x)  [(x)[A(x)]] temp. discharged [((x)[A(x)])] 1, dn [(x)A(x)] 6, 7, mt

Proving Verbal arguments: 

Proving Verbal arguments Every crocodile is bigger than every alligator. Sam is a crocodile. But there is a snake, and Sam isn’t bigger than that snake. Therefore, something is not an alligator. Use C(x): x is a crocodile; A(x): x is an alligator, B(x,y): x is bigger than y, s is a constant (Sam), S(x): x is a Snake Hence prove argument (x) (y)[C(x) Λ A(y)  B(x,y)] Λ C(s) Λ (x)(S(x) Λ [B(s,x)])  (x)[A(x)] (x) (y)[C(x) Λ A(x)  B(x,y)] hyp C(s) hyp (x)(S(x) Λ [B(s,x)]) hyp (y)[C(s) Λ A(y)  B(s,y)] 1, ui S(a) Λ [B(s,a)]) 3, ei C(s) Λ A(a)  B(s,a) 4, ui [B(s,a)] 5, sim [C(s) Λ A(a)] 6, 7, mt [C(s)] V [A(a)] 9, De Morgan [[C(s)]] 2, dn [A(a)] 9, 10, ds (x)[A(x)] 11, eg

Class Exercise: 

Class Exercise Prove the argument (x)[(B(x) V C(x))  A(x)]  (x)[B(x)  A(x)] Proof sequence: (x)[(B(x) V C(x))  A(x)] hyp (B(x) V C(x))  A(x) 1, ui B(x) temp. hyp B(x) V C(x) 3, add A(x) 2, 4, mp B(x)  A(x) temp. hyp discharged (x)[B(x)  A(x)] 6, ug

Class exercise: 

Class exercise Every ambassador speaks only to diplomats, and some ambassadors speak to someone. Therefore, there is a diplomat. Use A(x): x is an ambassador; S(x,y): x speaks to y; D(x): x is a diplomat Proof Sequence: (x) (y)[(A(x) Λ S(x,y))  D(y)] hyp (x)(y)(A(x) Λ S(x,y)) hyp (y)((A(a) Λ S(a,y))  D(y)) 1, ui (y)(A(a) Λ S(a,y)) 2, ei A(a) Λ S(a,b) 4, ei (A(a) Λ S(a,b))  D(b) 3, ui D(b) 5, 6, mp (x)D(x) 7, eg Prove the argument (x) (y)[(A(x) Λ S(x,y))  D(y)] Λ (x)(y)(A(x) Λ S(x,y))  (x)D(x)