Главная   Онлайн инструменты по математической логике   Мат. логика теория   Как считает компьютер?   Схемы для ЭВМ    

Совершенные нормальные формы

Определение булевой функции
Элементарные булевы функции
Задание булевых функций посредством элементарных
Существенные и несущественные переменные
Эквивалентные функции
Основные эквивалентности
Функциональная полнота
Нормальные формы
Совершенные нормальные формы
Минимизация ДНФ методом Квайна
Карты Карно
Полином Жегалкина
Высказывания
Предикаты
Кванторы
Определение формальной теории
Исчисление высказываний
Теорема о дедукции. Полнота ИВ
Автоматическое доказательство теорем
Метод резолюций в ИВ
Определение алгоритма
Машина Тьюринга
Рекурсивные функции
Алгоритмически неразрешимые задачи
Алгоритмы и их сложности



     Если в каждом члене нормальной формы представлены все переменные (либо сами, либо их отрицания), причем в каждом отдельном конъюнкте или дизъюнкте любая переменная входит ровно один раз (либо сама, либо ее отрицание), то эта форма называется совершенной нормальной формой (СДНФ или СКНФ).
     Примеры: Пусть задана функция трех переменных f(X,Y,Z).
     1. ¬XYZ v X¬Y¬Z v ¬X¬Y¬Z - это совершенная ДНФ.
     2. (XvYvZ)(Xv¬YvZ)(¬Xv¬YvZ) - это совершенная КНФ.
     3. (XvY)(XvZ) - это не совершенная КНФ, т.к. например, в первую сумму не входит переменная Z.
     4. XYZ - это совершенная ДНФ.
     Теорема
     1. Любая булева функция, не являющаяся тождественным нулем, имеет только одну СДНФ, с точностью до расположения членов.
     2. Любая булева функция, не являющаяся тождественной 1, имеет только одну СКНФ, с точностью до расположения членов.
     Доказательство теоремы проведем конструктивно, как решение следующей задачи: по данной таблице истинности построить СДНФ.
     Решение рассмотрим на примере функции f(X,Y,Z) заданной таблично при n=3.
     Пример. По данной таблице истинности построить СДНФ.
     Решение.

XYZОсновные конъюнкцииf(X,Y,Z)
000¬X¬Y¬Z0
001¬X¬YZ1
010¬XY¬Z1
011¬XYZ0
100X¬Y¬Z0
101X¬YZ1
110XY¬Z1
111XYZ1

     Основные конъюнкции (или конституенты_1), включенные в таблицу, соответствуют конкретному набору нулей и единиц, которые принимают переменные X,Y,Z. Строятся конституенты_1 по следующему правилу: переменная входит в произведение сама, если на данном наборе она принимает значение 1, в противном случае в произведение входит ее отрицание. Так, например, на наборе (0,0,1) переменные X,Y принимают значение 0 и поэтому в произведение входят их отрицания, а переменная Z принимает значение 1 и поэтому входит в произведение сама. Для данного набора (0,0,1) конституента_1 равна ¬X¬YZ.
     Очевидно, что конъюнкция ¬X¬Y¬Z равна 1 только на наборе (0,0,0), а ¬X¬YZ равна 1 на наборе (0,0,1) и т.д. (см. по таблице). Далее, заметим, что дизъюнкция двух основных конъюнкций равна 1 ровно на двух наборах, которые соответствуют данным основным конъюнкциям. Например, функция ¬X¬Y¬Z v ¬X¬YZ равна 1 только на двух наборах – (0,0,0) и (0,0,1), а на всех других наборах она равна 0. Аналогично, дизъюнкция трех основных конъюнкций равна 1 ровно на трех наборах, которые соответствуют данным основным конъюнкциям и т.д.
     Т.е. получаем правило: для построения СДНФ следует выбрать строки, в которых функция равна 1, а затем взять дизъюнкцию соответствующих основных конъюнкций, получим искомую СДНФ. Так, для нашего примера, имеем
     ¬X¬YZ v ¬XY¬Z v X¬YZ v XY¬Z v XYZ
     Задача. По данной таблице истинности построить СКНФ.
     Конституента_0 для набора нулей и единиц (которые принимают переменные X,Y,Z) строится следующим образом: переменная входит в дизъюнкцию сама, если на данном наборе она принимает значение 0, в противном случае в произведение входит ее отрицание.
     Правило для построения СКНФ: следует выбрать строки, в которых функция равна 0, а затем взять конъюнкцию соответствующих конституент_0. В результате получится искомая СКНФ. Так для нашего примера, имеем:
     f=(XvYvZ)(Xv¬Yv¬Z)(¬XvYvZ)
     Замечание. Для построения совершенной КНФ функции f, достаточно построить совершенную ДНФ для функции ¬f , а затем использовать f=¬(¬f) и законы де Моргана.
     Построим СКНФ для нашего примера на основании замечания.
     1. Строим СДНФ для отрицания.
     ¬X¬Y¬Z v ¬XYZ v X¬Y¬Z
     2. Используем законы де Моргана
     f=¬(¬f)=¬(¬X¬Y¬Z v ¬XYZ v X¬Y¬Z)=¬(¬X¬Y¬Z)&¬(¬XYZ)&¬(X¬Y¬Z)=
     =(XvYvZ)(Xv¬Yv¬Z)(¬XvYvZ)
     Описанный способ нахождения СДНФ (и СКНФ) по таблице истинности бывает часто более трудоемким, чем следующий алгоритм.
     1. Для нахождения СДНФ данную формулу приводим сначала к ДНФ.
     2. Если в некоторый конъюнкт К (т.е. К это произведение некоторого числа переменных или их отрицаний) не входит скажем переменная Y, то этот конъюнкт заменяем на эквивалентную формулу K&(Yv¬Y) и, применяя закон дистрибутивности, приводим полученную формулу к ДНФ; если недостающих переменных несколько, то для каждой из них к конъюнкту добавляем соответствующую формулу вида (Yv¬Y).
     3. Если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них. В результате получается СДНФ.
     Замечание: Для построения СКНФ в дизъюнкт не содержащий скажем переменную Y добавляем формулу вида Y¬Y, т.е. этот дизъюнкт заменяем на эквивалентную формулу D v Y¬Y и, применяя 2-й закон дистрибутивности.
     Пример. Построить СДНФ для функции f при помощи эквивалентных преобразований.
     f=XvYZ=X(Yv¬Y)(Zv¬Z)vYZ(Xv¬X)=XYZvXY¬ZvX¬YZvX¬Y¬ZvYZXvYZ¬X=
     =XYZvXY¬ZvX¬YZvX¬Y¬ZvYZ¬X

@ 2010 - 2016 tablica-istinnosti.ru Рейтинг@Mail.ru