Дискретная математика (1). Лекция Составные высказывания
![]()
|
Таблица истинности СДНФ
Конъюнктивные нормальные формы Определение. Элементарной дизъюнкцией называется дизъюнкция литералов (переменных или их отрицаний), взятых не более чем по одному разу. Например, дизъюнкции ![]() ![]() Следующие дизъюнкции: ![]() ![]() ![]() ![]() Определение. Элементарная дизъюнкция булевой функции ![]() Определение. Конъюнкция любого конечного множества элементарных дизъюнкций булевой функции F называется конъюнктивной нормальной формой (КНФ) функции F. Число элементарных дизъюнкций, составляющих КНФ, называется длиной КНФ. Например, КНФ ![]() Для произвольной булевой функции F существует, вообще говоря, много различных реализующих ее КНФ, отличающихся друг от друга длиной, числом вхождений литералов и т.д. Определение. Две (или несколько) КНФ, реализующих одну и ту же булеву функцию F , называются эквивалентными (или равносильными). Определение. КНФ булевой функции F, состоящая только из полных элементарных дизъюнкций, называется совершенной КНФ (СКНФ). Например, ![]() Отметим, что КДНФ является единственной (с точностью перестановки множителей) для конкретной булевой функции F . Любую булеву функцию F, заданную формулой, можно с помощью основных равносильностей преобразовать к КНФ, а затем к СКНФ. Пример. Привести к виду СКНФ булеву функцию F= ![]() Решение. С помощью основных равносильностей преобразуем к КНФ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() В данном примере сначала выразили функцию только с помощью операций дизъюнкции, конъюнкции и отрицания, а затем несколько раз применили формулу ![]() ![]() Применяя закон склеивания (в обратном порядке: ![]() ![]() ![]() ![]() ![]() Так как ![]() ![]() Составим таблицу истинности для булевой функции F= ![]() Таблица истинности СКНФ
В общем случае также можно вывести закономерности построения СКНФ по таблице истинности булевой функции, что является очень удобным. СКНФ состоит из конъюнкций полных элементарных дизъюнкций наборов переменных ![]() Пример. По таблице истинности составить СКНФ.
Решение: F ![]() Пример. Для булевой функции, заданной в виде ДНФ ![]() Решение: Применяя формулу ![]() ![]() Применяя закон склеивания (в обратном порядке: ![]() ![]() ![]() ![]() ![]() Так как ![]() ![]() Таблица истинности СКНФ
Лекция 6. Понятие полноты множества функций. Замкнутые классы. Интерес к разложению булевых функций в канонический полином Жегалкина объясняется прежде всего тем, что такое представление реализуемых функций является основой для синтеза логических схем в базисе элементов И и СЛОЖЕНИЕ по МОДУЛЮ ДВА. Определение.Полином булевой функции F, в слагаемые которого все переменные F входят только без отрицания или только с отрицанием, называется монотонно-поляризованным. Причем в первом случае полином функции F называется положительно-поляризованный и обозначается через P(F), а во втором случае - отрицательно-поляризованным и обозначается через Q(F). Полином P(F) иначе называется каноническим полиномом Жегалкина (или в зарубежной научно-технической литературе - формой Рида-Мюллера). Например, для булевой функции, заданной вектором значений таблицы истинности w(F)=(00100111) полиномы P(F) и Q(F) имеют вид: ![]() ![]() Отметим некоторые свойства монотонно-поляризованных полиномов P(F) и Q(F) булевой функции ![]() 1. Полиномы P(F) и Q(F) являются для булевой функции F единственными. 2. Полиномы P(F) и Q(F) имеют степень n тогда и только тогда, когда таблица истинности функции F содержит нечетное число единиц. 3. Число слагаемых полинома P(F) (Q(F)) четно тогда и только тогда, когда ![]() ![]() Основным достоинством представления булевых функций в виде канонического полинома Жегалкина является то, что в этом представлении любая булева функция задается с помощью всего двух логических операций: конъюнкции и сложения по модулю два, что сокращает набор различных элементов для синтеза логических схем. Опишем метод построения канонического полинома Жегалкина P(F) путем преобразования СДНФ для произвольных булевых функций n переменных F, заданных посредством таблицы истинности. Предварительно отметим основные свойства логической операции сложения по модулю два, которые используются при описании метода.Имеет место ![]() ![]() ![]() ![]() ![]() ![]() ![]() если ![]() ![]() ![]() ![]() Метод построения полинома P(F) заключается в последовательном выполнении следующих действий: 1) выписывается СДНФ булевой функции F; 2) на основе применения (6) СДНФ F преобразуется в СПНФ функции F; 3) в СПНФ все переменные с отрицанием заменяются по формуле (2); 4) в скобочной форме осуществляется раскрытие скобок согласно (3); 5) из полученного выражения удаляются попарно одинаковые слагаемые в соответствии с (1); 6) полученное выражение обозначается через P(F). Пример. Составить канонический полином Жегалкина P(F) булевой функции, если СДНФ данной булевой функции, имеет вид: ![]() Решение. Заменим операцию дизъюнкции операцией сложения по модулю два по (6). При этом воспользуемся тем, что произведение (конъюнкция) любых полных дизъюнкций СДНФ всегда равно нулю. Следовательно, СПНФ будет иметь вид: ![]() Все переменные с отрицанием заменяем по формуле (2), затем раскрываем скобки и из полученного выражения удаляем попарно одинаковые слагаемые в соответствии с (1): ![]() ![]() ![]() Ответ: P(F) ![]() Определение. Система функций ![]() ![]() Из теоремы 8.2 следует, что система ![]() ![]() ![]() ![]() Теорема. Если все функции функционально полной системы ![]() ![]() ![]() Пример. а) Системы ![]() ![]() ![]() ![]() С точки зрения функциональной полноты систему ![]() ![]() ![]() б) Системы ![]() ![]() ![]() Таким образом, система ![]() ![]() ![]() ![]() в) Система ![]() ![]() ![]() ![]() ![]() На свойствах этой системы остановимся подробнее. Определение. Множество ![]() ![]() ![]() Всякая система ![]() ![]() ![]() ![]() ![]() ![]() Пример. а) Множество всех дизъюнкций, то есть функций вида ![]() б) Множество всех линейных функций является замкнутым классом, так как подстановка формул вида ![]() Важнейшим примером замкнутого класса является класс монотонных функций, который будет рассмотрен далее. Ранее рассматривалось отношение частичного порядка ![]() ![]() ![]() ![]() ![]() ![]() Определение. Функция ![]() ![]() ![]() ![]() Пример. а) Функция ![]() б) Дизъюнкция и конъюнкция любого числа переменных являются монотонными функциями. в) Рассмотрим две функции от трёх переменных, заданных следующей таблицей.
Функция ![]() ![]() ![]() ![]() Проверка монотонности функции непосредственно по определению требует анализа таблицы функции и может оказаться достаточно трудоёмкой. Поэтому весьма полезной для установления монотонности является следующая теорема. Всякая булева формула, не содержащая отрицаний, представляет собой монотонную функцию отличную от константы; наоборот, для любой монотонной функции, отличной от 0 и 1, найдётся представляющая её булева формула без отрицаний. Теорема. Всякая булева формула, не содержащая отрицаний, представляет собой монотонную функцию отличную от константы; наоборот, для любой монотонной функции, отличной от 0 и 1, найдётся представляющая её булева формула без отрицаний. Из данной теоремы и того очевидного факта, что подстановка нескольких формул без отрицаний в формулу без отрицаний снова даёт формулу без отрицаний, вытекает следующая теорема. Теорема. Множество всех монотонных функций является замкнутым классом. Но поскольку всякая булева формула без отрицаний является суперпозицией дизъюнкций и конъюнкций, из данной теоремы непосредственно получаем следствие. Следствие. Класс монотонных функций является замыканием системы функций Лекция 7. Множества и подмножества. Основные определения Наиболее простая структура данных, используемых в математике, имеет место в случае, когда между отдельными данными присутствуют какие- либо взаимосвязи. Совокупность таких данных представляет собой множество. Понятие множество принадлежит к числу фундаментальных неопределяемых понятий математики. Множество можно представить себе как совокупность объектов, обладающих общим свойством. Объекты, из которых составлено множество, называются его элементами. Для того чтобы некоторую совокупность элементов можно было назвать множеством, необходимо, чтобы выполнялись условия: должно существовать правило, позволяющее определить, принадлежит ли некоторый элемент множеству; должно существовать правило, позволяющее отличать элементы друг от друга (множество не может содержать двух одинаковых элементов). Множества обычно обозначают большими латинскими буквами (например, A, S, D), а их элементы - строчными (например, a, s, d). Если элемент х принадлежит множеству А, то это обозначается: х ![]() ![]() Примеры множеств. Множество N - множество натуральных чисел. 1 ![]() ![]() Множество L - множество букв русского алфавита. ф ![]() ![]() Множество не содержащие элементов называется пустым. Это множество обозначается ![]() Множества можно задавать следующими способами. Перечисление элементов: P={точка, прямая, плоскость, тело}, S={0,1,2}. Задание характеристического свойства: L={n|n ![]() |