Теория Автоматов Конечные функциональные преобразователи Конечные функциональные преобразователи

Замкнутые классы булевых функций Решение проблемы нахождения любых других базисов булевых функций, отлич­ных от указанных в табл. 1.5, было найдено Эмилем Постом в 1921 году на пути изучения замкнутых классов таких функций. Множество М булевых функций называется замкнутым классом, если [М] = М. Мы уже встречали замкнутые клас­сы булевых функций: например, [{ИДЕНТ, НЕ}] = {ИДЕНТ, НЕ}. Другие приме­ры (а) множество всех конъюнкций от различного числа аргументов, (б) множе­ство всех дизъюнкций от различного числа аргументов. Существует множество разных замкнутых классов функций. Э. Постом было выделено пять таких клас­сов, на основе которых им была решена проблема базисов булевых функций. Ниже для каждого такого класса вводится его определение, примеры и формулируется теорема о том, что множество функций, обладающих указанным свойством С, со­ ставляет замкнутый класс

Замкнутые классы булевых функций. Доказать эти теоремы просто, доказательство основано на простой индукции по глубине суперпозиции функций. Базу индукции состав­ляет утверждение о том, что тождественная функция обладает указанным свой­ством С, а шаг индукции что если произвольная функция f (x1,x2,...,xm) обла­дает свойством С и все функции F^,...,^ обладают свойством С, то функция f (F1,F2,...,Fm) тоже обладает свойством С. Более подробно о замкнутых классах можно прочитать в [23].

Замкнутые классы булевых функций Определение 1.6. Функция f (x1,x2,...xm) сохраняет ноль, если f(0,0,...,0) = 0. Примером функции, сохраняющей ноль, является конъюнкция. Отрицание не со­храняет ноль. Функция f (p, q, r) = -ipvq®rq(pvr) примера 1.2 не сохраняет ноль; из табл. 1.3: f (0,0,0) = 1. Обозначим М0 множество всех функций, сохраняющих ноль. НФ Теорема [М0] = М0. Определение 1.7. Функция f(\l9\2,...,xm) сохраняет единицу, если f(l,l,...,l) = l. Примером функции, сохраняющей единицу, является конъюнкция. Отрицание не сохраняет единицу. Функция f (p, q, г ) = -пр v q © rq (p v r ) примера 1.2 не сохраня­ет единицу; из табл. 1.3: f (1,1,1) = 0. Обозначим Mt множество всех функций, со­храняющих единицу

Замкнутые классы булевых функций Теорема 1.7. [М1] = М1. Введем отношение порядка на множестве двоичных наборов. тогда и только тогда, когда для любого 1 < i < m, выполняется х{ < у,. Функциональная полнота 27 Определение 1.8. Функция f (x1,x2,...xm) называется монотонной, если для лю­бых двух наборов и ) выполнение,,,к..> (х1,х2,...,хт) и ) выполнение,,,к..> (х1,х2,...,хт)

Замкнутые классы булевых функций Определение 1.9. Функция f (x1}x2,...,xm) называется самодвойственной, если для любого набора, f(-ix,,x2,...,-ixm) = -if(x1,x2,...,xni). Примером самодвойственной функции является отрицание. Конъюнкция не яв­ляется самодвойственной функцией. Функция f (p, q, r) = - npvq0rq(pvr) при­мера 1.2 не является самодвойственной. Действительно, из табл. 1.3: f(0,0,l) = f(UO) = l. Обозначим Мсам множество всех самодвойственных функций. Теорема 1.9. [Мсам] в Мсам.

Замкнутые классы булевых функций Определение Функция f(x1,x2,...,xm) называется линейной, если ее полином Жегалкина имеет вид а0 0 Еах1х}. Примером линейной функции является отрицание (представляемое как -ix = 10х). Дизъюнкция не является линейной функцией: ранее мы видели, что pvq = p0q0pq. Функция f (p, q, r) = -ipvq®rq(pvr) примера 1.2 не является линейной: ранее мы видели, что f (p, q, г) = 10 р 0 pq 0 qr. Обозначим Мли множе­ство всех линейных функций. Теорема [Млин] - Млин.

