CHAPTER 1Logic1.1. PropositionsA proposition is a declarative sentence that is either true or false(but not both). For instance, the following are propositions: “Parisis in France” (true), “London is in Denmark” (false), “2 < 4” (true),“4 = 7 (false)”. However the following are not propositions: “whatis your name?” (this is a question), “do your homework” (this is acommand), “this sentence is false” (neithertrue nor false), “x is aneven number” (it depends on what x represents), “Socrates” (it is noteven a sentence). The truth or falsehood of a proposition is called itstruth value.1.1.1. Connectives, Truth Tables. Connectives are used formaking compound propositions. The main ones are the following (pand q represent given propositions):Name Represented MeaningNegation p “not p”Conjunction p ∧ q “p and q”Disjunction p ∨ q “p or q (or both)”Exclusive Or p Y q “either p or q, but not both”Implication p → q “if p then q”Biconditional p ↔ q “p if and only if q”The truth value of a compound proposition depends only on thevalue of its components. Writing F for “false” and T for “true”, wecan summarize the meaning of the connectives in thefollowing way:61.1. PROPOSITIONS 7p q p p ∧ q p ∨ q p Y 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 TNote that ∨ represents a non-exclusive or, i.e., p ∨ q is true whenany of p, qis true and also when both are true. On the other hand Yrepresents an exclusive or, i.e., p Y q is true only when exactly one of pand qis true.1.1.2. Conditional Propositions. A proposition of the form “ifp then q” or “p implies q”, represented “p → q” is called a conditionalproposition. For instance: “if Johnis from Chicago then John is fromIllinois”. The proposition p is called hypothesis or antecedent, and theproposition q is the conclusion or consequent.Note that p → q is true always except when p is true and q is false.So, the following sentences are true: “if 2 < 4 then Paris is in France”(true → true),“if London is in Denmark then 2 < 4” (false → true),“if 4 = 7 then London is in Denmark” (false → false). However thefollowing one is false: “if 2 < 4 then London is in Denmark” (true →false).In might seem strange that “p →q” is considered true when p isfalse, regardless of the truth value of q. This will become clearer whenwe study predicates such as “if x is a multiple of 4 then x is a multipleof 2”. That implication is obviously true, although for the particularcase x = 3 it becomes “if 3 is a multiple of 4 then 3 is a multiple of 2”.The proposition p ↔q, read “p if and only if q”, is called bicon-ditional. It is true precisely whenp and q have the same truth value,i.e., they are both true or both false.1.1.3. Logical Equivalence. Note that the compound proposi-tions p → q and p ∨ q have the same truth values:p q p p ∨ q p → qT T F T TT F F F FF T T T TF F T T T1.1. PROPOSITIONS 8When two compound propositions have the same truth values nomatter what truth value their constituent propositions have, they arecalled logically equivalent. For instance p → q and p ∨ q are logicallyequivalent, and we write it:p → q ≡ p ∨ qExample: De Morgan’s Laws for Logic. The following propositionsare logically equivalent:p ∨ q ≡ p ∧ qp ∧ q ≡ p ∨ qWe can check it by examining their truth tables:p q p q p ∨ q p ∨ q p ∧ q p ∧ q p ∧ q p ∨ qT T F F T F F T F FT F F T T F F F T TF T T F T F F F T TF F T T F T T F T TExample: The following propositions are logically equivalent:p ↔ q ≡ (p → q) ∧ (q → p)Again, this can bechecked with the truth tables:p q p → q q → p (p → q) ∧ (q → p) p ↔ qT T T T T TT F F T F FF T T F F FF F T T T TExercise: Check the following logical equivalences:p → q ≡ p ∧ qp → q ≡ q → pp ↔ q ≡ p Y q1.1.4. Converse, Contrapositive. The converse of a conditionalproposition p → q is the proposition q → p. As we have seen, the bi-conditional proposition is equivalent to the conjunction of a conditional1.1. PROPOSITIONS 9proposition an its converse.p ↔ q ≡ (p → q) ∧ (q → p)So, for instance, saying that “John is married if and only if he has aspouse” is the same as saying “if John is married then he has a spouse”and “if he has a spouse then he is married”.Note that the converse is not equivalent to the given conditionalproposition, for instance “if John is from Chicago then John is fromIllinois” is true, but the converse “if John is from Illinois then John isfrom Chicago” may be false.Thecontrapositive of a conditional proposition p → q is the propo-sition q → p. They are logically equivalent. For instance the contra-positive of “if John is from Chicago then John is from Illinois” is “ifJohn is not from Illinois then John is not from