4.1.3Законы алгебры логики
Определение формулы
Всякий символ, обозначающий переменную, является формулой.
Символы 1 и 0 являются формулами.
Если – формула, то и
– тоже формула.Если и – формулы, то выражения
,
,
,
также являются формулами.Других формул нет.
Приоритет операций следующий:
Формулы
и
называются равносильными, если на
любом наборе значений, входящих в них
переменных, они принимают одинаковое
значение. В этом случае пишут
.
Легко видеть, что отношение равносильности обладает свойствами рефлексивности, симметричности и транзитивности.
Основные законы:
-
Название закона
И
ИЛИ
Законы тождества
Законы нуля
Законы идемпотентности
Законы инверсии
Коммуникативные законы
Ассоциативные законы
Дистрибутивные законы
Законы поглощения
Законы Де Моргана
4.1.4Реализация функций формулами
Всякая формула представляет собой некоторую булеву функцию, т.к. всякому набору значений переменных, входящих в формулу соответствует значение формулы. Покажем, что справедливо и обратное утверждение: всякую функцию можно реализовать некоторой формулой.
Формула называется элементарной конъюнкцией, если она удовлетворяет двум требованиям:
в формулу могут входить символы только двух функций
.Отрицание может находиться лишь над символом переменных.
Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой ДНФ.
ДНФ называется совершенной (СДНФ), если в каждый дизъюнктивный член входит каждая переменная формулы ровно один раз (с отрицанием или без него).
Теорема. Всякую булеву функцию, тождественно не равную 0, можно представить в виде СДНФ.
Для построения булевой функции в виде СДНФ необходимо:
в таблице отметить строки, где функция принимает значение 1 и для каждой такой строки построить элементарную конъюнкцию;
полученные таким образом элементарные конъюнкции соединить знаком дизъюнкции, в результате чего получим СДНФ.
Например, для схемы И-НЕ имеем
.
4.2Логические элементы
Любое электронное устройство независимо от назначения и степени сложности состоит из активных (транзисторы, интегральные микросхемы) и пассивных (резисторы, конденсаторы, дроссели) компонентов.
Интегральная микросхема (ИМС) представляет собой изделие из активных и пассивных элементов и соединительных проводников, выполненное в объеме и на поверхности полупроводникового кристалла таким образом, что создается определенная электронная схема. Характерная особенность ИМС - большая плотность упаковки элементов.
Наибольшее распространение имеют следующие виды ИМС:
ТТЛ - микросхемы транзисторно-транзисторной логики на биполярных транзисторах;
ЭСЛ - микросхемы эмиттерно-связанной логики на биполярных транзисторах;
МОП (или МДП) - микросхемы на полевых транзисторах структуры металл - оксид-полупроводник (металл - диэлектрик- полупроводник);
КМОП - микросхемы с симметричной структурой на полевых транзисторах р- и n-типа.
Если в устройствах, собираемых из отдельных радиоэлементов, основным активным компонентом являются транзисторы, число которых определяет степень сложности схемы, то в устройствах на ИМС эту роль выполняют логические элементы (ЛЭ).
Логический элемент (или вентиль) представляет собой электронное устройство, на входах и выходах которого сигнал может иметь только один из двух дискретных уровней напряжения: низкий или высокий.
Эти уровни обычно называют логическим нулем (нулевой сигнал) или логической единицей (единичный сигнал). Выходной сигнал связан с входными сигналами определенной логической операцией.
Базовые элементы разных видов микросхем (ТТЛ, ЭСЛ, МОП, КМОП и др.) в функциональном отношении различаются. Базовым считают элемент с наиболее простой структурой, на основе которого легче всего создавать другие электронные схемы. Для микросхем ТТЛ таким элементом является логическая схема И-НЕ.