WIXLIB

Truth TablesCreator: Malik Magdon-Ismailpq pp qffttftftttffffftMaking Precise Statements: 10 / 27p qImplication (if. . . then. . . ), p q

Truth TablesCreator: Malik Magdon-Ismailpq pp qp qffttftftttffffftftttMaking Precise Statements: 10 / 27Implication (if. . . then. . . ), p q

Truth Tablespq pp qp qffttftftttffffftftttThe truth table defines the “meaning” of these logical connectors.Creator: Malik Magdon-IsmailMaking Precise Statements: 10 / 27Implication (if. . . then. . . ), p q

Implication (if. . . then. . . ), p qif “Porky the pig can fly” then “You got an A.”Creator: Malik Magdon-IsmailMaking Precise Statements: 11 / 27(t/f?)Adding New Information: p is t

Implication (if. . . then. . . ), p qif “Porky the pig can fly” then “You got an A.”(t/f?)Suppose T . Since pigs can’t fly, does it mean you can’t get an A?Creator: Malik Magdon-IsmailMaking Precise Statements: 11 / 27Adding New Information: p is t

Implication (if. . . then. . . ), p qif “Porky the pig can fly” then “You got an A.”(t/f?)Suppose T . Since pigs can’t fly, does it mean you can’t get an A?if “n2 is even”, then “n is even.”Creator: Malik Magdon-Ismail(t)Making Precise Statements: 11 / 27Adding New Information: p is t

Implication (if. . . then. . . ), p qif “Porky the pig can fly” then “You got an A.”(t/f?)Suppose T . Since pigs can’t fly, does it mean you can’t get an A?if “n2 is even”, then “n is even.”(t)Suppose n2 is even. Can we conclude n 6 5?Creator: Malik Magdon-IsmailMaking Precise Statements: 11 / 27Adding New Information: p is t

Implication (if. . . then. . . ), p qif “Porky the pig can fly” then “You got an A.”(t/f?)Suppose T . Since pigs can’t fly, does it mean you can’t get an A?if “n2 is even”, then “n is even.”(t)Suppose n2 is even. Can we conclude n 6 5?if “it rained last night” then “the grass is wet.”Creator: Malik Magdon-IsmailMaking Precise Statements: 11 / 27(t)Adding New Information: p is t

Implication (if. . . then. . . ), p qif “Porky the pig can fly” then “You got an A.”(t/f?)Suppose T . Since pigs can’t fly, does it mean you can’t get an A?if “n2 is even”, then “n is even.”(t)Suppose n2 is even. Can we conclude n 6 5?if “it rained last night” then “the grass is wet.”(t)p : it rained last nightq : the grass is wetp qCreator: Malik Magdon-IsmailMaking Precise Statements: 11 / 27Adding New Information: p is t

Implication (if. . . then. . . ), p qif “Porky the pig can fly” then “You got an A.”(t/f?)Suppose T . Since pigs can’t fly, does it mean you can’t get an A?if “n2 is even”, then “n is even.”(t)Suppose n2 is even. Can we conclude n 6 5?if “it rained last night” then “the grass is wet.”(t)p : it rained last nightq : the grass is wetp qWhat does it mean for this common-sense implication to be true?Creator: Malik Magdon-IsmailMaking Precise Statements: 11 / 27Adding New Information: p is t

Implication (if. . . then. . . ), p qif “Porky the pig can fly” then “You got an A.”(t/f?)Suppose T . Since pigs can’t fly, does it mean you can’t get an A?if “n2 is even”, then “n is even.”(t)Suppose n2 is even. Can we conclude n 6 5?if “it rained last night” then “the grass is wet.”(t)p : it rained last nightq : the grass is wetp qWhat does it mean for this common-sense implication to be true?What can you conclude? Did it rain last night? Is the grass wet?Creator: Malik Magdon-IsmailMaking Precise Statements: 11 / 27Adding New Information: p is t

Adding New Information to a True Implication: p is tif “it rained last night” then “the grass is wet.”p : it rained last nightq : the grass is wetp qWeather report in morning paper: rain last night.Creator: Malik Magdon-IsmailMaking Precise Statements: 12 / 27 new informationAdding New Information: q is t

Adding New Information to a True Implication: p is tif “it rained last night” then “the grass is wet.”p : it rained last nightq : the grass is wetp qWeather report in morning paper: rain last night. new informationif (it rained last night) then (the grass is wet) tIt rained last night (from the weather report)tIs the grass wet?Creator: Malik Magdon-IsmailYES!Making Precise Statements: 12 / 27Adding New Information: q is t

