X· (Y· Z).

3 Идемпотентности: X ∨ X = X; X · X = X.

4 Распределительный: (X ∨ Y)· Z = X· Z ∨ Y· Z.

5 Двойное отрицание: .

6 Закон двойственности (Правило де Моргана):

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

X ∨ X · Y = X; X(X ∨ Y) = X — Правила поглощения.

X· Y ∨ X·  = X, (X ∨ Y)·(X ∨ ) = X – Правила склеивания.

Правила старшинства логических операций.

1 Отрицание — логическое действие первой ступени.

2 Конъюнкция — логическое действие второй ступени.

3 Дизъюнкция — логическое действие третьей ступени.

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

2 Основы синтеза цифровых устройств

2.1 Последовательность операций при синтезе цифровых устройств комбинационного типа

1 Составление таблицы истинности комбинационного цифрового устройства (КЦУ) согласно его определения, назначения, словесного описания принципа работы.

2 Составление логической формулы согласно таблицы истинности.

3 Анализ полученной формулы с целью построения различных вариантов и нахождения наилучшего из них по тем или иным критериям.

4 Составление функциональной схемы КЦУ из элементов И, ИЛИ, НЕ.

2.2 Аналитическая запись логической формулы КЦУ 

Запись в форме СДНФ (Совершенная дизъюнктивная нормальная форма).

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

Формула получается в два этапа:

а) Записывается логическая сумма произведений, в каждое из которых входят все независимые переменные. Количество слагаемых равно  числу наборов таблицы истинности, на которых логическая функция равна «1»;

б) ставится знак инверсии над теми независимыми переменными, которые равны «0» в рассматриваемом наборе.

Запись в форме СКНФ (Совершенная конъюнктивная нормальная форма).

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

Как и в предыдущем случае, формула получается в два этапа:

а) Записывается логическое произведение всех сомножителей; количество сомножителей равно числу наборов таблицы истинности, на которых логическая функция равна «0»;

б) ставится знак инверсии над теми независимыми переменными, которые равны «1» в рассматриваемом наборе.

Структурные формулы в виде СДНФ и СКНФ эквивалентны и, с помощью законов алгебры, логики могут быть преобразованы одна в другую.

Пример: Синтезировать мажоритарный логический элемент на три входа.

Мажоритарным называется логический элемент, выходное состояние которого совпадает с большинством входных сигналов.

На основании данного словесного описания мажоритарного элемента составлена его таблица истинности (Таблица 5).

Таблица 5 - Таблица истинности мажоритарного элемента

X1 X2 X3 Y 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1  1 0 1 1 1 1 1 На основе таблицы истинности записывается СДНФ или СКНФ функции, а затем составляется функциональная схема элемента.

СДНФ:

СКНФ:

Рисунок 3 Функциональная схема мажоритарного элемента

Функциональная схема элемента, составленная на основе функции СДНФ мажоритарного элемента, приведена на рисунке 3. Схема  состоит из 8 элементов, имеющих общее количество входов 19. Количество входов характеризует сложность схемы и называется «Число по Квайну». Схема составленная на основе функции СКНФ, также будет иметь 19 входов.

2.3 Понятие базиса 

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

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

Рисунок 4 Реализация элемента ИЛИ на элементах НЕ, И

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

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