Logical Equivalence
COS1501 - Theoretical Computer Science I · Logic and Propositions
Logical Equivalence
Logical equivalence is a fundamental concept in propositional logic. It describes a relationship between two propositions that have the same truth value in every possible scenario. In other words, two propositions are logically equivalent if they yield the same truth table.
Understanding Propositions
A proposition is a statement that can either be true or false, but not both. For example, "It is raining" is a proposition. It can either be true (if it is indeed raining) or false (if it is not raining).
Logical Connectives
Logical connectives are symbols used to connect propositions. The most common logical connectives are:
- Conjunction (AND): Denoted by ∧, it is true if both propositions are true.
- Disjunction (OR): Denoted by ∨, it is true if at least one of the propositions is true.
- Negation (NOT): Denoted by ¬, it inverts the truth value of a proposition.
- Implication (IF...THEN): Denoted by →, it states that if the first proposition is true, then the second must also be true.
- Biconditional (IF AND ONLY IF): Denoted by ↔, it is true if both propositions are either true or false.
Definition of Logical Equivalence
Two propositions, P and Q, are logically equivalent if:
P ↔ Q is a tautology. A tautology is a statement that is always true regardless of the truth values of its components.
Examples of Logical Equivalence
Example 1: De Morgan's Laws
De Morgan's Laws provide a useful example of logical equivalence. They state that:
- ¬(P ∧ Q) is logically equivalent to (¬P ∨ ¬Q)
- ¬(P ∨ Q) is logically equivalent to (¬P ∧ ¬Q)
Let's prove the first part of De Morgan's Laws:
Proving ¬(P ∧ Q) ≡ (¬P ∨ ¬Q)
We will use a truth table to demonstrate that both expressions have the same truth values.
| P | Q | P ∧ Q | ¬(P ∧ Q) | ¬P | ¬Q | ¬P ∨ ¬Q |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | F | T | F | T | T |
| F | T | F | T | T | F | T |
| F | F | F | T | T | T | T |
From the truth table, we see that the truth values of ¬(P ∧ Q) and (¬P ∨ ¬Q) are the same for all combinations of P and Q. Thus, we conclude that:
¬(P ∧ Q) ≡ (¬P ∨ ¬Q)
Example 2: Implication
Another common logical equivalence is the relationship between implication and disjunction. The statement:
P → Q is logically equivalent to ¬P ∨ Q
Proving P → Q ≡ ¬P ∨ Q
We will again use a truth table to show that both expressions have the same truth values.
| P | Q | P → Q | ¬P | ¬P ∨ Q |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
From the truth table, we see that the truth values of P → Q and ¬P ∨ Q are the same for all combinations of P and Q. Thus, we conclude that:
P → Q ≡ ¬P ∨ Q
Properties of Logical Equivalence
Logical equivalence has several important properties:
- Reflexivity: Any proposition is logically equivalent to itself. For example, P ≡ P.
- Symmetry: If P is logically equivalent to Q, then Q is logically equivalent to P. For example, if P ≡ Q, then Q ≡ P.
- Transitivity: If P is logically equivalent to Q, and Q is logically equivalent to R, then P is logically equivalent to R. For example, if P ≡ Q and Q ≡ R, then P ≡ R.
Applications of Logical Equivalence
Logical equivalence is widely used in computer science, mathematics, and logic. It is essential for simplifying logical expressions and for proving the validity of arguments. For example, in programming, logical equivalence can help optimise conditional statements to improve code efficiency.
Common Mistakes
Watch out: A common mistake is assuming that two propositions are equivalent without proving it using truth tables or logical laws. Always verify logical equivalence through a systematic approach.
Summary
- Logical equivalence means two propositions have the same truth value in every scenario.
- Key logical equivalences include De Morgan's Laws and the relationship between implication and disjunction.
- Properties of logical equivalence include reflexivity, symmetry, and transitivity.
- Logical equivalence is essential for simplifying logical expressions and proving arguments.
Check your understanding
- What does it mean for two propositions to be logically equivalent?
- State De Morgan's Laws and provide an example of their application.
- Explain the relationship between implication and disjunction.
- List the properties of logical equivalence and provide a brief description of each.