Editing Propositional formula (section)

== Normal forms ==

An arbitrary propositional formula may have a very complicated structure. It is often convenient to work with formulas that have simpler forms, known as '''normal forms'''. Some common normal forms include [[conjunctive normal form]] and [[disjunctive normal form]]. Any propositional formula can be reduced to its conjunctive or disjunctive normal form.

=== 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)
|}

=== Reduction by use of the map method (Veitch, Karnaugh) ===
Veitch improved the notion of [[Venn diagram]]s by converting the circles to abutting squares, and Karnaugh simplified the Veitch diagram by converting the minterms, written in their literal-form (e.g. ~abc~d) into numbers.<ref>Wickes 1967:36ff. Wickes offers a good example of 8 of the 2 x 4 (3-variable maps) and 16 of the 4 x 4 (4-variable) maps. As an arbitrary 3-variable map could represent any one of 2<sup>8</sup>=256 2x4 maps, and an arbitrary 4-variable map could represent any one of 2<sup>16</sup> = 65,536 different formula-evaluations, writing down every one is infeasible.</ref> The method proceeds as follows:

==== Produce the formula's truth table ====

Produce the formula's truth table. Number its rows using the binary-equivalents of the variables (usually just sequentially 0 through n-1) for n variables.

: ''Technically, the [[propositional function]] has been reduced to its (unminimized) conjunctive normal form: each row has its minterm expression and these can be OR'd to produce the formula in its (unminimized) conjunctive normal form.''

Example: ((c & d) &or; (p & ~(c & (~d)))) = q in conjunctive normal form is:
::: ( (~p & d & c ) &or; (p & d & c) &or; (p & d & ~c) &or; (p & ~d & ~c) ) = q

However, this formula be reduced both in the number of terms (from 4 to 3) and in the total count of its literals (12 to 6).

{|
|- style="font-size:9pt;font-weight:bold" align="center"
!style="background-color:#F2F2F2" width="25.5" Height="24" | row
! Minterms
! width="21" | p
! width="21" | d
! width="21" | c
! width="10.5" | (
! width="10.5" | (
! width="10.5" | c
! width="10.5" | &
! width="10.5" | d
! width="10.5" | )
!style="background-color:#FDE9D9" width="10.5" | &or;
! width="10.5" | (
! width="10.5" | p
! width="10.5" | &
! width="10.5" | ~
! width="10.5" | (
! width="10.5" | (
! width="10.5" | c
! width="10.5" | &
! width="10.5" | ~
! width="10.5" | (
! width="10.5" | d
! width="10.5" | )
! width="10.5" | )
! width="10.5" | )
! width="10.5" | )
! width="10.5" | )
! {{Active}} minterms
! Formula in conjunctive normal form
|- style="font-size:9pt"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 0
| align="center" valign="bottom" | ( ~p & ~d & ~c )
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
|style="background-color:#FDE9D9" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
|style="background-color:#EAF1DD" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
|style="background-color:#EAF1DD" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|- style="font-size:9pt"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 1
| align="center" valign="bottom" | ( ~p & ~d & c)
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 1
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
|style="background-color:#FDE9D9" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
|style="background-color:#EAF1DD" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 1
|style="background-color:#DBE5F1" align="center" valign="bottom" | 1
|style="background-color:#EAF1DD" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|- style="font-size:9pt"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 2
| align="center" valign="bottom" | ( ~p & d & ~c )
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
|style="background-color:#FDE9D9" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
|style="background-color:#EAF1DD" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
|style="background-color:#EAF1DD" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|- style="font-size:9pt"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 3
| align="center" valign="bottom" | ( ~p & d & c )
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 1
|style="background-color:#DBE5F1" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
|style="background-color:#FCD5B4" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
|style="background-color:#EAF1DD" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 1
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
|style="background-color:#EAF1DD" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
|style="background-color:#FCD5B4" align="center" | (~p & d & c)
|  valign="bottom" | 
|- style="font-size:9pt"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 4
| align="center" valign="bottom" | ( p & ~d & ~c )
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
|style="background-color:#FCD5B4" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 1
|style="background-color:#DBE5F1" align="center" valign="bottom" | 1
|style="background-color:#EAF1DD" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
|style="background-color:#EAF1DD" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
|style="background-color:#FCD5B4" align="center" | (~p & d & c)
|  valign="bottom" | 
|- style="font-size:9pt"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 5
| align="center" valign="bottom" | ( p & ~d & c )
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 1
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
|style="background-color:#FDE9D9" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 1
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
|style="background-color:#EAF1DD" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 1
|style="background-color:#DBE5F1" align="center" valign="bottom" | 1
|style="background-color:#EAF1DD" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" | 
|  valign="bottom" | 
|- style="font-size:9pt"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 6
| align="center" valign="bottom" | ( p & d & ~c )
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
|style="background-color:#FCD5B4" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 1
|style="background-color:#DBE5F1" align="center" valign="bottom" | 1
|style="background-color:#EAF1DD" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
|style="background-color:#EAF1DD" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
|style="background-color:#FCD5B4" align="center" | (p & d & ~c)
|  valign="bottom" | 
|- style="font-size:9pt"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 7
| align="center" valign="bottom" | ( p & d & c )
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 0
|style="background-color:#DBE5F1" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
|style="background-color:#FCD5B4" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 1
|style="background-color:#DBE5F1" align="center" valign="bottom" | 1
|style="background-color:#EAF1DD" align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 1
|style="background-color:#DBE5F1" align="center" valign="bottom" | 0
|style="background-color:#EAF1DD" align="center" valign="bottom" | 0
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 1
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
| align="center" valign="bottom" | 
|style="background-color:#FCD5B4" align="center" | ( p & d & c )
|  valign="bottom" | 
|- style="font-size:9pt"
| Height="16.5"  valign="bottom" | 
| align="center" valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|style="background-color:#FFA7A9;font-weight:bold" align="center" | q
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|style="background-color:#FFA7A9" align="center" |  = (~p&d&c) &or; (~p&d&c) &or; (p&d&~c ) &or; (p&d&c )
|}

