Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Артикул: 826687.01.99
Доступ онлайн
1 000 ₽
В корзину
Краткий начальный курс по таким дискретным структурам как схемы, конечные автоматы и алгоритмы. Курс знакомит с двумя представлениями булевых функций с помощью специальных классов ориентированных графов без циклов: логическими схемами (схемами из функциональных элементов) и упорядоченными бинарными диаграммами решений (УБДР). Изложены основы теории конечных автоматов: конечные автоматы-преобразователи и -распознаватели, детерминированные автоматы и языки, недетерминированные автоматы и их детерминизация, регулярные выражения и языки, синтез конечного автомата по регулярному выражению, замкнутость класса автоматных языков относительно разных операций, теорема о разрастании для автоматных языков, примеры неавтоматных языков. Дается краткое введение в теорию алгоритмов, сравниваются три формальных модели описания алгоритмов: структурированные программы, частично рекурсивные функции и машины Тьюринга, формулируется тезис Тьюринга-Черча и устанавливается алгоритмическая неразрешимость ряда проблем, относящихся к свойствам структурированных программ. Решение большинства рассматриваемых в курсе проблем доведено до уровня алгоритмических процедур и проиллюстрировано на примерах. Каждая лекция завершается разделом с задачами и упражнениями, позволяющими закрепить пройденный материал.
Дехтярь, М. И. Лекции по дискретной математике : курс лекций / М. И. Дехтярь. - Москва : ИНТУИТ, 2016. - 113 с. - ISBN 978-5-94774-714-0. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2140215 (дата обращения: 18.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов

Введение в схемы, автоматы и алгоритмы
2-е издание, исправленное
Дехтярь М.И.
Национальный Открытый Университет “ИНТУИТ”


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


Предварительные сведения
Класс \mathcal{P}_n булевых функций от n переменных. Задание булевых функций с
помощью таблиц. Булевы функции от 1-ой и 2-х переменных. Булевы (логические)
формулы и их эквивалентность. Основные эквивалентности ( законы логики ).
Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Графы. Деревья.
Булевы функции от n переменных
Булевы функции1) названы в честь английского математика ХIХ века Дж. Буля,
который впервые применил алгебраические методы для решения логических задач.
Они образуют самый простой нетривиальный класс дискретных функций - их
аргументы и значения могут принимать всего два значения. С другой стороны, этот
класс достаточно богат и его функции имеют много интересных свойств. Булевы
функции находят применение в логике, электротехнике, многих разделах информатики.
Обозначим через 
 двухэлементное множество 
. Тогда 
 -
это множество всех двоичных последовательностей (наборов, векторов) длины .
Булевой функцией от  переменных (аргументов) называется любая функция 
. Каждый из ее аргументов 
 может принимать
одно из двух значений 0 или 1 и значением функции на любом наборе из 
 также
может быть 0 или 1. Обозначим через 
 множество всех булевых функций от 
переменных. Нетрудно подсчитать их число: 
.
Имеется несколько различных способов представления и интерпретации булевых
функций. В этом разделе мы рассмотрим табличное представление, а также
представление с помощью логических формул. В лекциях 2 и 3 будет рассмотрено еще
два способа представления булевых функций: логические схемы и упорядоченные
бинарные диаграммы решений.
Табличное представление
Булевы функции от небольшого числа аргументов удобно представлять с помощью
таблиц. Таблица для функции 
 имеет 
 столбец. В первых  столбцах
указываются значения аргументов 
, а в 
 -ом столбце значение функции
на этих аргументах - 
.
Таблица 1.1. Табличное
представление функции 
   .  .  .   
    
   .  .  .       
   .  .  .       


   .  .  .       
.  .  .  .  .  .
   .  .  .       
Наборы аргументов в строках обычно располагаются в лексикографическом порядке: 
 существует такое 
, что при 
, а 
. Если эти наборы рассматривать как записи чисел в двоичной системе счисления, то 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
Многие из этих функций часто считаются “элементарными” и имеют собственные
обозначения.


 - константа 0;
 - константа 1;
 - функция, равная 1-му аргументу;
 - отрицание 
 ;
 - функция, равная 2-му аргументу;
 - отрицание 
 ;
 - конъюнкция, читается ” 
 и 
 ” (используются также
обозначения 
, 
, 
 и 
 AND 
 ));
 - дизъюнкция, читается ” 
 или 
 ” (используются также
обозначения 
, 
 и 
 OR 
 ));
 - импликация, читается ” 
 влечет 
 ” или “из 
 следует 
 ” (используются также обозначения 
, и ( IF 
 THEN 
 ));
 - сложение по модулю 2, читается ” 
 плюс 
 ”
(используется также обозначение 
 );
 - эквивалентность, читается ” 
 эквивалентно
(равносильно) 
 ” (используется также обозначение 
 );
 - штрих Шеффера (антиконъюнкция), иногда читается как “не 
 и 
 “.
В качестве элементарных функций будем также рассматривать 0-местные функцииконстанты 0 и 1.
Отметим, что функции 
 и 
 фактически не зависят от значений обоих
аргументов, функции 
 и 
 не зависят от значений аргумента 
, а
функции 
 и 
 не зависят от значений аргумента 
.
Определение 1.1. Функция 
 не зависит от аргумента 
, если для
любого набора значений 
 остальных аргументов  имеет место
равенство
Такой аргумент 
 называется фиктивным. Аргументы, не являющиеся фиктивными,
называются существенными.
Функции 
 и 
 называются равными, если функцию 
 можно
получить из функции 
 путем добавления и удаления фиктивных аргументов.
Например, равными являются одноместная функция 
 и двухместная функция 
