Булевы функции

Московский государственный технический университет 
имени Н. Э. Баумана 
 
 
 
 
 
Булевы функции 
 
 
Методические указания по решению типовых задач 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1 

УДК 519.714.71 
ББК 22.17 
        Б90 
 
Издание доступно в электронном виде на портале ebooks.bmstu.ru 
по адресу: http://www.ebooks.bmstu.ru/catalog/199/book1337.html 
 
Факультет «Информатика и системы управления» 
Кафедра «Защита информации» 
Б90 
Рекомендовано Редакционно-издательским советом  
МГТУ им. Н.Э. Баумана в качестве методических указаний 
 
Авторы: 
Н.Е. Богомолова, Е.В. Вайц,  
Ю.В. Грачёва, А.И. Добрыченко 
 
Булевы функции : методические указания по решению типовых 
задач / [Н. Е. Богомолова и др.].  — Москва : Издательство МГТУ  
им. Н. Э. Баумана, 2015. — 56, [4] с.  
 
ISBN 978-5-7038-4288-1 
 
Рассмотрены следующие разделы теории булевых функций: булев 
куб, способы задания булевых функций, дизъюнктивные и конъюнктивные нормальные формы, тупиковые формы, минимизация булевых функций, полином Жегалкина, критерий Поста. Представлены варианты типовых задач, даны указания по их выполнению. 
Для студентов 1-го курса МГТУ им. Н. Э. Баумана, изучающих математические основы теории информационных систем. 
 
УДК 519.714.71 
 ББК 22.17 
 
 
 
 
 
 
 
 МГТУ им. Н.Э. Баумана, 2015 
 Оформление. Издательство  
ISBN 978-5-7038-4288-1                             
 
      МГТУ им. Н.Э. Баумана, 2015 
 
2 

Предисловие 
Курс «Математические основы теории информационных систем» является базовым для ряда учебных дисциплин, преподаваемых на кафедре «Защита информации», таких как «Информационные сети», «Математическая логика и теория алгоритмов», 
«Информатика», «Электроника и схемотехника». Данный курс читается в первом семестре, поэтому его материал опирается только 
на довузовскую подготовку студентов.  
Одним из основных разделов курса «Математические основы 
теории информационных систем» является раздел «Булевы функции». Для закрепления полученных студентами знаний, оказания 
помощи в подготовке к рубежному контролю и зачету и при выполнении домашних заданий в методических указаниях приведены 
типовые задачи раздела «Булевы функции» с подробным и наглядным описанием их решения, а также краткие теоретические сведения по каждой теме раздела.  
Методические указания адресованы студентам 1-го курса 
МГТУ им. Н.Э. Баумана, изучающим математические основы теории информационных систем. 
 
3 

1. ПОНЯТИЕ БУЛЕВОЙ ФУНКЦИИ.  
БУЛЕВ КУБ. РАЗВЕРТКИ БУЛЕВА КУБА 
Булева функция (от n переменных) — это произвольное отображение вида 
 




: 0, 1
0, 1 ,
n
f

 
т. е. булева функция определена на множестве всех n-элементных 
(при 
0
n 
) последовательностей нулей и единиц и принимает два 
возможных значения: 0 или 1 [1]. 
Булево переменное — это переменное с областью значений 
{0,1
},  т. е. переменное, которое может принимать только два значения: 0 или 1.  
Булеву функцию можно записать в виде
1
(
, ...,
),
n
y
f x
x

 где 
каждое булево переменное 
____
,
1, ,
i
x i
n

 и функция f принимают два 
возможных значения: 0 и 1. Фиксируя значение 


0, 1
i
a 
каждого 
переменного 
,
i
x  получаем кортеж 


1, ...,
n
а
a
a


 из множества 


0, 1
,
n  называемый набором значений переменных 
1, ...,
,
n
x
x
 и 
соответствующее ему значение функции 
1
(
, ...,
).
n
f a
a
 
Областью определения любой булевой функции от n переменных является множество {0, 1} ,
n  т. е. булев куб размерностью n. 
Число всех элементов булева куба равно 2 .
n  Элементы булева куба называют его вершинами. Стоит отметить, что соседними вершинами в булевом кубе являются соседние наборы булевой функции, отличающиеся только в одном разряде. 
Рассмотрим геометрические представления булевой функции. 
Геометрическое представление области определения булевой 
функции от одной переменной приведено на рис. 1.1, а. Отметим, 
что здесь 
1.
x
x


 Данное утверждение в теории булевых функций называется законом склеивания. 
4 

Геометрическое представление области определения булевой функции от 
двух переменных показано на рис. 1.1, б. 
Все вершины булева куба, представляющие собой наборы булевой функции, 
обозначены здесь тремя способами  
(в 
десятичной 
системе 
счисления,  
в двоичной системе счисления и через  
переменные x  и 
),
y  а все ребра показаны как результат склеивания двух вер- 
шин. Например, вершины y x  и y x   
склеиваются в ребро 
,
y  т. е. y x
yx

 
Рис. 1.1 
(
)
.
y x
x
y



 Отметим, что склеить в 
ребро можно только соседние вершины 
булева куба, которые отличаются только в одном разряде. 
Геометрическое представление области определения булевой 
функции от трех переменных приведено на рис. 1.2, а.  
Рис. 1.2 
 
Все вершины булева куба можно обозначить тремя способами: 
В десятичной системе  
счисления ........................... 
 0 
    1        2 
     3 
   4      5 
  6     7 
В двоичной системе  
счисления ........................... 
 000    001    010     011    100    101     110 
   111 
Через переменные  
x, y, z ................................... 
 z y x  z yx  z yx   z yx   z yx  z y x  z yx   z yx  
5 

Ребра и грани булева куба, приведенного на рис. 1.2, а, имеют 
следующие обозначения: 
Ребро ................ 
 0–1  0–2  1–3   2–3  1–5  3–7  2–6   0–4   4–5  4–6  5–7   6–7 
Обозначение .... 
 z y   z x   z x    z y   yx   yx   yx    y x   z y    z x   zx   z y  
 
Грань ................ 
 0–1–3–2  4–5–7–6   2–3–7–6  1–3–7–5   0–4–5–1   0–4–6–2 
Обозначение .... 
  
z    
 z   
    y  
 
 
 x   
   y   
 
x  
Представление булева куба на плоскости называется его разверткой. Строят развертки для булевых кубов с размерностью 
3.
n 
 Основной целью их построения является наглядное представление соседних наборов булевой функции на плоскости для последующего 
применения закона склеивания и минимизации функции. 
На рис. 1.2, б приведена развертка булева куба, изображенного 
на рис. 1.2, а. «Разрыв» выполнен по ребрам, соединяющим вершины 0, 1 и 4, 5 (обозначены на рис. 1.2, а значком «»).  
Геометрическое представление области определения булевой 
функции от четырех переменных показано на рис. 1.3, а, а на  
рис. 1.3, б построена соответствующая развертка. «Разрыв» выполнен по ребрам 0–2, 4–6, 8–10, 12–14, 2–10, 3–11, 0–8, 1–9, которые обозначены значком «».  
Рис. 1.3 (Начало) 
6