Adding New Information to a True Implication: p is tif “it rained last night” then “the grass is wet.”p : it rained last nightq : the grass is wetp qWeather report in morning paper: rain last night.if (it rained last night) then (the grass is wet) tIt rained last night (from the weather report)tIs the grass wet?YES! new informationp q tpt qtFor a true implication p q , when p is t, you can conclude q is t.Creator: Malik Magdon-IsmailMaking Precise Statements: 12 / 27Adding New Information: q is t

Adding New Information to a True Implication: q is tif “it rained last night” then “the grass is wet.”p : it rained last nightq : the grass is wetp qWhile picking up the morning paper, you see wet grass.Creator: Malik Magdon-IsmailMaking Precise Statements: 13 / 27 new informationAdding New Information p is f

Adding New Information to a True Implication: q is tif “it rained last night” then “the grass is wet.”p : it rained last nightq : the grass is wetp qWhile picking up the morning paper, you see wet grass. new informationif (it rained last night) then (the grass is wet) tThe grass is wet (from walking outside)tDid it rain last night?Creator: Malik Magdon-IsmailMaking Precise Statements: 13 / 27Adding New Information p is f

Adding New Information to a True Implication: q is tif “it rained last night” then “the grass is wet.”p : it rained last nightq : the grass is wetp qWhile picking up the morning paper, you see wet grass.if (it rained last night) then (the grass is wet) tThe grass is wet (from walking outside)tDid it rain last night? new informationp q tqt pt or fFor a true implication p q , when q is t, you cannot conclude p is t.Creator: Malik Magdon-IsmailMaking Precise Statements: 13 / 27Adding New Information p is f

Adding New Information to a True Implication: p is fif “it rained last night” then “the grass is wet.”p : it rained last nightq : the grass is wetp qWeather report in morning paper: no rain last night.Creator: Malik Magdon-IsmailMaking Precise Statements: 14 / 27 new informationAdding New Information p is f

Adding New Information to a True Implication: p is fif “it rained last night” then “the grass is wet.”p : it rained last nightq : the grass is wetp qWeather report in morning paper: no rain last night.if (it rained last night) then (the grass is wet) tIt rained last night (from the weather report)fIs the grass wet? new informationp q tpf qt or fFor a true implication p q , when p is f, you cannot conclude q is f.Creator: Malik Magdon-IsmailMaking Precise Statements: 14 / 27Adding New Information p is f

Adding New Information to a True Implication: q is fif “it rained last night” then “the grass is wet.”p : it rained last nightq : the grass is wetp qWhile picking up the paper, you see dry grass.Creator: Malik Magdon-IsmailMaking Precise Statements: 15 / 27 new informationNew Information (Summary)

Adding New Information to a True Implication: q is fif “it rained last night” then “the grass is wet.”p : it rained last nightq : the grass is wetp qWhile picking up the paper, you see dry grass.if (it rained last night) then (the grass is wet) tIt grass is wet (from walking outside)fDid it rain last night? new informationp q tqf pfFor a true implication p q , when q is f, you can conclude p is f.Creator: Malik Magdon-IsmailMaking Precise Statements: 15 / 27New Information (Summary)

Implication: Inferences When New Information ComesFor a true implication p q :When p is t, you can conclude that q is t.When q is t, you cannot conclude p is t.When p is f, you cannot conclude q is f.When q is f, you can conclude p is f.Creator: Malik Magdon-IsmailMaking Precise Statements: 16 / 27Falsifying an Implication

Implication: Inferences When New Information ComesFor a true implication p q :When p is t, you can conclude that q is t.When q is t, you cannot conclude p is t.When p is f, you cannot conclude q is f.When q is f, you can conclude p is f.if (Porky the pig can fly) then (You got an A) Creator: Malik Magdon-Ismail{zf}Making Precise Statements: 16 / 27 {zcan be t or f (phew)}Falsifying an Implication

Falsifying “if (it rained last night) then (the grass is wet)”You are a scientist collecting data to verify that the implication is valid (true).Creator: Malik Magdon-IsmailMaking Precise Statements: 17 / 27Implication is Important

Falsifying “if (it rained last night) then (the grass is wet)”You are a scientist collecting data to verify that the implication is valid (true).One night it rained. That morning the grass was dry.Creator: Malik Magdon-IsmailMaking Precise Statements: 17 / 27 new informationImplication is Important

Falsifying “if (it rained last night) then (the grass is wet)”You are a scientist collecting data to verify that the implication is valid (true).One night it rained. That morning the grass was dry. new informationWhat do you think about the implication now?Creator: Malik Magdon-IsmailMaking Precise Statements: 17 / 27Implication is Important