, так как вторая получается из первой добавлением фиктивного аргумента 
.
Мы не будем различать равные функции и, как правило, будем использовать для
обозначения равных функций одно и то же имя функции. В частности, это позволяет
считать, что во всяком конечном множестве функций все функции зависят от одного и
того же множества переменных.


Формулы
Как мы видели, табличное представление булевых функций подходит лишь для
функций с небольшим числом аргументов. Формулы позволяют удобно представлять
многие функции от большего числа аргументов и оперировать различными
представлениями одной и той же функции.
Мы будем рассматривать формулы, построенные над множеством элементарных
функций 
. Все эти функции, кроме констант, называются
логическими связками или логическими операциями. При этом для 2-местных функций
из этого списка будем использовать инфиксную запись, в которой имя логической
связки помещается между 1-ым и 2-ым аргументами.
Зафиксируем некоторое счетное множество переменных 
. Определим
по индукции множество формул над 
 с переменными из . Одновременно будем
определять числовую характеристику 
 формулы , называемую ее глубиной, и
множество ее подформул.
Определение 1.2. а) Базис индукции. 0, 1 и каждая переменная 
 является
формулой глубины 0, т.е. 
. Множество ее подформул
состоит из нее самой.
б) Шаг индукции. Пусть 
 и 
 - формулы, 
. Тогда выражения 
 и 
 являются формулами. При этом 
, а 
. Множество подформул  включает саму
формулу  и для 
 все подформулы формулы 
, а для 
 все
подформулы формул 
 и 
.
Каждой формуле 
 сопоставим булеву функцию, которую эта формула
задает, используя индукцию по глубине формулы.
Базис индукции. Пусть 
. Тогда 
 или 
 В первом случае 
задает функцию 
, во втором - функцию, тождественно равную константе .
Шаг индукции. Пусть  - произвольная формула глубины 
. Тогда 
 или 
для некоторой булевой связки 
. Так как 
,
то формулам 
 и 
 соответствующие функции 
 и 
 уже
сопоставлены. Тогда формула 
 задает функцию 
, а формула 
 задает функцию 
.
Для определения функции, задаваемой небольшой формулой, удобно использовать
таблицу, строки которой сответствуют наборам значений переменных, а в столбце под
знаком каждой логической связки стоят значения функции, задаваемой


соответствующей подформулой.
Пример 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. Булевы формулы  и 
 называются эквивалентными, если
соответствующие им функции 
 и 
 равны.
Обозначение: 
. Эквивалентные формулы называют также тождественно
равными, а выражения вида 
 логическими тождествами.
Таким образом, эквивалентные формулы являются различными заданиями одной и той
же булевой функции. Ниже мы приводим ряд пар эквивалентных формул (тождеств),
отражающих существенные свойства логических операций и важные соотношения
между различными операциями. Они часто позволяют находить для булевых функций
по одним задающим их формулам более простые формулы. Большинство из


приводимых тождеств имеют собственные имена. Часто их называют законами логики.
Пусть  - это одна из функций 
. Для этих трех функций выполнены следующие
две эквивалентности (законы ассоциативности и коммутативности).
(1) Ассоциативность:
(2) Коммутативность:
(3) Дистрибутивные законы:
(4) Двойное отрицание:
(5) Законы де Моргана (внесение отрицания внутрь скобок):
(6) Законы упрощения:
Некоторые законы упрощения имеют собственные названия: эквивалентности в
первой строке называются законами идемпотентности, 
 - это закон
противоречия, 
 - это закон исключенного третьего.Следующие две
эквивалентности позволяют выразить импликацию и сложение по модулю 2 через
дизъюнкцию, конъюкцию и отрицание.
(7)
(8)
Правильность этих эквивалентностей легко устанавливается прямым вычислением
функций для их левых и правых частей.
Соглашения об упрощенной записи формул. Законы ассоциативности показывают,
что значения формул, составленных из переменных и одних операций конъюнкции, не
зависят от расстановки скобок. Поэтому вместо формул 
 и 


 мы будем для упрощения писать 
. Аналогично, будем
использовать выражения 
 и 
 для сокращения формул,
состоящих из одних дизъюнкций или одних сложений по модулю 2, соответственно.
Будем также опускать внешние скобки в записи формулы, если ее внешней функцией
является одна из функций 
.
Таким образом, с использованием этих соглашений формула 
 может быть записана как 
.
Дизъюнктивные и конъюнктивные нормальные формы
Имеется ряд специальных подклассов формул, позволяющих задавать все булевы
функции. В этом разделе мы определим два таких подкласса функций, использующих
только операции 
 и 
.
Пусть 
 - это множество пропозициональных переменных. Введем для
каждого 
 обозначения: 
 и 
. Формула 
( 
 ), в которой 
 и все переменные разные, т.е. 
при 
, называется элементарной конъюнкцией (элементарной дизъюнкцией).
Определение 1.4.Формула 
 называется дизъюнктивной нормальной формой (ДНФ),
если она является дизъюнкцией элементарных конъюнкций, т.е. имеет вид 
, где каждая формула 
 - это элементарная
конъюнкция. 
 называется совершенной ДНФ, если в каждую из ее конъюнкций 
входят все  переменных из 
. Аналогично, формула  называется конъюнктивной
нормальной формой (КНФ), если она является конъюнкцией элементарных дизъюнкций,
т.е. 
, где каждая формула 
 - это элементарная
дизъюнкция. Она является совершенной КНФ, если в каждую 
 входят все 
переменных из 
.
Рассмотрим произвольную булеву функцию
, зависящую от переменных из
. Oбозначим через 
 множество наборов значений переменных, на которых 
принимает значение 1, а через 
 множество наборов, на которых  принимает
значение 0, т.е. 
 и 
. Определим по этим множествам две формулы:
и


Доступ онлайн
1 000 ₽
В корзину