Contradiction in Discrete Mathematics [ English ]

Languages

• English

1. Introduction to Contradiction

In discrete mathematics, logic forms the foundation for reasoning, proof construction, and computational thinking. Among the fundamental concepts in logic is contradiction, which plays a critical role in evaluating propositions and constructing mathematical proofs.

A contradiction represents a situation where a statement cannot possibly be true under any circumstances. It highlights inconsistency within logical expressions and is widely used in formal reasoning, especially in proof techniques.

Understanding contradiction helps in:

• Identifying false logical statements
• Constructing rigorous proofs
• Analyzing logical expressions in computer science and mathematics

2. Definition of Contradiction

A contradiction is a proposition that is always false, regardless of the truth values of its constituent variables.

Formal Definition:

A compound proposition is called a contradiction if its truth value is false for all possible combinations of truth values of its variables.

3. Symbol and Representation

Contradictions are commonly represented using logical operators. The most basic and standard form is:

p ∧ ¬p

Where:

• p is a proposition
• ¬p is the negation of p
• ∧ represents logical AND

Explanation:

• If p is true, then ¬p is false
• If p is false, then ¬p is true
• In both cases, p ∧ ¬p is always false

Thus, this expression is a contradiction.

4. Truth Table of Contradiction

Let us construct the truth table for:

p ∧ ¬p

Explanation:

• Column ¬p is the opposite of p
• The final column (p ∧ ¬p) is false in all cases

Hence, the expression is a contradiction.

5. Examples of Contradiction

Example 1: Simple Contradiction

p ∧ ¬p

Always false as shown in the truth table.

Example 2: Compound Contradiction

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

Let:

• A = (p ∨ q)

Then expression becomes:

A ∧ ¬A

This follows the same structure as p ∧ ¬p, hence always false.

Example 3: Using Implication

(p → q) ∧ p ∧ ¬q

Explanation:

• p → q means if p is true, then q must be true
• But ¬q states q is false
• This creates a logical conflict

Thus, the expression becomes a contradiction.

6. Contradiction vs Tautology vs Contingency

Understanding contradiction is clearer when compared with other logical classifications.

(a) Tautology

A proposition that is always true.

Example:

p ∨ ¬p

(b) Contradiction

A proposition that is always false.

Example:

p ∧ ¬p

(c) Contingency

A proposition that is sometimes true and sometimes false.

Example:

p → q

7. Laws Related to Contradiction

Law of Non-Contradiction

This fundamental law states:

¬(p ∧ ¬p)

Meaning:

A proposition and its negation cannot both be true at the same time.

Explanation:

• p ∧ ¬p is always false
• Therefore, its negation ¬(p ∧ ¬p) is always true

This law is essential in classical logic and ensures consistency in reasoning.

8. Proof by Contradiction (Indirect Proof)

Proof by contradiction is a powerful technique used in mathematics.

Method:

1. Assume the negation of the statement you want to prove
2. Derive a contradiction (something logically impossible)
3. Conclude that the original statement must be true

Example 1: Simple Logical Proof

Statement: If p → q and p is true, then q must be true.

Proof by contradiction:

• Assume q is false (¬q)
• Given p → q, if p is true, then q must be true
• This contradicts ¬q
• Therefore, assumption is false
• Hence, q is true

Example 2: Mathematical Insight

Statement: √2 is irrational (conceptual outline)

Proof idea:

• Assume √2 is rational
• Express it as a fraction in simplest form
• Derive a contradiction (both numerator and denominator become even)
• This violates the assumption of simplest form
• Hence, √2 is irrational

9. Applications of Contradiction

Contradictions are widely used in:

(a) Mathematics

• Proving theorems
• Establishing impossibility

(b) Computer Science

• Logic circuit design
• Program correctness
• Debugging logical errors

(c) Logical Reasoning

• Identifying inconsistencies
• Validating arguments

10. Summary

• A contradiction is a proposition that is always false

• Standard form: p ∧ ¬p

• Truth tables confirm its always-false nature

• It contrasts with:

  • Tautology (always true)
  • Contingency (sometimes true)

• Governed by the Law of Non-Contradiction

• Essential in proof by contradiction, a key mathematical technique