Discrete Mathematics: Logical Equivalence and Laws of Logic

Foundations of Propositional Logic: Logical Equivalence and Laws of Logic

• Prepared by: Randy O. Bosquillos
• Course Context: Discrete Mathematics - Foundations of Propositional Logic
• Core Learning Objectives:
  • Understand Logical Equivalence: Define logical equivalence and recognize when two propositions have identical truth values across all truth value assignments.
  • Apply Laws of Logic: Identify and correctly apply fundamental laws of logic, including De Morgan's, Distributive, and Identity laws.
  • Simplify Logical Expressions: Utilize laws of logic to transform and simplify complex logical expressions into equivalent, simpler forms.

Logical Equivalence: Definition and Core Concepts

• Definition: Two propositions $p$ and $q$ are logically equivalent if they possess identical truth values under every possible truth assignment for their constituent variables. This relation is written as $p \equiv q$ or $p \Leftrightarrow q$.
• Truth Value Consistency: When $p \equiv q$, regardless of the truth values assigned to the variable inputs, both logical expressions yield the exact same output.
• Biconditional Tautology Relationship: $p \equiv q$ if and only if the biconditional statement $p \leftrightarrow q$ is a tautology (an expression that evaluates to TRUE in all possible cases).
• Fundamental Example:
  • Conditional expression: $p \rightarrow q$
  • Disjunctive expression: $\neg p \vee q$
  • Logical equivalence: $p \rightarrow q \equiv \neg p \vee q$
• Practical Applications: Logical equivalence provides the foundation for simplifying complex logical expressions, optimizing digital circuit designs, writing efficient algorithms, and constructing formal mathematical proofs in discrete mathematics.

Truth Table Verification and Conditional Statements

• Conditional Statement ($p \rightarrow q$):
  • Statement form: "If $p$, then $q$".
  • Evaluation rule: Evaluates to FALSE if and only if $p$ is TRUE and $q$ is FALSE. Evaluates to TRUE in all other cases.
  • Truth evaluation breakdown:
  • When $p = \text{TRUE}$ and $q = \text{TRUE}$, $p \rightarrow q = \text{TRUE}$.
  • When $p = \text{TRUE}$ and $q = \text{FALSE}$, $p \rightarrow q = \text{FALSE}$.
  • When $p = \text{FALSE}$ and $q = \text{TRUE}$, $p \rightarrow q = \text{TRUE}$.
  • When $p = \text{FALSE}$ and $q = \text{FALSE}$, $p \rightarrow q = \text{TRUE}$.
• Disjunction Form ($\neg p \vee q$):
  • Statement form: "not $p$ or $q$".
  • Evaluation rule: Evaluates to FALSE if and only if $\neg p$ is FALSE and $q$ is FALSE (which occurs when $p = \text{TRUE}$ and $q = \text{FALSE}$).
  • Truth evaluation breakdown:
  • When $p = \text{TRUE}$ and $q = \text{TRUE}$, $\neg p \vee q = \text{TRUE}$.
  • When $p = \text{TRUE}$ and $q = \text{FALSE}$, $\neg p \vee q = \text{FALSE}$.
  • When $p = \text{FALSE}$ and $q = \text{TRUE}$, $\neg p \vee q = \text{TRUE}$.
  • When $p = \text{FALSE}$ and $q = \text{FALSE}$, $\neg p \vee q = \text{TRUE}$.
• Row-by-Row Truth Table Comparison ($p \rightarrow q \equiv \neg p \vee q$):
  • Row 1: $p = \text{TRUE}, q = \text{TRUE} \implies p \rightarrow q = \text{TRUE}, \neg p \vee q = \text{TRUE}$ (Matched)
  • Row 2: $p = \text{TRUE}, q = \text{FALSE} \implies p \rightarrow q = \text{FALSE}, \neg p \vee q = \text{FALSE}$ (Matched)
  • Row 3: $p = \text{FALSE}, q = \text{TRUE} \implies p \rightarrow q = \text{TRUE}, \neg p \vee q = \text{TRUE}$ (Matched)
  • Row 4: $p = \text{FALSE}, q = \text{FALSE} \implies p \rightarrow q = \text{TRUE}, \neg p \vee q = \text{TRUE}$ (Matched)

