Законы алгебры логики, следствия из них.

Основные соотношения булевой алгебры можно сформулировать в виде следующих законов:

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

х_1&х₂ = х_2&х₁; или х₁ Ú х₂ = х₂ Ú х₁;

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

(х_1&х₂) _& х₃ = (х_1& х₃) _&х₂;

(х₁ Ú х₂) Ú х₃ = х₁ Ú (х₂ Ú х₃).

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

х_{1 &} (х₂ Ú х₃) = х_1&х₂ Ú х_1&х₃.

4) Законы поглощения (в данном случае х₁ поглощает х₂):

х₁ Ú х_1&х₂ = х₁;

х_1& (х₁ Ú х₂) = х₁.

5) Законы склеивания:

х_1&х₂ Ú х_1&х₂ = х₁.

6) Законы свертки:

х Ú х F = х Ú F;

х _& (х Ú F) = хF.

8) Закон инверсии (правило де Моргана):

х₁ Ú х₂ = х_1&х₂;

х_1&х₂ = х₁ Ú х_2.

9) Закон повторения:

х _& х _&…_& х = х; x v x v …v x = x.

Основные законы дают правила преобразования булевых выражений, позволяющие получать эквивалентные выражения. Преобразованное выражение может быть проще или сложнее исходного в зависимости от преследуемой цели. Например, целью преобразования может быть получение выражения с минимальным числом символов или выражение в некоторой канонической форме (дизъюнктивная нормальная форма — ДНФ, конъюнктивная нормальная форма — КНФ и др.). Вопросы преобразования логических выражений представляют большой прикладной интерес, позволяя на формульном уровне получать оптимальные логические схемы.

 

Свойства элементарных функций.

Дизъюнкция, конъюнкция и инверсия обладают следующими свойствами:

х Ú 1 = 1;

х Ú х = 1;

х _& 0 = 0;

х Ú 0 = х;

х _& 1 = х;

х _& х = 0;

х _& х... х = х;

х Ú х... х = х.

Логические элементы.

 

Элемент изделия (ЭВМ) - составная часть изделия, которая выполняет определенную функцию и не может быть разделена на части, имеющие самостоятельное функциональное назначение. (ГОСТ 2.701 - 76).

В связи с этим термин «элементная база ЭВМ» означает некоторую совокупность элементов на базе которых построена ЭВМ.

Совокупность логических элементов называется системой элементов, если выполняются следующие условия:

- функциональная полнота системы логических функций, реализованных элементами;

- одинаковая форма представления информации на входах и выходах элементов;

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

- отсутствие настройки элементов;

- минимальное число номиналов напряжений питания.

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

Элементы подразделяются на:

Ø логические;

Ø запоминающие;

Ø вспомогательные.

Логические элементы (ЛЭ) относятся к цифровым автоматам (ЦА) без памяти (комбинационные схемы), т.е. состояние выходов таких схем зависит только от состояния входов. Таким образом ЛЭ - это элемент, реализующий ту или иную логическую функцию. Использование ЛЭ позволяет реализовать любую логическую функцию.

Запоминающие элементы (ЗЭ) - относятся к ЦА с памятью (состояние выходов зависит не только от состояния входов, но и от своего внутреннего состояния). Запоминающие элементы реализуются либо на ферритовых сердечниках, либо на базе триггеров - ЦА, имеющих два устойчивых состояния (0 или 1). Количество входов триггера определяется его типом, а количество выходов равно двум: прямой и инверсный. Применение триггеров в качестве ЗЭ позволяет строить устройства памяти большой емкости.

Вспомогательные элементы применяются в ЭВМ для выполнения вспомогательных функций. Например, генерация импульсов, задержка сигналов, формирование сигналов (импульсов), усиление сигналов и т.д.

На основе ЛЭ, ЗЭ и вспомогательных элементов строятся узлы ЭВМ: регистры, счетчики, дешифраторы, сумматоры и т.д.

Наборы логических элементов для построения цифровых вычислительных устройств чаще всего функциональноизбыточны, что позволяет создавать логические схемы более экономными по количеству используемых элементов. Наборы содержат элементы для выполнения базовых и дополнительных логических операций, запоминающие элементы, реализующие функции узлов ЭВМ, а также элементы для усиления, восстановления и формирования сигналов стандартной формы. Физически элементы представляют собой микросхемы, сформированные в полупроводниковом кристалле по соответствующей технологии. Серии элементов могут содержать различные по сложности микросхемы: малой степени интеграции (ИС), средней (СИС), большой (БИС) и сверхбольшой степени (СБИС). Логические элементы в виде ИС реализуют совокупность используемых логических вентилей: AND, OR, NOT, AND-OR, OR-ELSE и др., а также триггеры. На логических элементах на СИС, БИС и СБИС реализуются узлы и даже целые ЭВМ.

 

 

Рис.3.1. Базовые вентили: (a) — И {AND}; (б) — ИЛИ {OR}; (в) — НЕ {NOT}

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

{И-НЕ} (штрих Шеффера), {ИЛИ-НЕ} (стрелка Пирса) и др. Схемы с изображениями элементарных или базовых ЛС и их связей называются логическими диаграммами (ЛД). Если ЛД состоит из вентилей и у нее отсутствуют обратные связи, то соответствующую ей ЛС называют комбинационной. Ввиду взаимно однозначного соответствия между комбинационными ЛД и булевыми выражениями, последние используются также для анализа и/или синтеза ЛД/ЛС; наряду с этим, булевы выражения в составе аппарата булевой алгебры широко используются во многих разделах современных технических наук.