I am confused as to what the difference between Conjunctive Normal Form and Product of Sums is. Can someone explain what is different about them? It seems like they both only use groups of OR statements all AND'd together.
Thanks.
[Math] Conjunctive Normal Form vs Product of Sums
boolean-algebralogic
Related Solutions
The point of 3CNF is that it is a "normal form" for formulas: as you mention, every formula is equivalent, up to a quadratic (linear?) blowup, to a 3CNF formula. 3CNF formulas are "simple", and so more easy to deal with. In particular, if you ever read about NP-completeness, you will find out that we want our to put our "challenging problems" in as simple a form as possible. This makes it easier both to design and analyze algorithms solving these problems, and to prove that other problems are also difficult by reducing 3CNF to them (showing how to solve 3CNF using an algorithm for them).
We care specifically about 3CNF for historical reasons, it was the first (or one of the first) NP-complete problems (check out Cook's paper or Karp's paper on their respective pages). Also, 2CNF is not "complete" (arbitrary formulas cannot are not equivalent to a 2CNF), and it is easy to determine whether they are satisfiable or not (google if interested).
The conversion from CNF to 3CNF is best explained by an example. We convert each clause separately. The clause $A \lor B \lor C \lor D \lor E$ is equivalent to the 3CNF $$(A \lor B \lor x_1) \land (\lnot x_1 \lor C \lor x_2) \land (\lnot x_2 \lor D \lor E), $$ in the sense that the original formula (in this case, a single clause) is satisfiable iff the converted formula is. You convert each of the clauses, and take their conjunction.
Suppose you have an arbitrary formula using the connectives $\lnot,\lor,\land$. Picture it as a tree, where inner nodes are labeled with $\lnot,\lor,\land$, and each node has either one ($\lnot$) or two ($\lor,\land$) children. I'm sorry I can't provide a picture. The first step is "pushing the negations to the leaves" using de Morgan's rules (q.v.). That rids us of all $\lnot$ nodes, but now leaves may be literals (variables or negations of variables). Now we convert the formula to a CNF recursively.
Denote by $\varphi$ the function we're constructing, that takes a formula as above (with $\land,\lor$ and possibly negated variables) and returns a CNF. For the base case, we have $\varphi(x) = x$ and $\varphi(\lnot x) = \lnot x$. For a formula of the form $A \land B$, we don't have to work hard: we define $\varphi(A \land B) = \varphi(A) \land \varphi(B)$. The hardest case is formulas of the form $A \lor B$: a somewhat economical choice is $$\varphi(A \lor B) = (y \lor \varphi(A)) \land ((\lnot y) \lor \varphi(B)), $$ where $y$ is a new variable, and $y \lor \varphi(A)$ means adding $y$ to all the clauses.
General formulas with arbitrary connectives can be handled by expressing the connectives using $\lor,\land,\lnot$, for example by writing a truth-table; this can be quite wasteful, though.
The entire construction results in a quadratic blowup in formula size (your "occurrences of variables"; there are many other ways to define formula size). However, the result you're quoting is only a linear blowup (indeed, by a factor of $24$). It is entirely possible that such a construction exists, but I'm not aware of it; perhaps one of the readers is. The SAT to 3SAT part has a linear blowup with a factor of $3$.
If you do not allow adding new variables, then no simple conversion is possible. While it is always possible to convert an arbitrary formula into a CNF (using the "truth table" approach), not every formula is convertible to a 3CNF without adding new variables. An example is parity on $4$ variables. Also, the conversion from an arbitrary formula to a CNF can result in exponential blow-up, for example for parity on $n$ variables we go from $\Theta(n^2)$ to $\Theta(n2^n)$.
The identity sign is standardly used for a two-place relation, and to get a well formed sentence, a two-place relation needs to be combined with two terms (referring expressions denoting objects), not two propositions. So $P = Q$ is ill-formed in a standard syntax where $P$, $Q$ are propositional variables.
Conventions differ. One common convention is that $\leftrightarrow$ belongs to the formal language of propositional or predicate logic (to express "if and only if"), while $\Leftrightarrow$ is shorthand added to mathematician's English, and means "entails and is entailed by" or "is logically equivalent to".
Conventions differ. But perhaps most common is that $\equiv$ belongs to the formal language of propositional or predicate logic (to express "if and only if") — so is just a stylistic variant of $\leftrightarrow$.
"Compound statements are like functions that deal with truth values rather than numerical values". Applying the square of function to a number gives us a number. Applying the logical operator $\neg$ to the proposition $P$ (grass is blue) gives us another proposition $\neg P$ (grass is not blue). True, the compound proposition has a truth-value, but it isn't happy to say that it deals with a truth-value (it deals with the colour of grass!). But to be sure, the logical operator is such that the truth-value of $P$ fixes the truth-value of $\neg P$ — so, as they say, it is truth-functional.
Best Answer
The CNF is a special type of POSE. We take max terms, which are negations and ORs of variables that evaluate to 1. We then AND the max-terms together. With a POSE, the terms don't have to be max-terms.