ELEMENTARY-LOGIC.docx.pdf

Mathematical Logic  Where We're Going Propositional Logic Basic logical connectives. Truth tables. Logical equivalences. First-Order Logic  Reasoning about properties of multiple objects. Propositional Logic A pro...

Mathematical Logic  Where We're Going Propositional Logic Basic logical connectives. Truth tables. Logical equivalences. First-Order Logic  Reasoning about properties of multiple objects. Propositional Logic A proposition is a statement that is, by itself, either true or false.  Some Sample Propositions Puppies are cuter than kittens. Kittens are cuter than puppies. I'm a single. This place about to blow. Party rock is in the house tonight. We can dance if we want to. We can leave your friends behind. Things That Aren't Propositions Things That Aren't Propositions  Propositional Logic Propositional logic is a mathematical system for reasoning about propositions and how they relate to one another. Propositional logic enables us to Formally encode how the truth of various propositions influences the truth of other propositions. Determine if certain combinations of propositions are always, sometimes, or never true. Determine whether certain combinations of propositions logically entail other combinations.  Variables and Connectives Propositional logic is a formal mathematical system whose syntax is rigidly specified. Every statement in propositional logic consists of propositional variables combined via logical connectives. Each variable represents some proposition, such as “You wanted it” or “You should have put a ring on it.” Connectives encode how propositions are related, such as “If you wanted it, you should have put a ring on it.”  Propositional Variables Each proposition will be represented by a propositional variable. Propositional variables are usually represented as lower-case letters, such as p, q,  r, s, etc. If we need more, we can use subscripts: p1, p2, etc. Each variable can take one of two values: true or false.  Logical Connectives Logical NOT: ¬p Read “not p” ¬p is true if and only if p is false. Also called logical negation. Logical AND: p ∧ q  Read “p and q.” p ∧ q is true if both p and q are true. Also called logical conjunction. Logical OR: p ∨ q Read “p or q.” p ∨ q is true if at least one of p or q are true (inclusive OR)  Also called logical disjunction. Truth Tables ( AND ) Truth Tables ( OR ) Truth Tables ( NOT )  Implication An important connective is logical implication: p → q. Recall: p → q means “if p is true, q is true as well.” Recall: p → q says nothing about what happens if p is false. Recall: p → q says nothing about causality; it just says that if p is true, q will be true as well. Implication, Diagrammatically Any time P is true, Q is true as well. Set of where P is true Set of where Q is true Any time P isn't true, Q may or may not be true.  When p Does Not Imply q p → q means “if p is true, q is true as well.” Recall: The only way for p → q to be false is if we know that p is true but q is false. Rationale: If p is false, p → q doesn't guarantee anything. It's true, but it's not meaningful. If p is true and q is true, then the statement “if p is true, then q is also true” is itself true.  If p is true and q is false, then the statement “if p is true, q is also true” is false.  Set of where P is true P → Q is false P can be true without Q being true as well Truth Table for Implication  The Biconditional The biconditional connective p ↔ q is read “p if and only if q.” Intuitively, either both p and q are true, or neither of them are. One interpretation of ↔ is p q p↔q F F T F T F T F F T T T to think of it as equality: the two propositions must have equal truth values.  True and False There are two more “connectives” to speak of: true and false. The symbol ⊤ is a value that is always true. The symbol ⊥ is value that is always false. These are often called connectives, though they don't connect anything. (Or rather, they connect zero things.)  Operator Precedence How do we parse this statement? (¬x) → ((y ∨ z) → (x ∨ (y ∧ z))) Operator precedence for propositional logic: Negation ¬ NOT Disjunction ∧ AND Conjunction ∨ OR Implication → IF p ,then Biconditional ⃡ p if and only if q All operators are right-associative. We can use parentheses to disambiguate.  Recap So Far A propositional variable is a variable that is either true or false. The logical connectives are Negation: ¬p Conjunction: p ∧ q Disjunction: p ∨ q Implication: p → q Biconditional: p ↔ q True: ⊤ False: ⊥ Translating into Propositional Logic  Some Sample Propositions a: There is a velociraptor outside my apartment. b: Velociraptors can open windows. c: I am in my apartment right now. d: My apartment has windows. e: I am going to be eaten by a velociraptor I won't be eaten by a velociraptor if there isn't a velociraptor outside my apartment. ¬a → ¬e  “p if q” translates to q→p It does not translate to p→q  Some Sample Propositions a: There is a velociraptor outside my apartment. b: Velociraptors can open windows. c: I am in my apartment right now. d: My apartment has windows. e: I am going to be eaten by a velociraptor If there is a velociraptor outside my apartment, but it can't open windows, I am not going to be eaten by a velociraptor. a ∧ ¬b → ¬e “p, but q” translates to p∧q  The Takeaway Point When translating into or out of propositional logic, be very careful not to get tripped up by nuances of the English language. In fact, this is one of the reasons we have a symbolic notation in the first place! Many prepositions lead to counterintuitive translations; make sure to double-check yourself! Logical Equivalence More Elaborate Truth Tables This gives the final truth value for the expression. F F F T F T F T T F F F T T T T  Negations p ∧ q is false if and only if ¬(p ∧ q) is true. Intuitively, this is only possible if either p is false or q is false (or both!) In propositional logic, we can write this as ¬p ∨ ¬q. How would we prove that ¬(p ∧ q) and ¬p ∨ ¬q are equivalent? Idea: Build truth tables for both expressions and confirm that they always agree.  Negating AND p q ¬(p ∧ q) p q ¬p ∨ ¬q F F T F F F T T T F T T F F T T T F T F T F T F F T T T T F T T T F F F These two are always the same!  Logical Equivalence If two propositional logic statements φ and ψ always have the same truth values as one another, they are called logically equivalent. We denote this by φ ≡ ψ. ≡ is not a connective. Connectives are a part of logic statements; ≡ is something used to describe logic statements. It is part of the metalanguage rather than the language.  If φ ≡ ψ, we can modify any propositional logic formula containing φ by replacing it with ψ. This is not true when we talk about first-order logic; we'll see why later.  De Morgan's Laws Using truth tables, we concluded that ¬(p ∧ q) ≡ ¬p ∨ ¬q We can also use truth tables to show that ¬(p ∨ q) ≡ ¬p ∧ ¬q These two equivalences are called De Morgan's Laws.  More Negations When is p → q false? Answer: p must be true and q must be false. In propositional logic: p ∧ ¬q Negating Implications ¬(p → q) ≡ p ∧ ¬q