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

Определение 1. Элементарной конъюнкцией n переменных называется конъюнкция переменных или их отрицаний.

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

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

1. все элементарные конъюнкции, входящие в ДНФ, содержат все переменные;

2. все элементарные конъюнкции, входящие в ДНФ, различны;

3. каждая элементарная конъюнкции, входящая в ДНФ, содержит переменную один раз;

4. ни одна элементарная конъюнкции, входящая в ДНФ, не содержит переменную и ее отрицание.

СДНФ можно получить двумя способами: а) с помощью таблицы истинности; б) с помощью равносильных преобразований.

ПОСТРОЕНИЕ СДНФ ПО ТАБЛИЦЕ ИСТИННОСТИ Алгоритм:

1. Отметить те строки таблицы истинности, в последнем столбце которых стоят 1.

2. Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, то ее отрицание.

3. Все полученные конъюнкции связать в дизъюнкцию

4. Упростить логическое выражение.

 

б) По заданной таблице истинности построить СДНФ и упростить ее.

Решение 1 б.

X1	X2	X3	F

1. Выбираем строки, в которых F=1.

2. Строим для них конъюнкции:

1 строка 2 строка 3 строка

3. Объединяем конъюнкции дизъюнкцией.

4. Упрощаем логическое выражение.

ПРИМЕР2. Составьте СКНФ и СДНФ по таблице истинности

									А

 

ПРИМЕР 3. Для формулы найти СДНФ и СКНФ, каждую двумя способами.

I способ получения СДНФ:

II способ получения СДНФ А: составим таблицу истинности для формулы .

а	в	с	вс	ав		А

Тогда

Задание 1. По таблице истинности найдите формулу, определяющую функцию F(x,y,z), и

придайте ей более простой вид:

x	y	z	F(x,y,z)

Решение.

Задание 2. Приведите к КНФ и ДНФ формулу: B проверьте результат при помощи таблицы истинности.