Основы построения цифровых устройств автоматики

Содержание
ВВЕДЕНИЕ	1
1.	Цели и задачи дипломного проекта	1
1.1.	Проблема разработки методов логического проектирования	1
1.2.	Постановка задачи дипломного проекта	5
2.	Анализ предметной области	6
2.1.	Принципы построения цифровых систем	6
2.1.1.	Обзор уровней проектирования	7
2.1.2.	Основы построения цифровых устройств автоматики	8
2.2.	Логические основы проектирования	9
2.2.1.	Основные положения алгебры логики	10
2.2.2.	Способы представления и минимизации логических функций	12
2.3.	Обобщенные логические функции	18
2.3.1.	Основные понятия. Область определения	20
2.3.2.	Минимизация обобщенных логических функций	23
3.	Анализ методики и алгоритма многоверсионной минимизации цифровых устройств автоматики, основанной на представлении логических функций в обобщенной форме	28
3.1.	Алгоритм минимизации логических функций от пяти переменных	…………………………………………………………...………….31
3.2.	Алгоритм минимизации логических функций от шести переменных	…………………………………………………………...………….38


3.3.	Алгоритм минимизации логических функций от семи переменных	…………………………………………………………...………….42
4.	Синтез комбинационных схем и схем цифровых автоматов с памятью, основанный на представлении логических функций в обобщенной форме…………………………………………………………...…………………50
4.1.	Синтез многоразрядных компараторов	50
4.2.	Синтез многофункциональных однобитовых элементов памяти (триггеров) …………………………………………………………...…………..57
4.2.1.	Синтез синхронного универсального триггера с мультиплексным приёмом данных	58
4.2.2.	Синтез синхронного универсального тестируемого триггера	61
4.3.	Синтез цифровых автоматов с перестраиваемыми параметрами выходных сигналов.	63
ЗАКЛЮЧЕНИЕ	74
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ	75
















ВВЕДЕНИЕ
 Цели и задачи дипломного проекта
 Проблема разработки методов логического проектирования
Проектирование цифровых устройств - сравнительно молодая наука, свои первые теоретические основы получила в 30-хх годах прошлого века, благодаря ученым СССР, Японии и США, которые смогли доказать возможность применения булевой алгебры логики при синтезе и анализе релейно-контактных схем. Благодаря созданию ЭВМ расширились границы теории цифровых устройств (ЦУ), без их использования решение задач, связанных с анализом и синтезом ЦУ представлялось невозможным [21].
На сегодняшний день, вычислительные устройства и системы управления, проникшие во все области человеческой жизни, нуждаются в создании новых и усовершенствовании уже имеющихся алгоритмических и программных средств, а также методов логического проектирования, использующихся при создании цифровых устройств. В этом случае логическое проектирование понимают и как статику систем, т.е. их иерархию и функциональные связи, и как анализ динамики, связанной с изменением переменных и временными характеристиками составляющих на уровне состава устройства, и на уровне переходных процессов.
Активное развитие программируемых логических интегральных схем вернули прежнюю актуальность вопросов, касающихся логического проектирования цифровых систем с учетом требований к техническим характеристикам; анализа, преобразования и минимизации логических функций; оптимального синтеза в различных базисах и других [28].  Именно поэтому, разработка методов логического проектирования цифровых схем, позволяющих улучшить основные характеристики ЦУ, упростить процедуру проектирования, а

