Form Conversion

Form Conversion Overview

Converting between Boolean representations:

Main conversion paths:

1. Expression $\to$ Truth Table $\to$ Normal Form (Always works, can be slow for many variables)

2. Expression $\to$ Algebraic manipulation $\to$ Normal Form (Faster, requires knowing laws)

3. DNF $\leftrightarrow$ CNF via truth table (Build table, read off the other form)

4. DNF $\leftrightarrow$ CNF via De Morgan (Negate, convert, negate again)

Each method has tradeoffs between simplicity and efficiency.

Converting DNF to CNF

DNF $\to$ CNF conversion methods:

Method 1: Truth Table

1. Evaluate DNF to build truth table
2. Find FALSE rows
3. Write maxterm for each FALSE row
4. AND maxterms together

Method 2: Distribute Apply: A $\lor$ (B $\land$ C) = (A $\lor$ B) $\land$ (A $\lor$ C)

Example: (A $\land$ B) $\lor$ C = (A $\lor$ C) $\land$ (B $\lor$ C) $\leftarrow$ CNF!

Note: Distribution can cause exponential blowup in expression size.

Converting CNF to DNF

CNF $\to$ DNF conversion methods:

Method 1: Truth Table

1. Evaluate CNF to build truth table
2. Find TRUE rows
3. Write minterm for each TRUE row
4. OR minterms together

Method 2: Distribute Apply: A $\land$ (B $\lor$ C) = (A $\land$ B) $\lor$ (A $\land$ C)

Example: (A $\lor$ B) $\land$ C = (A $\land$ C) $\lor$ (B $\land$ C) $\leftarrow$ DNF!

Same exponential blowup risk as DNF$\to$CNF.

Negating Normal Forms

De Morgan's transforms between DNF and CNF:

Negating a DNF gives CNF:

• $\neg$[(A $\land$ B) $\lor$ (C $\land$ D)]
• = $\neg$(A $\land$ B) $\land$ $\neg$(C $\land$ D) [De Morgan on $\lor$]
• = ($\neg$A $\lor$ $\neg$B) $\land$ ($\neg$C $\lor$ $\neg$D) [De Morgan on $\land$]
• This is CNF!

Negating a CNF gives DNF:

• $\neg$[(A $\lor$ B) $\land$ (C $\lor$ D)]
• = ($\neg$A $\land$ $\neg$B) $\lor$ ($\neg$C $\land$ $\neg$D)
• This is DNF!

Key insight: $\neg$(DNF) = CNF with flipped literals, and vice versa.

Truth Table to Normal Form

Universal conversion via truth table:

Given any expression, to get DNF:

1. Evaluate expression for all input combinations
2. List rows where output = 1
3. Write minterm for each TRUE row
4. OR all minterms: $\Sigma$m(TRUE rows)

To get CNF from same table:

1. List rows where output = 0
2. Write maxterm for each FALSE row
3. AND all maxterms: $\Pi$M(FALSE rows)

Both forms represent the same function!

Simplifying After Conversion

Canonical forms are often not minimal. After conversion, simplify:

Common simplifications:

1. Adjacency (terms differing by one literal): (A $\land$ B) $\lor$ (A $\land$ $\neg$B) = A

2. Absorption: A $\lor$ (A $\land$ B) = A

3. Idempotence: A $\lor$ A = A, A $\land$ A = A

4. Complement elimination: (A $\lor$ $\neg$A) = 1, (A $\land$ $\neg$A) = 0

Simplified form uses fewer gates in circuits.

Form Conversion Practice

Conversion summary:

Always simplify the result when possible!

Choosing Between DNF and CNF

When to use DNF:

• Function is TRUE for few rows (few minterms)
• Building AND-OR circuits (sum of products)
• When you need to check satisfiability quickly
• Representing "any of these conditions"

When to use CNF:

• Function is FALSE for few rows (few maxterms)
• SAT solving (standard input format)
• Building OR-AND circuits (product of sums)
• Representing "all of these constraints"

Rule of thumb: Use whichever has fewer terms.

Systematic Conversion Algorithms

Systematic conversion procedures:

To DNF (Sum of Products):

1. Build truth table
2. Find rows where output = 1
3. Write minterm for each such row
4. OR all minterms together

To CNF (Product of Sums):

1. Build truth table
2. Find rows where output = 0
3. Write maxterm for each such row
4. AND all maxterms together

Choosing the Optimal Form

When to use DNF:

• Few true outputs (sparse function)
• Implementing with OR-of-ANDs circuits
• Describing "success cases"

When to use CNF:

• Few false outputs
• SAT solver input
• Describing "constraints that must all hold"
• Implementing with AND-of-ORs circuits

Choose the form that gives fewer terms!

Verifying Conversion Correctness

Verifying conversion correctness:

1. Truth table comparison: Both forms should have identical outputs
2. Spot check: Test a few input combinations
3. Algebraic verification: Apply laws to show equivalence
4. Canonical form: Convert both to same canonical form

Always verify - conversion errors are common!

Normal Forms Synthesis

Normal Forms Summary:

Both forms can represent ANY Boolean function!

Normal Forms Challenge

This challenge integrates all Normal Forms concepts:

• Minterms and maxterms
• DNF and CNF construction
• Conversion between forms
• Minimization awareness
• Choosing optimal representations

Form Size Heuristic

The size heuristic:

• Canonical DNF has one minterm per TRUE row
• Canonical CNF has one maxterm per FALSE row
• TRUE rows + FALSE rows = 2ⁿ (for n variables)

The rule: Count TRUE and FALSE rows. The smaller count tells you which form is shorter.

• Few TRUE rows $\to$ compact DNF
• Few FALSE rows $\to$ compact CNF
• Equal counts $\to$ both forms are the same size