Intro to Discrete Structures Lecture 2 Pawel M Wocjan School of Electrical Engineering and Computer Science University of Central Florida wocjan eecs ucf edu Intro to Discrete StructuresLecture 2 p 1 36 Recap of Lecture 1 propositions propositional calculus or propositional logic propositional variables or statement variables truth value T F compound propositions logical operators negation connectives conjuction disjuction exclusive or conditional statement and biconditional statement hypothesis or antecedent or premise conclusion or consequence Intro to Discrete StructuresLecture 2 p 2 36 Recap of Lecture 1 Enter the missing truth values into the truth table p T T F F q p T F T F p q p q p q p q p q Intro to Discrete StructuresLecture 2 p 3 36 Recap of Lecture 1 Enter the missing truth values into the truth table p T T F F q p T F F F T T F T p q T F F F p q T T T F p q F T T F p q T F T T p q T F F T Intro to Discrete StructuresLecture 2 p 4 36 Translating English Sentences Parent If you don t clean your room you can t watch a DVD C C D D and means C D Implicit use of biconditionals You should be aware that biconditional are not always explicitly used in natural language Intro to Discrete StructuresLecture 2 p 5 36 Translating English Sentences Mathematician If a function is not continuous then it is not differentiable C D but C D is not implied For instance the absolute value function f R R x 7 x is continuous but it is not differentiable since it doesn t have a well defined tangent at x 0 Intro to Discrete StructuresLecture 2 p 6 36 System Specification Intro to Discrete StructuresLecture 2 p 7 36 Boolean Searches Intro to Discrete StructuresLecture 2 p 8 36 Logic and Bit Operations Intro to Discrete StructuresLecture 2 p 9 36 Logic Puzzel Alien Encounter The starship Indefensible is in orbit around the planet Noncomposmentis and Captain Quirk and Mr Crock have just beamed down to the surface Intro to Discrete StructuresLecture 2 p 10 36 Alien Encounter Quirk According to the Good Galaxy Guide there are two species of intelligent aliens on this planet Crook Correct Captain Veracitors and Gibberish They all speak Galaxic and they can be distinguished by how they answer questions The Veracitors always reply truthfully and the Gibberish always lie Quirk But physically Crook They are indistinguishable Captain Intro to Discrete StructuresLecture 2 p 11 36 Alien Encounter Quirk hears a sound and turns to find three aliens creeping up on them They look identical Intro to Discrete StructuresLecture 2 p 12 36 Alien Encounter One of the Aliens Welcome to Noncomposmentis Quirk I thank you My name is Quirk Now you are Quirk pauses No point in asking their names he mutters For all we know they ll be wrong Crook That is logical Captain Quirk Because we are poor speakers of Galaxic I hope you will not mind if I call you Alfy Betty and Gemma As he speaks he points to each of them in turn Then he turns to Crock and whispers Not that we know what sex they are either Crook They are all hermandrofemigynes Intro to Discrete StructuresLecture 2 p 13 36 Alien Encounter Quirk Whatever Now Alfy to which species does Betty belong Alphy Gibberish Quirk Ah Betty do Alfy and Gemma belong to different species Betty No Quirk Right Talkative lot aren t they Um Gemma to which species does Betty belong Gemma Veracitor Intro to Discrete StructuresLecture 2 p 14 36 Alien Encounter Quirk Right that s settled it then He nods knowledgeably Crook Settled what Captain Quirk Which species each belongs to Intro to Discrete StructuresLecture 2 p 15 36 Alien Encounter Are you as smart as Captain Quirk Do you know which species each belongs to Intro to Discrete StructuresLecture 2 p 16 36 I Translating Galaxic to Logix says G says says 6 V assume V first possibility G 6 G 6 V G Intro to Discrete StructuresLecture 2 p 17 36 II Translating Galaxic to Logix says G says says 6 V assume G second possibility V G 6 V contradition Intro to Discrete StructuresLecture 2 p 18 36 Extending the Puzzle Can we always ask the right questions That is can we always formulate questions that allow us to deduce the three aliens correct specie types no matter what they are There are 8 different configurations that are possible V V V V V G GGG Intro to Discrete StructuresLecture 2 p 19 36 1 2 Propositional Equivalence Definition 1 A compound proposition that is always true no matter what the truth value of the propositions that occur in it is called a tautology A compound proposition that is always false is called a contradition A compound proposition that is neither a tautology nor a contradiction is called a contingency Tautologies and contraditions are often important in mathematical reasoning Intro to Discrete StructuresLecture 2 p 20 36 Example of a Tautology and a Contradiction We can construct examples of tautologies and contradictions using just one proposition p p T F F T p p T T p p F F Intro to Discrete StructuresLecture 2 p 21 36 Logical Equivalence Compound propositions that have the same truth value in all possible cases are called logically equivalent We can also define this notion as follows Definition 2 The compound propositions p and q are called logically equivalent if p q is a tautology The notation p q denotes that p and q are logically equivalent Remark The symbol is not a logical connective and p q is not a compound proposition but rather is the statement that p q is a tautology The symbol is sometimes used instead of Intro to Discrete StructuresLecture 2 p 22 36 Logical Equivalence One way to determine whether two compund propositions are equivalent is to use a truth table In particular the compound propositions p and q are equivalent if and only if the columns giving their truth values agree Example 2 Show that p q p q p T T F F q p q T T F T T T F F p q p F F F F F T T T q F T F T p q F F F T It follows that p q p q holds which is the first of the two DeMorgan Laws Intro to Discrete StructuresLecture 2 p 23 36 De Morgan Laws p q p q p q p q Intro to Discrete StructuresLecture 2 p 24 36 Logical Equivalences Equivalance p T p p F p p T T p F F p p p p p p p p p q q p p q q p Name Identity laws Domination laws Idempotent laws Double negation Commutative laws Further laws are the associative distributive De Morgan s absorption negation laws see page 24 Intro to Discrete StructuresLecture 2 p 25 36 Further Logical Equivalences See page 25 for …
View Full Document
Unlocking...