Logical Equivalence Tautology And Contradiction Notes Discrete Mathematics F16 PDF

Preview

Summary

Discrete Mathematics, Lamar University, Prof. Couch, Fall 2016, Lecture Notes #7...

Description

LOGICAL EQUIVALENCE, TAUTOLOGIES & CONTRADICTIONS

LOGICAL EQUIVALENCE, TAUTOLOGIES & CONTRADICTIONS MATH 3311 DISCRETE MATH

1

2

LOGICAL EQUIVALENCE, TAUTOLOGIES & CONTRADICTIONS

7. Logically Equivalent Statements, Tautologies, & Contradictions Definition 27. Two statements are logically equivalent provided that they have exactly the same truth values in all possible cases. In other words, their columns on a truth table are identical. If p and q are logically equivalent, we can represent this symbolically as “p ⇔ q ” Definition 28. A statement is a tautology provided that its truth value in all possible cases is true. Definition 29. A statement is a contradiction provided that its truth value in all possible cases is false. 7.1. Examples. (1) “Not all sheep are white” is logically equivalent to “At least one sheep is not white”. (2) If p is a statement, then p ∨ ¬p is a tautology, since p and ¬p can’t be false at the same time. (3) Similarly, p ∧ ¬p is a contradiction, since p and ¬p can’t be true at the same time. 7.2. Exercises. Complete the truth table below. p T T F F

q T F T F

¬p ¬q p ∨ ¬p p ∧ ¬p p ∨ q ¬(p ∨ q) ¬p ∨ ¬q ¬p ∧ ¬q

Figure 3. (1) Which statements, if any, are equivalent? (2) Which statements, if any, are tautologies? (3) Which statements, if any, are contradictions?...