В этой лекции рассмотрим операцию, именуемую суммой по модулю 2, а также представим алгоритм построения полинома Жегалкина (алгоритм приведения формулы к алгебраической нормальной форме). Определение. Двоичным сложением (суммой по модулю 2, сложением по модулю 2, кольцевой суммой или операцией «Исключающее или») называется формула логики высказываний (булева функция), таблица истинности которой представлена в виде Таблица истинности для двоичного сложения Таким образом, формула логики высказываний...

В лекции приводятся определения основных классов булевых функций, а также формулируется теорема Поста о полноте. Класс самодвойственных функций. Пример 1. Используя принцип двойственности, запишем булеву функцию, двойственную заданной булевой функции, расставим в полученной булевой функции скобки, указывающие порядок выполнения действий. Пример 2. Несамодвойственная функция F = (01011001) задана вектором значений. Используя лемму о несамодвойственной функции, под­становкой вместо переменных x, y, z только переменную x и её отрицание получим одну из констант (0 либо 1)...