Полные системы операций. алгебра жегалкина

Совокупность операций a именуется полной, в случае если каждая логическая операция возможно представлена формулой над a.

Так как любая формула возможно представлена приведенной формулой, то совокупность a0 = {U, U, } — полна.

Совокупность a сводится к a*, обозначается a®a*, в случае если все операции совокупности a* представимы формулами над совокупностью a. В случае если a* полна, то и a полна.

Последнее утверждение даёт один из способов доказательства полноты совокупности операций – сведение её к известной полной совокупности, к примеру к a0. Другими словами полной будет совокупность a, через операции которой возможно выразить конъюнкцию, отрицание и дизъюнкцию.

Так в силу законов де Моргана, полными будут и совокупности a1 = {U , } и a2 = {U, }.

Алгебра над множеством логических функций с двумя операциями U и A именуется алгеброй Жегалкина. В алгебре Жегалкина выполняются следующие соотношения:

, ,

, ,

и ассоциативность, коммутативность, свойства констант и идемпотентность конъюнкции.

Задание. Доказать полноту совокупности a5 = {U, A}.

Ответ. Сведем совокупность a5 к полной совокупности a0.

.

В случае если в произвольной формуле алгебры Жегалкина, реализующей булеву функцию f, раскрыть скобки и произвести все вероятные упрощения, то окажется формула, имеющая вид суммы произведений, другими словами полинома по mod 2. Такая формула именуется полиномом Жегалкина для данной функции. Линейной именуется функция, полином Жегалкина которой линеен.

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

Совокупность булевых функций F именуется полной, в случае если каждая функция возможно реализована формулой над F.

Замыканием множества F (обозначается [F]) именуется множество всех булевых функций, реализуемых формулами над F. Класс функций именуется замкнутым, в случае если [F] = F.

Примеры замкнутых классов.

1. Класс функций, сохраняющих 0.

.

2. Класс функций, сохраняющих 1.

.

3. Класс самодвойственных функций.

.

4. Класс монотонных функций.

, где

.

5. Класс линейных функций.

.

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

Функция Принадлежность классу
T0 T1 T* T? TL
+ — — + — + — + — — + — + + — + + + + —

Замкнутые классы попарно разны, не безлюдны и не совпадают с .

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

Подтверждение.

Необходимость. Предположим неприятное, т.е. совокупность булевых функций F полна ( [F] = ) и входит в один из замкнутых классов ( F U F U U F U F U F ). Обозначим через Ti тот класс, для которого справедливо включение F . Тогда [F] = , что противоречит тому, что ни один из классов не сходится с .

Достаточность. Пускай совокупность булевых функций F содержит хотя бы по одной функции, не принадлежащих каждому из замкнутых классов. Т.е. $ F¢ = , причем функции не обязательно разны и не обязательно исчерпывают F. Продемонстрируем, что конъюнкция и отрицание, каковые образуют полную совокупность булевых функций, реализуются формулами над F¢.

1) Совершим сначала построение запасных формул над F¢. Реализуем константы 0 и 1, каковые будут употребляться в формуле для конъюнкции.

Для реализации 1 воспользуемся функцией . Обозначим . Так как , то . В случае если , то вероятны 2 случая:

a) и тогда реализует 1;

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

Константа 0 строится подобно с применением функции .

2) Для построения формулы, реализующей функцию отрицания, воспользуемся немонотонной функцией . Так как , то , такие что . Неравенство свидетельствует, что или соответствующие координаты векторов , совпадают, или и . Так как , то , а, следовательно, найдутся такие индексы, что . Обозначим через I множество таких индексов. Определим функцию , где , в случае если , и , в случае если . Вычислим значение функции в 0 и 1: , . Так как , то , а это указывает, что .

3) Для построения формулы, реализующей конъюнкцию, будем применять нелинейную функцию . Так как , то её полином Жегалкина содержит слагаемое, являющееся конъюнкцией, по крайней мере, двух переменных. Выберем произвольное слагаемое, содержащее мельчайшее число переменных пускай это . Разглядим функцию, взятую заменой всех переменных, не вошедших в данный комплект, нулями, т.е. . Её полином Жегалкина имеет форму

. Разглядим функцию

, где , , . Определим функцию

,

Такое представление корректно, поскольку являются константами 0 либо 1, определенными ранее формулами над F¢, а сложение по модулю 2 с константой дает или функцию, или её отрицание, которое кроме этого выражено формулой над F¢. Преобразуем , воспользовавшись понятием c,

. Так, функция реализует конъюнкцию.

Выводимость

Пускай задано множество формул от высказывательных переменных

( ), ( ), . . . , ( ). (1)

Это множество формул назовем совокупностью посылок.

Определение.Формула ( ) именуется выводимой из совокупности формул (1) в алгебре высказываний, что обозначается , . . , u- , тогда и лишь тогда, в то время, когда формула

(2)

есть ТИ-высказыванием, т.е. u= .

Из определения направляться, что в случае если конъюнкция

(3)

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

В случае если формула выводима из совокупности формул (1), то из истинности всех формул совокупности при некоторых значениях высказывательных переменных направляться истинность формулы при тех же значениях переменных.

Нетрудно доказать следующие особенности выводимости.

1. В случае если u- и u- то u- .

2. В случае если u- и ~ , то u- .

Проверка выводимости формулы из совокупности посылок (1) конкретно по определению, т.е. методом доказательства тождественной истинности формулы (2), достаточно громоздко. Разглядим более несложный метод доказательства выводимости формулы из совокупности посылок (1), для которых конъюнкция (3) не есть ни ТИ-высказыванием, ни ТЛ-высказыванием.

Теорема 7.1. Формула ( ) тогда и лишь тогда выводима из совокупности формул (1), в то время, когда все полные элементарные дизъюнкции формулы входят в СКН-форму , эквивалентную формуле (3) довольно высказывательных переменных .

Так как теорема 1 формулирует нужное и достаточное условие выводимости формулы, то на базе нее возможно сформулировать метод доказательства выводимости формулы.

1. Из совокупности посылок (1) строится конъюнкция (3).

2. Находим СКН-форму от высказывательных переменных для формулы (3).

3. Строим СКН-форму для формулы и контролируем вхождение полных элементарных дизъюнкций СКН-формы для формулы в СКН-форму для формулы (3).

Задание 1. Доказать выводимость u- .

Ответ.

1. Обозначим = X, = . Строим их конъюнкцию .

2. Отыщем СКН-форму эквивалентную данной конъюнкции.

V

3. Возьмём СКН-форму для формулы B .

Так как обе дизъюнкции входят в СКН-форму , то выводимость доказана.

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

Помимо этого, воспользовавшись теоремой 1, возможно выстроить все СКН-формы выводимые из данной совокупности посылок. Для этого требуется маленькая модификация метода доказательства выводимости формулы. По окончании построения СКН-формы для формулы (3) нужно

3°. Из полных элементарных дизъюнкций взятой СКН-формы строим разные комбинации конъюнкций. Эти конъюнкции и будут исчерпывать все СКН-формы, выводимые из совокупности посылок (1).

Лекция 14: Многочлены Жегалкина


Также читать:

Понравилась статья? Поделиться с друзьями: