CS 201 - 11/25/14 ChiQat Lab - Class on Date: 12/02/2014 (Tuesday next week) - Lab Location- SCE 408 - Time Start: 11:00 AM - Time End: 12:15 PM Chapter 14 in A&U, Predicate Logic Quantifiers: Existential Quantifier There exists X such that p(X) exists Universal Quantifier For all X, p(X) exists (ThereExists S)gradeA(S) (ForAll S)needsMoney(S) Note the negation of these Quantifers ~( (ForAll S)needsMoney(S) ) becomes: (ThereExits S)~needsMoney(S) ~( (ThereExists S)gradeA(S) ) becomes: (ForAll S)~gradeA(S) ------------------------------ A conditional statement is an implication if p then q p -> q The contrapositive of an conditional statement if ~q then ~p ~q -> ~p the contrapositive (of a true condition) is always true There are two common types of errors when dealing with these condition statements: converse error inverse error for the statement: if p then q (p -> q) the converse is: if q then p (q -> p) the converse cannot be counted as always being true. the inverse is: if ~p then ~q (~p -> ~q) the inverse cannot be counted as always being true Example: If today is Thanksgiving, then tomorrow is Friday Converse: If Tomorrow is Friday, today is Thanksgiving. Inverse: If Today is not Thanksgiving, then tomorrow is not Friday ======================================= Rule of Universal Modus Ponens Given: (ForAll X) p(X)->q(X) (when p is True for some X then q will also be true for that same X) p(A) (p is true for this particular A) :. q(A) (q is also true for this particular A) =========================================== Rule of Universal Modus Tollens: Given: (ForAllX) p(X)->q(X) (p implies q) ~q(A) (q is not true for this particular A) :. ~p(A) (p is also not true for this particular A) =========================================== Given the following information about a computer program, find the mistake in the program. a. There is an undeclared variable or there is a syntax error in the first five lines. b. If there is a syntax error in the first five lines, then there is a missing semicolon or a variable name is misspelled. c. There is not a missing semicolon. d. There is not a misspelled variable name. First: write out the statement symbolically z: There is an undeclared variable y: there is a syntax error in the first five lines x: there is a missing semicolon w: a variable name is misspelled a. z V y b. y -> ( x V w ) c. ~x d. ~w 1. ~x ^ ~W ( by Rule of Conjuction on c and d ) 2. ~ ( x V W ) ( by DeMorgan's Law on 1 ) 3. ~y ( by Modus Tollens on 2 and b ) 4. z ( by Rule of Elimination on 4 and a ) You then encounter natives E and F. E says: F is a knave. F says: E is a knave. How many knaves are there? z: F is a knave (F is not a knight) y: E is a knave (E is not a knight) x: There are 2 knaves w: There is 1 knave (and 1 knight) v: There are 0 knave (and 2 knights) 0. x V w V v (There is either 0, 1 or 2 knaves) 1. z -> ~(F says is true) (Knaves always lie) 2. ~z -> (F says is true (Knights never lie) 3. y -> ~(E says is true) (Knaves always lie) 4. ~y -> (E says is true (Knights never lie) E says z F says y s5. Suppose x is true (2 knaves: E is a knave and F is a knave.) s6. y (supposition) s7. z (supposition) s8. ~z (by Modus Ponens on 3 and s6) This gives us a contradiction, so the Supposition 5 is false 9. ~x (by Contradiction on 5, s7 and s8) 10. w V v (by elimination on 9 and 0 ) s11. Suppose v is true (0 knaves: E is not a knight and F is not a knight) s12. ~y (supposition) s13. ~z (supposition) s14. z (by Modus Pones on 4 and s12) Another contraditions so s11 is false 15. ~v 16 w (by elimination on 15 and 10) => This is one knave All healthy people eat an apple a day. Herbert is not a healthy person. ∴ Herbert does not eat an apple a day. If a product of two numbers is 0, then at least one of the numbers is 0. For a particular number x, neither (2x + 1) nor (x − 7) equals 0. ∴ The product (2x + 1)(x − 7) is not 0. For all students x, if x studies discrete mathematics, then x is good at logic. Tarik studies discrete mathematics. ∴ Tarik is good at logic. Any sum of two rational numbers is rational. The sum r + s is rational. ∴ The numbers r and s are both rational.