Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Можно доказать, что для всякой булевой функции не равной тождественно нулю, существует единственная СДНФ.




 

Свойства СДНФ:

1. каждая конституента содержит все переменные, входящие в функцию

2. все конституенты различны;

3. ни одна конституента не содержит одновременно переменную и её отрицание;

4. ни одна конституента не содержит одну и ту же переменную дважды.

Эти свойства СДНФ называются свойствами совершенства.

 

Существует два способа получения СДНФ для булевой функции: с помощью таблицы истинности и с помощью равносильных преобразований.

Пример. Получим СДНФ для функции .

1. С помощью таблицы истинности.

Построим таблицу истинности функции. Выполним следующие действия:

- строки, в которых функция равна 1 (строки 3,4), единицу заменим обозначением функции f (x,y);

- строим конъюнкции для этих 2-х строк, соответственно из аргументов строки 3 и 4 по следующему правилу: если аргумент равен 1, то он входит в конъюнкцию без изменения, если равен 0, то входит с отрицанием, т.е. для 3-ей строки для 4-ой ;

- комбинации конъюнкций соединим знаками дизъюнкции. Для рассматриваемого примера получим СДНФ в виде

 

x y

 

 

2. С помощью равносильных преобразований.

Используя закон дистрибутивности и закон противоречия получим

= .

Фактически получили ДНФ функции, чтобы первая конъюнкция была полной, используем тождество . Тогда получим

что представляет СДНФ.

Если каждая элементарная конъюнкция формулы содержит символы всех переменных, то такая формула называется совершенной конъюнктивной нормальной формой (СКНФ). Каждое слагаемое (дизъюнкция) в СКНФ называется конституентойнуля.

Пример СКНФ:

.


mylektsii.ru - Мои Лекции - 2015-2018 год. (0.011 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал