Цифровые и микропроцессорные устройства 3 page

(8)

(9)

если то (10)

Справедливость этих выражений может быть доказана с помощью таблиц истинности.

Второе свойство инверсии называется законом двойного отрицания.

– Переместительный (коммутативный) закон справедлив как для дизъюнкции, так и для конъюнкции. Например, для двух аргументов можно записать:

(11)

(12)

Справедливость выражений (11) и (12) можно доказать подстановкой в них различных значений и Закон будет справедлив при любом числе аргументов.

– Сочетательный (ассоциативный) закон также является симметричным, т.е. справедлив и для дизъюнкции, и для конъюнкции. При логическом сложении (умножении) нескольких аргументов любую группу слагаемых (сомножителей) можно заменить их логической суммой (логическим произведением). Для трех аргументов можно записать:

(13)

(14)

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

(15)

Формула (15) справедлива и для большего числа слагаемых в скобках. Для доказательства справедливости выражения (15) следует рассмотреть условия обращения в 0 или в 1 левой и правой частей.

Для трех аргументов в соответствии с распределительным законом второго рода можно записать:

(16)

Справедливость формулы (16) можно доказать путем непосредственных преобразований. Для этого преобразуем ее правую часть в соответствии с распределительным законом первого рода.

В результате преобразований мы пришли к левой части формулы (16), что и требовалось доказать.

– Закон инверсии (правило де Моргана), как и все предыдущие, симметричен относительно логических сложения и умножения.

Отрицание логической суммы нескольких аргументов равно логическому произведению отрицаний этих же аргументов:

(17)

Отрицание логического произведения нескольких аргументов равно логической сумме отрицаний этих же аргументов:

(18)

Доказательство справедливости выражений (17) и (18) не представляет трудностей, поскольку левые и правые части равны 0 либо 1 при одинаковых условиях.

– Правило старшинства логических операций является следствием закона инверсии и устанавливает очередность выполнения логических операций в логических функциях, т.е. логические операции обладают приоритетом и выполняются в следующей очередности:

– одиночное отрицание;

– конъюнкция;

– дизъюнкция, сложение по модулю 2 и т.д.;

– общее отрицание.

Всякое отклонение от этого порядка должно быть обозначено скобками.

– Правило склеивания обеспечивает упрощение логических выражений и является следствием распределительных законов. Для двух аргументов можно записать:

(19)

(20)

Докажем справедливость выражений (19) и (20):

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

– Правило поглощения также позволяет упрощать логические выражения и является следствием распределительных законов. Для двух аргументов можно записать:

(21)

(22)

Докажем справедливость выражений (21) и (22):

Название рассмотренного правила удачно характеризует операцию замены двух членов логического выражения одним из них.

Понятие базиса и минимального базиса

Элементарные логические функции двух аргументов могут быть реализованы простейшими логическими элементами, УГО которых представлены в таблице 5. Для реализации сложных логических функций их сначала следует представить элементарными, которые затем последовательно выполнять с помощью простейших логических элементов. Например, функция может быть реализована с помощью логической схемы на рисунке 5.

Рисунок 5 – Логическая схема устройства

Имея логические элементы, выполняющие элементарные функции можно реализовать любую сложную логическую функцию. Такая система функций называется полной системой, или базисом. Но это условие не является необходимым, т.е. при синтезе логических устройств можно ограничиться меньшим набором элементарных логических функций, взятых из

Таким образом, под базисом понимают ограниченный набор элементарных логических функций, с помощью которого можно реализовать логическую функцию любой сложности.

Последовательно исключая из базиса функции, можно получить минимальный базис. Под минимальным базисом понимают такой набор элементарных логических функций, исключение из которого любой функции превращает полную систему в неполную.

Возможны различные базисы и минимальные базисы, отличающиеся друг от друга числом входящих в них функций и видом этих функций. Выбор базиса связан с тем, насколько просто, удобно и экономично можно выполнить логические элементы, реализующие входящие в базис функции, и в целом все логическое устройство.

Один из базисов называется основным. Это базис И, ИЛИ, НЕ, состоящий из трех элементарных логических функций. Основным этот базис называется, потому что при переходе от табличной формы задания к аналитической логическая функция вначале всегда записывается в базисе И, ИЛИ, НЕ, а только затем может быть преобразована в любой другой неосновной базис.

Базис И, ИЛИ, НЕ не является минимальным. Из этой совокупности функций можно исключить функцию И либо функцию ИЛИ. Избыточность основного базиса позволяет упростить схемы логических устройств. Например, если исключить функцию И, то логическую операцию И можно выразить через оставшиеся операции ИЛИ и НЕ. Для этого применим закон двойного отрицания и правило де Моргана:

(23)

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

Рассмотрим некоторые другие базисы. При этом выбранный набор логических функций будет удовлетворять свойствам базиса, если с его помощью можно будет выразить функции И и НЕ (либо функции ИЛИ и НЕ).

Базис образует функция И-НЕ. Действительно, логические операции И и НЕ можно следующим образом выразить через операцию И-НЕ:

(24)

(25)

Таким образом, из логических функций (24) и (25) следует, что для реализации логического элемента НЕ требуется один логический элемент И-НЕ с объединенными входами, а для реализации логического элемента И – два логических И-НЕ (рисунок 6).

Рисунок 6 – Реализация на основе логических элементов И‑НЕ логических элементов НЕ (а) и И (б)

Следовательно, для построения логического устройства произвольной сложности достаточно иметь логические элементы И-НЕ.

Базис образует функция ИЛИ-НЕ. Докажем, что логические операции НЕ и ИЛИ выражаются через операцию ИЛИ-НЕ:

(26)