TL;DR

• Shannon expansion is the formula for decomposing a Boolean function into a single MUX.
• cofactor is "a new function that fixes one variable to 0/1" so that that variable disappears inside the cofactor.
• Boolean difference is a sensitivity function that computes "does the output change when the input x is flipped?".
• ∃(existential) quantification is a formula for "only one solution needs to exist," which is the core of the SAT.
• Why optimization is hard: SAT only needs to find one solution, optimization needs to compare all candidates.

1. Problem: When Karnaugh map breaks

1.1 40 variables, the Karnaugh map is over

• 2^40 scale → "I can draw it, but I can't write it"
• Conclusion: we should treat Boolean functions as data structure + operator, not by hand.

1.2 The 3 things this article targets

• decomposition (decomposition)
• computation (representation that a program can handle)
• application (computation directly in EDA)

2. Shannon cofactor: a new function created by "fixing a variable"

2.1 Definition: A cofactor is a substitution

• For an input variable x in f, the
  • positive cofactor: ( f_{x} = f(x=1) )
  • negative cofactor: ( f_{~{x}} = f(x=0) )

2.2 Key point: "This is a new function, x disappears"

• We have fixed x to 0/1, so x can no longer appear in the result.
• If you miss this, all subsequent Boolean difference/quantification falls apart.

2.3 (short example)

• Example: ( f(x,y,z) = xy+x~z+~xyz )
  • ( f(x=1) = y + \bar{z} ) (can be simplified)
  • ( f(x=0) = yz )

3. Shannon expansion: "Boolean function = MUX" ends as soon as you see it

3.1 Theorem (Shannon expansion theorem)

For any f and any variable x:
f=x⋅f(x=1)+~x⋅f(x=0)

3.2 Hardware perspective: Shannon expansion = 2:1 MUX

• select = x
• data1 = f(x=1)
• data0 = f(x=0)
• output is f

📌 This is where the "branch" sense comes in:

• When we go down the x=0 branch, we only need to look at f(x=0)
• When we go down the x=1 branch, we only need to look at f(x=1)

3.3 MUX tree = recursive decomposition

• 1 variable → 2 branches
• 2 variables → 4 branches
• k variables → 2^k branches
• This looks like "enumeration", but EDA does pruning here. (explained later)

[Figure 1] Shannon expansion as a 2:1 MUX
[Figure 2] Illustration of a MUX tree where a 2-variable expansion creates four leaves

4. cofactor means "operations are exchanged": 계산이 쉬워지는 이유

4.1 A very important property

• complement:
  • (~f)x=~(𝑓𝑥)
• AND/OR/XOR can do the same "cofactor first → operation later" thing
  • (𝑓∧𝑔)𝑥=𝑓𝑥∧𝑔𝑥

In other words, you don't make a big expression and then cofactor it, you
cofactor first to make the expression smaller and then calculate it.

5. Boolean difference: "sensitivity" as a formula

5.1 Definition

∂f/∂x=f(x=1)⊕f(x=0)

5.2 Meaning: "The condition that the output changes when x is flipped"

• XOR is "1 if different"
• So, for an input pattern with a Boolean difference of 1:
  • Changing x by 0→1 or 1→0 will definitely change f

5.3 Sensitivity by Example

• inverter: f=~x
  • 𝑓(1)=0,𝑓(0)=1⇒∂𝑓/∂𝑥=1
  • Always sensitive
• AND: ( f=xy )
  • 𝑓(1)=𝑦,𝑓(0)=0⇒∂𝑓/∂𝑥=𝑦
  • Change in x affects output only when y=1
• OR: ( f=x+y )
  • 𝑓(1)=1, 𝑓(0)=𝑦 ⇒ ∂𝑓/∂𝑥=~𝑦
  • affects only when y=0

5.4 The correct interpretation of "x has no logical effect on F?"

• Doesn't mean "always no effect".
• It means that under certain input conditions it may have no effect.
• Picking out those conditions is a Boolean difference.

[Figure 3] Gate illustration of why Boolean difference is y / ȳ in AND/OR

6. Quantification: “변수 제거”를 목적 함수로 만든 연산

6.1 existential quantification (∃): "only one solution is required"

∃xf=f(x=0)∨f(x=1)

• Meaning: Given other inputs fixed, does choosing x well result in f=1?

6.2 universal quantification (∀): "must be true in all cases"

∀xf=f(x=0)∧f(x=1)

• Meaning: Is f=1 always true no matter what x is?

6.3 1:1 correspondence with the sentence you said

"You don't have to enumerate them all, just find any one year"

This is exactly what you did:

∃ quantification

• And the core form of the SAT:∃X:F(X)=1

7. SAT vs Optimization: Why "Optimization" is Tighter

7.1 SAT is "find one and done"

• Ends when a solution exists that satisfies the condition
• Can be terminated (pruning)

7.2 Optimization is "comparison is the essence"

• To prove that there is a better solution
  • You need to keep looking at other branches
• That's why EDA optimization is structurally hard (which leads to the NP-hard story)

[Figure 4] SAT stops at first satisfaction, Optimization continues to explore

다음 강의로 자연스럽게 연결: Tautology와 URP

8.1 Is a tautology "always 1?"

• f≡1?
• Key idea: if f is a tautology ⇔ f(x=0) and f(x=1) are both tautologies

8.2 URP's intuition

• Decomposition into Shannon coefficients (branching)
• Terminate right in the middle (strong pruning)
• Ends up not being an "enumeration" algorithm, but a "throw away what you can" algorithm

이 글에서 반드시 가져가야 하는 5개

1. cofactor는 substitution이며, in the resulting function, the variable disappears
2. Shannon expansion is both a formula and a 2:1 MUX model
3. Boolean difference is a function that gives "the conditions under which a change in x affects the output"
4. ∃ quantification implements "only one is needed" as an OR
5. SAT is one and done, Optimization takes longer because of comparisons