Методические рекомендации по изучению дисциплины (стр. 7 )

Упражнение 1.7.11 Н. Ф. представляющую функцию f:

а) ;

б) .

Всякую формулу А над В от можно посредством равносильных преобразований привести к Д. Н.Ф. (К. Н.Ф.), придерживаясь следующих предписаний:

1) используя равносильности. Выражающие одни элементарные функции через другие, приводим А к формуле , в которую входят только элементарные функции &; ; ;

2) используя законы де Моргана и закон двойного отрицания, приводим к формуле , в которой отрицание может действовать только на подформулы сложности 0 (т. е. на переменные);

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

Исходя из транзитивности отношения «», получаем:

.

Пример 1.7.9 Приведём формулу

посредством равносильных преобразований к Д. Н.Ф. (К. Н.Ф.).

1) для исключения операций воспользуемся равносильностями:

1.1 ;

1.2 ;

1.3

1.4 .

В рассматриваемом примере применение этих равносильностей даёт

1.1 ;

1.2 ;

1.3 ;

1.4 .

Таким образом,

.

2) Применение законов де Моргана и законов двойного отрицания даёт 2.1 ;

2.2 ;

2.3 .

Таким образом,

.

3) а) Для преобразования формулы в логическую сумму конъюнкций (т. е. к Д. Н.Ф.) применяем закон

3.1 .

Таким образом,

искомая Д. Н.Ф.

б) Для преобразования формулы в логическое произведение дизъюнкций (т. е. к К. Н.Ф.) применяем закон

3.2 .

Таким образом,

искомая К. Н.Ф.

Упражнение 1.7.12 Привести формулу А к Д. Н.Ф. (К. Н.Ф.)

а) ;

б) .

Используя равносильные преобразования от Д. Н.Ф. (К. Н.Ф.) А, можно перейти к С. Д.Н. Ф. (С. К.Н. Ф.):

а) Последовательность действий при переходе от Д. Н.Ф. к С. Д.Н. Ф.:

а.1 основываясь на равносильностях ; и , удаляем из данной Д. Н.Ф. те логические слагаемые(конъюнкции), которые в качестве логических сомножителей входят некоторая переменная и её отрицание ();

а.2 основываясь на законах коммутативности, ассоциативности и идемпотентности функции &, добиваемся того, чтобы каждая из оставшихся (после шага а.1) конъюнкция была преобразована в элементарную конъюнкцию, т. е. чтобы всякая переменная (или её отрицание ) входила бы в каждую из этих конъюнкций не более одного раза и чтобы переменные (или их отрицания) следовали в каждой из этих конъюнкций в порядке возрастания номеров;

а.3 если (после шага а.2) имеется конъюнкция К, ранг которой строго меньше n и ни переменная ни её отрицание не входят в К в качестве логического сомножителя (), то, основываясь на цепочке равносильностей

,

заменяем её на две новых элементарных конъюнкции и большего (на 1) ранга.

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

а.4 используя закон идемпотентности операции , удаляем элементарные конъюнкции.

Пример 1.7.10 Н.Ф.

к С. Д.Н. Ф., используя равносильные преобразования.

а.1 Удаляем из А конъюнкции , т. к.в первую из них входят и , а во вторую и .

Таким образом,

.

а.2 Удаляя из конъюнкции повторяющиеся сомножители и и располагая сомножители в порядке возрастания номеров переменных, получим:

.

а.3 Ранги элементарных конъюнкций и равны 2и 1 соответственно, т. е. каждую из них нужно преобразовать в логическую сумму элементарных конъюнкций ранга 3:

а.4 Вставляя в А вместо конъюнкции равносильную ей сумму двух элементарных конъюнкций ранга 3, а вместо конъюнкции - сумму четырёх элементарных конъюнкций ранга 3 и, удаляя повторяющиеся слагаемые, в итоге получим:

- С. Д.Н. Ф., равносильная формуле А.

Упражнение 1.7.13 Ф. А к С. Д.Н. Ф.

а)

б) .

б) Последовательность действий при переходе от К. Н.Ф. к С. К.Н. Ф.:

б.1 Основываясь на равносильностях ; ; , удаляем из данной К. Н.Ф. те логические сомножители (дизъюнкции), в которые в качестве логических слагаемых входят некоторая переменная и её отрицание ();

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

б.3 если (после шага б.2) имеется дизъюнкция Д, ранг которой строго меньше n и ни переменная ни её отрицание не входят в Д в качестве логического слагаемого (), то, основываясь на цепочке равносильностей

,

