1-7. АНАЛИТИЧЕСКАЯ ЗАПИСЬ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ

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

Пусть мы имеем двоичный набор Сопоставим ему число определяемое следующим образом:

Число I будем называть номером набора Рассмотрим функцию определяемую следующим соотношением:

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

Теорема 1-3. Любая таблично заданная функция алгебры логики может быть задана в следующей аналитической форме:

где есть множество номеров наборов, на которых функция обращается в единицу.

Справедливость этой теоремы вытекает из следующего. Возьмем произвольный набор аргументов из таблицы, задающей функцию. Возможны два случая. Если на этом наборе функция равна единице, то в соотношении (1-25) в его правой части найдется которой соответствует номеру рассматриваемого набора. Но тогда на основании (1-24) на данном наборе будет равна единице. В силу (1-11) при этом вся правая часть (1-25) также будет равна единице. Если же на рассматриваемом наборе аргументов функция равна нулю, то, как это следует из формулировки теоремы, среди характеристических функций входящих в соотношение (1-25), не будет такой, у которой индекс совпадает с номером рассматриваемого набора аргументов. Но тогда в силу (1-24) все члены дизъюнкции в правой части (1-25) будут равны нулю, что эквивалентно обращению всей правой части в нуль. Так как мы показали, что левая и правая части соотношения (1-25) совпадают на любом наборе аргументов, то теорема 1-3 доказана.

В теореме 1-3 мы воспользовались дизъюнкцией характеристических функций. Посмотрим, нельзя ли вместо дизъюнкции использовать какую-либо другую функцию алгебры логики. Для того чтобы выполнялось соотношение, подобное соотношению (1-25), необходимо, чтобы при обращении любой из характеристических функций в единицу все выражение обращалось в единицу, а при обращении всех характеристических функций в нуль все выражение также становилось равным нулю. Если обозначить неизвестную операцию значком V, то сформулированные нами условия можно записать в виде следующей таблицы:

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

случай рассматривался нами в теореме 1-3. Если же вопросительный знак в таблице заменить нулем, то мы получим функцию сложения по модулю 2.

Следствие. Любая таблично заданная функция алгебры логики может быть представлена в следующей аналитической форме:

Представление функции в виде (1-25) мы будем называть дизъюнктивным представлением, а представление ее в виде (1-26) — полиномиальным представлением.

Для получения представлений другого типа рассмотрим функции определяемые, как

Такие функции мы будем называть характеристическими функциями нуля. Из соотношений (1-24) и

Теорема 1-4. Любая таблично заданная функция алгебры логики может быть задана в следующей аналитической форме:

где То есть множество номеров наборов, на которых функция обращается в нуль.

Доказательство теоремы 1-4 проводится точно также, как и теоремы 1-3.

Вместо конъюнкции в соотношении (1-28) можно взять любую функцию, которая удовлетворяет следующим условиям:

При записи в первой строке правого столбца таблицы нуля получаем конъюнкцию, рассматривавшуюся в теореме 1-4, а при замене знака вопроса единицей — функцию эквивалентности.

Следствие. Любая таблично заданная функция алгебры логики может быть представлена в следующей аналитической форме:

где

Представление функции в виде (1-28) мы будем называть конъюнктивным представлением. Представление ее в виде (1-29) не имеет традиционного установившегося названия.

Найденные нами четыре представления с использованием характеристических функций являются основными для всего дальнейшего исследования.

Перейдем теперь к аналитическому выражению самих характеристических функций.

Условимся о ряде обозначений. Введем в рассмотрение «степень» аргумента х, которую будем обозначать Положим, что

Рассмотрим конъюнкцию

Набор двоичный и существует ровно различных таких наборов. Таким образом, число различных конъюнкций вида (1-31) также равно

Сопоставим каждой конъюнкции (1-31) номер, определяемый номером набора Тогда запись

означает дизъюнкцию всех конъюнкций с номерами из множества а.

Введенный нами знак V является аналогом знака суммы в математике.

Аналогично запись

означает конъюнкцию всех дизъюнкций с номерами из множества . Знак аналогичен знаку произведения.

Покажем, что тогда и только тогда, когда выполняется равенство

Это вытекает из рассмотрения следующих четырех возможных случаев:

Таким образом, конъюнкция не обращается в нуль только в том случае, если одновременно выполняются следующие равенств:

Из (1-32) вытекает, что

при условии, что

Тогда на основании теоремы 1-3 можно утверждать, что любая функция алгебры логики, кроме нуля, может быть представлена в следующей форме:

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

