Совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ).
Формула называется СДНФ, если: 1) она является ДНФ; 2) каждая элементарная конъюнкция ДНФ содержит все наименования переменных, от которых зависит формула, и каждое наименование входит в него один раз; 3) среди элементарных конъюнкций ДНФ нет одинаковых. Примеры: 1. - СДНФ 2. - не является СДНФ, т.к. в первой скобке нет переменной Z. Формула называется СКНФ, если 1) она является КНФ; 2) каждая элементарная дизъюнкция КНФ содержит все наименования переменных, от которых зависит формула и это наименование входит только один раз; 3) среди элементарных дизъюнкций КНФ нет одинаковых. Пример: - СКНФ Теорема 1: Если формула не тождественно истинная, то для нее существует и при том единственная СКНФ. Теорема 2: Если формула не тождественно ложная, то для нее существует и при том единственная СДНФ. Совершенные формы можно строить с помощью: 1) равносильных преобразований; 2) таблиц истинности.
Алгоритм построения СДНФ с помощью таблице истинности: Рассмотрим этот алгоритм на конкретном примере, используя таблицу истинности
1) выбираем те строки таблицы , на которых формула принимает значение истина: 2, 4, 7, 8; 2) для каждой выбранной строки строим элементарную конъюнкцию из переменных, от которых зависит формула следующим образом: если переменная в строке принимает значение истина, то она непосредственно входит в элементарную конъюнкцию, если ложь, то она входит с отрицанием; 3) из элементарных конъюнкций составляем ДНФ. - СДНФ Замечание: Если все строки формулы в таблице истинности принимают значение ложь, то СДНФ построить нельзя.
Алгоритм построения СКНФ по таблице истинности: Данный алгоритм аналогичен алгоритму построения СДНФ. 1) выбираем строки таблицы, на которых формула принимает значение ложь: 1, 3, 5, 6; 2) для каждой выбранной строки строим элементарную дизъюнкцию из переменных, от которых зависит формула, следующим образом: если переменная в строке принимает значение ложь, то она сама входит в элементарную дизъюнкцию, если истина, то она входит с отрицанием; 3) из элементарных дизъюнкции составляем КНФ. - СКНФ Замечание: Если все строки формулы в таблице принимают значение истина, то СКНФ построить нельзя. С точки зрения алгебры логики представление функции в виде СНКФ рациональнее, когда таблица истинности содержит меньше нулей , чем единиц Описанный способ нахождения СНДФ и СНКФ исходной формулы по таблице истинности бывает более трудоёмким, чем следующий: Алгоритм построения СДНФ с помощью равносильных преобразований: 1) приводим исходную формулу к ДНФ; 2) если в элементарную конъюнкцию некоторая переменная входит со своим отрицанием, то удаляем эту конъюнкцию из ДНФ; 3) если в элементарную конъюнкцию некоторая переменная входит несколько раз, то удаляем эти переменные кроме одной; 4) если в некоторую элементарную конъюнкцию некоторая переменная или переменные не входят, то заменяем её на эквивалентную форму, добавляя к ней одну или несколько переменных в виде и, применяя закон дистрибутивности, приводим формулу к ДНФ; 5) если в полученной ДНФ имеется несколько одинаковых элементарных конъюнкций, то оставляем только одну из них. В результате получаем СДНФ. Пример: Пусть дана ДНФ функции. Найдте СДНФ функции.
-СДНФ
Алгоритм построения СКНФ с помощью равносильных преобразований: 1) приводим исходную формулу к КНФ; 2) если в элементарную дизъюнкцию некоторая переменная входит со своим отрицанием, то удаляем эту конъюнкцию из КНФ; 3) если в элементарную дизъюнкцию некоторая переменная входит несколько раз, то удаляем эти переменные кроме одной; 4) если в некоторую элементарную дизъюнкцию некоторая переменная или переменные не входят, то заменяем её на эквивалентную форму, добавляя к ней одну или несколько переменных в виде и, применяя закон дистрибутивности, приводим формулу к КНФ; 5) если в полученной КНФ имеется несколько одинаковых элементарных конъюнкций, то оставляем только одну из них. В результате получаем СКНФ. Пример: Пусть дана КНФ функции . Найти СКНФ функции.
- СКНФ. В алгебре высказываний существуют алгоритмы для формул, с помощью которых можно сказать, является ли формула тождественно истинной, тождественно ложной или выполнимой. Рассмотрим следующие алгоритмы: 1) Для определения типа формулы надо построить ДНФ (КНФ) и проверить критерий ложности (критерий истинности). Если критерий выполнен, то формула тождественно ложна (тождественно истинна), если нет, то строим КНФ (ДНФ) и проверяем критерий истинности (критерий ложности), если критерий выполнен, то формула тождественно истинна (тождественно ложна) в противном случае, формула только выполнима. 2) Для определения типа формулы надо построить СДНФ или СКНФ. Если СДНФ построена, то формула не является тождественно ложной. Далее считаем число слагаемых в СДНФ: если их ,где n - число переменных, от которых зависит формула, то формула тождественно истинна, в противном случае выполнима. Если СКНФ построена, то формула не тождественно истинна. Если число слагаемых в СКНФ равно , где n - число переменных, то формула тождественно ложна, в противном случае формула выполнима.
III. БУЛЕВЫ ФУНКЦИИ.
Популярное: Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1938)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |