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

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

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

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

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

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

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

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