Представление функции алгебры логики в виде (1-33) мы будем называть дизъюнктивной совершенной нормальной формой этой функции.

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

1. Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в единицу.

2. Выписать конъюнкции, соответствующие этим наборам аргументов. При этом, если аргумент х, входит в данный набор как 1, он вписывается без изменения в конъюнкцию, соответствующую данному набору. Если же - ходит в данный набор как 0, то в соответствующую конъюнкцию вписывается его отрицание.

3. Все полученные конъюнкции соединяются между собой знаками дизъюнкции.

Пример 1-6. Пусть задана функция следующей таблицей:

Требуется получить для нее дизъюнктивную совершенную нормальную форму.

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

Соединяя эти конъюнкции знаками дизъюнкций, окончательно получаем:

Если вместо соотношения (1-25) воспользоваться соотношением (1 -26), то мы получим полиномиальную совершенную нормальную форму (ПСНФ). ПСНФ получается из ДСНФ путем замены знака дизъюнкции знаком сложения по модулю два. Так, для функции, рассмотренной нами в примере имеет следующий вид:

Кроме представления функции алгебры логики в ДСНФ, возможно представление ее в некоторой другой форме, двойственной по отношению к ДСНФ.

Теорема 1-5. Любая функция алгебры логики, кроме единицы, может быть представлена в следующей форме:

Символ означает, что конъюнкция берется только по тем наборам для которых выполняется равенство

Переходим к доказательству соотношения (1-34). Имеем:

или

Как известно, равенство не нарушается, если от обеих его частей взять отрицание:

К правой части теперь можно применить соотношение

К конъюнкциям применим формулу де Моргана (1-15):

На тех наборах, для которых

соответствующая дизъюнкция

Такие наборы в силу (1-11) на значение конъюнкции не влияют, и ими можно пренебречь:

Теорема доказана для всех Для функции тождественно равной нулю, на основании (1-13) имеем:

Теорема полностью доказана.

Представление функции алгебры логики в виде (1-34) носит название конъюнктивной совершенной нормальной формы (КСНФ).

Из сравнения (1-28) и (1-34) вытекает, что

при условии, что

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

Из теоремы 1-5 вытекает алгоритм построения КСНФ:

1. Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в нуль.

2. Выписать дизъюнкции, соответствующие этим наборам аргументов. При этом, если аргумент входит

в данный набор как 0, он вписывается без изменения в дизъюнкцию, соответствующую данному набору. Если же входит в данный набор как 1, то в соответствующую дизъюнкцию вписывается его отрицание.

3. Все полученные дизъюнкции соединяются между собой знаками конъюнкций.

Пример 1-7. Написать КСНФ для функции, заданной следующей таблицей:

Как следует из алгоритмов построения ДСНФ и КСНФ, выбор той или иной формы аналитической записи определяется видом таблицы заданной функции. Если большинство значений данной функции нулевое, то выгодно записывать ее в ДСНФ, в противном случае более экономную запись дает КСНФ.

Если вместо конъюнкции в (1-34) использовать функцию эквивалентности, то мы получим представление в форме (1-29). Для функции из примера 1-7 это представление имеет следующий вид:

Характеристические функции и Ф» мсгут быть выражены через функции, отличные от конъюнкции и отрицания или дизъюнкции и отрицания. Можно, например, выразить их с помощью отрицания и импликации.

Теорема 1-6. Любая функция алгебры логики, кроме тождественной единицы, может быть представлена в следующей форме:

Для доказательства заметим, что для любого набора значений аргументов для которого найдется в конъюнкции импликация

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

При желании в (1-35) можно заменить конъюнкцию импликацией и отрицанием на основании (1-19):

Пример 1-8. Пусть задана функция таблицей

Записать эту функцию в импликативной форме. Составляем импликативные функции

Записываем фуякцшо в форме (1-35):

После применения (1-19) получим:

Импликативная форма записи (1-35) является аналогом КСНФ. Аналогом ДСНФ является вторая форма импликативной записи.

Теорема 1-7. Любая функция алгебры логики, кроме тождественного нуля, может быть представлена в следующей форме:

Для доказательства справедливости (1-36) достаточно заметить, что функции

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

При желании дизъюнкция в (1-36) может быть заменена через импликацию и отрицание на основании (1-19):

Пример 1-9. Записать в форме (1-36) функцию

Выписываем функции Для наборов, на которых

На основании (1-36) получаем:

или, применяя (1-19),