Fundamental Laws of Logic

• Overview: Laws of Logic are fundamental rules governing the manipulation and simplification of logical expressions using connectives such as $\wedge$ (AND), $\vee$ (OR), $\neg$ (NOT), and $\rightarrow$ (Implication).
• Identity Laws:
  • Conjunction Identity: $p \wedge T \equiv p$
  • ANDing any proposition $p$ with TRUE ($T$) always results in $p$ itself.
  • Example: "It is raining" $\wedge T \equiv$ "It is raining".
  • $T$ serves as the identity element for the AND ($\wedge$) operation.
  • Disjunction Identity: $p \vee F \equiv p$
  • ORing any proposition $p$ with FALSE ($F$) always results in $p$ itself.
  • Example: "It is raining" $\vee F \equiv$ "It is raining".
  • $F$ serves as the identity element for the OR ($\vee$) operation.
• Domination Laws:
  • OR Domination: $p \vee T \equiv T$
  • ORing any proposition $p$ with TRUE ($T$) yields TRUE, regardless of $p$'s truth value.
  • When $p = \text{TRUE}$, $T \vee T = \text{TRUE}$.
  • When $p = \text{FALSE}$, $F \vee T = \text{TRUE}$.
  • Truth dominates in disjunction.
  • AND Domination: $p \wedge F \equiv F$
  • ANDing any proposition $p$ with FALSE ($F$) yields FALSE, regardless of $p$'s truth value.
  • When $p = \text{TRUE}$, $T \wedge F = \text{FALSE}$.
  • When $p = \text{FALSE}$, $F \wedge F = \text{FALSE}$.
  • Falsehood dominates in conjunction.
• Idempotent Laws:
  • OR Idempotent Law: $p \vee p \equiv p$
  • A proposition OR-ed with itself returns the original proposition.
  • Example: "It is raining OR it is raining" $\equiv$ "It is raining".
  • Verification: If $p = \text{TRUE}$, $T \vee T = \text{TRUE}$; if $p = \text{FALSE}$, $F \vee F = \text{FALSE}$.
  • AND Idempotent Law: $p \wedge p \equiv p$
  • A proposition AND-ed with itself returns the original proposition.
  • Example: "It is raining AND it is raining" $\equiv$ "It is raining".
  • Verification: If $p = \text{TRUE}$, $T \wedge T = \text{TRUE}$; if $p = \text{FALSE}$, $F \wedge F = \text{FALSE}$.
• Double Negation Law:
  • Formulation: $\neg(\neg p) \equiv p$
  • Principle: Negating a proposition twice cancels the negation and returns the original proposition.
  • Truth Table Verification:
  • When $p = \text{TRUE}$, $\neg p = \text{FALSE}$, leading to $\neg(\neg p) = \text{TRUE}$.
  • When $p = \text{FALSE}$, $\neg p = \text{TRUE}$, leading to $\neg(\neg p) = \text{FALSE}$.
  • Intuition: A statement that is "not false" is logically true.
  • Example: Let $p =$ "It is raining." Then $\neg p =$ "It is not raining," and $\neg(\neg p) =$ "It is not the case that it is not raining," which simplifies to "It is raining."
  • Application in Simplification: $\neg(\neg p) \vee q \equiv p \vee q$.
• Complement Laws:
  • Tautology Form: $p \vee \neg p \equiv T$
  • The disjunction of a proposition and its negation is always TRUE (a tautology).
  • Verification: If $p = \text{TRUE}$, $T \vee F = \text{TRUE}$; if $p = \text{FALSE}$, $F \vee T = \text{TRUE}$.
  • Contradiction Form: $p \wedge \neg p \equiv F$
  • The conjunction of a proposition and its negation is always FALSE (a contradiction).
  • Verification: If $p = \text{TRUE}$, $T \wedge F = \text{FALSE}$; if $p = \text{FALSE}$, $F \wedge T = \text{FALSE}$.
• Commutative Laws:
  • Disjunction (OR): $p \vee q \equiv q \vee p$
  • The order of operands in a disjunction does not alter the truth value.
  • Example: "It is raining OR it is cold" $\equiv$ "It is cold OR it is raining".
  • Conjunction (AND): $p \wedge q \equiv q \wedge p$
  • The order of operands in a conjunction does not alter the truth value.
  • Example: "It is raining AND it is cold" $\equiv$ "It is cold AND it is raining".
