Recap of Lecture 1Recap of Lecture 1Recap of Lecture 1Translating English SentencesTranslating English SentencesSystem SpecificationBoolean SearchesLogic and Bit OperationsLogic Puzzel -- Alien EncounterAlien EncounterAlien EncounterAlien EncounterAlien EncounterAlien EncounterAlien EncounterI. Translating Galaxic to LogixII. Translating Galaxic to LogixExtending the Puzzle???1.2. Propositional EquivalenceExample of a Tautology and a ContradictionLogical EquivalenceLogical EquivalenceDe Morgan LawsLogical EquivalencesFurther Logical EquivalencesUsing De Morgan's LawsConstructing New Logical Equivalences$300$$300$$300$$300$$300$1.3. Predicates and QuantifiersPredicatesPredicatesIntro to Discrete StructuresLecture 2Pawel M. WocjanSchool of Electrical Engineering and Computer ScienceUniversity of Central [email protected] to Discrete StructuresLecture 2 – p. 1/36Recap of Lecture 1propositions, propositional calculus (or propositionallogic)propositional variables (or statement variables)truth value, T, Fcompound propositions, logical operatorsnegation ¬connectives: conjuction ∧, disjuction ∨, exclusive or ⊕,conditional statement →, and biconditional statement ↔hypothesis (or antecedent or premise) → conclusion (orconsequence)Intro to Discrete StructuresLecture 2 – p. 2/36Recap of Lecture 1Enter the missing truth values into the truth table:p q ¬p p ∧ q p ∨ q p ⊕ q p → q p ↔ qT TT FF TF FIntro to Discrete StructuresLecture 2 – p. 3/36Recap of Lecture 1Enter the missing truth values into the truth table:p q ¬p p ∧ q p ∨ q p ⊕ q p → q p ↔ qT T F T T F T TT F F F T T F FF T T F T T T FF F T F F F T TIntro to Discrete StructuresLecture 2 – p. 4/36Translating English SentencesParent: If you don’t clean your room, you can’t watch aDVD.¬C → ¬D andC → DmeansC ↔ DImplicit use of biconditionals: You should be aware thatbiconditional are not always explicitly used in naturallanguage.Intro to Discrete StructuresLecture 2 – p. 5/36Translating English SentencesMathematician: If a function is not continuous, then it is notdifferentiable.¬C → ¬DbutC → Dis 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 havea well defined tangent at x = 0.Intro to Discrete StructuresLecture 2 – p. 6/36System SpecificationIntro to Discrete StructuresLecture 2 – p. 7/36Boolean SearchesIntro to Discrete StructuresLecture 2 – p. 8/36Logic and Bit OperationsIntro to Discrete StructuresLecture 2 – p. 9/36Logic Puzzel – Alien EncounterThe starship Indefensible is in orbit around the planetNoncomposmentis, and Captain Quirk and Mr Crock havejust beamed down to the surface.Intro to Discrete StructuresLecture 2 – p. 10/36Alien EncounterQuirk: ‘According to the Good Galaxy Guide, there aretwo species of intelligent aliens on this planet.’Crook: ‘Correct, Captain - Veracitors and Gibberish.They all speak Galaxic, and they can be distinguishedby how they answer questions. The Veracitors alwaysreply truthfully, and the Gibberish always lie.’Quirk: ‘But physically –’Crook: ‘They are indistinguishable, Captain.’Intro to Discrete StructuresLecture 2 – p. 11/36Alien EncounterQuirk hears a sound, and turns to find three aliens creepingup on them. They look identical.Intro to Discrete StructuresLecture 2 – p. 12/36Alien EncounterOne 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,’ hemutters.‘For all we know, they’ll be wrong.’Crook: ‘That is logical, Captain.’Quirk: ‘Because we are poor speakers of Galaxic, Ihope you will not mind if I call you Alfy, Betty andGemma.’ As he speaks, he points to each of them inturn. Then he turns to Crock and whispers, ‘Not that weknow what sex they are, either.’Crook: ‘They are all hermandrofemigynes.’Intro to Discrete StructuresLecture 2 – p. 13/36Alien EncounterQuirk: ‘Whatever. Now, Alfy, to which species doesBetty belong?’Alphy: ‘Gibberish.’Quirk: ‘Ah. Betty, do Alfy and Gemma belong todifferent 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/36Alien EncounterQuirk: ‘Right, that’s settled it, then!’ He nodsknowledgeably.Crook: ‘Settled what, Captain?’Quirk: ‘Which species each belongs to.’Intro to Discrete StructuresLecture 2 – p. 15/36Alien EncounterAre you as smart as Captain Quirk? Do you know whichspecies each belongs to?Intro to Discrete StructuresLecture 2 – p. 16/36I. Translating Galaxic to Logixα saysβ = Gβ says¬(α 6= γ) ⇔ (α = γ)γ saysβ = Vassume α = V (first possibility)⇒β = G ⇒ α 6= γ ⇒ γ = G ⇒ β 6= V ⇒ β = GIntro to Discrete StructuresLecture 2 – p. 17/36II. Translating Galaxic to Logixα saysβ = Gβ says¬(α 6= γ) ⇔ (α = γ)γ saysβ = Vassume α = G (second possibility)⇒β = V ⇒ γ = G ⇒ β 6= V contraditionIntro to Discrete StructuresLecture 2 – p. 18/36Extending the Puzzle???Can we always ask the right questions?That is, can we always formulate questions that allow us todeduce the three aliens’ correct specie types, no matterwhat they are?There are 8 different configurations that are possible(α, β, γ) ∈ {V V V, V V G, . . . , GGG}.Intro to Discrete StructuresLecture 2 – p. 19/361.2. Propositional EquivalenceDefinition 1: A compound proposition that is always true, nomatter what the truth value of the propositions that occur init, is called a tautology.A compound proposition that is always false is called acontradition.A compound proposition that is neither a tautology nor acontradiction is called a contingency.Tautologies and contraditions are often important inmathematical reasoning.Intro to Discrete StructuresLecture 2 – p. 20/36Example of a Tautology and a ContradictionWe can construct examples of tautologies andcontradictions using just one proposition.p ¬p p ∨ ¬p p ∧ ¬pT F T FF T T FIntro to Discrete StructuresLecture 2 – p. 21/36Logical EquivalenceCompound propositions that have the same truth value inall possible cases are called logically equivalent.We can also define this notion as follows.Definition 2: The compound propositions p and q are calledlogically equivalent if p ↔ q is a tautology. The
View Full Document
Unlocking...