2.2.2. Реализация булевых функций в виде сднф и скнф.

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

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

Введем обозначение:

Теорема (о реализации функции в виде СДНФ). Если , то она может быть реализована формулой

. (*)

Формулу (*) называют совершенной дизъюнктивной нормальной формой или, сокращенно, СДНФ.

Согласно (*), чтобы записать СДНФ функции, нужно действовать так:

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

2) для каждого такого набора записать конъюнкцию, в которую войдут все переменные, причем, если значение переменной на данном наборе равно 0, то она войдет в конъюнкцию со знаком отрицания, а если – 1, то без знака отрицания;

3) записать дизъюнкцию всех выписанных в п. 2 конъюнкций.

Упражнение 2.20. Реализовать функции в виде СДНФ:

а) ; б) ; в) ; г) ; д) .

◄ а) – в) Зададим функции таблично и выпишем для них СДНФ.

0	0	1	1	1
0	1	1	1	0
1	0	0	1	0
1	1	1	0	0

;

;

.

г) Таблица истинности функции приведена в упражнении 2.18 б. Запишем СДНФ: .

д) решите самостоятельно. ►

Рассмотрим еще один способ реализации функции формулой.

Теорема (о реализации функции в виде СКНФ). Если , то она может быть реализована формулой

. (**)

Формулу (**), называют совершенной конъюнктивной нормальной формой или, сокращенно, СКНФ.

Согласно (**), чтобы записать СКНФ функции, нужно действовать так:

1) выбрать в ее таблице истинности все наборы значений переменных, на которых функция равна 0;

2) для каждого такого набора записать дизъюнкцию, в которую войдут все переменные, причем, если значение переменной на данном наборе равно 1, то она войдет в дизъюнкцию со знаком отрицания, а если – 1, то без знака отрицания;

3) записать конъюнкцию всех выписанных в п. 2 дизъюнкций.

Упражнение 2.21. Реализовать функции в виде СКНФ:

а) ; б) ; в) ; г) ; д) .

◄ а) – г) Опираясь на таблицы истинности функций (они приведены в упражнениях 20 и 18), запишем:

а) ;

б) ;

в) ;

г) .

д) решите самостоятельно. ►