1 LOGIC – REVIEW Prof. Ive Barreiros2 STATEMENTS A statement is a declarative sentence that is either TRUE or FALSE. The truthfulness or falsity of a statement is called its truth value. Examples of statements: Bayside is closed after 10:00 pm. • Every multiple of 10 is a multiple of 5. • Georgia is a southern state. Examples of sentences that are not statements: • Mathematics is a hard subject. (Opinion) • Women are oppressed. (It may be true or false depending on other factors.) • Study hard! (Imperative sentence) Lower case letters symbolize statements: p: “Every multiple of 5 is a multiple of 10.” q: “Georgia is a southern state.” r: “He studies every night.” s: “She is not used to travel so much.”3 COMPOUND STATEMENTS Sentences that combine several statements are called compound statements. Later on there will be a discussion about connectives. Examples of a compound statement: • She is expecting a baby and she reads a book every week. (The connective in this compound statement is “and”.) • Charles speaks English well or he has forgotten his child years. (The connective in this compound statement is “or”.)4 CONJUNCTION Connective: “and” p ∧ q : "p and q" Example: He is a veteran of the war and he is an ocean engineer. Truth Table for Conjunction p q p ∧ q T T T T F F F T F F F F Notice that a conjunction is TRUE only when both statements are TRUE!5 DISJUNCTION Connective: “or” p ∨ q : "p or q" Example: He is a veteran of war or he has a high regard for the love of his country. Truth Table for Disjunction p q p ∨ q T T T T F T F T T F F F Notice that a disjunction is FALSE only when both statements are FALSE!6 NEGATION ~ p : “not p” Examples: • Los Angeles is not in North Carolina. • Tigers are not feline. Truth Table for Negation p ~ p T F F T Notice that the truth value of a statement is the opposite of the truth value of its negation!7 PROPOSITIONS A compound statement in which the individual statements are expressed by letters without specifying their truth value is called a proposition. Example of a proposition: ~ (p ∧ ~ q): “It is not the case that p and not q” (r ∨ ~q): r or not q The truth value of a proposition depends on the truth values of the involved statements. Propositions can be visualized in a concise way by using a truth table.8 TRUTH TABLE • In a truth table the first columns shows all the possible truth values for the composing statements. There should be enough rows to consider all the possible combination of truth values. • Each of the remaining columns corresponds to a step in the construction of the proposition. Example of a Truth Table: Proposition: ~ (p ∧ ~ q) p q ~ ( p ∧ ~ q) T T T T F F T T F F T T T F F T T F F F T F F T F F T F Another example of a Truth Table: Proposition: ~ (p ∨ ~ q) p q ~ ( p ∨ ~ q) T T F T T F T T F F T T T F F T T F F F T F F F F T T F Truth value of the proposition Truth value of the proposition9 One more example of a Truth Table: Proposition: ~ (p ∧ ~ q) ∨ p p q ~ ( p ∧ ~ q ) ∨ p T T T T F F T T T T F F T T T F T T F T T F F F T T F F F T F F T F T F Truth value of the proposition10 TAUTOLOGY A proposition that is true independently of the truth value of the component statements. In a tautology the final (resulting) column of the truth table consists of all T’s. Example of Tautology: Proposition: p ∨ ~ p p p ∨ ~ p T T T F T T T T F T F F T T F F F T T F CONTRADICTION A proposition that is false independently of the truth value of the component statements. In a contradiction the final (resulting) column of the truth table consists of all F’s. Example of Contradiction: Proposition: p ∧ ~ p p p ∧ ~ p T T F F T T T F F T F F F T F F F F T F11 LOGICAL EQUIVALENCE Two propositions are logically equivalent when they have identical truth tables. Logical Equivalence is denoted by the symbol ≡ . Example: Proposition: p ≡ ~ (~ p) Example of two Logically Equivalent propositions: Proposition: ~ (p ∧ q) ≡ ~ p ∨ ~ q p q ~ (p ∧ q ) T T F T T T T F T T F F F T T F F T F F T F F F p q ~ p ∨ ~ q T T F T F F T T F F T T T F F T T F T F T F F T F T T F Same truth table12 CONDITIONAL If p, then q p → q The conditional is frequently read as “p implies q” or “p only if q” p is called the antecedent and q is called the consequent. Other expressions for p → q are: “p is sufficient for q” “q is necessary for p” Example: • If one sleeps during the flight, then the trip will seem short. • Sleeping during the flight implies that the trip will seem short. • Sleep during the flight only if the trip seems short. • Sleeping during the flight is sufficient for the flight to seem shorter. • The flight seems shorter is necessary for sleeping during it.13 Truth Table for Conditional p → q p q p → q T T T T F F F T T F F T Example of the four cases: • If 4 > 3, then cats have four legs. (True) • If 4 > 3, then cats do not have four legs. (False) • If 4 < 3, then cats have four legs. (True) • If 4 < 3, then cats do not have four legs. (True) Notice that a conditional is false only when the antecedent is true and the consequent is false. Note: This example should convince you that true and false statements in propositional logic sometimes do not “sound” like the way we usually talk.14 BICONDITIONAL p if and only if q Biconditional is equivalent to “p ↔ q and q ↔ p” p ↔ q Example: A number is even if and only if it is divisible by 2. The Truth Table for Biconditional p q p ↔ q T T T T F F F T F F F T Example of the four cases: • 4 > 3 if and only if cats have four …