Как было показано ранее, комбинационный автомат может быть представлен в виде автомата с одним состоянием и реализует некоторую дискретную функцию. В связи с тем, что для произвольного автомата, его комбинационный автомат может быть довольно сложным и в общем случае отличаться от комбинационных автоматов, полученных при декомпозиции других автоматов, то ставится задача выделить некоторое множество комбинационных автоматов, составляющий автоматный базис и с их помощью реализовать комбинационный автомат любой сложности.
Теорема 4.3. О структурном синтезе комбинационных автоматов.
Утверждение: Для того чтобы произвольная дискретная функция могла быть реализована схемой из элементарных комбинационных автоматов, образующих автоматный базис , необходимо и достаточно, чтобы множество функций реализуемых автоматным базисом было функционально полным.
Замечание: доказано, что не существует конечного автоматного базиса, позволяющего представить произвольный КА в виде схемы, состоящей из конечных автоматов с памятью.
Доказательство:
A) Если и — функционально полная система дискретных функций, то производная дискретная функция может быть представлен в виде формулы Ф над множеством функций . (Доказательство из дискретной математики.)
B) Пусть получена такая формула , что для всех комбинационных автоматов независимые переменные значения функции на этих наборах переменных совпадают с результатами вычисления по формуле.
Очевидно, что переменные входящие в это выражение принадлежат различным множествам.

Чтобы отвлечься от конкретного вида множеств и установим изоморфизм между подмножеством натуральных чисел и множествами.
, где и говорить, что переменная имеет значность .
C) Предположим, что функции входящие в функционально полный базис реализован в виде элементарных комбинационных автоматов,

заданных на алфавите , , где — значность функции .
D) Построим Г с использованием автоматного базиса . Построение будем осуществлять индукцией по глубине формулы. В формуле Ф поставим в соответствие схему Г из элементарных комбинационных автоматов, реализующих функции базиса следующим образом:
a) Если окажется, что , то схема Г состоит из одного элемента , входы которого отождествлены с входными параметрами, а выходом которого является выход нашей схемы, таким образом где — выходные переменные, а — -местная функция автоматного базиса .

b) Если формула представлена как , где или переменные из множества входных переменных , или функции уже реализованные схемами Гij . То схема Г для функции строится так:
К тому входу элемента подсоединяется выход схемы Гij , если — формула или же переменная если . Выходом схемы Гi объявляется выход элемента . Входами схемы являются входы схемы Гj, где
Вывод: Схема полученная описанным способом имеет вид ориентированного дерева. Ее входы соответствуют концевым вершинам (переменным функции), а выход — корню дерева (значению функций ). Для того чтобы произвольная функция могла быть реализована схемой над автоматным базисом W , необходимо и достаточно, чтобы множество функций из W образовывало функционально полную систему.
Замечание: для доказательства достаточности необходимо по произвольной схеме над автоматным базисом построить формулу функции, которую эта схема реализовывает (осуществляется в обратном порядке).
Пример:
Дана произвольная схема над автоматным базисом

Построим формулу функции, которую эта функция реализовывает:

Сведения из многозадачной логики
Определение: Многозадачная логика — есть алгебра, заданная на множестве c операциями &, V, ? , где
Для любых » x, y ? вводятся три операции:
Дизъюнкция — x ? y = max ( x, y ) ;
Конъюнкция — x & y = min ( x, y ) ;
= ( x + 1 ) mod k (по Лукасевичу )
Постом было доказано, что &, V, ? , является функционально полная система.
}к
Для k – значной логики, закон двойного отрицания будет выглядеть:

(в булевой)
Для представления дискретной функции с различными значностями переменных поступают так:
Выбирают алгебру логики с К равным:
, где
— значности переменных функции.
— значность самой функции.
Тогда в соответствии с результатами Поста, произвольная дискретная функция с указанными значностями представима в виде формулы конечной длины в алгебре логики.
Пример: Синтез комбинационного автомата.
Пусть задан комбинационный автомат со входными алфавитами , представим его виде логических элементов:

где, — число знаков выходного алфавита,
а — число знаков в алфавите .
Переходим от алфавитов к алфавитам или многочленам с помощью изоморфизма полученного автомата К.

Из автоматной таблицы после применения алфавита получаем дискретную функцию, в k-значной логике, где k равно:

Формула в автоматном базисе будет иметь вид:

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

Кодирование алфавитов
Т.к. самым распространёным автоматным базисом является базис W :
W = { , , }, в булевой алгебре над двоичным алфавитом, то необходимо так представить исходную дискретную функцию, чтобы она могла быть реализована над этим алфавитным базисом. Для этого используют кодирование алфавита в виде элементов декартового произведения нескольких булевых множеств.
Общий вид:

Тогда каждый знак любого из алфавитов кодируется в виде последовательности знаков двоичного алфавита длиной не менее чем , где ] x [ — это наименьшее целое, превосходящее или равное х.
Установим изоморфизм:

В результате получаем булевых функций, зависящих от .
Пример: Используем дискретную функцию из предыдущего примера .
Закодируем знак при помощи двух знаков и ,чтобы прийти к двоичному алфавиту. — для кодирования 3х-значного алфавита хватает двух разрядов.

Представим функцию в СДНФ.