Дискретная математика

66 которых каждая из булевых переменных XI,X2,..;X „ входит один и только один раз либо без знака отрицания, либо со знаком отрицания. Такие элементарные суммы называют конституентой нуля. Таким образом, конституента нуля для булевых переменных представляет собой формулу вида: X']VX'2... vx' „, (3.12) где x'i (l<i^n) есть либо х,-, либо Ixj. Примеры конституент нуля для переменных Xj,X2,...yX „: XiVX2:. VXn IXiVXj... VX„,..., Ixivlx2v...vlx„. Как известно, дизъюнкция обращается в нуль тогда и только тогда, когда равен нулю каждый дизъюнктивный член. Следовательно, формула (3.12) будет равна нулю тогда и только тогда, когда равны нулю все переменные х,-, которые входят без знака отрицания, и равны единице все те Xi, которые входят в (3.12) со знаком отрицания. Таким образом, доказана теорема. Теорема 3.8. Конституента нуля булевых переменных xi,x2, —yx„ принимает значение О только на одном наборе значений этих переменных, 1 именно, на том наборе, где х,- = О, если х,- входит без отрицания, и х, = 1, если I х,- входит со знаком отрицания. На остальных наборах значений переменных Xi,x2,...^n конституента нуля принимает значение 1. Пример. Пусть задана конституента нуля: lXiVX2... vx „. Очевидно, что эта конституента нуля принимает значение О на наборе n,0,0,...,0j и значение 1 на остальных наборах. Среди всевозможных элементарных произведений, которые можно составить из данных булевых переменных Xj, Х2,..., х„ и их отрицаний, выделяют элементарные произведения, в которых каждая из переменных Xj, Х2,..., х„ входит один и только один раз либо без знака отрицания, либо со знаком отрицания, т.е. элементарные произведения вида x'i&x '2 &...&x' „, (3.13) где х',- (1</<?2) есть либо х,, либо ]х, .Элементарные произведения вида (3.13) называются конституентой единицы. Легко убедиться, что имеет место теорема. Теорема 3.9. Конституента единицы булевых переменных xi,x2,..,^ „ принимает значение 1 только на одном наборе значений этих переменных, I именно на том наборе, где х, = 1, если х, входит в (3.13) без отрицания, и х, = О, если X, входит в (3.13) со знаком отрицания. На остальных наборах значений переменных х;,.х7,...,х„ конституента единицы принимает значение 0.