Logic Laws, Simplification, and Disjunctive Normal Form Notes

Logic Laws and Formula Simplification

• Goal of Simplification for Validity:

  • To show a logical expression is valid, a truth table would result in a final column where every entry is "True."
  • When using logic laws to simplify a valid expression, the final result should be a single $T$ (True).

• Eliminating Conditionals (Laws 10, 11, 12):

  • The first step in simplification is usually removing conditional (implies) or biconditional (if and only if) signs.
  • Conditional Law: $A \rightarrow B$ is replaced with $\neg A \lor B$.

• Laws of Movement and Grouping:

  • Commutativity: Allows swapping the order of variables (e.g., $A \lor B \equiv B \lor A$).
  • Associativity: Allows changing the placement of brackets when the operations are all the same (e.g., $(P \lor Q) \lor R \equiv P \lor (Q \lor R)$).
  • Practical Application: If a long series of operations consists entirely of ORs (or entirely of ANDs), terms can be shuffled and rearranged using both Commutativity and Associativity simultaneously.

• Key Simplification Laws:

  • Excluded Middle: $A \lor \neg A$ is replaced with $T$.
  • Domination Law:
    • $A \lor T \equiv T$
    • $A \land F \equiv F$
  • Identity Law:
    • $A \land T \equiv A$
    • $A \lor F \equiv A$
  • Double Negation: $\neg \neg P \equiv P$.

• Mathematical Analogies:

  • OR and AND work like Addition ($+$) and Multiplication ($\times$) in real numbers because they are commutative and associative.
  • Subtraction and Division do not work this way, as changing the order or grouping changes the result.
  • Distributivity: This law must be used when there is a mixture of ANDs and ORs; terms cannot simply be rearranged.

Proving Logical Equivalence

• Methodology:

  • To show logical equivalence using laws, one can work from both sides of the equation simultaneously.
  • Once both sides simplify to the exact same expression, the proof is complete.

• Exercise 1: Beginner Level

  • Problem: Show $\neg P \rightarrow Q \equiv P \lor Q$.
  • Step 1 (Conditional Law): Negate the left side of the implies and change the arrow to an OR: $\neg (\neg P) \lor Q$.
  • Step 2 (Double Negation): $\neg \neg P$ becomes $P$, resulting in $P \lor Q$.
  • Step 3 (Commutativity): If needed, rearrange to match the other side.

• Exercise 2: Advanced Level (Biconditional)

  • Problem: Show equivalence involving a biconditional sign ($\leftrightarrow$).
  • Biconditional Law (Law 11): $A \leftrightarrow B$ is replaced with $(A \rightarrow B) \land (B \rightarrow A)$.
  • De Morgan's Law: Used to expand a negation over brackets: $\neg (A \land B) \equiv \neg A \lor \neg B$ and $\neg (A \lor B) \equiv \neg A \land \neg B$.
  • Complex Simplification Steps:
    • Expand Biconditional to Conditionals.
    • Apply Conditional Law ($\neg A \lor B$).
    • Apply De Morgan's if negations are outside brackets.
    • Apply Distributivity ($A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$).
    • Simplify using Excluded Middle ($T$) and Identity or Domination laws.

Logic in Natural Language

• The Conditional in English:
  • Statements like "Clean your room or you won't get dinner" are logically equivalent to "if-then" statements.
  • Let $A =$ "You clean your room" and $B =$ "You get dinner."
  • The English statement "Clean your room or you won't get dinner" is represented as $A \lor \neg B$.
  • This is logically equivalent to $\neg A \rightarrow \neg B$ ("If you don't clean your room, then you don't get dinner").
  • Precedence of NOT: The negation symbol ($\neg$) is the strongest operator; brackets are not strictly required around negated variables (e.g., $\neg A \lor B$ is clearly $( \neg A ) \lor B$).

Full Disjunctive Normal Form (DNF)

• Definition: A standard way of representing a logical formula based on its truth table. It allows for the comparison of different but equivalent expressions.

• The Goal: Given the final column of a truth table, find the formula that produces it.

• The Procedure for Full DNF:

  1. Identify Model Rows: Focus only on the rows where the final result is TRUE.
  2. Create Row Formulas (Min-terms):
     • For each model row, look at the values of the variables.
     • If a variable is TRUE, write the variable (e.g., $P$).
     • If a variable is FALSE, write its negation (e.g., $\neg P$).
     • Connect all variables in that row using AND ($\land$).
  3. Combine with OR: Link all the individual row formulas together using OR ($\lor$).

• Example 1 (2 Variables):

  • Row 1: $P=F, Q=F$, Result=$T$. Row Formula: $\neg P \land \neg Q$.
  • Row 3: $P=T, Q=F$, Result=$T$. Row Formula: $P \land \neg Q$.
  • Full DNF: $(\neg P \land \neg Q) \lor (P \land \neg Q)$.

• Example 2 (3 Variables - Q, R, S):

  • The task is to find the DNF for $\neg P$, given a truth table for $P$.
  • Step 1: Negate the final column of $P$ to get the column for $\neg P$.
  • Step 2: Identify rows where $\neg P = T$. In this specific case, Rows 1, 2, and 4 are models:
    • Row 1: $Q=F, R=F, S=F \rightarrow \neg Q \land \neg R \land \neg S$
    • Row 2: $Q=F, R=F, S=T \rightarrow \neg Q \land \neg R \land S$
    • Row 4: $Q=F, R=T, S=T \rightarrow \neg Q \land R \land S$
  • Step 3: The Full DNF is the OR summation of these terms:
    • $(\neg Q \land \neg R \land \neg S) \lor (\neg Q \land \neg R \land S) \lor (\neg Q \land R \land S)$

Questions & Discussion

• Question: If it's valid, what would the final column of a truth table look like?
  • Response: It would be all True.
• Question: What do we expect the final answer to be when simplifying a valid formula using logic laws?
  • Response: It should simplify down to just a $T$.
• Question: What law allows us to swap the order of variables?
  • Response: The Commutative Law.
• Question: Which law describes $A \lor \neg A$ being replaced with True?
  • Response: The Excluded Middle.
• Question: Do we need brackets around negations?
  • Response: No, because "not" is stronger than any other operation. $\neg A \lor B$ is unambiguous.
• Question: Can we just rearrange terms if there is a mixture of ANDs and ORs?
  • Response: No, we must be careful and use the Distributivity law in those cases.