также снизить время и стоимость производства является важнейшим этапом в развитии логического проектирования в целом.
Повсеместно использующимся математическим аппаратом логического проектирования цифровых устройств является алгебра логики. Одним из основных понятий алгебры логики является понятие логической функции (ЛФ) и её области определения [21].
Большое количество разработанных методов логического проектирования основано на традиционном представлении ЛФ в виде логических 0 и 1, главным недостатком которого, является большое множество точек области определения, что приводит к большой вероятности возникновения ошибок и усложнению задач проектирования ЦУ, которое связано с рассмотрением большого числа вариаций. Такими задачами являются:
•	организация структуры конечного автомата, оптимального по требуемому критерию,
•	синтез конечных автоматов с перестраиваемыми параметрами,
•	поиск оптимального варианта кодирования автомата,
•	контроль безошибочного получения результатов минимизации логических функций.
Также, при таком традиционном представлении процедура определения реакции ЛФ на изменение значений аргументов значительно усложняется [21].
Разработка методов логического проектирования зачастую основана на нетрадиционном представлении булевых функций, дающих положительный результат при синтезе и анализе цифровых устройств. Одним из таких способов представления, является представление ЛФ в обобщенной форме. Данное представление подразумевает, что значения функции во множестве точек области определения могут быть представлены 0, 1 и некоторыми параметрами, зависимыми или независимыми от других переменных. Такое представление ЛФ ведет к уменьшению множества точек области определения, что значительно упрощает процедуру решения задач проектирования и синтеза ЦУ [22].

 Постановка задачи дипломного проекта
Целью данного дипломного проекта является синтез цифровых устройств автоматики, основанный на представлении ЛФ в обобщенной форме. Для достижения поставленной цели необходимо решить следующие подзадачи:
•	Провести анализ предметной области проектирования ЦУ;
•	Рассмотреть основные способы представления и минимизации логических функций;
•	Освоить термин обобщенной логической функции, изучить основные понятия, область определения и способы ее минимизации;
•	Исследовать принцип многоверсионной минимизации, выполнить минимизацию функций, зависящих от различного числа переменных применяя сжатие их области определения по одной, двум и трем переменным;
•	Выполнить синтез многоразрядных компараторов;
•	Выполнить синтез многофункциональных однобитовых элементов памяти (триггеров);
•	Провести синтез цифрового автомата с перестраиваемыми параметрами выходных сигналов с дальнейшей оценкой результатов достоверности результатов данного синтеза, как аналитическим способом, так и с помощью компьютерного моделирования.
Проведя полный анализ и синтез выбранного цифрового автомата, можно оценить возможность реализации данной модели на практике и выявить способы расширения области применения данного устройства.






 Анализ предметной области
 Принципы построения цифровых систем
Под проектирование цифровых устройств подразумевается процесс разработки, сопровождаемые технической документацией, позволяющий перейти к разработке технологии и последующего изготовления определенного устройства [25]. 
На практике для цифровой системы, а также ее блоков, используется принцип «черного ящика». Для данного «черного ящика» разрабатывается функциональная спецификация, состоящая из внешнего описания входов и выходов блока, и внутреннего описания алгоритма работы: F=Ф(X, t), где X - вектор входных величин, F – вектор выходных величин, t - время. При анализе алгоритма работы, функция Ф разбивается на более простые функции Ф1 … Фk, между которыми должны быть установлены определенные связи, соответствующие принятому алгоритму реализации функции Ф. В результате такого разбиения и получается структура [21]. Данный процесс перехода от функции к структуре называется синтезом. Синтез обладает неоднозначностью. Выбор наилучшего варианта осуществляется по результатам анализа, когда проверяется правильность работы и некоторые показатели, характеризующие проектируемое устройство. Разбиение функции происходит до тех пор, пока не получаться типовые функции, каждая из которых может быть реализована тем или иным элементом. Характер проектирования существенно зависит от применяемой элементной базы [29]. 
Проектирование цифровых устройств – это, по большей части, механическая работа, которую на сегодняшний день стало выполнять гораздо проще, чем 10 - 20 лет назад [22]. Однако, помимо данной работы, имеет место множество аспектов, которые разработчик не должен оставить без должного


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


 Обзор уровней проектирования
