View source for Algebra of logic

The branch of mathematical logic that deals with propositions from the aspect of their logical meanings (true or false) and with logical operations on them.

The algebra of logic originated in the middle of the 19th century with the studies of G. Boole [[#References|[1]]], [[#References|[2]]], and was subsequently developed by C.S. Peirce, P.S. Poretskii, B. Russell, D. Hilbert, and others. The development of the algebra of logic was an attempt to solve traditional logical problems by algebraic methods. With the birth of the theory of sets (in the 1870s), propositions and logical operations on them became the principal subject of algebra of logic. Propositions are understood to mean statements about which it is meaningful to ask whether they are true or false. For instance, the proposition "a whale is an animal" is true, while the statement "all angles are right angles" is false. The connectives "and" , "or" , "if … then" , "is equivalent to" , the particle "not" , etc., which are commonly used in the language of logic, make it possible to construct new, more "complicated" , propositions from those already established. Thus, given that "x&gt; 2" and "x≤ 3" , it is possible to obtain, by using the connective "and" , the proposition "x&gt; 2 and x≤ 3" ; by using the connective "or" it is possible to obtain the proposition "x&gt; 2 or x≤ 3" , etc.

The truth or the falsehood of the propositions obtained in this way depend on the truth or falsehood of the initial propositions and on a corresponding treatment of the connectives as operations on propositions. Often truth is symbolized by the digit "1" and falsehood by the digit "0" . The connectives "and" , "or" , "if … then" , and "is equivalent to" are denoted, respectively, by the symbols &amp; (conjunction), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a0113801.png" /> (disjunction), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a0113802.png" /> (implication), and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a0113803.png" /> (equivalence); negation is represented by a bar <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a0113804.png" /> above the symbol. In addition to individual propositions, examples of which are given above, one also uses variable propositions, i.e. variables whose values may be any individual statements given in advance. As the next step, the concept of a formula was inductively introduced. It formalizes the concept of a compound proposition. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a0113805.png" /> denote individual propositions, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a0113806.png" /> denote variable propositions. Each one of the above letters is known as a formula. Let the symbol * denote any one of the connectives listed above, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a0113807.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a0113808.png" /> denote formulas; then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a0113809.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138010.png" /> will be formulas (e.g. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138011.png" />). The connectives and the particle "not" are looked upon as operations on quantities which assume the values 0 and 1, the results of these operations are also the digits 0 and 1. The conjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138012.png" /> is equal to 1 if and only if both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138013.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138014.png" /> equal 1; the disjunction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138015.png" /> equals 0 if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138017.png" /> are both equal to 0; the implication <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138018.png" /> is equal to 0 if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138020.png" />; the equivalence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138021.png" /> equals 1 if and only if the values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138022.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138023.png" /> are identical; and the negation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138024.png" /> is equal to 1 if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138025.png" />. If the values of the propositions in each formula are given, the value 0 or 1 can be assigned to the formula. This means that any formula can be considered as a way of stating or as a way of realizing a function of the algebra of logic, i.e. a function which is defined on samples of zeros and ones, and with as values also 0 or 1. Two formulas <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138026.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138027.png" /> are said to be equal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138028.png" /> if they realize equal functions. The subject matter of the algebra of logic is the treatment of functions of the algebra of logic and the operations on these functions. In what follows below, the class of functions of the algebra of logic will be extended to the class of functions whose arguments, as well as the functions themselves, assume the values of elements of a finite fixed set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138029.png" />; the number of operations on the functions will also be extended. The algebra of logic is sometimes understood to mean this latter concept. However, from the aspect of practical applications, the most important case is that of sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138030.png" /> of cardinality two, and this case will therefore be discussed in greatest detail. The results presented here are also closely connected with a second approach to the study of propositions — the so-called [[Propositional calculus|propositional calculus]].

In specifying the functions of the algebra of logic one often uses tables which contain all the combinations of the values of the variables and the values of the functions on these combinations. Thus, the synoptic table of the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138031.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138032.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138033.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138034.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138035.png" /> is given below:''''''<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138036.png" /></td> <td colname="2" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138037.png" /></td> <td colname="3" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138038.png" /></td> <td colname="4" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138039.png" /></td> <td colname="5" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138040.png" /></td> <td colname="6" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138041.png" /></td> <td colname="7" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138042.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">0</td> <td colname="2" style="background-color:white;" colspan="1">0</td> <td colname="3" style="background-color:white;" colspan="1">1</td> <td colname="4" style="background-color:white;" colspan="1">0</td> <td colname="5" style="background-color:white;" colspan="1">0</td> <td colname="6" style="background-color:white;" colspan="1">1</td> <td colname="7" style="background-color:white;" colspan="1">1</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">0</td> <td colname="2" style="background-color:white;" colspan="1">1</td> <td colname="3" style="background-color:white;" colspan="1">1</td> <td colname="4" style="background-color:white;" colspan="1">0</td> <td colname="5" style="background-color:white;" colspan="1">1</td> <td colname="6" style="background-color:white;" colspan="1">1</td> <td colname="7" style="background-color:white;" colspan="1">0</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">1</td> <td colname="2" style="background-color:white;" colspan="1">0</td> <td colname="3" style="background-color:white;" colspan="1">0</td> <td colname="4" style="background-color:white;" colspan="1">0</td> <td colname="5" style="background-color:white;" colspan="1">1</td> <td colname="6" style="background-color:white;" colspan="1">0</td> <td colname="7" style="background-color:white;" colspan="1">0</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1">1</td> <td colname="2" style="background-color:white;" colspan="1">1</td> <td colname="3" style="background-color:white;" colspan="1">0</td> <td colname="4" style="background-color:white;" colspan="1">1</td> <td colname="5" style="background-color:white;" colspan="1">1</td> <td colname="6" style="background-color:white;" colspan="1">1</td> <td colname="7" style="background-color:white;" colspan="1">1</td> </tr> </tbody> </table>

</td></tr> </table>

Tables for arbitrary functions of the algebra of logic are constructed in a similar manner. This is the so-called tabular way of specifying functions of the algebra of logic. The tables themselves are sometimes called truth tables. The following equalities play an important part in the transformations of formulas into equivalent formulas:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138043.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

(the law of commutativity);

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138044.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

(the law of associativity);

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138045.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>

(the law of absorption);

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138046.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138047.png" /></td> </tr></table>

(the laws of distributivity);

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138048.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>

(the law of contradiction);

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138049.png" /></td> <td valign="top" style="width:5%;text-align:right;">(6)</td></tr></table>

(the law of the excluded middle);

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138050.png" /></td> <td valign="top" style="width:5%;text-align:right;">(7)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138051.png" /></td> </tr></table>

If these equalities are used, it is possible to obtain new equalities, even without the use of tables. These new equalities are obtained by the so-called identity transformations which, generally speaking, alter the expression, but not the function realized by the expression. For instance, the absorption laws yield the law of idempotency <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138052.png" />. The above equalities frequently simplify the notation of formulas by eliminating some of the parentheses. Thus, the relations (1) and (2) make it possible to replace the formulas <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138053.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138054.png" /> by the more compact notation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138055.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138056.png" />. The former relation is known as the conjunction of the factors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138057.png" />, while the latter is called the disjunction of the terms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138058.png" />. It is also seen from the equalities (5), (6) and (7) that, if the constants 0 and 1, the implication and the equivalence, are regarded as functions, they may be expressed by conjunctions, disjunctions and negations. Thus, any function of the algebra of logic may be realized by a formula written using only the symbols &amp;, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138059.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138060.png" />.

The set of all formulas involving variable propositions, some of the symbols &amp;, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138061.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138062.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138063.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138064.png" />, and the constants 0 and 1 is called a language over these symbols and constants. Equations (1)–(7) show that, for any formula in the language over &amp;, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138065.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138066.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138067.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138068.png" />, 0, and 1, it is possible to find an equivalent formula in the language over &amp;, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138069.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138070.png" />, 0, and 1; for example

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138071.png" /></td> </tr></table>

In the latter language a special role is played by a class of formulas which may be written in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138072.png" />, 0 or 1, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138073.png" /> and where each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138074.png" /> is either a variable proposition, its negation or a conjunction of them, so that none of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138075.png" /> contains equal factors or factors of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138076.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138077.png" /> together, and all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138078.png" /> are pairwise unequal. Here the parentheses are omitted, since it is assumed that the conjunction operation is "stronger" than disjunction, i.e. when calculating with respect to the given values of the variables, the values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138079.png" /> are calculated first. These expressions are called disjunctive normal forms. Each formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138080.png" /> in a language over &amp;, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138081.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138082.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138083.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138084.png" />, 0, 1 which realizes a non-zero function of the algebra of logic, may be converted with the aid of the equalities (1)–(7) into an equivalent disjunctive normal form, containing all variable formulas of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138085.png" /> and any number of other variables, and each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138086.png" /> in this disjunctive normal form containing the same variables. Such a disjunctive normal form is said to be a perfect disjunctive normal form of the formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138087.png" />; the perfect disjunctive normal form of 0 is the formula 0 itself. The possibility of reduction to a perfect disjunctive normal form forms the basis of an algorithm determining the equality or inequality of two given formulas. The procedure of this algorithm is as follows: The given formulas <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138088.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138089.png" /> are reduced to perfect disjunctive normal forms which contain all the variables comprised in both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138090.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138091.png" /> and the two expressions are compared; if they are identical, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138092.png" />; if not, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138093.png" />. An important role in the algebra of logic and its applications is played by contracted disjunctive normal forms, i.e. disjunctive normal forms which satisfy the following conditions: 1) it does not contain pairs of elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138094.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138095.png" /> such that any factor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138096.png" /> is contained in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138097.png" />; 2) for any two elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138098.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a01138099.png" /> one of which contains some variable as factor, while the other contains the negation of this variable (under the condition that the pair of elements does not contain a second variable for which the same is true), there exists (in the same disjunctive normal form) an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380100.png" /> which is equal to the conjunction of the other factors of these two elements. Any disjunctive normal form may be reduced with the aid of the equalities (1)–(7) to an equal contracted disjunctive normal form. Thus, the contracted disjunctive normal form for the formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380101.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380102.png" />. The formulas <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380103.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380104.png" /> are equal if and only if their contracted disjunctive normal forms are identical. In addition to the disjunctive normal form, use is also made of the conjunctive normal form, i.e. of expressions which are obtained from a disjunctive normal form by substituting the symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380105.png" /> for &amp;, &amp; for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380106.png" />, and 0 for 1. For instance, the disjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380107.png" /> yields the conjunctive normal form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380108.png" />. An operation (or function) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380109.png" /> is said to be the dual of an operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380110.png" /> if the table defining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380111.png" /> is obtained from the table which defines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380112.png" /> by substituting 1 for 0 and 0 for 1 throughout (including interchange in the values of the functions). Thus, the conjunction and the disjunction are mutually dual, the negation is dual to itself, the constants 0 and 1 are mutually dual, etc. A transformation of a formula which consists in replacing the symbols of all operations and expressions by the symbols of their dual operations, and in exchanging 0 for 1 and 1 for 0, is called a duality transformation. If the equality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380113.png" /> is true, and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380114.png" /> is the dual of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380115.png" /> while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380116.png" /> is the dual of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380117.png" />, then it is also true that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380118.png" />, and this equality is called the dual of the above equality; this is the so-called duality principle. The pairs of the laws (1), (2) and (3) are examples of dual equalities; equality (5) is dual to equality (6), and each conjunctive normal form is the dual of some disjunctive normal form. A perfect conjunctive normal form and a contracted conjunctive normal form are defined as conjunctive normal forms such that their dual expressions are a perfect disjunctive normal form and a contracted disjunctive normal form, respectively. Perfect and contracted disjunctive and conjunctive normal forms are used for surveying all hypotheses and all consequences of a given formula. A hypothesis of a formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380119.png" /> is understood to be a formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380120.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380121.png" />; a consequence of a formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380122.png" /> is a formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380123.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380124.png" />. A hypothesis of a formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380125.png" /> is said to be simple if it is a conjunction of variable formulas or their negations and if, after discarding any one of its factors, it is no longer a hypothesis of the formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380126.png" />. Similarly, a consequence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380127.png" /> is called simple if it is a disjunction of variable formulas or their negations and if, after one of its elements is discarded, it is no longer a consequence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380128.png" />. The survey of hypotheses and consequences is based on the indication of an algorithm which transforms a given formula into all of its simple hypotheses and consequences and, with the aid of the laws (2)–(7), into all remaining hypotheses and consequences. The algorithm is based on the following facts. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380129.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380130.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380131.png" /> have identical hypotheses and identical consequences. An element of a disjunctive normal form is a hypothesis of that disjunctive normal form, while a factor of a conjunctive normal form is a consequence of that conjunctive normal form. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380132.png" /> is a hypothesis of a proposition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380133.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380134.png" /> is also a hypothesis for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380135.png" />; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380136.png" /> is a consequence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380137.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380138.png" /> is also a consequence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380139.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380140.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380141.png" /> are hypotheses of a proposition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380142.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380143.png" /> is also a hypothesis for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380144.png" />; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380145.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380146.png" /> are consequences of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380147.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380148.png" /> is also a consequence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380149.png" />. A perfect disjunctive normal form has no hypotheses (not containing letters which are not contained in that disjunctive normal form) other than the disjunctions of some of its elements or of disjunctive normal forms equal to them. A perfect conjunctive normal form has no consequences other than the conjunctions of some of its factors or of propositions equal to them. A contracted disjunctive normal form is the disjunction of all its simple hypotheses; a contracted conjunctive normal form is the conjunction of all its simple consequences. A contracted disjunctive normal form has important applications. The first problem which should be mentioned is the minimization of functions of the algebra of logic, which is a part of the problem of synthesis of control (switching) systems. The minimization of functions of the algebra of logic consists in constructing a disjunctive normal form for the given function of the algebra of logic which realizes this function and has the smallest sum of the number of factors in its elements, i.e. has minimal complexity. Such disjunctive normal forms are called minimal. Each minimal disjunctive normal form for a given function of the algebra of logic which is not a constant is obtained from the contracted disjunctive normal form of this function by discarding a number of elements. For certain functions the contracted disjunctive normal form may coincide with the minimal disjunctive normal form. Such a case occurs, for example, with monotone functions, i.e. functions realizable by formulas over &amp;, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380150.png" />, 0, 1.

In the language over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380151.png" />, when the sign <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380152.png" /> is interpreted as addition modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380153.png" />, the following relations are valid:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380154.png" /></td> <td valign="top" style="width:5%;text-align:right;">(8)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380155.png" /></td> <td valign="top" style="width:5%;text-align:right;">(9)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380156.png" /></td> <td valign="top" style="width:5%;text-align:right;">(10)</td></tr></table>

These formulas make it possible to translate formulas from the language over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380157.png" /> into equivalent formulas in the language over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380158.png" />, and vice versa. The identity transformations in the latter language are realized with the aid of equalities established for the conjunction and the following additional equalities:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380159.png" /></td> <td valign="top" style="width:5%;text-align:right;">(11)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380160.png" /></td> <td valign="top" style="width:5%;text-align:right;">(12)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380161.png" /></td> <td valign="top" style="width:5%;text-align:right;">(13)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380162.png" /></td> <td valign="top" style="width:5%;text-align:right;">(14)</td></tr></table>

Here it is considered, as before, that conjunction is a stronger connective than the sign <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380163.png" />. These equalities are sufficient to deduce any valid equality in the language over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380164.png" />, with the aid of identity transformations, just as in the case of the language over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380165.png" />. A proposition in this language is called a reduced polynomial if it is of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380166.png" />, when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380167.png" /> is equal to 1 or is a variable or a conjunction of various variables without negations, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380168.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380169.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380170.png" />, or else is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380171.png" />. Thus, the expression <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380172.png" /> is a reduced polynomial. Any formula of the algebra of logic may be converted to a reduced polynomial by identity transformations. The equality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380173.png" /> is valid if and only if the reduced polynomial for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380174.png" /> is identical with the reduced polynomial for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380175.png" />. In addition to the languages mentioned above there are also other languages equivalent to them. Two languages are called equivalent if each formula in one language can be converted, by means of certain conversion rules, into another equivalent formula in the second language, and vice versa. It is sufficient to base such a language on an arbitrary system of operations (and constants) such that the operations (and constants) of the system may be used to represent any function of the algebra of logic. Such systems are said to be functionally complete. Examples of complete systems are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380176.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380177.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380178.png" />, etc. There exists an algorithm which can be used to establish the completeness or incompleteness of an arbitrary finite system of functions of the algebra of logic. It is based on the following fact. A system of functions of the algebra of logic is complete if and only if it contains functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380179.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380180.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380181.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380182.png" />, as well as functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380183.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380184.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380185.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380186.png" /> is not monotone, and the reduced polynomial of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380187.png" /> contains an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380188.png" /> with more than one factor. There are also other languages based on systems of operations which are not functionally complete, and the number of such languages is infinite. They contain infinitely many pairwise incomparable languages (in the sense that there is no way of translating from one language to another by means of identity transformations). However, for any language based on some operations of the algebra of logic there exists a finite system of equations in this language such that any equality can be deduced with the aid of identity transformations of the equations of this system. Such a system called a deductively complete system of equalities in this language. Thus, the equalities (1)–(6) constitute a complete system of equalities of the language over &amp;, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380189.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380190.png" />, 0, 1.

In considering one of the languages discussed above in conjunction with some complete system of equalities in this language, a tabular statement of the basic operations in the language and the requirement that propositions be the values of its variables are sometimes discarded. Instead, various interpretations of the language are permitted. These interpretations involve some set of objects (which are used as values of the variables) and some system of operations over the objects of this set, which satisfy the equalities from a complete system of equalities of the language. Thus, such a procedure results in the transformation of the language over &amp;, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380191.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380192.png" />, 0, 1 into the language of a [[Boolean algebra|Boolean algebra]]; the language over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380193.png" /> is transformed into the language of a [[Boolean ring|Boolean ring]] (with a unit element); the language over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/a/a011/a011380/a011380194.png" /> is transformed into the language of a [[Distributive lattice|distributive lattice]], etc.

Historically, the development of the algebra of logic has been stimulated mainly by the problems to which it has been applied. An important application is the theory of electric circuits. In certain cases circuits cannot be described in terms of the ordinary two-valued algebra of logic, and a many-valued logic must be considered (cf. [[Many-valued logic|Many-valued logic]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> G. Boole, "The mathematical analysis of logic: being an essay towards a calculus of deductive reasoning" , Macmillan (1847) {{MR|2015605}} {{MR|0028250}} {{ZBL|1200.03003}} {{ZBL|1020.03001}} </TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> G. Boole, "An investigation of the laws of thought, on which are founded the mathematical theories of logic and probabilities" , Dover, reprint (1951) {{MR|0085180}} {{ZBL|1205.03003}} </TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> P.S. Poretskii, "On methods of solving logical equalities and on an inverse method of mathematical logic" , ''Collection of protocols of sessions of the Fiz-Mat. section of the Society of Natural Scientists at Kazan. Univ.'' , '''2''' , Kazan' (1884) pp. 161–330 (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> D. Hilbert, W. Ackerman, "Grundzüge der theoretischen Logik" , Dover, reprint (1946) {{MR|0015342}} {{ZBL|0239.02001}} {{ZBL|0158.00602}} {{ZBL|0088.00901}} {{ZBL|0034.29002}} {{ZBL|0018.19301}} {{ZBL|64.0026.05}} {{ZBL|54.0055.01}} </TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top"> P.S. Novikov, "Elements of mathematical logic" , Oliver &amp; Boyd and Acad. Press (1964) (Translated from Russian) {{MR|0164868}} {{ZBL|0113.00301}} </TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top"> S.V. Yablonskii, G.P. Gavrilov, V.B. Kudryavtsev, "Functions of the algebra of logic and Post classes" , Moscow (1964) (In Russian)</TD></TR></table>



====Comments====
In the theory of Boolean functions contracted disjunctive normal forms are also called abridged disjunctive normal forms, cf. [[Boolean functions, normal forms of|Boolean functions, normal forms of]].