Falsifying “if (it rained last night) then (the grass is wet)”You are a scientist collecting data to verify that the implication is valid (true).One night it rained. That morning the grass was dry. new informationWhat do you think about the implication now?This is a falsifying scenario.if (it rains) then (the grass is wet) not tp q is f only when p is t and q is f. In all other cases p q is t.Creator: Malik Magdon-IsmailMaking Precise Statements: 17 / 27Implication is Important

Implication is Extremely Important, p qAll these are p q (p “it rained last night” and q “the grass is wet”):If it rained last night then the grass is wet.Creator: Malik Magdon-IsmailMaking Precise Statements: 18 / 27if p then qExample

Implication is Extremely Important, p qAll these are p q (p “it rained last night” and q “the grass is wet”):If it rained last night then the grass is wet.It rained last night implies the grass is wet.Creator: Malik Magdon-IsmailMaking Precise Statements: 18 / 27if p then qp implies qExample

Implication is Extremely Important, p qAll these are p q (p “it rained last night” and q “the grass is wet”):If it rained last night then the grass is wet.It rained last night implies the grass is wet.It rained last night only if the grass is wet.Creator: Malik Magdon-IsmailMaking Precise Statements: 18 / 27if p then qp implies qp only if qExample

Implication is Extremely Important, p qAll these are p q (p “it rained last night” and q “the grass is wet”):If it rained last night then the grass is wet.It rained last night implies the grass is wet.It rained last night only if the grass is wet.The grass is wet if it rained last night.Creator: Malik Magdon-IsmailMaking Precise Statements: 18 / 27if p then qp implies qp only if qq if pExample

Implication is Extremely Important, p qAll these are p q (p “it rained last night” and q “the grass is wet”):If it rained last night then the grass is wet.It rained last night implies the grass is wet.It rained last night only if the grass is wet.The grass is wet if it rained last night.The grass is wet whenever it rains.if p then qp implies qp only if qq if pq whenever pTruth Tables:Creator: Malik Magdon-Ismailpq pp qp qp qffttftftttffffftftttttftMaking Precise Statements: 18 / 27Example

Example:if (you are hungry or you are thirsty) then you visit the cafeteria(p q) rwherep : you are hungryq : you are thirstyr : you visit the cafeteria1.2.3.4.5.6.7.8.Creator: Malik Magdon-IsmailMaking Precise Statements: 19 / 27pqrffffttttffttffttftftftftEquivalent Compound Statements

Example:if (you are hungry or you are thirsty) then you visit the cafeteria(p q) rwherep : you are hungryq : you are thirstyr : you visit the cafeteria1.2.3.4.5.6.7.8.Creator: Malik Magdon-IsmailMaking Precise Statements: 19 / 27pqr (p q)ffffttttffttffttftftftftffttttttEquivalent Compound Statements

Example:if (you are hungry or you are thirsty) then you visit the cafeteria(p q) rwherep : you are hungryq : you are thirstyr : you visit the cafeteria1.2.3.4.5.6.7.8.Creator: Malik Magdon-IsmailMaking Precise Statements: 19 / 27pqr (p q) (p q) t Compound Statements

Example:if (you are hungry or you are thirsty) then you visit the cafeteria(p q) rwherep : you are hungryq : you are thirstyr : you visit the cafeteria1.2.3.4.5.6.7.8.Creator: Malik Magdon-IsmailMaking Precise Statements: 19 / 27pqr(p q) rffffttttffttffttftftftftttftftftEquivalent Compound Statements

Example:if (you are hungry or you are thirsty) then you visit the cafeteria(p q) rYou are thirsty: q is t.Creator: Malik Magdon-Ismailwherep : you are hungryq : you are thirstyr : you visit the cafeteria1.2.3.4.5.6.7.8.Making Precise Statements: 19 / 27pqr(p q) rffffttttffttffttftftftftttftftftEquivalent Compound Statements

Example:if (you are hungry or you are thirsty) then you visit the cafeteria(p q) rwhereYou are thirsty: q is t. In both cases r is t.(you visit the cafeteria)Creator: Malik Magdon-Ismailp : you are hungryq : you are thirstyr : you visit the cafeteria1.2.3.4.5.6.7.8.Making Precise Statements: 19 / 27pqr(p q) rffffttttffttffttftftftftttftftftEquivalent Compound Statements

Example:if (you are hungry or you are thirsty) then you visit the cafeteria(p q) rwhereYou are thirsty: q is t. In both cases r is t.(you visit the cafeteria)You did visit the cafeteria: r is t.Creator: Malik Magdon-Ismailp : you are hungryq : you are thirstyr : you visit the cafeteria1.2.3.4.5.6.7.8.Making Precise Statements: 19 / 27pqr(p q) rffffttttffttffttftftftftttftftftEquivalent Compound Statements

