CSC 28 - Discrete Structures - Logic ------------------------------------ ** These notes are not intended as a replacement to lecture. Their sole purpose ** is to remind me what I want to say, and remind you what I thought was ** important Logical Statements: ------------------- A statement is any declarative sentence. It is either true or false. "There are exactly 35 people in this room" "10 + 2 = 11" "There is carbon-based life on other planets in the universe" Statements can be combined into compound statements. They are still statements. If p and q are both statements, then so are p and q p or q not p p implies q Draw truth tables for each. ** Implication: The only one of these that gives people trouble is implication. - The only time "p implies q" is contradicted is when p is true and q is false. Consider "If x > 2 then x^2 > 4" This statement is always true. No matter what value x actually is, it does not change the fact that if it were greater than 2 then its square would be greater than 4. By making x different values we can make the hypothesis true or false and the consequent true or false, but we can never make the hypothesis true and the consequent false. Thus, p -> q == not (p and not q) == (not p) or q -------- Because compound statements are statements themselves, they can be combined with the operators as well. p AND q OR r ===> Ooops! Ambiguous! Just like 2 + 3 * 4 in math. Just like +/- with numbers, the order of evaluation matters. p = f q = f r = t In math we use precedence or parentheses to resolve the problem. precedence: NOT > AND > OR > IMPLIES. To resolve a compound statement: Repeatedly evaluate the highest precedent operator whose operands are already resolved. Ex: (p and q) or (not p and q) Use truth tables to determine the answer. [ Write truth table ] Tautology --------- A statement that is always true is a tautology. A statement that is always false is a contradiction. is ((not p) and q) and (p or (not q)) either? Logical equivalence ------------------- Sometimes we have a statement such as "it is not true that x is even and x is odd", and it may be more convenient to have the statement "x is not even or x is not odd" As it turns out, these statements are equivalent. Either both are true or both are false. Some other examples of logical equivalents are: not not p == p p --> q == (not p) or q ==> eg, (x <= 2) or (x^2 > 4) When do we know if two statements are logically equivalent? When their truth values are identical for all possible truth combinations. Statements P and Q are logically equivalent if they share the same truth table Ex (De Morgan) : not (p and q) \equiv not p or not q Ex p --> q \equiv not p or q. Algebra of logical equivalences ------------------------------- There are many simple equivalents which are useful to manipulate compound statements. For example p and (q and r) == (p and q) and r [associative law] not (p or q) == not p and not q [demorgan] not not p = p [double negation] We can use this algebra to show equivalencies between two statements instead of using a truth table. (p and q) or (not p and q) \equiv (p or not p) and q [distributive law] true and q [complement law] q [identity law] This is also how one would simplify a statement to its simplest form (something not easily done via truth table). truth tables become unwieldy as the number of variables increase. This algebra is another way to evaluate equivalence. Arguments --------- Sometimes we have a combination of true statements that together allow us to claim another statement as true: raining --> wet outside not wet outside ----------------------- ? raining --> wet outside not raining ----------------------- ? x not even or x not odd x even ----------------------- ? An argument is a collection of statements, which when all true, imply a consequence. if it's raining then the ground is wet it is raining ------------------------ the ground is wet p --> q q --> r -------- p --> r In general an argument form is valid if the conclusion is true everywhere all the premises are true. This means we can prove arguments by building truth tables. Ex: Show p --> (q --> r) q --------------- p --> r Figure 1.4.1 (pg 36) lists seven rules of inference (valid argument forms) and their names, some of which are p Modus ponens p --> q ------- q not q Modus tollens p --> q ------- not p p or q [disjunctive syllogism] not p ------- q p --> q [hypothetical syllogism] q --> r ------- p --> r Ex: If I study, then I will pass If I do not go to a movie, then I will study I failed --------------------- I went to a movie p: study q: pass r: movie 1 p --> q 2 not r --> p 3 not q ----------- r Two ways to solve this problem (a) truth table (b) logical deduction 1. not p [premises 1 and 3, Modus tollens] 2. not not r [1 and premise 2, modus tollens] 3. r [2, double negation] Summary ------- To show logical equivalence (i) Draw truth-tables for two statements. If identical, then equivalent; or (ii) Write a sequence of logical equivalences according to the laws of propositions. To show an argument valid, (iii) (a) Draw truth table for all statements involved (b) Identify truth assignments that make all premises true (c) if the conclusion is true everywhere the premises are, the argument is valid. (iv) Begin with what is known true, use rules of inference and logical equivalences to deduce the sought conclusion.