Проектирование цифровых устройств может выполняться на нескольких различных уровнях представления. Существует возможность работы на каком-то определенном, хорошо изученном, уровне, однако со временем будет возникать необходимость перехода на уровни выше или ниже, для завершения начатой работы [28]. Кроме этого, увеличение плотности схем и их функциональной сложности постоянно заставляют проектировщиков и промышленность в целом к переходу на более высокие уровни представления.
На самом низком уровне представления, при проектировании цифровых устройств, происходит анализ физики того, что происходит в логической схеме, и процессов, протекающих при изготовлении интегральных схем (ИС). Достижением этого уровня, в первую очередь является невероятный прогресс в отношении быстродействия и плотности ИС за последние десятилетия. Это стремительное развитие отражает закон Мура, впервые сформулированный основателем фирмы Intel Гордоном Муром в 1965 году, состоящий в том, что число транзисторов, приходящихся на квадратный дюйм в ИС, удваивается каждый год, с момента создания ИС [21]. Важно отметить, что вместе с удвоением плотности также вдвое возрастает и быстродействие схем.
Проектируя системы и планируя их выпуск, необходимо иметь представление о вероятном прогрессе в области технологий и других изменениях. Например, недавнее уменьшение геометрии в кристалле привело к переходу на более низкие напряжения питания логических схем, вызвав значительные изменения в том, как разработчики проектируют модульные системы, описывают и модернизируют их [29].


 Основы построения цифровых устройств автоматики
Самые элементарные цифровые устройства называют логическими элементами (реже - вентили). Первоначально вентили получили свое название по выполняемой ими функции, состоящей в том, чтобы пропускать или задерживать потом цифровой информации. В общем случае вентиль имеет один или большее число входов и вырабатывает выходной сигнал, который зависит от значения сигнала на входе (на входах) в настоящий момент [12].
Несмотря на то, что на вход может быть подан аналоговый сигнал, например такой как напряжение или ток, согласно современной цифровой схемотехнике считается что принимают только два дискретных значения: 0 или 1.
Логический элемент представляет собой комбинационную схему, так как сигнал на его выходе определяется только комбинацией входных сигналов в данный момент времени [26]. Современные логические схемы выполняются на транзисторных структурах, однако нужно помнить, что они также строились или могут быть построены и на другой основе, например, на реле или на электронных лампах, а также в виде гидравлической конструкции или молекулярной решетке.
Устройство способное хранить 0 или 1 называется триггером, состояние которого показывает какое из значений храниться в нем в данный момент. Сохраняемое значение можно изменить только в определенные моменты времени, задаваемые «тактовым» входным сигналом, и то, что будет храниться в дальнейшем, зависит от предшествующего состояния триггера и от значений сигналов на его управляющих входах. Триггер можно построить с помощью некоторой комбинации соединенных между собой в определенной последовательности логических элементов.


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


 Логические основы проектирования
Все множество ЦУ можно разделить на комбинационные схемы и последовательные устройства, или как чаще их называют автоматы с памятью. Комбинационные устройства состоят из простейших элементов, выполняющих основные логические функции. Триггеры, выполняющие функции памяти в последовательностных автоматах, также состоят из подобных элементов [12]. Поэтому отличие автоматов с памятью от комбинационных устройств на уровне структуры автомата состоит не в элементной базе, а в способе их взаимных соединений. Характерной особенностью автоматов с памятью является наличие в их структуру обратных связей [26].
При проектировании автоматов с памятью принято представлять их в виде двух взаимно связанных частей – комбинационной части, выполняющей функции управления, и собственно памяти, состоящей из набора триггеров. На входы комбинационной схемы поступают управляющие сигналы и сигналы обратной связи с выходов триггеров [13]. Комбинационная схема формирует сигналы, подаваемые на управляющие входы триггеров, обеспечивая их переход в новое состояние, которое зависит от управляющих сигналов, подаваемых на входы комбинационной схемы, и от сигналов с выходов элементов памяти, что собственно и обеспечивает переход автомата в новое состояние в зависимости от предыдущего.
Исходя из сказанного, можно подвести итог, что основным моментом в проектировании цифровых автоматов является синтез комбинационных схем. Комбинационная схема может иметь один или большее число выходов. Большинство методов анализа и синтеза очевидным образом можно перенести со случая одиночного выхода на схему со многими выходами [14].
Синтез, как и анализ,  является составной частью проектирования логических схем, так как решение реальной задачи проектирования начинается со словесного описания схемы. Обычно,  самой трудной частью при проектировании является формализация описания схемы, состоящая в указании входных и выходных сигналов схемы и задании ее функционального поведения посредством таблиц истинности или уравнений. После завершения процесса формального описания, обычно происходит однообразная процедура синтеза, целью которой является получении логической схемы устройства, обеспечивающей требуемое функциональное поведение [27]. Математическим аппаратом анализа и синтеза комбинационных схем является алгебра логики (булева алгебра).


 Основные положения алгебры логики
