DISCRETE
MATHEMATICS
Logical Reasoning &
Equivalences
Tautology, Contradiction, Contingency
Definition:
Tautology: A logical statement that is always true, regardless of
the truth values of its components.
Contradiction: A logical statement that is always false,
regardless of the truth values of its components.
Contingency: A logical statement that is neither always true nor
always false; its truth value depends on the input values.
p ¬ p p v ¬p
Examples
Examples of Propositional Statements
1 0 1
1. Tautology (Always True)
"Either it is raining, or it is not raining.“
0 1 1
• P∨¬P (Law of the Excluded Middle)
"If it is raining, then either it is raining or it is p q pvq p → (p v q)
cold."
• P→(P∨Q)
1 1 1 1
1 0 1 1
0 1 1 1
0 0 1 1
Examples p ¬ p p ^ ¬p
Examples of Propositional Statements
1 0 0
2. Contradiction (Always False)
"It is both raining and not raining at the same time." 0 1 0
• P∧¬P (Law of Contradiction)
"The sky is either cloudy or clear, and at the same time, it is
neither cloudy nor clear."
• (P∨Q)∧(¬P∧¬Q) (A proposition that contradicts itself)
Examples
2. Contradiction (Always False)
"The sky is either cloudy or clear, and at the same time,
it is neither cloudy nor clear."
• (P∨Q)∧(¬P∧¬Q) (A proposition that contradicts itself)
p q ¬p ¬q pvq ¬p ^ ¬q (p∨q)∧(¬p∧¬q)
1 1 0 0 1 0 0
1 0 0 1 1 0 0
0 1 1 0 1 0 0
0 0 1 1 0 1 0
Examples
Examples of Propositional Statements p q p^q
3. Contingency (Depends on Truth Values of Components)
0 0 0
0 1 0
"It is raining, and it is cold outside."
1 0 0
• P∧Q
1 1 1
"If you study, then you will pass, and if you pass, then you will graduate."
• (P→Q)∧(Q→R)
Examples
• (P→Q)∧(Q→R)
p q r p→q q→r (p→q)∧(q→r)
1 1 1 1 1 1
1 1 0 1 0 0
1 0 1 0 1 0
1 0 0 0 1 0
0 1 1 1 1 1
0 1 0 1 0 0
0 0 1 1 1 1
0 0 0 1 1 1
MORE EXAMPLES
Determine whether each of the following is a tautology, contradiction, or
contingency by constructing a truth table.
1. It is raining and the wind is blowing. 1. P ∧ Q (Contingency)
2. If it is daytime, then the sun is up, or the sun is not up. 2. P→(Q∨¬Q) (Tautology)
3. Either it is sunny, or it is not sunny, or both. 3. P ∨ ¬P ∨ (P ∧ ¬P) (Tautology)
4. It is raining and not raining at the same time, and the sky is cloudy 4. (P∧¬P)∧(Q∧¬Q)
and not cloudy at the same time. (Contradiction)
5. I will eat pizza or I will drink soda, but not both. 5. P ⊕ Q (Contingency)
Assignment
Determine whether each of the following is a tautology, contradiction, or contingency by constructing a truth
table.
1. Either I will go to the gym or I will stay home, and I will either go to the gym or not stay home.
2. Either both the light is on and the fan is running, or neither the light is on nor the fan is running.
3. It is both the case that I will eat pizza and not eat pizza, or I will drink soda and not drink soda.
4. Either the car has fuel or the battery is charged, and at the same time, either the car does not
have fuel or the battery is charged.
5. Either today is Monday or today is not Monday, and either it is raining or it is not raining.
