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

Совершенная дизъюнктивная нормальная форма.

Операции над множествами. | Основные свойства операций над множествами. | Алгебра высказываний. | Отрицание. | Конъюнкция. | Дизъюнкция. | Эквиваленция | Т.е. импликация ложна тогда и только тогда, когда a – истина, а b – ложь. | Формулы алгебры высказываний. | Формулы алгебры высказываний. |


Читайте также:
  1. ГЛАВА LXVII. РАДОСТЬ СОВЕРШЕННАЯ
  2. Гомосексуальность. Нормальная разновидность человеческой сексуальности
  3. Денежная реформа.
  4. Дизъюнктивная и конъюнктивной нормальная формы
  5. Динамика тиреоидных гормонов: нормальная физиология
  6. Исходное положение: схема ПС 35 кВ “Тупичев” – нормальная
  7. Коллежская реформа. Идеи камерализма

Как уже отмечалось, система операций булевой алг ебры функционально полна, это означает, что для любой логической формулы переход к булевской формуле всегда возможен..

Пусть зафиксирован набор булевых переменных x1, x2,..., xn.

Определение 1. Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза. Если число переменных равно n, то такая элементарная конъюнкция называется полной.

В примере 1 - полные элементарные конъюнкции.

Определение 2. Дизъюнкция полных элементарных конъюнкций называется совершенной дизъюнктивной нормальной формой (СДНФ).

Теорема. Любая булева формула может быть представлена и притом единственным образом в виде СДНФ.

Приведение формулы к СДНФ.

Способ перехода от табличного задания к булевой формуле: для каждого набора переменных x1, x2,... xn, для которого функция f(x1, x2,... xn) равна 1, выписывается конъюнкция всех переменных: над теми переменными, которые на этом наборе равны 0, ставятся отрицания; все такие конъюнкции соединяются знаком дизъюнкции.

Полученная таким образом формула является совершенной дизъюнктивной нормальной формой (СДНФ) логической функции f(x1, x2,..., xn).

СДНФ из таблицы примера 1 предыдущего параграфа имеет вид

(Для удобства восприятия символ конъюнкции представлен в виде ∙).

Пример 1 0 0 1

0 1 1

1 0 0

1 0 0

П р и ме р 2. f(x1, x2) ≡ x1 ~ x2 x1 x2 x1 ~ x2 f(x) ≡

0 0 1

0 1 0

1 0 0

1 1 1


Дата добавления: 2015-07-20; просмотров: 56 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Равносильность формул.| Совершенная конъюнктивная нормальная форма.

mybiblioteka.su - 2015-2024 год. (0.005 сек.)