заменяем её на две новых элементарных дизъюнкции большего (на 1) ранга.

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

б.4 используя закон идемпотентности операции &, удаляем элементарные конъюнкции.

Пример 1.7.10 Н.Ф.

к С. К.Н. Ф., используя равносильные преобразования.

б.1 Удаляем из А конъюнкции и , т. к. в первую из них входят и , а во вторую и .

Таким образом,

.

б.2 Удаляем из дизъюнкции повторяющиеся сомножители и и, располагая слагаемые в порядке возрастания номеров переменных, получим:

.

б.3 Ранги элементарных дизъюнкций и равны 2 и 1 соответственно, каждую из них нужно преобразовать в логическое произведение элементарных дизъюнкций ранга 3:

Упражнение 1.7.14 Ф. А к С. К.Н. Ф.

а)

б)

Упражнение 1.7.15 Доказать, что число различных С. Д.Н. Ф. (С. К.Н. Ф.) над равно

Упражнение 1.7.16 Доказать, что С. Д.Н. Ф. (С. К.Н. Ф.) над содержит не более вхождений переменных из .

Упражнение 1.7.17 Выписать все С. Д.Н. Ф. над . Определить, какие из них будут существенными, а какие – нет.

1.8 Полиномы Жегалкина

Элементарная конъюнкция К над называется монотонной, если она не содержит отрицаний переменных.

Монотонной элементарной конъюнкции поставим в соответствие набор ,

определённый по правилу:

.

Пример 1.8.1 монотонной элементарной конъюнкции над соответствует набор .

Номером монотонной элементарной конъюнкции назовём номер набора , соответствующего этой конъюнкции. Логическая константа 1 получит в этой нумерации номер 0.

Упражнение 1.8.1 Доказать, что число различных монотонных конъюнкций над равно .

Формула вида , где - попарно различные монотонные элементарные конъюнкции над , называется полиномом Жегалкина (или полиномом по модулю 2) над . Наибольшим из рангов элементарных конъюнкций, входящих в А называется степенью полинома, а число t его длиной.

Упражнение 1.8.2 Найти число различных полиномов Жегалкина над множеством переменных .

Упражнение 1.8.3 Доказать, что элементарные функции

представимы полиномами Жегалкина

.

Упражнение 1.8.4 Доказать, что всякая функция алгебры логики представима посредством полинома Жегалкина единственным образом.

Посредством элементарных преобразований полином Жегалкина для формулы А можно найти придерживаясь следующих предписаний:

1) исключая из формулы А функции (смотри упражнение 1.8.3) приводим эту формулу к равносильной ей формуле , содержащей только функции и логические константы 1; 0.

2) используя равносильности ; , коммутативность и ассоциативность операции &, преобразуем формулу равносильным образом к формуле , являющейся полиномом Жегалкина.

Пример 1.8.2 Найдём полином Жегалкина, раносильный формуле ,

используя равносильные преобразования.

1)

2)

- полином Жегалкина.

Пусть - множество всех монотонных элементарных конъюнкций над (i – номер конъюнкции ). Тогда всякий полином Жегалкина А над можно единственным образом записать в виде:

, (1)

где ( - коэффициенты этого полинома, .

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

.

Для каждого набора составляем уравнение вида

.

Всего получим уравнений от неизвестных . Решая эту систему, находим коэффициенты.

Пример 1.8.3 Методом неопределённых коэффициентов найдём полином Жегалкина .

Записываем полином в виде (1):

.

Здесь в связи с нумерацией монотонных элементарных конъюнкций:

Т. е.

Переходим от векторного к табличному заданию функции

0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

Таблица 15

Соответствующая система уравнений будет иметь вид:

Из этой системы последовательно находим:

Таким образом:

.С целью самоконтроля найдём методом элементарных преобразований. Н. Ф., представляющую функцию f и преобразовываем её:

, т. е получили тот же самый результат.

Упражнение 1.8.5 Доказать, что если в С. Д.Н. Ф. А символ во всех местах его вхождения в А заменить на , то получится формула, равносильная исходной.

Основываясь на упражнении 1.8.5, получаем ещё один способ нахождения полинома Жегалкина , представляющего функцию :

1) находим С. Д.Н. Ф. , представляющую функцию ;

2) заменяем символ во всех его вхождениях в на ;

3) заменяем каждую подформулу вида , входящую в на ;

4) применяем обобщённый закон дистрибутивности & относительно .

Пример 1.8.4 Найдём полином Жегалкина , представляющий функцию .

Переходя к табличному заданию, получим:

0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

Таблица 16