Лекции по дискретной математике

Введение в схемы, автоматы и алгоритмы

2-е издание, исправленное

Дехтярь М.И.

Национальный Открытый Университет “ИНТУИТ”
2016

2

УДК 51”735”(076.6)
ББК 10
Д39
Лекции по дискретной математике / Дехтярь М.И. - M.: Национальный Открытый Университет
“ИНТУИТ”, 2016 (Основы информационных технологий)
ISBN 978-5-94774-714-0

Краткий начальный курс по таким дискретным структурам как схемы, конечные автоматы и
алгоритмы.
Курс знакомит с двумя представлениями булевых функций с помощью специальных классов
ориентированных графов без циклов: логическими схемами (схемами из функциональных элементов)
и упорядоченными бинарными диаграммами решений (УБДР). Изложены основы теории конечных
автоматов: конечные автоматы-преобразователи и -распознаватели, детерминированные автоматы и
языки, недетерминированные автоматы и их детерминизация, регулярные выражения и языки, синтез
конечного автомата по регулярному выражению, замкнутость класса автоматных языков
относительно разных операций, теорема о разрастании для автоматных языков, примеры
неавтоматных языков. Дается краткое введение в теорию алгоритмов, сравниваются три формальных
модели описания алгоритмов: структурированные программы, частично рекурсивные функции и
машины Тьюринга, формулируется тезис Тьюринга-Черча и устанавливается алгоритмическая
неразрешимость ряда проблем, относящихся к свойствам структурированных программ. Решение
большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и
проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями,
позволяющими закрепить пройденный материал.

(c) ООО “ИНТУИТ.РУ”, 2007-2016
(c) Дехтярь М.И., 2007-2016

3

Предварительные сведения

Класс \mathcal{P}_n булевых функций от n переменных. Задание булевых функций с
помощью таблиц. Булевы функции от 1-ой и 2-х переменных. Булевы (логические)
формулы и их эквивалентность. Основные эквивалентности ( законы логики ).
Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Графы. Деревья.

Булевы функции от n переменных

Булевы функции1) названы в честь английского математика ХIХ века Дж. Буля,
который впервые применил алгебраические методы для решения логических задач.
Они образуют самый простой нетривиальный класс дискретных функций - их
аргументы и значения могут принимать всего два значения. С другой стороны, этот
класс достаточно богат и его функции имеют много интересных свойств. Булевы
функции находят применение в логике, электротехнике, многих разделах информатики.

Обозначим через 
 двухэлементное множество 
. Тогда 
 
это множество всех двоичных последовательностей (наборов, векторов) длины .
Булевой функцией от  переменных (аргументов) называется любая функция 

. Каждый из ее аргументов 
 может принимать

одно из двух значений 0 или 1 и значением функции на любом наборе из 
 также

может быть 0 или 1. Обозначим через 
 множество всех булевых функций от 

переменных. Нетрудно подсчитать их число: 
.

Имеется несколько различных способов представления и интерпретации булевых
функций. В этом разделе мы рассмотрим табличное представление, а также
представление с помощью логических формул. В лекциях 2 и 3 будет рассмотрено еще
два способа представления булевых функций: логические схемы и упорядоченные
бинарные диаграммы решений.

Табличное представление

Булевы функции от небольшого числа аргументов удобно представлять с помощью
таблиц. Таблица для функции 
 имеет 
 столбец. В первых  столбцах

указываются значения аргументов 
, а в 
 -ом столбце значение функции

на этих аргументах - 
.

Таблица 1.1. Табличное

представление функции 

   .  .  .   
    

   .  .  .       

   .  .  .       

4

   .  .  .       

.  .  .  .  .  .

   .  .  .       

Наборы аргументов в строках обычно располагаются в лексикографическом порядке: 

 существует такое 
, что при 
, а 

. Если эти наборы рассматривать как записи чисел в двоичной системе счисления, то 1ая строка представляет число 0, 2-ая - 1, 3-я - 2, … , а последняя - 
.

При больших  табличное представление становится громоздким, например, для
функции от 10 переменных потребуется таблица с 1024 строками. Но для малых  оно
достаточно наглядно.

Булевы функции от 1-ой и 2-х переменных

Перечислим вначале все булевы функции от 1-ой переменной 
. Как мы знаем, их

