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

65 X .V х°у Если второе и третье места в столбце 0 0 1 значений этой таблицы заняты 0 1 соответственно значениями 1, 1 или 0, 0, 1 0 то получаем jc"jj = xiу либо х°у = xjу . 1 1 0 Если же на этих местах стоит 0, 1 или 1, 0, то получаем соответственно х ° у равносильно 1у либо 7x. В обоих случаях функция ° выражена через 7. Однако связка 7 не является достаточной для выражения любой формулы, ибо с помощью 7 можно получать формулы только вида ]х, Jlx) и т.п., а например формулу, тождественно равную I, получить нельзя. Теорема доказана. Для операции сложения по модулю два имеем: х+у= 7(х=у). Эта операция, очевидно, коммутативна: х+у=у+х. Легко убедиться, что конъюнкция дистрибутивна относительно сложения по модулю два, т.е. xc&^y+zj ~ (x&yj-i-fxe&zj, (y+zj&x-fy&xj+fz&xj. Также просто показать, чтох+ X' - О, X + X + X ~ л:. Более обще: если суммировать одинаковые слагаемые чётное число раз, то получим нуль, если же число одинаковых слагаемых, например х, нечётно, то эта сумма равносильна х. § 8, Элементарные суммы и произведения. Конституенты нуля и единицы Известно, что в математическом анализе среди всевозможных функций выделяют элементарные (основные) функции: степенные, показательные, тригонометрические и т.п. Среди булевых функций тоже выделяют некоторые как элементарные (основные), а далее из них можно получать более сложные. Элементарной суммой (элементарным произведением) называют дизъюнкцию (конъюнкцию) булевых переменных либо их отрицаний. Одну переменную тоже будем рассматривать как элементарную сумму или как элементарное произведение. Элементарную сумму часто называют дизъюнктом, а слагаемые этой суммы называются литералами (литерами). Примеры элементарных сумм: х, х\уу, xvyvjxvz. Примеры элементарных произведений; ]х, х&у, Ix&z&x&y. Очевидно, что элементарная сумма является тавтологией (тождественно равной единице) тогда и только тогда, когда в ней содержится хотя бы одна пара слагаемых, из которых одно есть некоторая переменная, а другое - отрицание этой переменной. Аналогично имеем, что элементарное произведение является противоречием тогда и только тогда, когда в нем содержится хотя бы одна пара множителей, из которых один множитель является отрицанием другого. Среди элементарных сумм, которые можно составить из данных переменных и их отрицаний, выделяют элементарные суммы, в