Практическая работа № 5

Тема: Полнота систем булевых функций

Цели работы:

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

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

Пояснения:

Определение 1: Систему функций {f₁,f₂,…f_m} алгебры логики называют функционально полной, если любую функцию алгебры можно записать с помощью суперпозиции некоторого набора булевых функций f₁,f₂,…f_m.

Определение 2: Класс функций R называется функционально замкнутым, если любая суперпозиция функций этого класса R принадлежит этому классу.

Важнейшие замкнутые классы:

- Класс функций, сохраняющих константу 0 (T₀)

Так называют функции, для которых выполняется f(0, 0, … 0) = 0

T₀ = {f | f(0, 0, … 0) = 0}

- Класс функций, сохраняющих константу 1 (T₁)

Так называют функции, для которых выполняется f(1, 1, … 1) = 1

T₁ = {f | f(1, 1, … 1) = 1}

- Класс самодвойственных функций (S)

Функция f(x₁, … x_n), удовлетворяющая условию f*(x₁, … x_n) = называется двойственной по отношению к функции f(x₁, …x_n). Функция f(x₁, … x_n) называется самодвойственной, если f(x₁, … x_n) = f*(x₁, … x).

S = {f | f(x₁, … x_n) = }

- Класс линейных функций (L)

Функция алгебры логики вида f(x₁, … x_n) называют линейной, если её полином Жегалкина имеет вид многочлена первой степени.

L = {f | f(x₁, x₂, … x_n) = k₀ k₁x₁ … k_nx_n}

- Класс монотонных функций (M)

Функция f(x₁, … x_n) называется монотонной, если для любых двух элементов сравнимых между собой, из () < () следует, что f() < f().

M = {f | () < () f() < f()}

Теорема Поста: Для того, чтобы система булевых функций {f₁,f₂,…f_m} была полной, необходимо и достаточно, чтобы для каждого из классов T₀, T₁, S, L, M нашлась функция f_i, не принадлежащая этому классу.

Оборудование, аппаратура, материалы и их характеристики: персональные компьютеры с лицензионным программным обеспечением; доска, маркеры; рабочие тетради; раздаточный материал.

Порядок выполнения работы:

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

1. Докажите, что все следующие булевы функции линейны:

Таблица 1 – Задание № 1

№ варианта	Исходные данные

2. Докажите, что следующие булевы функции самодвойственны:

Таблица 2 – Задание № 2

№ варианта	Исходные данные

3. Докажите монотонность следующих булевых функций:

Таблица 3 – Задание № 3

№ варианта	Исходные данные

4. Докажите полноту или неполноту следующих систем булевых функций:

Таблица 4 – Задание № 4

№ варианта	Исходные данные
	{ }
	{ }
	{ }
	{ }
	{ }
	{ }
	{ }
	{ }
	{ }
	{ }

Требования к отчету: Отчет должен содержать:

- название практической работы;

- формулировку цели работы;

- краткие теоретические сведения по теме работы в виде таблиц, графиков, диаграмм, схем, рисунков и формул;

- результаты решения заданий;

- выводы по работе;

- краткие письменные ответы на контрольные вопросы.

Текст отчета набирается на компьютере. Допускается тип шрифта Times New Roman, размер 12 – 14, межстрочный 1,5 интервал, выравнивание текста по ширине странице, абзацный отступ 1,25.

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

1) Что такое замкнутый класс?

2) Какие функции сохраняют единицу?

3) Какие функции называются самодвойственными?

4) Какие наборы называются сравнимыми?

5) В чем суть теоремы Поста?

Учебная и специальная литература:

1) Спирина М.С., Спирин В.В. Дискретная математика: Учебник. – М.: Издательский центр «Академия», 2009. – 370 с.

2) Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для высш. учеб. заведений. – М.: Издательский центр «Академия», 2009. – 304 с.

3) Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВ – Петербург, 2008. – 352 с.