Editing Propositional formula (section)

=== Reduction to normal form ===

[[File:Propositional formula maps 1.png|450px|thumb|right| A truth table will contain 2<sup>n</sup> rows, where n is the number of variables (e.g. three variables "p", "d", "c" produce 2<sup>3</sup> rows). Each row represents a minterm. Each minterm can be found on the Hasse diagram, on the Veitch diagram, and on the Karnaugh map. (The evaluations of "p" shown in the truth table are not shown in the Hasse, Veitch and Karnaugh diagrams; these are shown in the Karnaugh map of the following section.)<!-- For example, row 2 represents the minterm (~p & d & ~c). If "~v" (where v is any variable) is thought of as "0" and "v" is thought of as "1", then the minterm can be thought of as a binary number, e.g. (~p & d & ~c) = 010<sub>2</sub> = 2<sub>10</sub>. A formula (e.g. the formula for q) evaluated for variabiles ''p'' = 0, ''d'' = 1, ''c'' = 0 will produce an output (e.g. q). -->]]

Reduction to normal form is relatively simple once a truth table for the formula is prepared. But further attempts to minimize the number of literals (see below) requires some tools: reduction by De Morgan's laws and [[truth table]]s can be unwieldy, but [[Karnaugh map]]s are very suitable a small number of variables (5 or less). Some sophisticated tabular methods exist for more complex circuits with multiple outputs but these are beyond the scope of this article; for more see [[Quine&ndash;McCluskey algorithm]].

==== Literal, term and alterm ====

In electrical engineering, a variable x or its negation ~(x) can be referred to as a [[literal (mathematical logic)|literal]]. A string of literals connected by ANDs is called a term. A string of literals connected by OR is called an alterm. Typically the literal ~(x) is abbreviated ~x. Sometimes the &-symbol is omitted altogether in the manner of algebraic multiplication.

* Examples
*# a, b, c, d are variables. ((( a & ~(b) ) & ~(c)) & d) is a term. This can be abbreviated as (a & ~b & ~c & d), or a~b~cd.
*# p, q, r, s are variables. (((p &or; ~(q) ) &or; r) &or; ~(s) ) is an alterm. This can be abbreviated as (p &or; ~q &or; r &or; ~s).

==== Minterms ====
In the same way that a 2<sup>n</sup>-row truth table displays the evaluation of a propositional formula for all 2<sup>n</sup> possible values of its variables, n variables produces a 2<sup>n</sup>-square Karnaugh map (even though we cannot draw it in its full-dimensional realization). For example, 3 variables produces 2<sup>3</sup> = 8 rows and 8 Karnaugh squares; 4 variables produces 16 truth-table rows and 16 squares and therefore 16 [[minterms]]. Each Karnaugh-map square and its corresponding truth-table evaluation represents one minterm.

Any propositional formula can be reduced to the "logical sum" (OR) of the active (i.e. "1"- or "T"-valued) minterms. When in this form the formula is said to be in [[disjunctive normal form]]. But even though it is in this form, it is not necessarily minimized with respect to either the number of terms or the number of literals.

In the following table, observe the peculiar numbering of the rows: (0, 1, 3, 2, 6, 7, 5, 4, 0). The first column is the decimal equivalent of the binary equivalent of the digits "cba", in other words:
* Example
*: cba<sub>2</sub> = c*2<sup>2</sup> + b*2<sup>1</sup> + a*2<sup>0</sup>:
*: cba = (c=1, b=0, a=1) = 101<sub>2</sub> = 1*2<sup>2</sup> + 0*2<sup>1</sup> + 1*2<sup>0</sup> = 5<sub>10</sub>

This numbering comes about because as one moves down the table from row to row only one variable at a time changes its value. [[Gray code]] is derived from this notion. This notion can be extended to three and four-dimensional [[hypercube]]s called [[Hasse diagram]]s where each corner's variables change only one at a time as one moves around the edges of the cube. Hasse diagrams (hypercubes) flattened into two dimensions are either [[Veitch diagram]]s or [[Karnaugh map]]s (these are virtually the same thing).

When working with Karnaugh maps one must always keep in mind that the top edge "wrap arounds" to the bottom edge, and the left edge wraps around to the right edge—the Karnaugh diagram is really a three- or four- or n-dimensional flattened object.

{|class="wikitable"
|- style="font-size:9pt" align="center" valign="bottom"
! width="60" Height="39" | decimal equivalent of (c, b, a)
! c
! b
! a
! minterm
|- style="font-size:9pt" align="center" valign="bottom"
| Height="15" | 0
| 0
| 0
| 0
|style="background-color:#FDE9D9" | (~c  &  ~b  &  ~a)
|- style="font-size:9pt" align="center" valign="bottom"
| Height="15" | 1
| 0
| 0
| 1
|style="background-color:#FDE9D9" | (~c  &  ~b  &  a)
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | 3
| 0
| 1
| 1
|style="background-color:#FDE9D9" | (~c  &  b  &  a)
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | 2
| 0
| 1
| 0
|style="background-color:#FDE9D9" | (~c &  b  &  ~a)
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | 6
| 1
| 1
| 0
|style="background-color:#FDE9D9" | (c  &  b  &  ~a)
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | 7
| 1
| 1
| 1
|style="background-color:#FDE9D9" | (c &  b &  a)
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | 5
| 1
| 0
| 1
|style="background-color:#FDE9D9" | (c  &  ~b  &  a)
|- style="font-size:9pt" align="center" valign="bottom"
| Height="12" | 4
| 1
| 0
| 0
|style="background-color:#FDE9D9" | (c  &  ~b  &  ~a)
|- style="font-size:9pt;color:#A5A5A5" align="center" valign="bottom"
| Height="12" | 0
|style="font-weight:bold" | 0
| 0
| 0
| (~a  &  ~b  &  ~c)
|}