Теорема 2.1. Любая переключательная функция равняется дизъ­юнк­ции всех своих простых импликант.

Определение 2.2. Функция j(х1, х2, …, хn) называется простой им­пли­кантой функции f(х1, х2, …, хn), если сама функция j входит в функ­цию f, но никакая собственная часть функции j в f не входит.

Определение 2.1. Функция j(х1, х2, …, хn), входящая в функцию f(х1, х2, …, хn) называется импликантой этой функции.

Применение термина "импликанта" связано с переключательной функ­цией двух переменных f₁₃(x,y) = x® y, именуемой импликацией. Восполь­зо­вав­шись таблицей истинности для функции f₁₃(x,y) можно убедиться в том, что выражение j®f тождественно равно единице, т.е. является всегда истинным только тогда, когда функция j входит в функцию f. Тот факт, что j входит в f обозначается следующим образом: j Ì f.

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

Очевидно, что f₄(x₁,x ₂) Ì f₆(x₁,x ₂); f₂(x₁,x ₂) Ì f₆(x₁,x ₂); f₀(x₁,x ₂) Ì f₆(x₁,x ₂), т.е. функции f₄, f₂, f₀ являются импликантами функции f₆. Кроме того, очевидно, что в соответствии с определением понятия вхождения функции в функцию f₆(x,y)Ìf₆(x,y). Если сравнить значения функции f₆(x,y) и f₃(x,y) на всех наборах аргументов, то можно заключить, что f₃(x,y)Ëf₆(x,y), т.е. функция f₃ в функцию f₆ не входит.

Если некоторая импликанта представлена, например, в виде элементарного логического произведения, то ее собственные части могут быть получены путем исключения из данного произведения одного или нескольких сомножителей. Например, произведение x₁×x₂×x₃ имеет собст­вен­ные части x₁, x₂, x₃, x₁×x₂, x₁×x₃ и x₂×x₃.

Предположим, что выполняется следующее условие:

x₁×x₂×x₃ x₄Ì f(х₁, х₂, х₃, х₄),

x₁ ×x₃ Ì f(х₁, х₂, х₃, х₄),

x₁ Ë f(х₁, х₂, х₃, х₄),

x₃ Ë f(х₁, х₂, х₃, х₄),

т.е. элементарное произведение x₁×x₃ является простой импликантой функции f(х₁, х₂, х₃, х₄). Символ Ë означает, что в данном случае условие вхождения одной функции в другую не выполняется.

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

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

Рассмотрим далее наборы, на которых переключательная функция равна единице. Для каждого такого набора найдется хотя бы одна импликанта, равная на этом наборе единице. Действительно, простые импликанты выбираются среди все элементарных произведений, входящих в переключательную функцию. В число этих произведений входят и все конституенты единицы данной функции. Но любая простая импликанта является собственной частью некоторых конституент единицы (или совпадает с одной из них). Например, при трех переменных элементарное произведение х₁х₂ будет собственной частью конституент х₁х₂х₃ и , а элементарное произведение х₂ – собственной частью конституент , , .

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

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

2.2. Теорема Квайна

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

Следует обратить внимание на требование теоремы "выполнить все операции неполного склеивания" и "все операции поглощения". Кроме того, теорема дает определение сокращенной дизъюнктивной нормальной формы переключательной функции – это дизъюнкция всех ее простых импликант.

Точно так же теорема Квайна формулируется применительно к конъ­юнк­тив­ным формам переключательных функций.

Важность этой теоремы обусловлена тем, что она определяет конструк­тив­ное правило нахождения всех простых импликант переключательной функ­ции.

Доказать теорему можно путем следующих рассуждений. Прежде всего покажем, что в результате проведения операций непол­но­го склеивания получим все простые импликанты. Для этого рассмотрим операцию, обратную операции склеивания, называемую операцией раз­вер­ты­вания. Операция развертывания заключается в умножении некоторых импликант на выражение типа = 1, что, естественно, не меняет их значений. С помощью операции развертывания любую простую импли­канту можно представить в виде дизъюнкции конституент единицы.

Пусть, например, – простая импликанта переключательной функции че­ты­рех аргументов: x, y, z, u. Тогда, применяя дважды операцию развер­тыва­ния, получаем

.

Сокращенная дизъюнктивная нормальная форма содержит все простые им­пликанты заданной функции. Применяя к каждой импликанте операцию раз­вертывания, получаем, очевидно, все конституенты единицы этой функ­ции.

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

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

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

Пусть, например, после проведения всех операций склеивания дизъюнктивная форма будет содержать слагаемое q, не являющееся простой импликантой. Тогда оно должно входить в данную функцию (qÌf), так как в противном случае полученной выражение не равняется исходному. Но по предположению q не является простой импликантой и входит в функций f; следовательно, в эту функцию входит какая-то его часть p, которая будет простой импликантой. Тогда q = q₁p и слагаемое q будет поглощаться простой импликантой p:

.

Это и доказывает теорему Квайна.

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

Практически сокращенную дизъюнктивную нормальную форму удобно на­ходить в такой последовательности.

Провести в совершенной дизъюнктивной нормальной форме функции f(x₁, x₂, …, x_n) все возможные операции склеивания конституент единицы. В результате этого образуются произведения, содержание (n-1) букв. Заметим, что конституенты единицы в дальнейшем не будут склеиваться ни с одним вновь полученным логическим слагаемым, так как склеиваться могут только произведения с одинаковым количеством букв. Потому можно сразу же провести операции поглощения, а затем выполнить все возможные склеивания слагаемых, состоящих из (n-1) букв. После этого провести поглощения слагаемых с (n-1) буквой и вновь выполнить операции склеивания слагаемых с числом букв, равным (n-2), и т.д.

Приведем несколько примеров получения сокращенных дизъ­юнк­тивных нормальных форм переключательных функций методом Квайна.

2.3. Метод импликантных матриц

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

.

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

Таблица 2.3.1.