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

Правила построения СДНФ:

1) проанализировать ф-цию:

а) определить кол-во переменных;

б) определить вид ф-ции (если ф-ция задана таблицей начений то перейти к построению, а если формулой, то получить таблицу значений ф-ции, выполняя операции по действиям);

2) построить СДНФ:

а) в таблице значений выбрать только те наборы переменных, на которых ф-ция принимает значение равное 1 и записать конъюнкции инвертируя переменны со значениями 0 и оставлять без изменения переменные со значениями 1. Каждому набору соответствует конъюнкция все переменных, таким образом между таблицей значений и СДНФ устанавливается взаимооднозначноо соответствие.

Теорема:

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

Теорема:

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

Определение:

Длиной дизъюнктивной нормальной формулы ф-ции n переменных называют количество переменных, как букв в этой форме.

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

ДНФ, которая имеет минимальную длину называется минимальной ДНФ.

33. Эквивалентные преобразования. Доказательство.

Эквив-е преоб-я – преоб-я, использ-е эквивалентные соотн-я и правила замены. Эквив-е преобр-я явл-ся мощным ср-м доказ-ва эквивалентности формул.

1.Правило подстановки формулы F вместо переменной х. При подстановке ф-kf вместо пре-й х все вхождения пер-й х в исходное соотн-е д.б. одновременно заменены ф-й F. Правило применяется к эквивал-м соот-м для получения эк-х соот-й.

Правило замены подформул. Если какая-либо ф-ла F, описываюшая ф-ю f, содержит F1 в качестве подформулы, то замена F₁ на эквивал-ю F2 (F₁=F₂) не изменит ф-и f; полученная при такой замене ф-ла F’ эквив-на исходной F. Правило замены подформул позволяет, используя известные эквив-е соотн-я, получать ф-лы, эквив-е данной, в частности, упрощать формулы.

Соотношения:

(*= или )

Ассоциативность конъюнкции и дизъюнкции:

x₁*(x₂*x₃)=(x₁*x₂)*x₃=x₁*x₂*x₃

Коммутативность

x₁*x₂=x₂* x₁

Дистрибутивность К отн-но Д

x₁ (x₂ x₃)=x₁ x₂ x₁ x₃

Дистрибутивность К отн-но Д

x₁ (x₂ x₃)=(x₁ x₂) (x₁ x₃)

Идемпотентность

x*x=x

Закон 2-го отрицания

=х

Св-ва констант 0 и 1

х 1=х; х 0=0; х 1=1; х 0=х; =1; =0

Правило Де Моргана

= ; =

Закон противоречия

х =0

Закон исключенного третьего

х =1

Поглощение

х х у=х; х (х у)=х

Склеивание

х у х =х

Обощенное склеивание

x z y x y=x z y

x y=x y