МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

Пермский государственный технический университет

Лысьвенский филиал

Методические материалы к изучению курса «Дискретная математика»

Часть IV. Булевы функции

Лысьва, 2006

Мухаметьянов И.Т. Методические материалы к изучению курса «Дискретная математика». Часть IV. Булевы функции.  Лысьва: Издательство ЛФ ПГТУ, 2006.  32 с.

Рецензент 

Данное пособие является одним из серии пособий по дискретной математике. Читатель в нём найдёт как теоретический материал, так и материал для практических занятий по теории булевых функций. Кроме того, в пособии приведены варианты для самостоятельной работы студентов (всего 30 вариантов), а также образцы оформления их решений.

 Мухаметьянов И.Т., 2006 г.

 Лысьвенский филиал Пермского государственного технического университета (ЛФ ПГТУ), 2006 г.

Содержание

Содержание……………………………………………………………………….3

Предисловие……………………………………………………………………...4

§1. Высказывания и операции над ними…………………………….……….5

1.1. Понятие высказывания……….…………………………………………..5

1.2. Основные логические операции над высказываниями...…………….…6

1.3. Дальнейшие логические операции над высказываниями……………..11

§2. Формулы алгебры логики. Таблицы истинности……………………...12

2.1. Формулы алгебры логики……………………………………………….12

2.2. Таблицы истинности……………………..…………………………..….13

2.3. Законы логики……………………………………………………………16

§3. Логическое следование и равносильность формул.

Связь с булевыми алгебрами......................................................................18

3.1. Логическое следование и равносильность формул……………………18

3.2. Связь с булевыми алгебрами....................................................................21

§4. Нормальные формы. Двойственность…………...……………………...22

4.1. Дизъюнктивная нормальная форма.

Совершенная дизъюнктивная нормальная форма…………………….22

4.2. Конъюнктивная нормальная форма.

Совершенная конъюнктивная нормальная форма…………………….25

§5. Булевы функции и их основные классы. Полином Жегалкина……..29

5.1. Понятие булевой функции и способы её задания..……………………29

5.2. Основные классы булевых функций.......................................................31

5.3. Полином Жегалкина……………………………………………………..35

5.4. Функциональная полнота…………………………………………….….35

§6. Минимизация булевых функций ……………………….………………..36

6.1. Проблема минимизации…………………………...….…………………36

6.2. Сокращённая ДНФ. Метод Квайна..........................................................36

6.3. Минимальная ДНФ. Таблица Квайна......................................................37

6.4. Метод Квайна-Мак-Класки......................................................................38

§7. Применение к релейно-контактным схемам ……………………….….36

Приложение 1. Варианты индивидуальных заданий………………….…..43

Приложение 2. Образец выполнения индивидуального задания………..60

Литература…………………………………………………...71

Предисловие

Предлагаемое читателю учебно-методическое пособие является одним из серии пособий по дискретной математике для студентов. Мы предполагаем выпустить эту серию в следующем составе:

Элементы теории множеств

Алгебраические структуры

Элементы теории графов

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

Каждое пособие состоит из двух частей.

В первой части приводится необходимый теоретический материал в сокращённом виде (без доказательств), приводятся примеры решения задач технического характера для практических занятий и самостоятельной работы студентов, а также упражнения. Теоретические задачи в пособие мы не включили, так как ограниченность во времени для аудиторных занятий не позволяет, как правило, довести дело до рассмотрения таких задач. Поэтому желающих не ограничиваться техническими задачами мы отсылаем к источникам, которые приведены в списке литературы. Среди задач есть как заимствованные из различных сборников задач, так и составленные нами.

Вторая часть включает в себя приложения. Приложение 1 содержит варианты для индивидуальных самостоятельных работ. Они в значительной степени заимствованы из [4]. В приложении 2 мы приводим образцы выполнения индивидуального задания. В этой связи нам пришлось повторять изложение некоторых методов решения задач. Следует обратить внимание на то, что индивидуальная самостоятельная работа выполняется за рамками аудиторных часов, и поэтому при выполнении задания следует приводить подробные пояснения, с соответствующими ссылками на теоретический материал.

Автор надеется, что каждое пособие серии будет значительным подспорьем в изучении дискретной математики не только под руководством преподавателя, но и при самостоятельной работе.