Дискретная математика (1). Лекция Составные высказывания
 Скачать 2.15 Mb.
|
|
Пример. С помощью основных равносильностей доказать, что в булевой функции F =  переменная  является фиктивной.Решение. Применяя закон поглощения и закон склеивания, получим F =  .Так как существует такая формула, реализующая эту булеву функцию, в которой отсутствует , то эта переменная является фиктивной.Пример. С помощью таблицы истинности убедиться в справедливости законов де Моргана  .Решение. Построим таблицу истинности для  и  .
Так как в таблице истинности булевым функциям и соответствуют одинаковые столбцы, то формулы и равносильны.Пример. С помощью основных равносильностей доказать закон обобщенного склеивания  .Решение. Применяя закон склеивания (в обратном порядке, то есть  ) и дистрибутивность (то есть вынесем за скобки  и  ), получим  .Пример. С помощью основных равносильностей доказать, что  .Решение. Применяя основные равносильности, получим  .Лекция 5. Совершенная дизъюнктивная и конъюнктивная нормальные формы (СДНФ и СКНФ) Дизъюнктивные нормальные формы Определение. Элементарной конъюнкцией называется конъюнкция литералов (переменных или их отрицаний), взятых не более чем по одному разу. Например, конъюнкции  ,  , 1 являются элементарными. Причем первая элементарная конъюнкция имеет ранг (число литералов) 2, вторая 3, а третья 0.Следующие конъюнкции:  ,  ,  ,  , 0 не являются элементарными.Определение. Элементарная конъюнкция булевой функции  , содержащая n литералов, называется полной (или минтермом).Определение. Дизъюнкция любого конечного множества элементарных конъюнкций булевой функции F называется дизъюнктивной нормальной формой (ДНФ) функции F. Число элементарных конъюнкций (слагаемых, термов), составляющих ДНФ, называется длиной ДНФ. Например, ДНФ  имеет длину, равную 3.Для произвольной булевой функции F существует, вообще говоря, много различных реализующих ее ДНФ, отличающихся друг от друга длиной, числом вхождений литералов и т.д. Определение. Две (или несколько) ДНФ, реализующих одну и ту же булеву функцию F , называются эквивалентными (или равносильными). Например, для функции  , заданной булевым вектором w(F)=(00100111), существуют следующие эквивалентные ДНФ: , (1) , (2) , (3) , (4) . (5)Определение. ДНФ булевой функции F, состоящая только из полных элементарных конъюнкций, называется совершенной ДНФ (СДНФ). Например, (1) СДНФ функции F. Отметим, что СДНФ является единственной (с точностью перестановки слагаемых) для конкретной булевой функции F . Любую булеву функцию F, заданную формулой, можно с помощью основных равносильностей преобразовать к ДНФ, а затем к СДНФ. Пример. Привести к виду СДНФ булеву функцию F=  .Решение. С помощью основных равносильностей преобразуем к ДНФ: = = = = = ДНФ.Применяя закон склеивания (в обратном порядке:  ), дополняем конъюнкции  ,  до полных элементарных конъюнкций: = .Так как  , то после сокращения одинаковых конъюнкций, получаем СДНФ: F= .Составим таблицу истинности для булевой функции F= (функция из предыдущего примера). Отметим связь между СДНФ и таблицей истинности.Таблица истинности СДНФ
В общем случае также можно вывести закономерности построения СДНФ по таблице истинности булевой функции, что является очень удобным. СДНФ состоит из дизъюнкций полных элементарных конъюнкций наборов переменных  , на которых функция принимает значение 1. Переменные берутся без отрицания, если им соответствует в таблице истинности 1, с отрицанием, если 0.Пример. По таблице истинности составить СДНФ
Решение: СДНФ:  .Пример. Для булевой функции, заданной в виде ДНФ  , составить СДНФ и выполнить проверку по таблице истинности.Решение: Применяя закон склеивания (в обратном порядке: ), дополняем конъюнкции, до полных элементарных конъюнкций. Конъюнкцию  дополняем в два этапа, так как не является элементарной конъюнкцией:  .Так как , после сокращения одинаковых конъюнкций получаем СДНФ: . |
