Дизъюнктивная совершенная нормальная форма (ДСНФ)

Любая таблично заданная ФАЛ f(x₁, x₂, …, x_n) (кроме тождественного нуля) может быть представлена в следующем аналитическом виде:

Представление ФАЛ в таком виде называется дизъюнктивной совершенной нормальной формой этой функции (ДСНФ).

Алгоритм перехода от табличного задания функции к ДСНФ

1. Выбрать в таблице все наборы аргументов, на которых функция обращается в единицу.

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

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

Конъюнктивная совершенная нормальная форма

Любая таблично заданная ФАЛ f(x₁, x₂, …, x_n) (кроме тождественной единицы) может быть представлена в следующем аналитическом виде:

Представление ФАЛ в таком виде называется конъюнктивной совершенной нормальной формой этой функции (КСНФ).

Алгоритм построения конъюнктивной
совершенной нормальной формы

1. Выбрать в таблице все наборы аргументов, на которых функция обращается в 0.

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

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

Например:

Построить ДСНФ и КСНФ для функции F(x,y,z).

Решение:

Для нахождения ДСНФ выбираем из таблицы №4 только те строки, в которых стоят наборы значений аргументов, обращающие функцию в единицу. Это вторая, третья и пятая строки. Выпишем конъюнкции, соответствующие выбранным строкам:

.

Соединяя эти конъюнкции знаками дизъюнкции, получаем:

.

Для нахождения КСНФ выбираем из таблицы №4 только те строки, в которых стоят наборы значений аргументов, обращающие функцию в ноль. Выпишем соответствующие дизъюнкции и соединим их знаками конъюнкции.

Получим: .

Полные системы ФАЛ

Система ФАЛ {f₁, f₂,…, f_n} называется полной в некотором классе функций, если любая функция из этого класса может быть представлена суперпозицией этих функций.

Система ФАЛ, являющаяся полной в некотором классе функций, называется базисом.

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

Любая функция может быть представлена с помощью элементарных функций {, &, Ú}. Эта система ФАЛ образует универсальный базис.

Наиболее популярными в алгебре логики являются базисы{Ú,},{&,},{¯},{|}, которые являются минимальными.

Например:

Представить функцию в базисах
{Ú, Ø}, {|}. Для проверки результата составить таблицу истинности.

Решение:

Для перевода в базис {Ú, Ø} применим закон де Моргана к ДСНФ функции: .

Для перевода функции в базис {|} применим следующие соотношения к ДСНФ функции:

Обозначим

Выполним перевод в базис {|} по действиям.

1.

2.

3.

4.

Проверим преобразования с использованием таблицы истинности:

2 1 3 5 4 6

Таблица истинности для выражения :

№	x	y	z	y | y	x | (y | y)		z | z

Аналогично, проверяем и .

Для проверки, построим таблицу истинности для полученной формы функции F(x, y, z).

Таблица истинности для F(x,y,z)

№

x

y

z

A

B

C

A | B

Cтолбцы, соответствующие функции F(x, y, z) в таблицах истинности равны, следовательно, преобразования выполнены правильно.

Задание к лабораторной работе

1. По заданному варианту, составить таблицу истинности функции трех переменных F(x,y,z). Изобразить графически F(x,y,z) на кубе.

2. Построить ДСНФ и КСНФ.

3. Используя законы алгебры логики, пошагово преобразовать заданную функцию в ДНФ. Построить таблицу истинности.

4. Наиболее простую аналитическую форму перевести в базисы {Ø,Ú}, {Ø,&}, {|}, {¯} и сравнить с заданной функцией, построив таблицу истинности.

1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.

16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30.

Контрольные вопросы

1. Определение двоичного набора.

2. Определение булевой функции или функции алгебры логики (ФАЛ).

3. Область определения и область значений ФАЛ.

4. ФАЛ от одной переменной.

5. Элементарные ФАЛ от двух переменных.

6. Основные законы алгебры логики.

7. Полные системы функций, минимальный базис.

8. Аналитическое описание ФАЛ: дизъюнктивная и конъюнктивная нормальные формы.

Лабораторная работа № 4