Формальные методы анализа и синтеза цифровых схем, берут свое начало в работе английского математика Джорджа Буля. В 1854 году он ввел алгебраическую систему, состоящую из двух значений, называемую теперь алгеброй логики или булевой алгеброй. С помощью такой системы можно высказывать истинные или ложные суждения, составлять из них новые высказывания и определять истинность или ложность этих высказываний [1].
Спустя долгое время, в 1938 году Клод Э. Шеннон объяснил как можно приспособить булеву алгебру для анализа схем, составленных из реле, и описания ее поведения, которые в те года были наиболее распространенными логическими элементами. В алгебре логики Шеннона состояние контакта реле - замкнутое или разомкнутое - представляется переменной X, которая в свою очередь могла принимать одно из двух значений [27]. Одно из этих значений обозначают как 0, второе – как 1, чтобы не смешивать эти значения с двоичными цифрами, эти символы называют логическим 0 и логической 1. В некоторых случаях логическом 0 и 1 соответствуют двоичные цифры 0 и 1, а в других случаях логическая 1 соответствует выполнению некоторого условия, а логический 0 – его невыполнение.
В алгебре логики для представления логических сигналов используется символическая переменная, например х. Логический сигнал может принимать одно из двух значений, обычно мы говорим, что переменная х равна нулю для одного из данных значений и 1 для другого, абстрагируясь от физической природы самого сигнала [29].
Достоинство абстрактной алгебры состоит в том, что ее результаты применимы к элементам различной природы, лишь бы эти элементы удовлетворяли определенным аксиомам или постулатам.
Аксиомы или постулаты алгебры логики – это набор основных утверждений, о которых имеют в виду, что они справедливы, и из которых можно вывести все другие свойства системы. Первые две аксиомы алгебры логики устанавливают «цифровую абстракцию», формально утверждая, что переменная х может принимать только одно из двух значений:
(А1) х=0, если х?1;
(А1`) х=1, если х?0.
После определения элементов алгебры логики (логического 0 и 1) вводятся основные операции над переменными, которые в общем виде трактуются как функции от этих переменных, позволяющие формализовать описание поведения структуру схемы [30].
Первая такая операция получила название НЕ. Ее также называют отрицанием или инверсией. Для обозначения инверсии чаще всего используется надчеркивание над инвертируемой переменной. Операция НЕ непосредственно следует из приведенной ниже пары аксиом:
(А2) ?х=0, если х?0, т.е. х=1;
(А2`) ?х=1, если х?1, т.е. х=0
По правилам алгебры для обозначения этой функции нужно писать: F=?х, чтобы выразить тот факт, что значение F всегда имеет значение, противоположное аргументу х. 
Следует обратить внимание что приведенные аксиомы представлены в паре, различие между аксиомами А1 и А1` состоит лишь в перемене местами логических значений 0 и 1. Этим свойством обладают все аксиомы алгебры логики, и это обстоятельство служит обоснованием принципа «двойственности».
Следующие три пары аксиом дают формальное определение операций И (AND operation) и ИЛИ (OR operation):
(А3) 0?0=0
(А3`) 1?1=1
(А4) 1?1=1
(А4`) 0?0=0
(А5) 0?1=0
(А5`) 1?0=0?1=1
    Функция И принимает значение равное 1 лишь в том случае, когда оба ее аргументы равны 1. Эту функцию иногда называют логическим умножением и изображают алгебраическим знаком умножения – точкой (F=a?b), либо знаком конъюнкции (F=a?b или F=a&b). Элемент, реализующий функцию И, носит название элемент И (реже конъюнктор) [3].
