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

Система ФАЛ {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