Тема: Полнота систем булевых функций
Цели работы:
1) научиться проверять принадлежность булевых функций замкнутым классам;
2) научиться проверять системы булевых функций на полноту.
Пояснения:
Определение 1: Систему функций {f1,f2,…fm} алгебры логики называют функционально полной, если любую функцию алгебры можно записать с помощью суперпозиции некоторого набора булевых функций f1,f2,…fm.
Определение 2: Класс функций R называется функционально замкнутым, если любая суперпозиция функций этого класса R принадлежит этому классу.
Важнейшие замкнутые классы:
- Класс функций, сохраняющих константу 0 (T0)
Так называют функции, для которых выполняется f(0, 0, … 0) = 0
T0 = {f | f(0, 0, … 0) = 0}
- Класс функций, сохраняющих константу 1 (T1)
Так называют функции, для которых выполняется f(1, 1, … 1) = 1
T1 = {f | f(1, 1, … 1) = 1}
- Класс самодвойственных функций (S)
Функция f(x1, … xn), удовлетворяющая условию f*(x1, … xn) = называется двойственной по отношению к функции f(x1, …xn). Функция f(x1, … xn) называется самодвойственной, если f(x1, … xn) = f*(x1, … x).
|
|
S = {f | f(x1, … xn) = }
- Класс линейных функций (L)
Функция алгебры логики вида f(x1, … xn) называют линейной, если её полином Жегалкина имеет вид многочлена первой степени.
L = {f | f(x1, x2, … xn) = k0 k1x1 … knxn}
- Класс монотонных функций (M)
Функция f(x1, … xn) называется монотонной, если для любых двух элементов сравнимых между собой, из () < () следует, что f() < f().
M = {f | () < () f() < f()}
Теорема Поста: Для того, чтобы система булевых функций {f1,f2,…fm} была полной, необходимо и достаточно, чтобы для каждого из классов T0, T1, S, L, M нашлась функция fi, не принадлежащая этому классу.
Оборудование, аппаратура, материалы и их характеристики: персональные компьютеры с лицензионным программным обеспечением; доска, маркеры; рабочие тетради; раздаточный материал.
Порядок выполнения работы:
Студенты получают задания по вариантам. Метод решения выбирается студентами самостоятельно и зависит от приобретенных в процессе обучения навыков. В процессе выполнения практической работы преподаватель проводит как групповые, так и индивидуальные консультации по вопросам дополнительного разъяснения отдельных понятий и аспектов изученных тем, задания и оформления отчета.
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 с.