Пусть \(F (x_{1}, x_{2},...,x_{n})\) - произвольная функция алгебры логики \(n\) переменных.
Рассмотрим формулу (в дальнейшем будем на нее ссылаться - (1)):
$$F(1,1,...,1) \wedge x_{1}\wedge x_{2} \wedge ... \wedge x_{n} \vee F (1,1,...,1,0) \wedge x_{1}\wedge x_{2} \wedge ... \wedge x_{n-1} \wedge \bar{x_{n}} \vee$$
$$\vee F (1,1,...,1,0,1) \wedge x_{1}\wedge x_{2} \wedge ... \wedge x_{n-2 } \wedge \overline {x_{n-1}} \wedge x_{n} \vee ... \vee F (0,0,...,0) \wedge \bar{x_{1}} \wedge \bar{x_{2}} \wedge ... \wedge \bar{x_{n}}$$
Формула (1) составлена следующим образом: каждое слагаемое этой логической суммы представляет собой конъюнкцию, в которой первый член является значением функции \(F\) при некоторых определенных значениях переменных \(x_{1}, x_{2},...,x_{n}\), остальные же члены конъюнкции представляют собой переменные или их отрицания. При этом под знаком отрицания находятся те и только те переменные, которые в первом члене конъюнкции имеют значения 0.
Вместе с тем формула (1) содержит в виде логических слагаемых всевозможные конъюнкции указанного вида.
Ясно, что формула (1) полностью определяет функцию \(F (x_{1}, x_{2},...,x_{n})\). иначе говоря, значения функции \(F\) и формулы (1) совпадают на всех наборах значений переменных \(x_{1}, x_{2},...,x_{n}\).
Например, если \(x_{1}\) принимает значение 0, а остальные переменные принимают значения 1, то функция \(F\) принимает значение \(F (0,1,1,...,1)\). При этом логическое слагаемое \(F (0,1,...,1) \wedge \bar{x_{1}} \wedge x_{2} \wedge ... \wedge x_{n}\), входящие в формулу (1), принимает также значение \(F (0,1,...,1)\), все остальные логические слагаемые формулы (1) имеют значения 0. Действительно, в них знаки отрицания над переменными распределяются иначе, чем в рассмотренном слагаемом, но тогда при замене переменных теми же значениями в конъюнкцию войдет символ 0 без знака отрицания, символ 1 под знаком отрицания. В таком случае один из членов конъюнкции имеет значение 0, а по-этому вся конъюнкция имеет значение 0. В связи с этим на основании равносильности \(x \vee 0 \equiv x\) значением формулы (1) является \(F (0,1,...,1)\).
Ясно, что вид формулы (1) может быть значительно упрощен, если в ней отбросить те логические слагаемые, в которых первый член конъюнкции имеет значение 0 (и, следовательно, вся конъюнкция имеет значение 0). Если же в логическом слагаемом первый член конъюнкции имеет значение 1, то, пользуясь равносильностью \(1 \wedge x \equiv x\), этот член конъюнкции можно не выписывать.
Таким образом, в результате получается формула (1), которая содержит только элементарные переменные высказывания и обладает следующими свойствами:
1) Каждое логическое слагаемое содержит все переменные, входящие в функцию \(F (x_{1}, x_{2},...,x_{n})\).
2) Все логические слагаемые формулы различны.
3) Ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание.
4) Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.
Перечисленные свойства будем называть свойствами совершенства или, коротко, свойствами (С).
Из приведенных рассуждений видно, что каждое не тождественно ложной функции соответствует единственная формула указанного вида.
Если функция \(F (x_{1}, x_{2},...,x_{n})\) задана таблицей истинности, то соответствующая ей формула алгебры логики может быть получена просто. Действительно, для каждого набора значений переменных, на котором функция \(F (x_{1}, x_{2},...,x_{n})\) принимает значение 1, запишем конъюнкцию элементарных переменных высказываний, взяв за член конъюнкции \(x_{k}\), если значение \(x_{k}\) на указанном наборе значений переменных есть 1 и отрицание \(x_{k}\), если значение \(x_{k}\), есть 0. Дизъюнкция всех записанных конъюнкций и будет искомой формулой.
Пусть, например, функция \(F (x_{1}, x_{2}, x_{3})\) имеет следующую таблицу истинности:
| \(x_{1}\) | \(x_{2}\) | \(x_{3}\) | \(F (x_{1}, x_{2}, x_{3})\) |
| 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 |
Для наборов значений переменных (1,1,0), (1,0,1), (0,1,0), (0,0,0), на которых функция принимает значение 1, запишем конъюнкции \(x_{1}\wedge x_{2}\wedge \bar{x_{3}}\), \(x_{1}\wedge\bar{ x_{2}} \wedge x_{3}\), \(\bar{x_{1}} \wedge x_{2} \wedge \bar{x_{3}}\), \(\bar{x_{1}} \wedge \bar{ x_{2}} \wedge \bar{x_{3}}\), а искомая формула, обладающая свойствами (С), и имеет вид: $$x_{1} \wedge x_{2}\wedge \bar{x_{3}} \vee x_{1} \wedge \bar{x_{2}} \wedge x_{3} \vee \bar{x_{1}} \wedge x_{2} \wedge \bar{x_{3}} \vee \bar{x_{1}} \wedge \bar{ x_{2}} \wedge \bar{x_{3}}.$$
Пример. Найти формулу, определяющую функцию \(\Phi ( x, y, z)\), по заданной таблице истинности:
| x | y | z | \(\Phi ( x, y, z)\) |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 |
Решение. Используя правило получения формулы алгебры логики из таблицы истинности для функции \(\Phi ( x, y, z)\), получим: $$\Phi ( x, y, z) \equiv xyz \vee \bar{x}yz\vee \bar{x}y\bar{z} \vee \bar{x}\bar{y}z\vee \bar{x}\bar{y}\bar{z}.$$
Упростив эту формулу, получим: $$yz ( x \vee \bar{x} ) \vee \bar{x} \bar{z}(y \vee \bar{y}) \vee \bar{x}\bar{y}z \equiv yz \vee \bar{x}\bar{z} \vee \bar{x}\bar{y} z \equiv$$ $$\equiv yz \vee \bar{x}( \bar{z} \vee \bar{y}z) \equiv yz \vee \bar{x} (\bar{z} \vee \bar{y}) (\bar{z}\vee \bar{z}) \equiv yz \vee \bar{x} ( \bar{z} \vee \bar{y}) \equiv$$ $$\equiv ( yz \vee \bar{x}) \wedge ( yz \vee \bar{z} \vee \bar{y}) \equiv ( y \vee \bar{x}) (z \vee \bar{x}) ( y \vee \bar{z} \vee \bar{y}) ( z \vee \bar{z} \vee \bar{y}) \equiv$$ $$\equiv ( y \vee \bar{x}) ( z \vee \bar{x}) \equiv \bar{x} \vee yz \equiv x \rightarrow yz.$$
Таким образом, искомой формулой. определяющей функцию \(\Phi ( x, y, z)\), можно считать \(x\rightarrow yz\), или \(\bar{x} \vee yz\), или какую нибудь другую из равносильных им формул.
