Основные законы булевой алгебры

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

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

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

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

 

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

 

Основными элементами булевой алгебры являются:

§ логические константы

§ переменные;

§ операции;

§ выражения;

§ функции;

§ законы.

 

Логические константы

 

В булевой алгебре определены две логические константы: логический ноль (0) и логическая единица (1), которые отождествляются с понятиями “истина” и ”ложь”алгебры логики.

 

Переменные

 

Булевы (логические, двоичные) переменные - переменные, принимающие значения из множества {0,1}.

 

Операции

 

Основными операциями булевой алгебры являются:

§ отрицание (инверсия);

§ конъюнкция (логическое умножение);

§ дизъюнкция (логическое сложение).

Операция отрицания является унарной, а конъюнкция и дизъюнкция – n -арными.

Операции обозначаются следующим образом:

§ Отрицание , ù ;

§ Конъюнкция a & b, a× b, a* b, ab, a Ù b;

§ Дизъюнкция aÚ b.

 

Выражения

 

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

При отсутствии скобок порядок выполнения операций определяется их приоритетом (значимостью). Для булевых операций порядок убывания приоритета следующий: ù, &, Ú.

Примеры логических выражений: .

 

Функции

 

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

Областью определения булевой функции является совокупность 2 ⁿ двоичных наборов ее аргументов. Набор аргументов можно рассматривать как n -компонентный двоичный вектор.

Булеву функцию можно задать с помощью следующих форм:

§ аналитической;

§ табличной;

§ графической;

§ таблично-графической;

§ числовой;

§ символической.

 

Аналитическая форма – булева функция задается логическим выражением, например:

Табличная форма – булева функция задается таблицей истинности.

Переход от аналитической формы к табличной однозначен. Обратный переход однозначным не является.

 

Пример: таблица истинности для функции y₁

				y

 

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

 

Основные законы булевой алгебры

 

К основным законам (тождествам, правилам) булевой алгебры относятся:

1. Коммутативные (переместительные) законы:

2. Ассоциативные (сочетательные) законы:

3. Дистрибутивные (распределительные) законы:

4. Закон двойного отрицания:

5. Законы тавтологии (идемпотентности):

6. Законы нулевого элемента:

 

7. Законы единичного элемента:

 

8. Законы дополнительного элемента. В булевой алгебре дополнительным элементом по отношению к а является отрицание а

 

 

9. Законы двойственности (де Моргана):

Следствия:

 

10. Законы поглощения:

11. Правила сокращения:

Cледствия:

12. Правила склеивания:

 

 

1234567Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: