I find myself pretty confused by the quick explanation of conjunctive normal form. The slide with turning a boolean expression into conjunctive normal form says all of them are the same, but I felt like the lecture was lacking an explanation of how to actually do the operations or why they are the same. Is there a good explainer that kind of walks through this stuff a bit more thoroughly to show the logic of why something like (!CQ || (!HI && !CO)) is the same as (!CQ || !HI) && (!CQ || !C)?
1 Like
Hopefully I’m not overcomplicating this but here’s your answer
Conjunctive normal form (CNF) is a way of representing a Boolean expression as a conjunction (AND) of clauses, where each clause is a disjunction (OR) of literals. The idea is to transform the Boolean expression to an equivalent form that makes it easier to analyze or work with.
To convert a Boolean expression to CNF, you can follow these steps:
1.Eliminate implications and equivalence: Replace any implication and equivalence in the Boolean expression with their corresponding logical operators.
2.Push negation inwards: Use De Morgan’s laws to push negation inwards until they only apply to literals.
3.Distribute disjunction over conjunction: Use the distributive law to express any disjunction of conjunctions as a conjunction of disjunctions.
4.Simplify: Eliminate any tautologies (clauses that always evaluate to true) or contradictions (clauses that always evaluate to false).
For example, let’s consider the Boolean expression: (A && B) || (!A && C)
1.Eliminate implications and equivalence: None in this case.
2.Push negation inwards: None in this case.
3.Distribute disjunction over conjunction:
(A && B) || (!A && C)
= (A || !A) && (A || C) && (B || !A) && (B || C)
= (A || C) && (B || !A) && (B || C)
4.Simplify: None in this case.
The resulting CNF is: (A || C) && (B || !A) && (B || C)
Now let’s take the expression you provided: (!CQ || (!HI && !CO))
1.Eliminate implications and equivalence: None in this case.
2.Push negation inwards:
!(!CQ || (!HI && !CO))
= (CQ && (HI || CO))
3.Distribute disjunction over conjunction: None in this case.
4.Simplify: None in this case.
The resulting CNF is: (CQ || !HI) && (CQ || !CO)
Now let’s compare this CNF to the one you provided: (!CQ || !HI) && (!CQ || !C)
(CQ || !HI) && (CQ || !CO)
= (!(!CQ || !HI) || !CO) && (!CQ || !HI || !C)
This is a bit different from the CNF you provided, but it is still equivalent. To see this, you can use the distributive law to expand the first clause:
(!(!CQ || !HI) || !CO)
= (CQ && HI || CO)
= (CQ || CO) && (HI || CO)
Now we can substitute these expressions back into the CNF:
(!CQ || !HI) && (!CQ || !C)
= (!CQ || !HI || !C) && (!CQ || !HI || !CQ)
= (CQ || !HI) && (CQ || !C)
So, as you can see, the two CNFs are equivalent, even though they look different. The rules for transforming Boolean expressions to CNF are based on logic and algebraic manipulation, and while they may seem abstract at first, they can be applied systematically to any expression to obtain an equivalent CNF.
Hope this helps!
Almost word-for-word what ChatGPT said
1 Like
CNFs are not a terribly easy idea to express. We actually started with a different format for the Conditions which actually allowed us to put conditions within conditions, meaning we could express
if(!CQ || (!HI && !CO))
and even more complex conditions directly.
We ran into a snag, though, when we discovered that Unity has a built in limit to serialization depth, and throws warnings and or errors when you serialize a Condition within a Condition.
That led Sam to demonstrate the Conjunctive Normal Form, which is probably one of the more confusing topics in boolean algebra.
While ChatGPT’s explanation isan’t all that much clearer than Sams, it’s about as close as anything I could come up with.
1 Like