Функция ИЛИ принимает значение равное 0 лишь в том случае, когда оба ее аргументы равны 0. Функцию ИЛИ иногда называют логическим сложением и изображают алгебраическим знаком «плюс», записывая F=a+b или знаком «дизъюнкции» (?), записывая F=a?b. Элемент, реализующий функцию ИЛИ, носит название элемент ИЛИ (реже дизъюнктор).
Пятью парами аксиом (А1- А5) и (А1`- А5`) исчерпывается булева алгебра. Все другие свойства логических элементов можно вывести из этих аксиом, используя их в качестве базы.


  Способы представления и минимизации логических функций
Одним из основных понятий алгебры логики является понятие логической функции и ее области определения. Каждое логическое выражение, полученное из  n переменных множества Х=хn-1…x0 с помощью некоторого конечного числа операций булевой алгебры, рассматривается как логическая функция F(X). Областью определения логической функции n переменных называют совокупность точек n – мерного виртуального пространства [14]. Поскольку каждая точка этого пространства задается определенной комбинацией значений переменных, определяющих функцию, то каждую из таких комбинаций (наборов) можно отождествить с метрикой положения точки в n - мерном пространстве, т.е. с координатой. И тогда, в соответствии с предложенной трактовкой наборов переменных, любая форма задания логической функции, сводится к получению координат точек области определения и значений функций в этих точках [21].
Поскольку каждая переменная принимает два значения, то общее число точек области определения функции n переменных равно 2n. При этом координаты точек (от 0 до 2n-1) можно задавать не только в двоичной системе, но и в любой другой. Если значению единицы некоторой переменной поставить в соответствие x, то значение нуля будет соответствовать x ?, и тогда координату любой точки области определения ki можно представить в виде кортежа, образованного литералами переменных множества Х, определяющих заданную функцию F(X). Координату, представленную в виде k_i=x ?_(n-1) x ?_(n-2)…x ?_0, называют логической координатой i - й точки области определения функции [30]. Если кортеж рассматривать как произведение литералов, то такое представление координаты, обычно называют минтермом или конституентой единицы, подчеркивая тем самым равенство этого произведения единице только для данного набора значений переменных, определяющих заданную функцию [22].
Если значений функции в i - й точке области определения представить как fi, то каждую точку области определения заданной функции можно охарактеризовать в виде обобщенного кортежа, образованного координатой точки и значением функции в этой точке – kifi.
Представленный таким образом кортеж содержит информацию о положении i – й точки в области определения и значении данной функции. Объединяя кортежи для всех точек области определения заданной функции в одно множество, получаем обобщенное теоретико-множественное представления заданной логической функции в форме:
F(X)=?_(i=0)^(2^n-1)??k_i f_i ?  ,
которое содержит полную информацию о координатах всех точек области определения и значения функции в этих точках, т.е. о функции в целом.
Предложенное представление является обобщающим для всех способов задания функций, однако, с практических позиций оно не всегда удобно.
Простейшим, но в то же время громоздким способом представления логических функций является табличная форма, в которой перечисляются все возможные наборы значений переменных (координаты точек области определения) и показываются соответствующие им значения функции (таблицы истинности, карты Карно и т.д.) [4]. Одной из широко распространенных форм представления является таблица истинности. Данный способ представления состоит в перечислении значений сигнала на выходе схемы, для всех возможных входных комбинаций. Такая таблица содержит 2n строк (по числу наборов аргументов), n столбцов (по числу переменных) и один столбец значений функции. Каждому из входных наборов аргументов соответствует значение функции (fi). В таблице 2.1 показано представление функции от 2-х переменных.
                                                                                                Таблица 2.1
