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

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

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

Поглощение

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

Склеивание

хух=х

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

xzyxy=xzy

xy=xy

34. Правила подстановки, замены.

Эквивалентные преобразования можно использовать для подстановки вместо переменных логических ф-ций. При подстановке ф-ции F вместо переменной х все вхождения переменной х должны быть заменены ф-лой F одновременно.

Например:

(xy)x

x=z|p

((z|p) y) ( z|p)

При этом справедливо, что FF=1

Fx – недопустимо!!!

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

(x₁x₂)x₁=(x₁x₂)x₁=x₁x₁x₁x₂=x₁x₂