§ 8. Элементарные суммы и произведения. Конституенты нуля и единицы

Известно, что в математическом анализе среди всевозможных функций выделяют элементарные (основные) функции: степенные, показательные, тригонометрические и т.п. Среди булевых функций тоже выделяют некоторые как элементарные (основные), а далее из них можно получать более сложные.

Элементарной суммой (элементарным произведением) называют дизъюнкцию (конъюнкцию) булевых переменных либо их отрицаний. Одну переменную тоже будем рассматривать как элементарную сумму или как элементарное произведение. Элементарную сумму часто называют дизъюнктом, а слагаемые этой суммы называются литералами (литерами). Примеры элементарных сумм: x, x∨y, x∨y∨¬x∨z.

Примеры элементарных произведений: ¬x, x&y, ¬x&z&x&y

Очевидно, что элементарная сумма является тавтологией (тождественно равной единице) тогда и только тогда, когда в ней содержится хотя бы одна пара слагаемых, из которых одно есть некоторая переменная, а другое - отрицание этой переменной.

Аналогично имеем, что элементарное произведение является противоречием тогда и только тогда, когда в нем содержится хотя бы одна пара множителей, из которых один множитель является отрицанием другого.

Среди элементарных сумм, которые можно составить из данных переменных x1,x2,...,xn и их отрицаний, выделяют элементарные суммы, в которых каждая из булевых переменных x1,x2,...,xn входит один и только один раз либо без знака отрицания, либо со знаком отрицания. Такие элементарные суммы называют конституентой нуля. Таким образом, конституента нуля для булевых переменных x1,x2,...,xn представляет собой формулу вида:

$x'_1∨ x'_2 ... ∨ x'_n$

где $x'_i (1≤ i≤ n)$ есть либо $x_i, $либо $¬x_i.$

Примеры конституент нуля для переменных x1,x2,...,xn:

$x_1∨ x_2 ... ∨ x_n, ¬x_1∨ x_2 ... ∨ x_n ,…, ¬x_1∨¬x_2∨...∨¬x_n$

Как известно, дизъюнкция обращается в нуль тогда и только тогда, когда равен нулю каждый дизъюнктивный член. Следовательно, формула (3.12) будет равна нулю тогда и только тогда, когда равны нулю все переменные xi, которые входят без знака отрицания, и равны единице все те xi, которые входят в (3.12) со знаком отрицания. Таким образом, доказана теорема.

Теорема 3.8. Конституента нуля булевых переменных x1,x2,...,xn принимает значение 0 только на одном наборе значений этих переменных, именно, на том наборе, где xi = 0, если xi входит без отрицания, и xi = 1, если xi входит со знаком отрицания. На остальных наборах значений переменных x1,x2,...,xn конституента нуля принимает значение 1.

Пример. Пусть задана конституента нуля:

$¬x_1∨ x_2 ... ∨ x_n.$

Очевидно, что эта конституента нуля принимает значение 0 на наборе (1,0,0,...,0) и значение 1 на остальных наборах.

Среди всевозможных элементарных произведений, которые можно составить из данных булевых переменных x1, x2,..., xn и их отрицаний, выделяют элементарные произведения, в которых каждая из переменных x1, x2,..., xn входит один и только один раз либо без знака отрицания, либо со знаком отрицания, т.е. элементарные произведения вида

где $x'i (1<i<n)$ есть либо xi , либо ¬xi .Элементарные называются конституентой единицы. произведения вида

Легко убедиться, что имеет место теорема.

Теорема 3.9. Конституента единицы булевых переменных x1,x2,...,xn принимает значение 1 только на одном наборе значений этих переменных, именно на том наборе, где xi = 1, если xi входит в (3.13) без отрицания, и xi = 0, если xi входит в (3.13) со знаком отрицания. На остальных наборах значений переменных x1,x2,...,xn конституента единицы принимает значение 0.

Пример. Пусть имеем конституенту единицы:

Ясно, что эта конституента единицы принимает значение 1 на наборе (1,0,1,1,...1) и значение 0 на остальных наборах.