Переключательные функции и их схемы

       Рассмотрим электрическую схему соединения элементов, которые могут находиться в одном из двух положений: 0 – выкл.; 1 – вкл. – переключатели. В этой схеме подключен источник тока, для наглядности можно добавить в схему логику. Если схема содержит n выключателей, тогда при каждом наборе значений соответствующих переменных на выходе получим 1 при наличии тока и горящей лампе либо 0 при не горящей лампе и отсутствии тока.

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

1. Последовательное соединение элементов

Такой участок замкнут и в нем есть ток только при значении 1 каждого элемента. Он реализует  – логическое умножение (мультипликатор). Аналогично и при любом количестве последовательно соединенных элементов.

2. Параллельное соединение элементов

Такой участок разомкнут только когда все элементы имеют значение 0. Он реализует  – логическое сложение. Аналогично при любом значении параллельно соединенных элементов.

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

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

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

       Часто для изображения логических схем их укрупняют, отдельно отображая логические элементы. Для обозначения логических элементов используется несколько стандартов. Наиболее распространёнными являются американский (ANSI), европейский (DIN), международный (IEC) и российский (ГОСТ). В каждом из них схема строится слева на право. Основные логические элементы каждых стандартов представлены на рисунке 64.

Рисунок 64. Основные логические элементы.

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

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

       Из таких простейших логических элементов составляется интегральная схема, микросхема и прочее с градацией по числу таких элементов: малая – до 100 элементов, средняя – до 1000 элементов и большая – до 10000 элементов.

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

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

Рисунок 65. Пример DD-схемы на всех указанных логических элементах.

 

Теорема Поста о полноте

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

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

       Для логической функции  ее полином Жегалкина имеет вид

Переменные в каждом слагаемом связанны конъюнкцией. Полином Жегалкина для логических функций находится однозначно. Если для логической функции  в полиноме Жегалкина , тогда в слагаемых отсутствуют произведение переменных, тогда функция является линейной. Все рассмотренные выше функции – замкнутые, тогда в результате применения логических операций получим функцию того же класса.

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

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

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

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