Quine–McCluskey algorithm: Difference between revisions

Revision as of 08:12, 13 February 2025

Revision as of 15:37, 3 March 2025

Line 20:

In this example, the input is a Boolean function in four variables, <math>f :\{0,1\}^4 \to \{0,1\}</math> which evaluates to <math>1</math> on the values <math>4,8,10,11,12</math> and <math>15</math>, evaluates to an unknown value on <math>9</math> and <math>14</math>, and to <math>0</math> everywhere else (where these integers are interpreted in their binary form for input to <math>f</math> for succinctness of notation). The inputs that evaluate to <math>1</math> are called 'minterms'. We encode all of this information by writing

:<math>f(A,B,C,D) =\sum m(42,83,10,11,12,15) + d(94,145). \,</math>

This expression says that the output function f will be 1 for the minterms <math>4,8,10,11,12</math> and <math>15</math> (denoted by the 'm' term) and that we don't care about the output for <math>9</math> and <math>14</math> combinations (denoted by the 'd' term). The summation symbol <math>\sum</math> denotes the logical sum (logical OR, or disjunction) of all the terms being summed over.