==== Create the formula's Karnaugh map ====

[[File:Propositional formula maps 2.png|400px|thumb|right| Steps in the reduction using a Karnaugh map. The final result is the OR (logical "sum") of the three reduced terms.]]

Use the values of the formula (e.g. "p") found by the truth-table method and place them in their into their respective (associated) Karnaugh squares (these are numbered per the Gray code convention). If values of "d" for "don't care" appear in the table, this adds flexibility during the reduction phase.

==== Reduce minterms ====

Minterms of adjacent (abutting) 1-squares (T-squares) can be reduced with respect to the number of their [[literal (mathematical logic)|literal]]s, and the number terms also will be reduced in the process. Two abutting squares (2 x 1 horizontal or 1 x 2 vertical, even the edges represent abutting squares) lose one literal, four squares in a 4 x 1 rectangle (horizontal or vertical) or 2 x 2 square (even the four corners represent abutting squares) lose two literals, eight squares in a rectangle lose 3 literals, etc. (One seeks out the largest square or rectangles and ignores the smaller squares or rectangles contained totally within it. ) This process continues until all abutting squares are accounted for, at which point the propositional formula is minimized.

For example, squares #3 and #7 abut. These two abutting squares can lose one literal (e.g. "p" from squares #3 and #7), four squares in a rectangle or square lose two literals, eight squares in a rectangle lose 3 literals, etc. (One seeks out the largest square or rectangles.) This process continues until all abutting squares are accounted for, at which point the propositional formula is said to be minimized.

Example:  The map method usually is done by inspection. The following example expands the algebraic method to show the "trick" behind the combining of terms on a Karnaugh map:
: Minterms #3 and #7 abut, #7 and #6 abut, and #4 and #6 abut (because the table's edges wrap around). So each of these pairs can be reduced.

