В результате для заданной функции  можно получить следующие аналитические выражения в форме СДНФ:  

     Таким образом, любая булева функция представима  в совершенной нормальной форме (дизъюнктивной или конъюнктивной). Такое представление является первым шагом перехода от табличного задания функции к ее аналитическому выражению.

     Каноническая  задача синтеза логических схем сводится к минимизации булевых функций, т. е. к представлению их в дизъюнктивной  нормальной форме, которая содержит наименьшее число букв (переменных и их отрицаний). Такие формы называют минимальными. Формула, представленная в дизъюнктивной нормальной форме, упрощается многократным применением закона склеивания и закона поглощения . Здесь под a и b можно понимать любую формулу алгебры логики.  

     Минимизируем  булевы функции: 

Начинаем  склеивание входных слов в форме СДНФ: 

     Путем склеивания мы получили минмальную форму . 

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

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

      Для каждой вершины можно записать соответствующую  ей конституенту единицы. Легко обнаружить, что к конституентам единиц для точек, принадлежащих одному ребру можно применить закон склеивания. Тогда для ребер появятся новые конституенты, содержащие уже только две переменные. Аналогично к подобным конституентам для двух параллельных ребер, принадлежащих одной грани, также можно применить закон склеивания и получить значения переменных или их инверсий, выступающие в качестве конституент, соответствующих граням. Тогда конституенты, соответствующие ребрам могут быть получены как конъюнкции конституент граней, на пересечении которых данное ребро находится.      

      Теперь  можно легко получить минимальную форму, как дизъюнкцию конституент (минитермов), соответствующих точкам, ребрам, граням полностью покрывающим все зачерненные точки, в которых функция равна 1 (и только их).  
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      Рисунок 1 

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

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

      Теперь, используя графическое отображение  функции можно восстановить тождественные преобразования, с помощью которых фактически была получена данная форма. Для этого, воспользовавшись выражением , в СДНФ запишем дважды конституенту (минитерм), соответствующую точке, принадлежащей одновременно и грани и ребру. Затем, применим закон склеивания к точкам, принадлежащим одному ребру, а затем к параллельным ребрам:

В итоге  получаем минимальную функцию .  

      Таким образом, результат минимизации  методом S-кубов проверен тождественными преобразованиями.

3.Минимизация  логических функций  методом карт Карно. Построение логических схем. 

      Методом карт Карно минимизируются функции  с числом переменных до 5 – 6. Карта Карно представляет собой развертку логического пространства на плоскость. Аналогично методу S-кубов на карте также можно выделить области, соответствующие переменным или их инверсиям.

      Минимизируем  с помощью карты Карно функцию, заданную следующей таблицей соответствия:   

      Отобразим данную функцию на карте Карно, проставив 1 в ячейки карты, соответствующие  входным словам, при  которых функция =1. Ребрам, граням и кубам на карте Карно соответствуют ортогональные области (блоки  – строки, столбцы, квадраты, прямоугольники) заполненные 2, 4 и 8 единицами.

      Минитерм, соответствующий той иди иной области (блоку) определяется как конъюнкция переменных или их инверсий, соответствующих областям, на пересечении которых данная ассоциация находится. Минимальная форма формируется как дизъюнкция этих минитермов. Для приведенной функции минимальная форма будет содержать минитермы, соответствующие трем ассоциациям: из двух единиц и из 8 единиц. 

        В результате минимальная форма будет иметь вид: 

      Для полученной минимальной формы логическая схема будет иметь вид: 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

      Таблицa состояний и переходов конечного автомата: 
 

      В данной таблице указано, какие слова обозначают те или иные элементы таблицы. Построение графа начинается с построения четырех вершин, соответствующих четырем состояниям автомата. Затем построение ведется по строкам таблицы. Из соответствующей вершины для каждого входного слова X в графе проводится соответствующая дуга. Концом дуги будет вершина, соответствующая состоянию, в которое перейдет автомат в следующем такте, если на его вход подано слово X. Около каждой дуги указывается ее вес – в числителе входное слово, при котором произойдет данный переход, а в знаменателе – выходное слово, которое при этом установится.

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

      Граф  конечного автомата выглядит следующим образом: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      По  графу осуществляем моделирование работы автомата при подаче на него некоторой последовательности входных слов. Для каждого входного слова и данного состояния по графу определяется выходное слово и состояние в следующем такте S(n+1). Затем процедура повторяется для этого нового состояния и т.д. Таблица моделирования работы автомата приведена ниже: