Исследование полноты множества булевых функций

Московский государственный технический университет
имени Н. Э. Баумана
М.С. Виноградова, С.Б. Ткачев
Иcследование полноты множества
булевых функций
Методические указания
к выполнению домашнего задания
«Булевы функции»

УДК 517.5
ББК 22.161.5
B49
Издание доступно в электронном виде на портале ebooks/bmstu.ru
по адресу: http://ebooks.bmstu.ru/catalog/122/book907.html
Факультет «Фундаментальные науки»
Кафедра «Математическое моделирование»
Рекомендовано Редакционно-издательским советом
МГТУ им. Н. Э. Баумана в качестве методических указаний
Рецензенты:
д-р физ.-мат. наук, профессор А. С. Фурсов,
канд. техн. наук, доцент С. И. Шишкина
Виноградова, М. С.
В49
Исследование полноты множества булевых функций : методические указания к выполнению домашнего задания «Булевы функции» /
М. С. Виноградова, С. Б. Ткачев. – Москва : Издательство МГТУ
им. Н. Э. Баумана, 2015. – 29, [3] с.
ISBN 978-5-7038-3830-3
Приведены краткие теоретические сведения о представлении булевых функций формулами и способах исследования полноты заданного множества.
Разобраны задачи расчета значений булевой
функции, заданной формулой, с использованием таблицы, а также проведено исследование полноты заданного множества булевых
функций. Подробно рассмотрены примеры решения задач на исследование полноты множества булевых функций трех переменных.
Для студентов 2-го и 3-го курсов факультетов «Информатика и
управление», «Специальное машиностроение» и «Фундаментальные науки» МГТУ им. Н. Э. Баумана.
УДК 517.5
ББК 22.161.5
c
⃝
МГТУ им. Н.Э. Баумана, 2015
c
⃝
Оформление. Издательство
МГТУ им. Н. Э. Баумана, 2015
ISBN 978-5-7038-3830-3

1. БУЛЕВЫ ФУНКЦИИ
1.1. Понятие булевой функции. Булев куб
Булева функция от n переменных (при n ⩾0) — это произвольное отображение f: {0, 1}n →{0, 1}. Область изменения каждого
переменного булевой функции есть множество {0, 1}, значениями
функции также являются элементы указанного множества. Булеву
функцию от n переменных x1, . . . , xn записывают в виде y =
= f(x1, ...,xn).
Областью определения любой булевой функции от n переменных
является множество {0, 1}n.
Это множество называют булевым
кубом размерности n и обозначают Bn.
Элементы булева куба
называют n-мерными булевыми векторами или наборами.
Число
всех элементов булева куба {0, 1}n составляет 2n.
На Bn можно задать отношение порядка: для двух произвольных
наборов e
α = (α1, ..., αn) и e
β = (β1, ..., βn) из Bn существует
e
α ⩽e
β тогда и только тогда, когда αi ⩽βi для каждого i = 1, n, т. е.
αi ∨βi = βi.
Введенное отношение называют булевым порядком.
Этот порядок является частичным, поскольку не все наборы попарно
сравнимы.
Например, в булевом кубе B3 (0, 0, 1) ⩽(1, 0, 1), поскольку
0 ⩽1, 0 ⩽0 и 1 ⩽1. Однако наборы (0, 1, 0) и (1, 0, 1) несравнимы,
так как, например, первая компонента второго набора (1) больше
первой компоненты первого набора (0), а вторая компонента первого
набора (1) больше второй компоненты второго набора (0).
Булев куб как упорядоченное множество можно изобразить в
виде диаграммы Хассе. На рисунке приведены диаграммы Хассе
для булевых кубов размерностей 0, 1, 2 и 3.
1.2. Таблицы булевых функций
Для задания функции f(x1,...,xn) от n переменных необходимо
указать значение функции на каждом из наборов значений перемен3

Диаграммы Хассе
ных. Поскольку каждое переменное может принимать только два
значения (0 и 1), имеется 2n попарно различных наборов.
Следовательно, булева функция от n переменных может быть
задана таблицей, состоящей из двух столбцов и 2n строк. В первом
столбце перечисляются все наборы из Bn, а во втором — значения
функции на соответствующих наборах.
В таблице используют
стандартное расположение наборов: каждый набор рассматривают
как запись натурального числа в двоичном исчислении и располагают
наборы в соответствии с естественным числовым порядком.
Поскольку на каждом наборе булева функция может принимать
только два значения (0 и 1), число булевых функций от n переменных
равно 22n.
Cуществует две булевы константы: 0 и 1. Их можно рассматривать как функции любого числа переменных.
Для функции одного переменного можно задать четыре булевы
функции (табл. 1.1).
Таблица 1.1
x
f1(x)
f2(x)
f3(x)
f4(x)
0
0
0
1
1
1
1
0
1
0
Функцию f1 называют тождественной функцией, а функцию
f4 — отрицанием.
Для записи отрицания как унарной операции
4