Задачи для самостоятельного решения. Задача 1. Преобразовать в СДНФ булеву функцию, заданную формулой

Задача 1. Преобразовать в СДНФ булеву функцию, заданную формулой

а) f=( ® у)(zÅ );

б) f= ;

в) f=( ®z)V(y® ).

Задача 2. По таблице истинности получить СДНФ булевой функции

а) f=(x ® )(z® );

б) f= .

 

§ 2. Совершенная конъюнктивная нормальная форма (СКНФ)

Существует и другая нормальная форма (конъюнктивная).

Выражение (отрицание на любых местах) называется элементарной дизъюнкцией (ЭД).

Конъюнкция нескольких ЭД называется конъюнктивной нормальной формой (КНФ).

Если к тому же все ЭД правильны и полны, то КНФ называется совершенной (СКНФ).

Рассмотрим способ получения СКНФ с помощью СДНФ.

Пусть дана булева функция f(x₁…x_n). Двойственной булевой функцией называется булева функция f*, заданная формулой

f*(x₁…x_n)=

Заметим, что (f*)*=f.

Например, для f=x V y двойственной является f* = = xy.

Таким образом, двойственной к дизъюнкции является конъюнкция и наоборот.

Теорема (закон двойственности). Двойственная к композиции булевых функций есть соответствующая композиция двойственных булевых функций (композиция булевых функций – сложная функция, составленная из нескольких булевых функций).

Следствие 1. Если в формуле присутствует только дизъюнкция, конъюнкция и отрицания, то для получения достаточно заменить дизъюнкцию конъюнкцией и наоборот.

Следствие 2. Двойственной к СДНФ является СКНФ.

Из следствия 2 вытекает практический алгоритм преобразования данной формулы в СКНФ, используя двойственность:

1) найти f*;

2) преобразовать f* в СДНФ;

3) еще раз взять двойственную. (f*)*=f= СДНФ*=СКНФ.

Аналогично тому, как с помощью таблицы истинности была получена СДНФ, можно получить СКНФ. Для этого в последнем столбце таблицы выбираем нули, а в исходных наборах 0 заменим переменной, 1 – отрицанием переменной.

 

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

 

Задача 1. Найти двойственную функцию f* к функции f=x ®(y «). f*= x Ú(.

Заметим, что двойственная функция к дизъюнкции является конъюнкцией с сохранением переменных и их отрицаний, и наоборот.

Задача 2. f= . Найти f*.

Решение. f*=(x Ú )= .

Задача 3. Преобразовать СКНФ булеву функцию, заданную формулой (х Þ у)(z + x).

Решение. Действуем по алгоритму:

1. Находим f* =(х Þ у)(z + x)=( f*=

2. Преобразуем ее в СДНФ:

3. Еще раз возьмем двойственную:

f=( .

Получили СКНФ, задача решена.

Найдем СКНФ данной функции с помощью таблицы истинности

х	у	z	x ® y	z ®	(x ® y)(z ® )

В последнем столбце таблицы выберем нули. На исходных наборах 0 соответствует переменной, а 1 ее отрицанию, тогда СКНФ:

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задача 1. Преобразовать в СКНФ булеву функцию, заданную формулой

а) f=( ) (z® );

б) f= ;

в) f=( ) ®(z ).

Задача 2. По таблице истинности получить СКНФ заданной булевой функции

а) f=(x ) ®(z®t);

б) ®(x ).

 

Многочлены Жегалкина

 

Мы уже заметили, что конъюнкция совпадает с обычным арифметическим умножением, попробуем ввести сложение: 0+0=0; 0+1-1; 1+0=1; 1+1=? Если принять 1+1=1, то получим дизъюнкцию. Если принять 1+1=0, то получим исключающее или. Принимаем второе соотношение: х+у=хÅу. Такое сложение совпадает с известным в теории чисел сложением по модулю 2. Заметим, что всегда хÅх=0.

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

Многочленом Жегалкина называют многочлен вида , где суммирование ведется по некоторому множеству различных наборов (i₁, i₂,…,i_k), в котором ни один индекс не повторяется.

Теорема. Всякая булева функция может быть представлена в виде многочлена Жегалкина и притом единственным образом.

Выразим три основные логические операции через сложение и умножение, превратив их в многочлены Жегалкина.

Конъюнкция хÙу=ху уже готовый многочлен Жегалкина. Отрицание =хÅ1. Дизъюнкция

=(xÅ1)(yÅ1)+1= xy Å x Å y Å1Å1= xy Å x Å y.

 

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 1. Преобразовать многочлен Жегалкина в булеву функцию, заданную формулой (хÞу)(z+х).

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

(хÞу)(z+х)= )(z+x)=((x+1)Úy)(z+x)=((x+1)y+x+1+y)(z+x)= =(xy+y+x+1+y)(z+x)=(xy+x+1)(z+x)=xyz+xyx+xz+xx+z+x=xyz+xy+xz++x+z+x=xyz+xy+xz+z.