Теорема Поста Рассмотрим теперь, как определить, является ли некоторое произвольное множе­ство двоичных функций базисом. Теорема 1.11 (теорема Поста). Для того чтобы множество N двоичных функций было базисом, то есть 1. N содержало бы по крайней мере одну функцию, не сохраняющую ноль: N(ZM0, и *'--: 2. N содержало бы по крайней мере одну функцию, не сохраняющую единицу: N(2M,,H 3. N содержало бы по крайней мере одну немонотонную функцию: N£MMOH,H 4. N содержало бы по крайней мере одну несамодвойственную функцию: N(ZMcaM, и 5. N содержало бы по крайней мере одну нелинейную функцию: N £ Млин.

Теорема Поста Необходимость. Нужно доказать, что если N базис, то все условия выполняют­ся. Это элементарно доказывается от противного: если хотя бы одно условие не выполняется, то [N] ^ В. Действительно, пусть N является подмножеством какого- нибудь замкнутого класса из перечисленных пяти. Тогда, очевидно, замыкание N не может включать все функции из В: ни один из этих классов не полон. Напри­мер, пусть нарушается условие 2, то есть N не содержит ни одной функции, не сохраняющей единицу (все входящие в N функции сохраняют 1). Но все функции, сохраняющие 1, составляют замкнутый класс: их суперпозицией нельзя построить ни одной функции, не сохраняющей 1 (теорема 1.7). Поскольку В содержит и функ­ции, не сохраняющие 1, то суперпозицией функций из N нельзя построить все функции из В, то есть [N] Ф В. Необходимость доказана

Теорема Поста Это доказательство проведем конструктивно по следующей схеме: покажем не­посредственно, как из функций множествам построить функции базиса (конъюнк­тивного или дизъюнктивного). Схема доказательства (и, соответственно, построения функций) имеет следующий вид (рис. 1.10). Это доказательство проведем конструктивно по следующей схеме: покажем не­посредственно, как из функций множествам построить функции базиса (конъюнк­тивного или дизъюнктивного). Схема доказательства (и, соответственно, построения функций) имеет следующий вид (рис. 1.10).

Теорема Поста

Поясним схему. Пусть в соответствии с условием теоремы Поста множество N имеет функцию, не сохраняющую 0, функцию, не сохраняющую 1, не самодвойственную, немонотонную и нелинейную функции (все эти функции не обязательную, но различны). В соответствии со схемой, из первых трех функций мы на первом шаге можем построить константы 0 и 1, из констант и немонотонной функции на втором шаге строим функцию НЕ, а на третьем из отрицания, констант и нелиней­ной функции можем построить конъюнкцию или дизъюнкцию. Перейдем к дока­зательствуШаг 1. Пусть F0 не сохраняет 0 (то есть F0(0,..., 0) - 1), F{ не сохраняет 1 (то есть Fj(l,..., 1) в 0), a Fn несамодвойственная. Рассмотрим различные варианты, its Пусть F0 при этом сохраняет единицу (то есть F0(l,..., 1) == 1). Тогда при любом х ф(х) - F0(x,..., х) = 1 и р!(ф(х),..., ф(х)) = Fi(l,..., 1) = 0, то есть получили иско­мые функции- константы

Теорема Поста Пусть теперь F0 не сохраняет единицу, то есть F0(l,..., 1) =* 0. Но тогда w t\s{: ^ F0(x,...,х) = -.х. Имея отрицание, с помощью не самодвойственной функции легко получить кон­станту. Действительно, поскольку Fn функция не самодвойственная, то найдет­ся набор (аь а2,..., ат) такой, что Рп(аь а2,..., ат) - Fn(-nai, -ia2l..., -iam) - Const, где Const либо 0, либо 1. Подставим вместо а} в Рп х, если а{ = 1, и -ix, если с, = 0. Выход этой функции при любом х будет Const. Инвертировав Const с помощью отрицания, получим другую константу. Пример 1.11 Функция f, заданная табл. 1.3, не сохраняет ноль (f (0,0,0) = l) и не сохраняет еди­ницу (f (1,1,1) = 0). Следовательно, f (х,х,х) = -.х. Она же является несамодвойственной (существует два противоположных набора значений аргументов, на ко­торых значения f равны: f (0,0,1) = f (1,1,0) = 1. Тогда f (x,x,-ix) = 1, а -if (x,x,-ix) = 0 при любом х

Теорема Поста Использовав f(x,x,x) = -iX, получаем: f(x,x,f(x,x,x)) = l, а f(f(x,x,f(x,x,x))), f(x,x,f(x,x,x)), f(x,x,f(x,x,x)) = 0 при любом х. Шаг 2. Пусть F немонотонная функция. Покажем, как с помощью констант мож­но построить отрицание. В немонотонной функции всегда существует «единич­ный интервал» немонотонности, то есть пара соседних наборов (at,..., О,..., am) и (at,..., l,...,am), на которых F меняет значение: F(a1,...,О,...,am) = l и f(g!,..., 1,..., am) = 0. Подставив вместо

Теорема Поста Пример 1.12 Функция f, заданная табл. 1.3, немонотонна. Один из ее «единичных интерва­лов» немонотонности пара наборов (О, 1, 0) и (О, 1, 1), поскольку f (0,1,0) = 1 и f(0,l,l) = 0. Очевидно поэтому, что f (0,l,x) = -iX. Диаграмма Хассе, представля­ющая все пары соседних наборов и значения функции f на них, показана на рис Единичные интервалы немонотонности функции f выделены жирны­ми линиями. ШагЗ. Пусть F нелинейная функция. Покажем, как с помощью констант и отри­цания из нее можно построить конъюнкцию. В нелинейной функции при разло­жении ее в полином Жегалкина всегда существуют термы, содержащие произве­дения переменных. Выберем самый короткий такой терм, содержащий не менее двух переменных. Пусть он К = xu, xi2,..., xik. Подставляя в F единицы вместо всех переменных, входящих в К, кроме двух из них, и нули вместо всех переменных F,

Теорема Поста

Рис Диаграмма Хассе двоичных наборов Легко видеть, что с помощью отрицания из всех этих функций можно получить конъюнкцию. Действительно, каждая форма справа является отрицанием соответ­ствующей формы слева, поэтому рассмотрим только четыре левые формы. Первая из них конъюнкция, последняя дизъюнкция х и у. Вторая конъюнкция х-пу, третья конъюнкция-ixy. Итак, достаточность тоже доказана. Пример 1.13 Функция f, заданная табл. 1.3, нелинейна: из примера 1.3 f(p,q,r) = l©p©pq®qr. Выберем один из минимальных термов пусть это будет pq. Тогда f(p,q,0) = l®p®pq. Легко видеть, что это функция -i(p-iq) = - ipvq. Таким образом, pq = -if(p,-iq,0), pvq = f(-ip,q,0). Как результат, только одна эта функция составляет базис, то есть с ее помощью можно построить любую двоич­ную функцию. Очевидно также, что этот базис минимальный.

Теорема Поста Таблица 1.8 показывает, принадлежат ли рассмотренным пяти замкнутым клас­сам известные нам функции. Если функция не принадлежит замкнутому классу, в соответствующей позиции ставится знак V. Для выделения базиса, состоящего из этих функций, нужно найти строки, в совокупности покрывающие все пять стол­бцов знаком V. Кроме уже известных нам базисов, из табл. 1.8 можно найти базис Фреге {импликация, отрицание}, базис Гилберта {импликация, дизъюнкция, константа 0} и т. д.

Теорема Поста Интересный метод нахождения минимального покрытия, основанный на свойствах логических функций, состоит в том, что строится КНФ логической функции Ф, представляющей все возможные покрытия столбцов, и каждый терм дизъюнктив­ной нормальной формы этой функции, полученной, например, простыми преобра­зованиями, дает некоторое покрытие. Для табл. 1.8 функция Ф в форме КНФ име-етвид: vhviv j)&(avcvgvhvi)&(avbvdvevf vgvhvivj). &(cvf vgvhviv j)&(dvevf vhvi). Смысл этой функции очевиден. Каждый дизъюнкт определяет, какими строками может быть покрыт один из столбцов.

Теорема Поста Задача нахождения минимальнопхпокры-тия и анализ возможных минимальных базисов то есть раскрытие скобок и по­лучение минимальной ДНФ этой функции (после применения операций непол­ного склеивания Кх v К-пХ = К v Kx v K-iX и поглощения К v Кх = К) остается чи­тателю в качестве упражнения. Каждый терм минимальной ДНФ дает, очевидно, минимальный базис набор функций, удовлетворяющих всем требованиям тео­ремы Поста.

Теорема Поста Пример 1.15 Рассмотрим, сколько функций может содержать минимальный базис. Очевидно, что самое малое число функций в минимальном базисе одна, это, например, стрел­ка Пирса или штрих Шеффера, или функция f примера Мы знаем минималь­ные базисы из двух функций (например, конъюнктивный базис) и из трех функ­ций (базис Жегалкина). А какое максимальное число функций может содержать минимальный базис? Очевидно, что такой базис содержит не меньше трех и не больше пяти функций. Покажем, что минимальный базис с максимальным числом элементов включает ровно четыре двоичных функции. Действительно, любая функция, не сохраняю­щая 0, например, не может входить во все остальные четыре замкнутых класса, используемых в теореме Поста, она

Теорема Поста либо несамодвойственной. Пусть это функция 1. Она не сохраняет 0 и несамодвойственна. Дру­гая функция, 0, не сохраняет 1 и также несамодвойственна. Проблема сводится к нахождению нелинейной, но монотонной функции, а также линейной, но немо­нотонной функции, причем обе они должны сохранять 0 и 1. Первая это, на­ пример, конъюнкция, вторая линейная функция хфуфг. Таким образом, ис­комым минимальным базисом является {0,l,x&y,x©y0z}, содержащий четыре двоичных функции, и это число функций максимально возможное в минималь­ном базисе.