Example:if (you are hungry or you are thirsty) then you visit the cafeteria(p q) rwhereYou are thirsty: q is t. In both cases r is t.(you visit the cafeteria)You did visit the cafeteria: r is t.Are you hungry? We don’t know.Are you thirsty? We don’t know.(You accompanied your hungry friend (row 2).)Creator: Malik Magdon-Ismailp : you are hungryq : you are thirstyr : you visit the cafeteria1.2.3.4.5.6.7.8.Making Precise Statements: 19 / 27pqr(p q) rffffttttffttffttftftftftttftftftEquivalent Compound Statements

Example:if (you are hungry or you are thirsty) then you visit the cafeteria(p q) rwhereYou are thirsty: q is t. In both cases r is t.(you visit the cafeteria)You did visit the cafeteria: r is t.Are you hungry? We don’t know.Are you thirsty? We don’t know.(You accompanied your hungry friend (row 2).)You did not visit the cafeteria: r is f.Creator: Malik Magdon-Ismailp : you are hungryq : you are thirstyr : you visit the cafeteria1.2.3.4.5.6.7.8.Making Precise Statements: 19 / 27pqr(p q) rffffttttffttffttftftftftttftftftEquivalent Compound Statements

Example:if (you are hungry or you are thirsty) then you visit the cafeteria(p q) rwhereYou are thirsty: q is t. In both cases r is t.(you visit the cafeteria)You did visit the cafeteria: r is t.Are you hungry? We don’t know.Are you thirsty? We don’t know.(You accompanied your hungry friend (row 2).)You did not visit the cafeteria: r is f.p and q are both f.(You are neither hungry nor thirsty.)Creator: Malik Magdon-Ismailp : you are hungryq : you are thirstyr : you visit the cafeteria1.2.3.4.5.6.7.8.Making Precise Statements: 19 / 27pqr(p q) rffffttttffttffttftftftftttftftftEquivalent Compound Statements

Equivalent Compound Statementspffttqftftp qttft q pttft p qttftq ptfttrains wet grassdry grass no rainno rain wet grasswet grass raineqveqvp q q p p qCreator: Malik Magdon-IsmailMaking Precise Statements: 20 / 27Proving an Implication

Equivalent Compound Statementspffttqftftp qttft q pttft p qttftq ptfttrains wet grassdry grass no rainno rain wet grasswet grass raineqveqvp q q p p qOrder is very important: p q and q p do not mean the same thing.if I’m dead, then my eyes are closedCreator: Malik Magdon-Ismailvs.if my eyes are closed, then I’m deadMaking Precise Statements: 20 / 27Proving an Implication

Equivalent Compound Statementspffttqftftp qttft q pttft p qttftq ptfttrains wet grassdry grass no rainno rain wet grasswet grass raineqveqvp q q p p qOrder is very important: p q and q p do not mean the same thing.if I’m dead, then my eyes are closedvs.if my eyes are closed, then I’m deadPop Quiz 3.5. Compound propositions are used for program control flow, especially if. . . then. . . .if(x 0 k (y 1 && x y))Execute some instructions.if(x 0 k y 1)Execute some instructions.Use truth-tables to show that both do the same thing. Which do you prefer and why?Creator: Malik Magdon-IsmailMaking Precise Statements: 20 / 27Proving an Implication

Proving an Implication: Reasoning Without Factsif (n2 is even) then (n is even).p : n2 is evenq : n is evenp qpqp qffttftftttftWhat is n? How to prove?Creator: Malik Magdon-IsmailMaking Precise Statements: 21 / 27Quantifiers

Proving an Implication: Reasoning Without Factsif (n2 is even) then (n is even).p : n2 is evenq : n is evenp qpqp qffttftftttftWhat is n? How to prove?We must show that the highlighted row cannot occur.Creator: Malik Magdon-IsmailMaking Precise Statements: 21 / 27Quantifiers

Proving an Implication: Reasoning Without Factsif (n2 is even) then (n is even).p : n2 is evenq : n is evenp qpqp qffttftftttftWhat

Last Time 1 Sets, {3,5,11} 2 Sequences, 100111001 3 Graphs, C A D B E F 4 Examples of basic proofs. In 4 rounds of group dating, no one meets more than 12 people. x2 is even “is the same as” x is even. In any group of 6 people there is an orgy of 3 mutual friends or a war of 3 mutual enemies. Axiom: The Well-Ordering Principle 2 is not