Course contentsShow
← Computer Science
Lesson 43 of 2,8722. Discrete Mathematics for CSFree lesson

Tautologies and Contradictions

Identify propositions that are always true or always false and understand their role in logical reasoning.

Tautologies and Contradictions

What you'll learn: You'll discover how to identify propositions that are always true (tautologies) or always false (contradictions), and why they matter in logical reasoning.

The Core Idea

In propositional logic, some compound statements have predictable truth values regardless of their components. A tautology is a proposition that is always true, no matter what truth values its variables have. A contradiction is a proposition that is always false, no matter what.

Think of a tautology like saying "It will either rain tomorrow or it won't rain tomorrow." This is always true—there's no scenario where both parts are false. A contradiction is like saying "It will rain tomorrow AND it won't rain tomorrow"—impossible, always false.

Recognizing Them

Tautology example: p OR NOT p

If p is true, the statement is true. If p is false, NOT p is true, making the whole statement true. Every row in its truth table shows TRUE.

Contradiction example: p AND NOT p

If p is true, NOT p is false, so the conjunction is false. If p is false, the conjunction is still false. Every row shows FALSE.

Why They Matter

  • Tautologies represent logical laws that always hold—useful for proving equivalences and validating reasoning
  • Contradictions help identify impossible conditions or logical errors in arguments
  • In programming, recognizing these patterns helps optimize conditions (a tautology condition is redundant; a contradiction means unreachable code)

Key Takeaway: Tautologies are propositions that are true in every possible case, while contradictions are false in every case—recognizing these extremes is fundamental to understanding logical structure and validity.