Part 02- Properties of Proposition law of excluded middle and law of contradiction.
Part 02- Properties of Proposition law of excluded middle and law of contradiction.
Here is Part 02 of Discrete Mathematics – Properties of Proposition, focusing on two fundamental logical laws: the Law of Excluded Middle and the Law of Contradiction. These are essential for understanding propositional logic, used in mathematics, computer science, and GATE CSE.
Contents [hide]
What is a Proposition?
A proposition is a declarative statement that is either true (T) or false (F), but not both.
Example:
-
“2 + 2 = 4” (True) -
“It will rain today” (Not a proposition unless it has a definite truth value)
Law of Excluded Middle (LEM)
Definition:
For any proposition P:
P∨¬P is always TRUEP \lor \neg P \text{ is always TRUE}
This means that either the proposition is true, or its negation is true. There’s no third option.
Example:
Let P = “5 is an odd number”
-
P=TrueP = \text{True}
-
¬P=False\neg P = \text{False}
-
P∨¬P=True∨False=TrueP \lor \neg P = \text{True} \lor \text{False} = \text{True}
So the law holds.
Why It Matters:
-
Forms the basis of classical logic.
-
Used in proof by contradiction.
-
Helps in simplifying logical expressions in computer science.
Law of Contradiction
Definition:
For any proposition P:
P∧¬P is always FALSEP \land \neg P \text{ is always FALSE}
This means a proposition cannot be both true and false at the same time.
Example:
Let P = “The Earth is flat”
-
P=FalseP = \text{False}
-
¬P=True\neg P = \text{True}
-
P∧¬P=False∧True=FalseP \land \neg P = \text{False} \land \text{True} = \text{False}
So the law holds.
Why It Matters:
-
Ensures logical consistency
-
Used to reject contradictory systems
-
Essential in automated theorem proving and program correctness
Truth Table Comparison
| P | ¬P | P ∨ ¬P (LEM) | P ∧ ¬P (Contradiction) |
|---|---|---|---|
| T | F | T | F |
| F | T | T | F |
Summary
| Property | Statement | Always | Usefulness |
|---|---|---|---|
| Law of Excluded Middle | P∨¬PP \lor \neg P | TRUE | Binary logic, Proof by contradiction |
| Law of Contradiction | P∧¬PP \land \neg P | FALSE | Consistency checking, Contradiction test |
Tip for GATE & CS Students:
-
These laws are used heavily in logical gates, compiler design, algorithms, and automata theory.
-
Practice with truth tables and logical identities.
Would you like practice questions, truth table exercises, or a PDF notes version of this topic?