- •Дискретная математика
- •5B0704 – Вычислительная техника и программное обеспечение,
- •5B0703 – Информационные системы
- •Isbn – 601 – 7098 – 78 - 0
- •1 Элементы теории множеств.
- •1.1 Множества
- •1.2 Отношения
- •1.3 Понятие о мощности множеств
- •2 Элементы математической логики
- •2.1 Высказывания и логические операции
- •2.2 Функции алгебры логики
- •2.3 Дизъюнктивные и конъюнктивные нормальные формы
- •2.4 Булева алгебра и теория множеств. Коммутационные схемы
- •3 Элементы теории графов
- •3.1 Основные понятия и определения
2.4 Булева алгебра и теория множеств. Коммутационные схемы
Можно легко заметить аналогию между свойствами операций над множествами и свойствами логических операций. Это не случайно.
Множество вместе с заданными на нём операцияминазывается алгеброй и обозначается.
Определение. Всякая алгебра, содержащая две бинарные и одну унарную операции, которые удовлетворяют соотношениям 1) - 9) (см. основные эквивалентные соотношения булевой алгебры, или основные свойства операций над множествами) называется булевой.
Таким образом, булевыми алгебрами будут:
а) - булева алгебра всех логических функций с операциями конъюнкции, дизъюнкции, отрицания;
б) - булева алгебра логических функций m переменных – это подалгебра алгебры, т.к.;
в) (P - булева алгебра множеств над- универсумом, с операциями пересечения, объединения, дополнения;
г) - булева алгебра двоичных векторов длины n с покомпонентными логическими операциями над двоичными векторами, определёнными следующим образом:
имеет место:
1) , гдеесли; в любом другом случае.
2) , гдеесли; в любом другом случае.
3) , гдеесли,если.
Если мощности множеств P иравны (P ), то между ними можно установить взаимно однозначное соответствие, а соответствующие булевы алгебры будут изоморфны.
Изоморфизм булевых алгебр широко используется в компъютерных вычислениях, например, вместо выполнения операций над множествами или логическими функциями используют их изоморфные аналоги – поразрядные операции над двоичными векторами.
Коммутационные схемы
Возможность применения математической логики к техническим вопросам была обнаружена в 30-х годах ХХ века. Была замечена, например, связь между электрическими цепями и логическими функциями. Это открытие дало толчок к развитию ЭВМ. Рассмотрим упрощённо эту связь.
Основным элементом релейно-контактных устройств является электромеханическое реле (переключатель р). Реле может размыкать и замыкать цепь. Присвоим р значение 1, когда цепь замкнута (ток проходит), и значение 0, когда цепь разомкнута (ток не проходит).
Рассмотрим электрическую цепь на рисунке 2.4.1. При таком расположении контактов p и q лампочка будет гореть (т.е. схема имеет значение 1), если оба переключателя p и q замкнуты (т.е. имеют значения 1). Таким образом, эта схема соответствует логической формуле , а такое расположение переключателей называется логическим элементом «p и q» или схемой логического умножения, его часто обозначают на схеме как на рисунке 2.4.2.
Рисунок 2.4.1 Рисунок 2.4.2
Рассмотрим теперь схему на рисунке 2.4.3. В этой цепи лампочка будет гореть, и значение схемы равно 1, если хотя бы один из двух контактов p или q, или оба, будут замкнуты, т.е. или , или, или оба. Таким образом, эта схема соответствует логической формуле, а такое расположение переключателей называется логическим элементом «p или q» или схемой логического сложения. Этот элемент можно изображать на схемах, как на рисунке 2.4.4.
|
Рисунок 2.4.3 Рисунок 2.4.4 Рисунок 2.4.5
Если имеем схему с одним переключателем p, который обладает свойством, что лампочка загорается тогда и только тогда, когда p разомкнут (т.е. схема имеет значение 1, когда р=0, и значение 0, когда р=1), то эта схема
соответствует . Такой логический элемент называется «не р» или инвертором, его часто изображают на схемах, как на рисунке 2.4.5.
Рассмотрим примеры схем, реализующих простейшие логические формулы.
Пример 2.4.1 - Схема на рисунке 2.4.6 реализует формулу (переключательную функцию, или функцию проводимости) ; схема для формулыизображена на рисунке 2.4.7; схема на рисунке 2.4.8 - для формулы.
|
|
|
|
|
| |||
|
|
| ||||||
|
|
| ||||||
|
|
|
|
|
Рисунок 2.4.6 Рисунок 2.4.7 Рисунок 2.4.8
Так как любую логическую формулу можно привести к ДНФ или КНФ, то для неё всегда можно построить контактную схему. Очевидно, что чем проще формула, определяющая функцию проводимости, тем проще схема. Поэтому задача упрощения схемы сводится к задаче упрощения или минимизации соответствующих функций. Эту задачу мы решали выше.
Пример 2.4.2 - Упростим схему на рисунке 2.4.9.
Рисунок 2.4.9 Рисунок 2.4.10
Решение: составим переключательную функцию . Упростим эту функцию, используя эквивалентные преобразования:
.
Последней формуле соответствует упрощённая схема на рисунке 2.4.10.