• Associative Laws:
  • Disjunction (OR): $(p \vee q) \vee r \equiv p \vee (q \vee r)$
  • Grouping disjuncts with parentheses does not affect the truth value.
  • Example: $(T \vee F) \vee T \equiv T \vee (F \vee T) \equiv T$.
  • Conjunction (AND): $(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$
  • Grouping conjuncts with parentheses does not affect the truth value.
  • Example: $(T \wedge T) \wedge F \equiv T \wedge (T \wedge F) \equiv F$.
• Distributive Laws:
  • First Distributive Law (OR over AND): $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$
  • Disjunction distributes across conjunction. $p$ acts as the pivot element, with $q$ and $r$ as terms.
  • Second Distributive Law (AND over OR): $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$
  • Conjunction distributes across disjunction.
  • Bi-directionality: Both laws hold symmetrically from left-to-right (expansion) and right-to-left (factoring).
• De Morgan's Laws:
  • Law 1 (Negation of AND): $\neg(p \wedge q) \equiv \neg p \vee \neg q$
  • The negation of a conjunction equals the disjunction of the individual negations.
  • Example: "It is NOT the case that (it is raining AND cold)" $\equiv$ "It is NOT raining OR it is NOT cold."
  • Law 2 (Negation of OR): $\neg(p \vee q) \equiv \neg p \wedge \neg q$
  • The negation of a disjunction equals the conjunction of the individual negations.
  • Example: "It is NOT the case that (it is raining OR windy)" $\equiv$ "It is NOT raining AND it is NOT windy."
  • Detailed Application Step:
  1. Identify expression $\neg(p \wedge q)$.
  2. Apply De Morgan's Law: distribute negation to each variable and flip operator from $\wedge$ to $\vee$.
  3. Result: $\neg p \vee \neg q$, verified via matching truth table rows.
• Absorption Laws:
  • First Absorption Law: $p \vee (p \wedge q) \equiv p$
  • If $p$ is TRUE, the entire disjunction evaluates to TRUE. If $p$ is FALSE, $p \wedge q$ is FALSE, making the disjunction FALSE. The larger term absorbs the smaller intersection.
  • Second Absorption Law: $p \wedge (p \vee q) \equiv p$
  • If $p$ is FALSE, the entire conjunction evaluates to FALSE. If $p$ is TRUE, $p \vee q$ is TRUE, making the conjunction TRUE. The smaller term absorbs the larger union.
• Implication Law:
  • Formulation: $p \rightarrow q \equiv \neg p \vee q$
  • Explanation: Replaces the conditional operator $\rightarrow$ with disjunction $\vee$, allowing application of De Morgan's and Distributive laws.
  • Example: "If it rains, the ground is wet" $\equiv$ "It does not rain, or the ground is wet".

Step-by-Step Expression Simplification Examples

• Example 1: Simplification of $\neg(p \wedge q) \vee q$
  • Step 1 (Identify Expression): Start with $\neg(p \wedge q) \vee q$. Recognize that De Morgan's Law applies to $\neg(p \wedge q)$.
  • Step 2 (Apply De Morgan's Law): $\neg(p \wedge q) \equiv \neg p \vee \neg q$. Substitute into the expression to obtain $(\neg p \vee \neg q) \vee q$.
  • Step 3 (Simplify & Verify):
  • Group terms using the Associative Law: $\neg p \vee (\neg q \vee q)$
  • Apply Complement Law ($\neg q \vee q \equiv T$): $\neg p \vee T$
  • Apply Domination Law ($\neg p \vee T \equiv T$): $T$
• Example 2: Comprehensive Step Breakdown of $\neg(p \wedge q) \vee q$
  • Step 1 (De Morgan's Law): $\neg(p \wedge q) \vee q \equiv (\neg p \vee \neg q) \vee q$
  • Step 2 (Associative Law): $(\neg p \vee \neg q) \vee q \equiv \neg p \vee (\neg q \vee q)$
  • Step 3 (Complement & Domination Laws):
  • Complement Law: $\neg q \vee q \equiv T$
  • Expression becomes: $\neg p \vee T$
  • Domination Law: $\neg p \vee T \equiv T$
• Example 3: Simplification of $(p \wedge q) \vee (p \wedge \neg q)$
  • Step 1 (Identify Expression): Start with $(p \wedge q) \vee (p \wedge \neg q)$.
  • Step 2 (Apply Distributive Law): Factor out $p$:
  • $(p \wedge q) \vee (p \wedge \neg q) \equiv p \wedge (q \vee \neg q)$
  • Step 3 (Apply Complement & Identity Laws):
  • Apply Complement Law ($q \vee \neg q \equiv T$): $p \wedge T$
  • Apply Identity Law ($p \wedge T \equiv p$): $p$
  • Final simplified form: $p$
• Example 4: Simplification of $p \vee (\neg p \wedge q)$
  • Step 1 (Apply Distributive Law): Distribute $p \vee$ across the conjunction:
  • $p \vee (\neg p \wedge q) \equiv (p \vee \neg p) \wedge (p \vee q)$
  • Step 2 (Apply Complement Law):
  • Since $p \vee \neg p \equiv T$, the expression becomes $T \wedge (p \vee q)$
  • Step 3 (Apply Identity Law):
  • $T \wedge (p \vee q) \equiv p \vee q$
  • Final simplified form: $p \vee q$

Class Activity Problems and Formal Solutions

• Problem 1: Simplify $\neg(p \wedge q) \vee q$ using De Morgan's and Absorption/Domination Laws. Show each step.
  • Step 1: Apply De Morgan's Law: $\neg(p \wedge q) \vee q \equiv (\neg p \vee \neg q) \vee q$
  • Step 2: Apply Associative Law: $\neg p \vee (\neg q \vee q)$
  • Step 3: Apply Complement Law: $\neg p \vee T$
  • Step 4: Apply Domination Law: $T$
• Problem 2: Prove $p \rightarrow (p \vee q)$ is a tautology using the Implication Law and Identity/Domination Laws.
  • Step 1: Apply Implication Law to the outer conditional: $p \rightarrow (p \vee q) \equiv \neg p \vee (p \vee q)$
  • Step 2: Apply Associative Law to regroup: $(\neg p \vee p) \vee q$
  • Step 3: Apply Complement Law ($\neg p \vee p \equiv T$): $T \vee q$
  • Step 4: Apply Domination Law ($T \vee q \equiv T$): $T$
  • Conclusion: Since the expression evaluates to TRUE ($T$) for all truth assignments, $p \rightarrow (p \vee q)$ is a tautology.
• Problem 3: Simplify $(p \wedge q) \vee (\neg p \wedge q)$ using Distributive and Complement Laws.
  • Step 1: Apply Distributive Law (factor out $q$): $(p \wedge q) \vee (\neg p \wedge q) \equiv (p \vee \neg p) \wedge q$
  • Step 2: Apply Complement Law ($p \vee \neg p \equiv T$): $T \wedge q$
  • Step 3: Apply Identity Law ($T \wedge q \equiv q$): $q$
  • Conclusion: Simplest form is $q$.
• Summary Answer Key:
  • 1: $p \wedge T \equiv p$ (Identity Law)
  • 2: $\neg(p \wedge q) \equiv \neg p \vee \neg q$ (De Morgan's Law)
  • 3: $p \rightarrow q \equiv \neg p \vee q$ (Implication Law)
  • 4: $p \vee (p \wedge q) \equiv p$ (Absorption Law)
  • 5: $\neg(\neg p) \equiv p$ (Double Negation Law)

Key Takeaways

• Logical Equivalence: Two propositions are logically equivalent ($p \equiv q$) if and only if they yield identical truth values under every possible variable assignment, or equivalently, if $p \leftrightarrow q$ is a tautology.
• Laws of Logic as Algebraic Tools: Fundamental laws—including De Morgan's, Distributive, Absorption, Identity, Domination, Idempotent, and Implication laws—provide standard rules for manipulating and transforming complex logical expressions.
• Systematic Simplification Techniques: Applying logic laws step-by-step allows complex logical propositions to be reduced to equivalent minimal forms, facilitating theoretical proofs, algorithm optimization, and digital circuit simplification.