В лекции сформулируем основные понятия, связанные с булевыми функциями, а также представим алгоритм построения сокращённой булевой функции. Заметим, что: Способы задания булевых функций Способ 1. При задании булевых функций удобно пользоваться таблицами истинности, которые перечисляют всевозможные комбинации истинности и ложности булевых функций: Минимизация дизъюнктивных нормальных форм Определение. Булеву функцию G назовем импликантом булевой функции F, если для любых наборов значений аргументов этих функций из равенства G = 1 следует равенство F = 1...

Определение. Булева функция (формула логики высказываний) F называется частично (не всюду) определённой, если не для всех возможных наборов значений входящих в функцию F перемен­ных указаны её значения. Алгоритм минимизации частично определенных функций в классе дизъюнктивных нормальных форм (ДНФ) включает в себя следующие шаги. Шаг 1. Доопределить булеву функцию F нулями на тех наборах значений пе­ременных, где она не определена. Полученную булеву функцию обозначить через F0. Шаг 2. Построить совершенную дизъюнктивную нормальную форму (СДНФ) булевой функции F0...

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