Свойства переключательных функций

1. Любая ПФ n аргументов определена на 2ⁿ наборов.

2. Число различных ПФ n аргументов конечно и равно .

Мы будим использовать аппарат алгебры логики к синтезу схем ЭВМ. Это использование основано на следующем: будем отождествлять значение ПФ с выходными сигналами КС, а ее аргументы – с входными сигналами. Тогда ПФ будет описывать процесс преобразования КС входных сигналов в выходные и аппарат Булевой алгебры можно применять при синтезе таких схем. Под синтезом КС будем понимать определение таких способов соединения нескольких простейших схем, называемых логическими элементами, при которых построеные схемы реализуют заданный алгоритм преобразования сигналов при заданном критерии качества. В качестве критерии оценки качества технической реализации заданного алгоритма обычно используют критерий сложности или быстродействия схем.

Общий вид КС можно представить следующим образом:

Схема имеет n входов и m выходов и следовательно реализуют m ПФ от n аргументов. Любая сколь угодно сложная КС строится из более простых схем, называемых логическими элементами.

Логическим элементом называется электронная схема, реализующая элементарную ПФ и имеющая количество входов, равное числу аргументов ПФ и только один выход.

В ЭВМ в основном используются логические элементы с одним или двумя входами, реализующие ПФ одного или двух аргументов. Поэтому задача синтеза КС заключается в том, чтобы из логических элементов построить любую сколь угодно сложную схему, реализующую заданный набор ПФ. Математически в алгебре логики этой задачи соответствует задача представления любой сложной ПФ через элементарные ПФ. При составлении сложных КС из логических элементов используют два приема:

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

2. Перестановка входов элементов.

Пусть имеется два логических элемента, реализующие ПФ f1(x1, x2) и f2(у1, у2). При последовательном соединении этих элементов получим схему, реализующую функцию уже трех аргументов:

Эта схема реализует функцию f3(x1,x2, y2), получаемую в результате постановки вместо аргумента y1 функции f2 (y1,y2) значение функции f1(x1,x2). Подстановка в функцию вместо ее аргументов других функций называется суперпозицией.

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

Изменим порядок подключения входов элементов.

В этом случае схема реализует функцию f4(y2,x1,x2), которая в общем случае отличается от функции f3(x1,x2, y2). В математическом плане мы заменили одни аргументы ПФ другими.

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

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

Рассмотрим ПФ от разного числа аргументов.