1. Complete Boolean Base ~p = p => F Once we have define a connective, we can use it for the rest of the connectives T = ~F p \/ q = ~p => q p /\ q = ~( ~p V ~ q) p <=> q = (p => q) /\ (q => p) p xor q = ~p <=> q ite(p,q,r) = p /\ q) \/ (~p /\ r) Since we can write each connective in Propositional Logic in terms of just {=>,F}, every propositional(boolean) expression has an equivalent formula which uses just {=>,F}. Hence {=>,F} is a complete boolean base. 2. (p => r) /\ (q => r) /\ (~p => -r) ______________________________________________________ | (A) (B) (C) | | p q r |(p => r)|(q => r)|(~p => ~r)|A /\ B /\ C | |__________|________|________|__________|____________| | T T T | T | T | T | T | | T T F | F | F | T | F | | T F T | T | T | T | T | | T F F | F | T | T | F | | F T T | T | T | F | F | | F T F | T | F | T | F | | F F T | T | T | F | F | | F F F | T | T | T | T | |____________________________________________________| ite((~p \/ ~q), ~(p \/ q), r) ______________________________________________ | | (A) | (B) | | | p q r |(~p \/ ~q)|~(p \/ q)|ite(A,B,r) | |__________|__________|_________|____________| | T T T | F | F | T | | T T F | F | F | F | | T F T | T | F | F | | T F F | T | F | F | | F T T | T | F | F | | F T F | T | F | F | | F F T | T | T | T | | F F F | T | T | T | |____________________________________________| (p => q) = (~q => ~p) _______________________________________________ | | (A) | (B) | | | p q |(p => q) |(~q => ~p)| A = B | |_________|__________|__________|____________| | T T | T | T | T | | T F | F | F | T | | F T | T | T | T | | F F | T | T | T | |_________|__________|__________|____________| p /\ (p \/ q) = ~p ______________________________________________ | | (A) | (B) | | | p q | (p \/ q) | (p /\ A) | B = ~p | |_________|__________|__________|____________| | T T | T | T | F | | T F | T | T | F | | F T | T | F | F | | F F | F | F | F | |_________|__________|__________|____________| p (+) q (+) r __________________________________ | | (A) | | | p q r | p (+) q | A (+) r | |__________|__________|__________| | T T T | F | T | | T T F | F | F | | T F T | T | F | | T F F | T | T | | F T T | T | F | | F T F | T | T | | F F T | F | T | | F F F | F | F | |__________|__________|__________| 3. Characterizing Formula. 1. (p/\q)\/r = (p/\r)\/q To falsify the statement Take p = false q = false r = true. Take p = q = r would make this statement True. So the statement is both Satisfiable and Falsifiable. 2. ((p => q)/\(r=>s)/\(p\/r))=>(q\/s) Use method2(used in word problems), since this is an implication. Towards a contradiction, lets assume this formula is falsifiable. The only way a => b is false, is when conclusion(b) is false and antecedent(a) is true. i.e. q \/s is false, which makes q := false and s:= false The antecedent is true, when p => q, r=>s and p\/r is true. Since q and s is false, the first p=>q is true only when p is false and r=>s is true only when r is false. But then this makes p\/r false, which contradicts our assumption that the antecedent is true. Therefore this formula is valid. 3. (p\/q) => (p/\q)/\(~p/\q)/\(p/\~q) Take p = True q = False to see that the statement is Falsifiable. Take p = False and q = False to see that the statement is Satisfiable. 4. ~q /\ (p=>q) => q This can be simplified to p \/ q So the Statement is Satisfiable for p = True and q = True And Falsifiable p = False and q = False. 5. p/\((true/\r)/\(false \/ q)) This is simplified to p /\ q /\ r This is Satisfiable for p =q = r = T and Falsifiable for any other assignment to p , q , r. Simplification of Formulas. 1. ~(p \/ (~p/\ q)) ={ by De morgan's Identity } (~p /\ ~(~p /\ q)) ={ by Demorgans Identity} (~p /\ (p \/ ~q) = { by distributive property of /\ over \/} ~p /\ ~q 2. (p \/ q) /\ (( p/\r) \/ (p /\ ~r) \/ (p /\ q) \/ q ={by reverse distribution of /\ over \/} (p \/ q) /\ (( p /\ (r \/ ~r) \/ (p /\ q) \/ ( q)) ={by Absorption} (p \/ q) /\ (( p /\ (r \/ ~r)) \/ (q) ={ By using p \/ ~p = True and True \/ p = True } (p \/ q) /\ ( p \/ q) ={p /\ p = p} (p \/ q) 3. ( p /\ ( ~p \/ q)) \/ ((p \/ ~q) /\ q) ={by distribution of /\ over \/} (p /\ ~p \/ p /\ q) \/ ((p \/ ~q) /\ q) ={by p /\ ~p = False} (p /\ q) \/ ((p \/ ~q) /\ q) ={by distribution of \/ over /\} ( p /\ q ) \/ ((p /\q) \/ (~q /\ q)) ={by p /\ ~p = False} (p /\ q) /\ (p /\ q) = {by p /\ p = p} p /\ q 4. (~p /\ ( p \/ q)) \/ ((q \/ ( p /\ p)) /\ ( p \/ ~q)) ={by distributive of /\ over \/} (~p /\ p \/ ~p /\ q) \/ ((q \/ ( p /\ p)) /\ ( p \/ ~q))) ={by p /\p = False and False \/ p = p} (~p /\ q) \/ ((q \/ ( p /\ p)) /\ ( p \/ ~q))) ={by p /\ p = p } (~p /\ q) \/ ((q \/ p) /\ ( p \/ ~q))) ={ by p \/ q = q \/ p} (~p /\ q) \/ ((p \/ q) /\ ( p \/ ~q))) ={ By distribution } (~p /\ q) \/ ((p /\(p \/ ~q)) \/ (q /\ (p \/ ~q))) ={By Distribution} (~p /\ q) \/ ((p /\ p \/ p /\ ~q) \/ (q /\ p \/ q /\ ~q)) = { by p /\ p = p and q /\ ~q = False} (~p /\ q) \/ (p \/ (p /\ ~q) \/ (p /\ q)) = { by Absorption } (~p /\ q) \/ (p \/ (p /\ q)) = { by Absorption } (~p /\ q) \/ p 5. (p = q) /\ (~q = r) /\ (r = ~q) /\(p= ~r) = { by using p = ~q = ~p = q} (p = q) /\ (~q = r) /\ (~q = r) /\ (p = ~r) = { by using p /\ p = p} (p = q) /\ (~q = r) /\ (p = ~r) ={ by using p = q in rest of the expression} (p = q) /\ (~q = r) /\ (q = ~r) = { by using p = ~q is ~p = q} (p = q) /\ (~q = r) /\ (~q = r) = { by using p /\ p = p} (p = q) /\ (~q = r) 6. (~p /\ r) \/ (q /\ ~r) \/ (p /\ q /\ r) \/ ( p /\ ~q) ={by reverse distribution} (~p /\ r) \/ (q /\ ~r) \/ p /\ ((q /\ r) \/ ~q) ={distribute and use q \/ ~q = true} (~p /\ r) \/ (q /\ ~r) \/ p /\ ((q \/ ~q) /\ (r \/ ~q)) (~p /\ r) \/ (q /\ ~r) \/ p /\ (true /\ (r \/ ~q)) ={true /\ p = p} (~p /\ r) \/ (q /\ ~r) \/ p /\ (r \/ ~q) ={distribute} (~p /\ r) \/ (q /\ ~r) \/ (p /\ r) \/ (p /\ ~q) ={commutavity and associativity of \/} (~p /\ r) \/ (p /\ r) \/ (q /\ ~r) \/ (p /\ ~q) ={reverse distribute} ((p \/ ~p)/\r) \/ (q /\ ~r) \/ (p /\ ~q) ={p \/ ~p = true and true /\ p = p} r \/ (q /\ ~r) \/ (p /\ ~q) ={distribute, r \/ ~r = true and true /\ p = p} (r \/ q) \/ (p /\ ~q) 7. (p => (q => r) ) = ((p /\ q) => r) = { by boolean equality of p =>q = ~p \/ q} (p => (~q \/ r)) = ((p /\ q) => r) = { by boolean equality of p =>q = ~p \/ q} (~p \/ ~q \/ r) = ((p /\ q) => r) ={ by Demorgans equality} (~(p/\q) \/ r) = ((p /\ q) => r) = { by boolean equality of p =>q = ~p \/ q} ((p /\ q) => r) = ((p /\ q) => r) = { p=p = true} true Word problems 1. The weather is warm: p the sky is clear: q go swimming: r go boating: s weather is warm and sky is clear : p /\ q either we go swimming or we go boating : r \/ s do not go swimming : ~r sky is not clear : ~q not the case that if we do not go swimming then the sky is not clear ~( ~r => ~q) Conclusion : weather is warm or we go boating : p \/ s So the formalization is: (((p /\ q) => (r \/ s) ) /\ (~(~r => ~q))) => (p \/ s) Lets see if we can find an assignment for p,q,r,s that falsifies this statement For this expression to be false. p \/ s should be false ( i.e p = false and s = false) This reduces antecedent to (F => (r \/ F)) /\ (~( q=>r)) = T /\ ~(~q \/ r) = q /\ ~r Pick q := true and r :=false which would falsify the formula. 2. Tom takes the advanced course : p Cs 2800 is interesting.: q Tom gets good grade : r Statement 1 : p => q Statement 2 : r /\ p Conclusion : q Claim: ((p=>q) /\ (r/\p)) => q The only way to falsify this formula is q = false and ((p => q) /\ (r /\ p)) = True But q = false would mean antecedent = false. So this is not falsifiable and therefore a valid claim. 3. Ed wins first prize : p Fred wins second prize : q George is disappointed : r Statement 1: p -=> (q \/ r) Statement 2: ~q Conclusion r => ~p Claim: (( p => (q \/ r) ) /\ ~q ) => (r=> ~p) The only way this formula will not be valid is (( p => (q V r) ) /\ ~q ) = True (r => ~p) = False i.e r = True and p = True Choose q := False this would result in falsifying this formula. Therefore claim is not Valid. 4. weather forecast is correct : p seeds are planted in March : q first harvest happens in July : r Statement 1: p => (q=>r) Statement 2: ~r Conclusion: r => ~p Claim: ((p=> (q=>r )) /\ ~r) => (r=> ~p) Towards a contradiction lets try to falsify the claim (r=> ~p) = false and ((p=> (q=>r )) /\ ~r) = true which makes r = true and p = true but r = true makes the antecedent False, contradicting our assumption that the claim is false. So the claim is valid. 5. Natasha is a spy : p works for USA: q works for USSR : r Note (+) : XOR Statement 1: p => (q (+) r) Statement 2: p Conclusion: r /\ q Claim: (p => (q (+) r ) /\ p) => (r /\ q) to Falsify this choose r = false q = true p = true to show the counterexample(falsifying assignment) So the claim is not VALID 6. Arthur pulled a sword from stone : p Arthur is King : q Statement 1: p => q Statement 2: q Conclusion : p Claim: ((p => q ) /\ q ) => p To falsify this Choose p := false and q := false . So this claim is not valid. 6. Decision Procedures. 1.(defun Falsifiable (f) (not (UNSAT (not f)))) 2. (defun Satisfiable (f) (not (UNSAT f))) 3. (defun Validity (g) (UNSAT (not g)))