Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
sav08:normal_forms_for_propositional_logic [2008/03/09 13:25] thibaud Filled-in DNF |
sav08:normal_forms_for_propositional_logic [2008/03/09 13:33] thibaud Filled-in CNF |
||
|---|---|---|---|
| Line 30: | Line 30: | ||
| === Conjunctive Normal Form === | === Conjunctive Normal Form === | ||
| - | CNF | + | Formulas in Conjunctive-normal form look like this: |
| + | $(x_1 \lor x_2 \lor \lor x_3) \land (\lnot x_1 \lor x_3 \lor x_4) \land ...$ \\ | ||
| + | It's defined as $F = \bigwedge^{n}_{i=1} D_i$ and $D_i = \bigvee_{j=1}^{n_i} L_{ij}$ \\ | ||
| + | Like for DNF, $L_{ij}$ are elementary propositions or their negation. The terminology of clauses and literals also applies to CNF. | ||
| - | Literal. Clause. | + | There is no polynomial-time equivalence preserving transformation to CNF or to DNF. |
| - | + | ||
| - | No polynomial-time equivalence preserving transformation to CNF or to DNF. | + | |
| === Complete Sets of Connectives === | === Complete Sets of Connectives === | ||