Propositions • Definition ○ A proposition is a declarative sentence that is either true or false. • Examples of propositions ○ The Moon is made of green cheese. ○ Paris is the capital of Europe. ○ Toronto is the capital of Canada. ○ 1 + 0 = 1 ○ 0 + 0 = 2 • Examples that are not propositions ○ Sit down! ○ What time is it? ○ x+1=2 ○ x+y=z Constructing Propositions • Propositional Variables: p, q, r, s, … • The proposition that is always true is denoted by T • The proposition that is always false is denoted by F. Compound Propositions • Definition ○ Propositions constructed from logical connectives and other propositions • Negation ¬ ○ The negation of a proposition p is denoted by ¬p ○ Truth table p ¬p T F F T ○ Example § If p denotes “The earth is round.” § Then ¬p denotes “It is not the case that the earth is round,” § Or more simply “The earth is not round.” • Conjunction ∧ ○ The conjunction of propositions p and q is denoted by p∧q ○ Truth Table p q p∧q T T T T F F F T F F F F ○ Example § If p denotes “I am at home.” and q denotes “It is raining.” § Then p∧q denotes “I am at home and it is raining.” • Disjunction ∨ ○ The disjunction of propositions p and q is denoted by p∨q ○ Truth Table p q p∨q T T T T F T F T T F F F ○ Example § If p denotes “I am at home.” and q denotes “It is raining.” § Then p∨q denotes “I am at home or it is raining.” • Inclusive Or vs Exclusive Or ○ “Inclusive Or” § In the sentence “Students who have taken CS202 or Math120 may take this class,” we assume that students need to have taken one of the prerequisites, but may have taken both. § This is the meaning of disjunction. § For p ∨ q to be true, either one or both of p and q must be true. ○ “Exclusive Or” § When reading the sentence “Soup or salad comes with this entrée,” we do not expect to be able to get both soup and salad. § This is the meaning of Exclusive Or (XOR). § In p⊕q , one of p and q must be true, but not both. § The truth table for ⊕ is: p q p⊕q T T F T F T F T T F F F • Implication → ○ If p and q are propositions, then p→q is a conditional statement or implication which is read as “if p, then q ” ○ Truth Table p q p→q T T T T F F F T T F F T ○ Example § If p denotes “I am at home.” and q denotes “It is raining.” § Then p→q denotes “If I am at home then it is raining.” ○ In p→q, p is the hypothesis (antecedent or premise) and q is the conclusion (or consequence). • Biconditional ↔︎ ○ If p and q are propositions, then we can form the biconditional proposition p↔︎q , read as “p if and only if q.” ○ Truth Table p q p↔︎q T T T T F F F T F F F T ○ If p denotes “I am at home.” and q denotes “It is raining.” then p↔︎q denotes “I am at home if and only if it is raining.” • Example p q (¬p)∧(¬q) (¬p)∨(¬q) T T F F T F F T F T F T F F T T Converse, Contrapositive, and Inverse • From p→q we can form new conditional statements . ○ q→p is the converse of p→q ○ ¬q→¬p is the contrapositive of p→q ○ ¬p→¬q is the inverse of p→q • Example ○ “If it is raining, then I will not go to town.” ○ p: “It is raining” ○ q: “I am going to town” ○ Sufficient Condition § It raining is a sufficient condition for my not going to town. ○ Necessary Condition § My not going to town is a necessary condition for it raining. ○ Converse § If I do not go to town, then it is raining. ○ Inverse § If it is not raining, then I will go to town. ○ Contrapositive § If I go to town, then it is not raining. • Truth Table p q p→q q→p ¬q→¬p ¬p→¬q ¬(p→q) T T T T T T F T F F T F T T F T T F T F F F F T T T T F Truth Table for Compound Propositions • Construction of a truth table: ○ Rows § Need a row for every possible combination of values for the atomic propositions. ○ Columns § Need a column for the compound proposition (usually at far right) § Need a column for the truth value of each expression that occurs in the compound proposition as it is built up. § This includes the atomic propositions • Precedence of Logical Operators Operator Precedence ¬ 1 ∧ 2 ∨ 3 → 4 ↔︎ 5 • Example: p∨q→¬r p q r p∨q ¬r p∨q→¬r T T T T F F T F T T F F F T T T F F F F T F F T T T F T T T T F F T T T F T F T T T F F F F T T
