Переключательная функция двух переменных. Функциональные полные базисы.

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

Таблица 1.2.1

	Название функции	Обозначение функции
0 0 0 0	«константа нуля»	0
! 0 0 0 1	«логическое умножение» (конъюнкция)
0 0 1 0	«обратный запрет»
0 0 1 1	«повторение »
0 1 0 0	«прямой запрет»
0 1 0 1	«повторение »
0 1 1 0	«сложение по модулю два» (не равнозначность)
! 0 1 1 1	«логическое сложение» (дизъюнкция)
! 1 0 0 0	«функция Вебба»
! 1 0 0 1	«равнозначность» (эквивалентность)
1 0 1 0	«инверсия »
1 0 1 1	«обратная импликация»
1 1 0 0	«инверсия »
! 1 1 0 1	«прямая импликация»
1 1 1 0	«функция Шеффера» (конъюнкция)
1 1 1 1	«константа единицы»	1

Анализируя таблицу истинности, можно сделать следующие выводы:

· Для функции двух переменных первая половина (1 – 7) имеют прямые значения, а вторая половина (8 – 15) – инверсные.

· В наборах функций двух переменных входят все функции одной переменной, const 0, const 1, повторение , инверсия Некоторые из функций, а именно и, инверсная ей, могут применяться только для двух переменных. Еще две функции обратной и прямой запрет, а так же обратные и прямые импликации повторяют конъюнкцию и дизъюнкцию, только с инверсный.

· Только четыре функции: конъюнкция, дизъюнкция функция Вебба и функция Шеффера могут работать с любым количеством переменных.

Перечисленные четыре функции имеют техническую реализацию и вместе со схемой «НЕ» составляют набор трех функционально – полных технических базисов.

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

1. Базис Буля – этот базис содержит три элемента:

Функция «Инверсия Х»

Функция «Конъюнкция»

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

Функция «Дизъюнкция»

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

2. Базис Шеффера – содержит всего лишь один логический элемент.

Если при построении схемы необходимо про инвертировать переменную, то также используется двухвходовая схема «И – НЕ». Для получения инверсий:

Достоинством применения этого базиса является унификация элементов.

3. Базис Вебба – содержит всего лишь один элемент, реализующий функцию Вебба.

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

Основные законы алгебры логики.

Одинарные законы.

X v 0 = X X ^ 0 = 0

X v 1 = 1 X ^ 1 = X

X v X = X X ^ X = X

X v X ^ = 0

Отметим, что двойное инвертирование не только одной переменной, а логической формулы дает нам тоже значение формулы.

Отметим отдельно свойство конъюнкции:

X ^ 1 = Х X ^ 0 = 0

Эти свойства говорят о том, что элемент «И» можно использовать в качестве электронного ключа, который пропускает или не пропускает входной сигнал Х на выход в зависимости от присутствия на втором входе единицы или нуля.

Комбинационные законы.

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

1. Переместительный:

;

2. Сочетательный:

Например, при использовании двухвходовых схем.

Рисунок 1.3.1

3. Дистрибутивный:

;

Следующие два закона по сути дела являются следствием дистрибутивного, однако в логике имеют свое название из – за применения в методах минимизации.

4. Закон поглощения.

;

Говорят, что – поглощает второй член .

Что бы понять, как использоваться этот закон докажем:

Если имеется дизъюнкция двух конъюнкций и одна из них полностью входит во вторую (общий сомножитель), то эта конъюнкция поглощает вторую.

5. Закон склеивания.

;

Говорят, что произошло склеивание по переменной .

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

Анализируя доказательство, сделаем вывод:

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

2. Все остальные члены конъюнкции должны быть одинаковы (представлять общий сомножитель).

3. Результатом склеивания является общий сомножитель.

Пример:

;