Introduction to Discrete Structures Propositional Logic to Informal Proofs Statements propositions Declarative statement that is true or false but not both Examples Sandra De O Conner was my favorite justice on the Supreme Court statement proposition Read the syllabus carefully not a statement proposition Eat the cake not a statement but a good idea The cake is a lie is a statement X 4 2 Declarative not a statement because it could be true or false Propositional variables to represent statements p q r Ex p The cake is a lie p The cake is a lie Take on values true T or false F Logical Operators Negation gives the variable the opposite value p not p or the negation of p Conjunction p q p q p and q Compound statement A statement with multiple propositional variables Disjunction p q or operator At least one variable must be true for p q to be true Inclusive Allows both statements to be true XOR Operator Implication P Q read p xor q is true only when exactly one of P or Q is true P Q p implies q If P true then Q true Ex P cookies on desk today Q cookies will be eaten today P is sufficient for Q or Q is necessary for P Q P is logically equivalent to is the contraposi tive of P Q or Programming example If p q Bidirectional Implication P Q read P if and only if Q Abbreviated as p iff q Definition of implication P Q P Q T0 F0 Denotes a tautological statement Denotes a counterintuitive statement Tautology Contradiction Contingency A compound statement that is always true no matter the input A compound statement that is always false no matter the input A compound statement that is neither tautological nor contra dictive Converse vs Inverse Converse of P Q is Q P Converse is the contrapositive of the inverse P Q Q P Inverse of P Q is P Q Logical connective A logical operator that connects exactly two propositions Discrete exactly X or exactly Y Two compound propositions are logically equivalent if the truth values are the same Laws of logic Identity laws P T0 or P F0 P Domination laws P T0 T0 P F0 F0 Idempotent laws P P or P P P Double Negation law P P Commutative laws P Q Q P P Q Q P Associative laws P Q R P Q R P Q R P Q R Distributive laws P Q R P Q P R P Q R P Q P R DeMorgan s Law P Q P Q Negation Laws P Q P Q P P T0 P P F0 P P Q P P P Q P Rule of Substitution Absorption Laws really good for making things disappear If you have a compound statement p and it contains a sub statement q and if q q then you can replace q every where in p with q to create a new statement p and p p Example P Q R Q R R Q P R Q Frequently asked questions with examples for some Simplify a compound proposition 1 2 4 5 6 7 8 9 P Q P Q Definition of Implication on 1 P Q P Q Definition of Implication on 2 Idempotent Law 3 P Q P Q DeMorgan s Law on 3 P Q P Q Double Negation on 4 P Q P Q Associative laws on 5 P Q P Q Distribute on 6 P P Q P Q Negation on 7 T0 Q P Q Identity on 8 Q P Q Commutative on 9 10 P Q Q Associative on 10 11 P Q Q Negation on 11 Show that two compound statements are logically equivalent 12 P T0 13 T0 Domination law on 12 P Q P Q T0 P P Q P Q 1 Start with what s given 1 P P Q 1 DeMorgan s law on 1 2 P P Q 1 DeMorgan s Law on 2 3 P P Q 1 Double Negation on 3 4 P P Q 1 Distributive Law on 4 5 P P P Q 1 Negation Law on 5 6 F0 P Q 1 Identity law on 6 7 P Q 1 QED P P Q P Q Show a compound statement is a tautology or a contradiction Negate and simplify P Q R Start with what is given 1 P Q R Apply definition of implication on 1 2 P Q R DeMorgan s Law on 2 3 P Q R Double negation law on 3 P Q R QED Operator Precedence from High to low 4 Therefore p q r means p q r Open statement A declarative statement that Has one or more variables Is not a statement but it becomes a statement when the variables are replaced by certain allowable choices These allowable choices form a universe of dis course or a fancy U Example set of all integers p x x is an integer This becomes a statement when given an integer value for x Existential quantifier This states that x exists There exists an x such that p x x p x x p x x p x Example For all x p x x p x x p x P x x 0 Q x x 2 0 R x x2 3x 4 0 Nested quantifiers 4 0 True True for 4 True for 0 and 1 p x x is in this class q x x has a 4 0 U all students The integer 41 is equal to the sum of two perfect squares Let U If m2 n2 41 m n m2 n2 41 x p x r x x p x q x x p x q x x p x q x There is a student in this class who has a x p x q x T0 x y p x q x y x y p x q x y x p x x p x x p x x p x x x logically implies x p x does NOT logically imply x p x x r x s x x r x x s x False P x x is in this class q x y x earned an A in class y x x all students y y all classes Left p x MUST be true for ALL x Right p x must have AT LEAST ONE x to be true False p x F not all students are in this class Not bidirectional All students have all A s in all classes If p q then p q T0 Multi variable statements Observations Left there is an r x and s x that is the same thing Right there is an r x and there is a s x Example Negate and simplify x p x x p x x p x x p x x p x x p x q x x p x x q x x p x q x x p x x q x x p …
View Full Document
Unlocking...