всего четыре.

1. 
 - константа 0;

2. 
 - константа 1;

3. 
 - тождественная функция;

4. 
. Эта функция называется отрицанием 
 и обозначается 

(используется также обозначение 
, а в языках программирования эта функция

часто обозначается как 
 ).

В следующей таблице представлены наиболее используемые 12 (из 16) функций от 2-х
переменных.

Таблица 1.2. Булевы функции от 2-х

переменных

    

0  0

0  1

1  0

1  1

0

0

0

0

1

1

1

1

0

0

1

1

1

1

0

0

0

1

0

1

1

0

1

0

0

0

0

1

0

1

1

1

1

1

0

1

0

1

1

0

1

0

0

1

1

1

1

0

Многие из этих функций часто считаются “элементарными” и имеют собственные
обозначения.

5

 - константа 0;
 - константа 1;
 - функция, равная 1-му аргументу;

 - отрицание 
 ;

 - функция, равная 2-му аргументу;

 - отрицание 
 ;

 - конъюнкция, читается ” 
 и 
 ” (используются также

обозначения 
, 
, 
 и 
 AND 
 ));

 - дизъюнкция, читается ” 
 или 
 ” (используются также

обозначения 
, 
 и 
 OR 
 ));

 - импликация, читается ” 
 влечет 
 ” или “из 
 следует 

 ” (используются также обозначения 
, и ( IF 
 THEN 
 ));

 - сложение по модулю 2, читается ” 
 плюс 
 ”

(используется также обозначение 
 );

 - эквивалентность, читается ” 
 эквивалентно

(равносильно) 
 ” (используется также обозначение 
 );

 - штрих Шеффера (антиконъюнкция), иногда читается как “не 

 и 
 “.

В качестве элементарных функций будем также рассматривать 0-местные функцииконстанты 0 и 1.

Отметим, что функции 
 и 
 фактически не зависят от значений обоих

аргументов, функции 
 и 
 не зависят от значений аргумента 
, а

функции 
 и 
 не зависят от значений аргумента 
.

Определение 1.1. Функция 
 не зависит от аргумента 
, если для

любого набора значений 
 остальных аргументов  имеет место

равенство

Такой аргумент 
 называется фиктивным. Аргументы, не являющиеся фиктивными,

называются существенными.

Функции 
 и 
 называются равными, если функцию 
 можно

получить из функции 
 путем добавления и удаления фиктивных аргументов.

Например, равными являются одноместная функция 
 и двухместная функция 

, так как вторая получается из первой добавлением фиктивного аргумента 
.

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

6

Формулы

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

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

логическими связками или логическими операциями. При этом для 2-местных функций
из этого списка будем использовать инфиксную запись, в которой имя логической
связки помещается между 1-ым и 2-ым аргументами.

Зафиксируем некоторое счетное множество переменных 
. Определим

по индукции множество формул над 
 с переменными из . Одновременно будем

определять числовую характеристику 
 формулы , называемую ее глубиной, и

множество ее подформул.

Определение 1.2. а) Базис индукции. 0, 1 и каждая переменная 
 является

формулой глубины 0, т.е. 
. Множество ее подформул

состоит из нее самой.

б) Шаг индукции. Пусть 
 и 
 - формулы, 
. Тогда выражения 

 и 
 являются формулами. При этом 
, а 

. Множество подформул  включает саму

формулу  и для 
 все подформулы формулы 
, а для 
 все

подформулы формул 
 и 
.

Каждой формуле 
 сопоставим булеву функцию, которую эта формула

задает, используя индукцию по глубине формулы.

Базис индукции. Пусть 
. Тогда 
 или 
 В первом случае 

задает функцию 
, во втором - функцию, тождественно равную константе .

Шаг индукции. Пусть  - произвольная формула глубины 
. Тогда 

 или 

для некоторой булевой связки 
. Так как 
,

то формулам 
 и 
 соответствующие функции 
 и 
 уже

сопоставлены. Тогда формула 
 задает функцию 
, а формула 

 задает функцию 

.

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

7

соответствующей подформулой.

Пример 1.1. Например, для формулы

функция 
 задается выделенным столбцом 
 следующей таблицы.