Таблица истинности
х1
х0
F
0
0
f0(0,0,0)
0
1
f1(0,0,1)
1
0
f2(0,1,0)
1
1
f3(0,1,1)

Также ЛФ может быть представлена словесным способом, в этом случае словесное описание однозначно определяет все случаи, при которых функция принимает значения 0 или 1. Например, многовходовая функция И может иметь такое словесное описание: функция принимает значение 1, если оба аргумента принимают значение 1, иначе - 0. 
При числовом описании  функция задается в виде десятичных (или восьмеричных, или шестнадцатеричных) эквивалентов номеров тех наборов аргументов, на которых функция принимает значение 1. Условие, что функция f(x0, x1, x2)=1 на наборах 2, 3, 4, 6, записывается  f(2, 3, 4, 6)=1. Аналогичным образом ЛФ может быть задана по нулевым значениям. При нумерации наборов переменным x0, x1, x2 ставится в соответствие веса, т. е. шестому набору соответствует двоичный эквивалент 110, а первому набору – 001 [14]. 
Также, часто при описании ЛФ используют координатный метод, основанный на представлении функции с помощью карт состояний, которая часто называется картой Карно. Такая карта содержит 2n клеток по числу наборов всех возможных значений n переменных функции. Переменные функции разбиваются на две группы так, что одна группа определяет координаты столбца, а другая - координаты строки. При таком способе построения клетка определяется координатами переменных, соответствующих определенному двоичному набору. Внутри клетки карты Карно ставится значение функции на данном наборе. Переменные в строках и столбцах располагаются так, чтобы соседние клетки карты Карно различались только в одном разряде переменных, т. е были соседними [21]. Такой способ представления очень удобен для наглядности при минимизации ЛФ. 
Методы минимизации разрабатываются относительно каждой отдельной функционально полной системы элементарных логических функций, наиболее детально такие методы разработаны для случая, когда функционально полная система элементарных логических функций состоит из дизъюнкции, конъюнкции и инверсии. При этом минимизация логической функции сводится к нахождению такой ее формы, которая имеет наименьшее число элементарных ЛФ – дизъюнкций, конъюнкций и инверсий. Нахождение минимального представления функции в виде ДНФ или КНФ связана с решением двух главных задач, а именно, это нахождение конъюнкций (дизъюнкций), которые входят в ДНФ (КНФ), каждая из которых имеет минимально возможное число букв, и второй задачей является нахождение ДНФ (КНФ), которые имеют минимальное число разных элементарных конъюнкций (дизъюнкций) [21]. 
При решении задач минимизации существенную роль играют понятия импликанты, простой импликанты, существенной простой импликанты.
Импликантой функции F(X) от  n переменных является логическая сумма любого числа и сочетание минтермов, единичным точкам области определения функции F(X).
Если функция F(X) равна 1 в k точках области определения (k?2n), то общее число различных импликант функции F(X) будет равно сумме числа сочетаний из k элементов по числу от 1 до k:
N=C_n^1+C_n^2+…+C_n^k  .
Простой импликантой функции от n переменных F(X) называется логическая сумма 2? смежных минтермов, соответствующих прямоугольному массиву смежных единичных точек области определения функции F(X) размерностью 2a?2b (где a+b=?), если единичные точки этого массива не являются подмножеством единичных точек какого-либо другого подобного массива большей размерности, равной 2? (?>?). При этом, некоторые или даже все единичные точки массива 2? в виде отдельных совокупностей размерностью 2t<2? могут входить в другие подобные массивы размерностью 2s?2t.
Простые импликанты функции в полной своей совокупности покрывают все единичные точки области определения функции F(X). Логическая сумма всех простых импликант F(X) называется сокращенной дизъюнктивной нормальной формой функции F(X). Получение сокращенной ДНФ является первым этапом нахождения минимальных форм ЛФ 21. Хотя сокращенная ДНФ всегда указывает допустимый способ реализации логической функции, она не всегда является минимальной. Иногда из сокращенной ДНФ можно убрать одну или несколько простых импликант, не нарушая покрытия всех единичных точек области определения функции F(X). Такие простые импликанты называются лишними, и тогда возникает вопрос, какие из импликант следует оставить, а какие отбросить. 
В связи с этим введены еще два определения: существенная простая импликанта ЛФ и существенная или особая единичная точка области определения ЛФ [22]. Существенной простой импликантой ЛФ F(X) является логическая сумма 2d минтермов, соответствующих прямоугольному массиву смежных единичных точек области определения функции F(X) размерностью 2a+b (где a+b=d), если хотя бы одна из точек этого массива не входит в другие подобные массивы.
Существенная или особая единичная точка области определения ЛФ – это такая точка, которая входит только в один массив единичных точек, покрываемых существенной простой импликантой. Поскольку существенная простая импликанта является единственной простой импликантой, покрывающей одну из единичных точек области определения функции F(X), она должна входить в любую минимальную логическую сумму данной ЛФ.
Таким образом, первый шаг в процедуре выбора обязательных простых импликант состоит в следующем: мы устанавливаем, какие единичные точки являются существенными, включая их в массив точек максимально возможной размерности 2a+b.
Сокращенная ДНФ называется тупиковой, если в ней отсутствуют лишние простые импликанты. Устранение лишних простых импликант из сокращенной ДНФ ЛФ не является однозначным процессом, т.е. ЛФ может иметь несколько тупиковых ДНФ. Тупиковая ДНФ ЛФ, содержащая минимальное возможное число простых импликант минимально возможного ранга называется минимальной ДНФ. Функция F(X) может иметь несколько минимальных ДНФ.
Существующие методы минимизации ЛФ практически различают только на первом этапе – этапе нахождения сокращенной ДНФ. При решении практических задач синтеза ЦУ широко используют не полностью определенные ЛФ. Поскольку не полностью определенной функции соответствует совокупность полностью определенных функций, то их тупиковые и минимальные нормальные формы могут иметь существенные различия по числу букв в их представлении. Особенностью минимизации этих функций является то, что необходимо найти такое ее доопределение на недоопределенных наборах, которое соответствует минимальной ДНФ, имеющей наименьшее число букв [14]. Иначе говоря, при решении задач минимизации не полностью определенных функций недоопределенные наборы должны быть использованы для получения простейшего представления функций в заданной функционально полной системе элементарных ЛФ. 
Точное решение задачи минимизации ЛФ большого числа переменных достаточно трудоемкий процесс. Поэтому для решения практических задач для уменьшения объема работы ограничиваются нахождением одной или нескольких тупиковых нормальных форм, среди которых определяют минимальную. В связи с этим известные методы минимизации ЛФ позволяют либо решить задачи отдельных этапов минимизации, либо найти приближенное решение, т.е. одну из тупиковых форм или близкую к ним. Известно много методов нахождения сокращенных форм представления ЛФ [21]. Следует отметить, что поиск минимальных ДНФ всегда связан с некоторым перебором решений, существуют методы уменьшающие перебор, однако, в любом из этих методов он всегда имеет место.


 Обобщенные логические функции
