Введение

Министерство образования и науки Российской Федерации

Государственное образовательное учреждение

Высшего профессионального образования

“Cанкт-Петер­бургс­кий государ­ст­вен­ный университет

информационных тех­но­логий, механики и оп­тики”

Кафедра вычислительной техники

П.С. Довгий, В.И. Поляков

Приложение булевой алгебры

К синтезу комбинационных схем

Конспект лекций по курсу

«Дискретная математика»

(экспериментальный вариант)

Санкт-Петербург

2007 г.

Содержание

Введение 3

1. Элементы булевой алгебры 3

2. Разнообразие булевых функций 6

3. Нормальные формы булевых функций 7

4. Числовая и символическая формыпредставления булевых функций 11

5. Преобразование произвольной аналитической формы

булевой функции в нормальную 11

6. Приведение произвольных нормальных форм булевой функции к
каноническим 12

7. Разнообразие двоичных алгебр 13

8. Задача минимизации булевых функций 13

9. Кубическое представление булевых функций 14

10.Геометрическая интерпретация кубов малой размерности.

Графическое представление булевых функций 16

11.Покрытия булевых функций 17

12.Минимизация булевых функций на картах Карно 21

13.Импликанты булевой функции 28

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

14.1. Нахождение множества максимальных кубов

(простых импликант) булевой функции 31

14.2. Определение ядра покрытия 33

14.3. Определение множества минимальных покрытий 34

15.Функциональная полнота системы булевых функций 39

15.1. Теорема о функциональной полноте (теорема Поста) 40

15.2. Замечательные классы булевых функций 40

15.3. Конструктивный подход к доказательству функциональной

полноты системы булевых функций 43

Литература 43

Введение

Теоретическим фундаментом современных ЭВМ является алгебра логики, основы которой разработал английский математик и философ Дж. Буль (1815-1864). В 1847 году вышла его работа с характерным названием – “Математический анализ логики, являющийся опытом исчисления дедуктивного рассуждения”. Применяя алгебру (в дальнейшем она стала называться булевой алгеброй), можно было закодировать высказывания, истинность и ложность которых требовалось доказать, а потом оперировать ими, как в математике оперируют с числами. Дж. Буль ввел три основные операции: И, ИЛИ, НЕ, хотя алгебра допускает и другие операции – логические действия. Эти действия бинарны по своей сути, т.е. они оперируют с двумя состояниями: “истина” – “ложь”. Данное обстоятельство позволило в дальнейшем использовать булеву алгебру для описания переключательных схем. Необходимо отметить, что окончательное оформление и завершение булева алгебра получила в работах последователей Дж. Буля: У.С. Джевонса и Дж. Венна (Англия), Э. Шредера (Германия), П.С. Порецкого (Россия).