Observe that by the Idempotency law (A &or; A) = A, we can create more terms. Then by association and distributive laws the variables to disappear can be paired, and then "disappeared" with the Law of contradiction (x & ~x)=0. The following uses brackets [ and ] only to keep track of the terms; they have no special significance:
* Put the formula in conjunctive normal form with the formula to be reduced:
::: '''q = ( (~p & d & c ) &or; (p & d & c) &or; (p & d & ~c) &or; (p & ~d & ~c) )''' = ( #3 &or; #7 &or; #6 &or; #4 )
* Idempotency (absorption) [ A &or; A) = A:
::: ( #3 &or; [ #7 &or; #7 ] &or; [ #6 &or; #6 ] &or; #4 )
* Associative law (x &or; (y &or; z)) = ( (x &or; y) &or; z )
::: ( [ #3 &or; #7 ] &or; [ #7 &or; #6 ] &or; [ #6 &or; #4]  )
::: '''[''' (~p & d & c ) &or; (p & d & c) ''']''' &or; '''[''' (p & d & c) &or; (p & d & ~c) ''']''' &or; '''[''' (p & d & ~c) &or; (p & ~d & ~c) ''']'''.
* Distributive law ( x & (y &or; z) ) = ( (x & y) &or; (x & z) ) :
::: ( [ (d & c) &or; (~p & p) ]  &or; [ (p & d) &or; (~c & c) ] &or; [ (p & ~c) &or; (c & ~c) ] )
* Commutative law and law of contradiction (x & ~x) = (~x & x) = 0:
::: ( [ (d & c) &or; (0) ] &or; [ (p & d) &or; (0) ] &or; [ (p & ~c) &or; (0) ] )
* Law of identity ( x &or; 0 ) = x leading to the reduced form of the formula:
::: '''q = ( (d & c) &or; (p & d)  &or; (p & ~c) )'''

==== Verify reduction with a truth table ====

{|
|- style="font-size:9pt;font-weight:bold" align="center"
|style="background-color:#F2F2F2" width="25.5" Height="12" | row
! Minterms
! width="21" | p
! width="21" | d
! width="21" | c
! width="10.5" | (
! width="10.5" | (
! width="10.5" | d
!style="background-color:#DBE5F1" width="10.5" | &
! width="10.5" | c
! width="10.5" | )
!style="background-color:#FDE9D9" width="10.5" | &or;
! width="10.5" | (
! width="10.5" | p
!style="background-color:#DBE5F1" width="10.5" | &
! width="10.5" | d
! width="10.5" | )
!style="background-color:#FDE9D9" width="10.5" | &or;
! width="10.5" | (
! width="10.5" | p
!style="background-color:#DBE5F1" width="10.5" | &
!style="background-color:#EAF1DD" width="10.5" | ~
! width="10.5" | (
! width="10.5" | c
! width="10.5" | )
! width="10.5" | )
|- style="font-size:9pt" align="center"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" | 0
| ( ~p & ~d & ~c )
| 0
| 0
| 0
| 
| 
| 0
|style="background-color:#DBE5F1" | 0
| 0
| 
|style="background-color:#FDE9D9" | 0
| 
| 0
|style="background-color:#DBE5F1" | 0
| 0
| 
|style="background-color:#FDE9D9" | 0
| 
| 0
|style="background-color:#DBE5F1" | 0
|style="background-color:#EAF1DD" | 1
| 
| 0
| 
| 
|- style="font-size:9pt" align="center"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" | 1
| ( ~p & ~d & c)
| 0
| 0
| 1
| 
| 
| 0
|style="background-color:#DBE5F1" | 0
| 1
| 
|style="background-color:#FDE9D9" | 0
| 
| 0
|style="background-color:#DBE5F1" | 0
| 0
| 
|style="background-color:#FDE9D9" | 0
| 
| 0
|style="background-color:#DBE5F1" | 0
|style="background-color:#EAF1DD" | 0
| 
| 1
| 
| 
|- style="font-size:9pt" align="center"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" | 2
| ( ~p & d & ~c )
| 0
| 1
| 0
| 
| 
| 1
|style="background-color:#DBE5F1" | 0
| 0
| 
|style="background-color:#FDE9D9" | 0
| 
| 0
|style="background-color:#DBE5F1" | 0
| 1
| 
|style="background-color:#FDE9D9" | 0
| 
| 0
|style="background-color:#DBE5F1" | 0
|style="background-color:#EAF1DD" | 1
| 
| 0
| 
| 
|- style="font-size:9pt" align="center"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" | 3
| ( ~p & d & c )
| 0
| 1
| 1
| 
| 
| 1
|style="background-color:#DBE5F1" | 1
| 1
| 
|style="background-color:#FDE9D9" | 1
| 
| 0
|style="background-color:#DBE5F1" | 0
| 1
| 
|style="background-color:#FAC090" | 1
| 
| 0
|style="background-color:#DBE5F1" | 0
|style="background-color:#EAF1DD" | 0
| 
| 1
| 
| 
|- style="font-size:9pt" align="center"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" | 4
| ( p & ~d & ~c )
| 1
| 0
| 0
| 
| 
| 0
|style="background-color:#DBE5F1" | 0
| 0
| 
|style="background-color:#FDE9D9" | 0
| 
| 1
|style="background-color:#DBE5F1" | 0
| 0
| 
|style="background-color:#FAC090" | 1
| 
| 1
|style="background-color:#DBE5F1" | 1
|style="background-color:#EAF1DD" | 1
| 
| 0
| 
| 
|- style="font-size:9pt" align="center"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" | 5
| ( p & ~d & c )
| 1
| 0
| 1
| 
| 
| 0
|style="background-color:#DBE5F1" | 0
| 1
| 
|style="background-color:#FDE9D9" | 0
| 
| 1
|style="background-color:#DBE5F1" | 0
| 0
| 
|style="background-color:#FDE9D9" | 0
| 
| 1
|style="background-color:#DBE5F1" | 0
|style="background-color:#EAF1DD" | 0
| 
| 1
| 
| 
|- style="font-size:9pt" align="center"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" | 6
| ( p & d & ~c )
| 1
| 1
| 0
| 
| 
| 1
|style="background-color:#DBE5F1" | 0
| 0
| 
|style="background-color:#FDE9D9" | 1
| 
| 1
|style="background-color:#DBE5F1" | 1
| 1
| 
|style="background-color:#FAC090" | 1
| 
| 1
|style="background-color:#DBE5F1" | 1
|style="background-color:#EAF1DD" | 1
| 
| 0
| 
| 
|- style="font-size:9pt" align="center"
|style="background-color:#F2F2F2;font-weight:bold" Height="12" | 7
| ( p & d & c )
| 1
| 1
| 1
| 
| 
| 1
|style="background-color:#DBE5F1" | 1
| 1
| 
|style="background-color:#FDE9D9" | 1
| 
| 1
|style="background-color:#DBE5F1" | 1
| 1
| 
|style="background-color:#FAC090" | 1
| 
| 1
|style="background-color:#DBE5F1" | 0
|style="background-color:#EAF1DD" | 0
| 
| 1
| 
| 
|- style="font-size:9pt"
| Height="12"  valign="bottom" | 
| align="center" valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|style="background-color:#FAC090;font-weight:bold" align="center" | q
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|  valign="bottom" | 
|}