С целью удобства представления и обработки информации о положении точек в области определения обычно используют упорядоченное представление значений в форме кортежа. Поскольку в булевой алгебре значениями переменных являются логический ноль и логическая единица, то такую упорядоченную последовательность нулей и единиц называют булевым вектором [21]. 
Понимая составляющие булева вектора, как двоичные разряды, вес каждого из которых определяется местоположением его в кортеже, можно каждому кортежу поставить в соответствие  n - разрядное двоичное число, которое бы определяло координату точки в области определения функции. Поскольку, каждая переменная принимает два значения, то общее число точек области определения функции переменных равно 2n. При этом, координаты точек от 0 до   2n-1 можно задавать не только в двоичной системе, но и в любой другой, в частности, в восьмеричной или десятичной системах.
Если значению единицы некоторой переменной поставить в соответствие x, то значению нуля будет соответствовать , и тогда координату любой точки области определения ki можно представить в виде кортежа, образованного литералами переменных множества X, определяющих заданную функцию F(X). Координату, представленную в виде  , называют логической координатой i - й точки области определения функции. Если кортеж рассматривать как произведение литералов, то такое представление координаты называют минтермом или конституентой единицы. Если значение функции в i – й точке области определения представить как , то каждую точку области определения заданной функции можно охарактеризовать в виде обобщённого кортежа, образованного координатой точки  и значением функции в этой точке - . Представленный таким образом кортеж содержит информацию о положении i - й точки в области определения и значении заданной функции [21]. Представляя кортежи для всех точек области определения заданной функции и объединяя их в одно множество, имеют обобщенное теоретико-множественное представление заданной логической функции в форме: 
F(X)=?_(i=0)^(2^n-1)??k^i f^i ? ,
содержащей полную информацию о координатах всех точек области определения и значений функции в этих точках, т.е. о функции в целом [21]. Трактуя каждый из кортежей, входящих в обобщенную форму теоретико-множественного представления заданной логической функции, как произведение (ki·fi), и заменяя теоретико-множественную операцию объединения операцией логического сложения, получаем обобщенное математическое выражение основной теоремы алгебры логики:
F(x)=?_(i=0)^(2^n-1)??k_i?f_i ? .
Такая форма представления функции n переменных называется совершенной дизъюнктивной нормальной формой (СДНФ). При традиционном представлении логических функций в точках области определения значениями, равными 0,1 – fi={0,1} – СДНФ функции можно также представить в виде полного разложения Шеннона:
F(X)=x ?_(n-1)…x ?_0 f_0 (0,…0,0)?x ?_(n-1)… x ?_0 f_1 (0,…0,1)?x ?_(n-1)…x_1 x ?_0 f_2 (0,…1,0)?…
?x_(n-1)…x_0 f_(2^n-1) (1,…1) .
Сравнивая представление математического выражения основной теоремы алгебры логики и полного разложения Шеннона, видно, что коэффициенты, образуемые литералами всех переменных, определяющих заданную функцию в полном разложении Шеннона, представляют собой логические координаты точек области определения, т.е. минтермы. Поскольку при традиционных способах представления логических функций в точках области определения fi={0,1}, а каждый из минтермов (ki) равен единице только на одном наборе переменных, то произведение ki·fi равно единице только в тех точках области определения, в которых значение функции fi=1, т.е. при традиционных способах представления понятие логической координаты точки области определения и понятие значения функции в этой точке похожи. Исходя из вышесказанного, была предложена более широкая трактовка основной теоремы алгебры логики (полного разложения Шеннона), полагая, что значения функции в точках ее области определения могут быть равны не только нулю и единице, но и значениям других переменных a, b, c…, или некоторым функциям от них [21].
В соответствии с предложенной трактовкой введено понятие обобщенной логической функции (ОЛФ), понимая под ним класс функций, представление которых соответствует основной теореме алгебры логики в её широком смысле.


 Основные понятия. Область определения
Понятие обобщенных логических функций включает в себя класс традиционных функций, к которым относятся функции алгебры логики, зависящие от логических переменных и принимающие значения из того же множества, что и переменные, от которых они зависят. Особенностью данного понятия является специфика представления их и последующего преобразования, обеспечивающих возможность упрощения некоторых вопросов, связанных с анализом и синтезом цифровых устройств. Переменные, определяющие координаты точек области определения называют первичными или адресными, а переменные, определяющие значения функции в отдельных точках области определения - вторичными переменными или параметрами. Область определения ОЛФ n первичных переменных F(X)=F(x_(n-1)…x_0) также как и область определения классической логической функции, это множество точек n – мерного пространства, каждая из которых задается определенной комбинацией значений переменных множества X. Для задани.......................