Таблица 1.3. Функция 

   
   
    
    
 
    
    
    
    
    
 

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

 0  0  0 1  0

 0  0  0 1  0

 0  1  1 0  1

 0  1  1 0  1

 1  1  0 1  0

 1  1  0 1  0

 1  1  1 0  1

 1  1  1 0  1

1

1

0

1

1

0

0

1

0  0  0  0  1  0

1  1  0  0  1  0

0  0  0  0  0  1

1  1  0  0  0  1

0  1  1  1  1  0

1  0  1  1  1  0

0  0  1  0  0  1

1  1  1  0  0  1

Каждая строка этой таблицы задает процесс вычисления функции 
 на

соответствующих аргументах изнутри-наружу: вместо каждого вхождения переменной
в формулу подставляется ее значение, затем в полученной формуле, состоящей из
констант и булевых связок, последовательно вычисляются значения самых внутренних
функций ( подформул ), для которых уже определены значения их аргументов, до тех
пор, пока не будет получено значение всей формулы.

Эквивалентность булевых формул

Определение 1.3. Булевы формулы  и 
 называются эквивалентными, если

соответствующие им функции 
 и 
 равны.

Обозначение: 
. Эквивалентные формулы называют также тождественно

равными, а выражения вида 
 логическими тождествами.

Таким образом, эквивалентные формулы являются различными заданиями одной и той
же булевой функции. Ниже мы приводим ряд пар эквивалентных формул (тождеств),
отражающих существенные свойства логических операций и важные соотношения
между различными операциями. Они часто позволяют находить для булевых функций
по одним задающим их формулам более простые формулы. Большинство из

8

приводимых тождеств имеют собственные имена. Часто их называют законами логики.

Пусть  - это одна из функций 
. Для этих трех функций выполнены следующие

две эквивалентности (законы ассоциативности и коммутативности).

(1) Ассоциативность:

(2) Коммутативность:

(3) Дистрибутивные законы:

(4) Двойное отрицание:

(5) Законы де Моргана (внесение отрицания внутрь скобок):

(6) Законы упрощения:

Некоторые законы упрощения имеют собственные названия: эквивалентности в
первой строке называются законами идемпотентности, 
 - это закон

противоречия, 
 - это закон исключенного третьего.Следующие две

эквивалентности позволяют выразить импликацию и сложение по модулю 2 через
дизъюнкцию, конъюкцию и отрицание.

(7)

(8)

Правильность этих эквивалентностей легко устанавливается прямым вычислением
функций для их левых и правых частей.

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

9

 мы будем для упрощения писать 
. Аналогично, будем

использовать выражения 
 и 
 для сокращения формул,

состоящих из одних дизъюнкций или одних сложений по модулю 2, соответственно.
Будем также опускать внешние скобки в записи формулы, если ее внешней функцией
является одна из функций 
.

Таким образом, с использованием этих соглашений формула 

 может быть записана как 

.

Дизъюнктивные и конъюнктивные нормальные формы

Имеется ряд специальных подклассов формул, позволяющих задавать все булевы
функции. В этом разделе мы определим два таких подкласса функций, использующих
только операции 
 и 
.

Пусть 
 - это множество пропозициональных переменных. Введем для

каждого 
 обозначения: 
 и 
. Формула 

( 
 ), в которой 
 и все переменные разные, т.е. 

при 
, называется элементарной конъюнкцией (элементарной дизъюнкцией).

Определение 1.4.Формула 
 называется дизъюнктивной нормальной формой (ДНФ),

если она является дизъюнкцией элементарных конъюнкций, т.е. имеет вид 

, где каждая формула 
 - это элементарная

конъюнкция. 
 называется совершенной ДНФ, если в каждую из ее конъюнкций 

входят все  переменных из 
. Аналогично, формула  называется конъюнктивной

нормальной формой (КНФ), если она является конъюнкцией элементарных дизъюнкций,
т.е. 
, где каждая формула 
 - это элементарная

дизъюнкция. Она является совершенной КНФ, если в каждую 
 входят все 

переменных из 
.

Рассмотрим произвольную булеву функцию
, зависящую от переменных из

. Oбозначим через 
 множество наборов значений переменных, на которых 

принимает значение 1, а через 
 множество наборов, на которых  принимает

значение 0, т.е. 
 и 

. Определим по этим множествам две формулы:

и

10