DisMathTPU

151

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

Начнем с функции f0: по лемме о функции, не сохраняющей константу 0, подстановкой вместо аргументов функции переменной x получим либо

константу 1, либо x.

Проанализируем первый случай (верхняя ветвь схемы). Имея константу 1 и подставляя ее вместо каждого аргумента функции f1, получим кон- станту 0. Затем по лемме о немонотонной функции, подставляя в функцию fM вместо аргументов полученные константы и переменную x, получим x. Таким образом, инверсия выражена суперпозицией функций f0, f1 è fM .

Перейдем ко второму случаю (нижняя ветвь схемы). Инверсия уже по- лучена из функции f0. По лемме о несамодвойственной функции, подста-

âëÿÿ â fS вместо аргументов переменную x и ее инверсию x, получим либо константу 0, либо константу 1. Если имеем константу 0, то, подставляя

ее вместо каждого аргумента функции f0, получим константу 1 (средняя ветвь). Если имеем константу 1, то, подставляя ее вместо каждого аргу- мента функции f1, получим константу 0 (нижняя ветвь).

Таким образом, следуя по любой из трех ветвей схемы, мы получаем константы 0 и 1 и инверсию. Далее по лемме о нелинейной функции, подставляя в функцию fL константы 0 и 1, переменные x, y и их инверсии x, y и, возможно, инвертируя саму функцию, получим конъюнкцию xy.

Итак, мы показали, что конъюнкция и инверсия представимы суперпозицией функций из N, значит, N ÔÏÑ.

Пример 1. Ранее мы получили, что N1 = f#g является ФПС, значит, по теореме Поста-Яблонского стрелка Пирса не должна принадлежать ни одному из замкнутых классов, и это действительно так.

152

Пример 2. Как показано в таблице непринадлежности элементарных функций замкнутым классам, штрих Шеффера, как и стрелка Пирса, не принадлежит ни одному замкнутому классу, значит, N2 = f=g ÔÏÑ.

Пример 3. Рассмотрим множество N3 = f0; !g. Импликация принад- лежит только классу T 1, поэтому вместе с константой 0, не принадлежащей

этому классу, образует ФПС N3.

Пример 4. Рассмотрим теперь множество неэлементарных булевых функций N4 = ff; gg.

x y z f(x; y; z) g(x; y; z)

Непринадлежность функций f è g пяти замкнутым классам представлена таблицей (мажоритарная функция f рассматривалась нами в примерах к пяти замкнутым классам, исследование функции g оставляем читателям).

T 0 T 1 L S M

Так как обе функции являются самодвойственными, то система N4 íå ÿâëÿ- ется функционально полной. Но если к ней добавить несамодвойственную функцию, например, константу 1, то получим ФПС N5 = ff; g; 1g.

16.2. Упражнения

Упр. 1. Используя теорему о двух ФПС, показать, что системы функций являются функционально полными:

N1 = fx yz; 0g,

N3 = fx ,! y; x y zg,

N2 = fx ! (y ! z)g, N4 = fx ! y; 0g.

153

Упр. 2. Исследовать функцию g(x; y; z) из последнего примера на ее непринадлежность пяти замкнутым классам.

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

N1 = fFf = x ! y; Pg = x y zg,

Упр. 4. Какие элементарные булевы функции необходимо добавить в системы, чтобы они стали функционально полными? Не использовать штрих Шеффера и стрелку Пирса.

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

154

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

17. Контрольная работа 5

Темы контрольной работы: полиномы Жегалкина, замкнутые клас-

8 подстановка кратчайших ДНФ элементарных функций

9 разложение Шеннона

10 подстановка полиномов Жегалкина элементарных функций

11 разложение Дэвио

Схема контрольной работы (решение каждой из 20 предложенных здесь задач начинать с постановки задачи и делать вывод из сравнения полиномов Жегалкина, полученных разными способами; F означает фор-

мулу без лишних скобок, (F ) с недостающими скобками).

155

Задание на контрольную работу (формула F )

Пример. Задана формула

F= x # z x y:

0)Расставим скобки в формуле F .

(F ) = (x # z) (x y):

1) Построим таблицу истинности функции f(x; y; z) по формуле (F ). x y z (x # z) (x y) f

2) Построим матрицу Грея по таблице истинности.

y z

x

3) Получим кратчайшую ДНФ функции по ее матрице Грея.

x@ @

R@IR@3 I1

156

4) Получим полином Жегалкина функции по кратчайшей ДНФ.

КратДНФ = x _ y z _ y z =

[ дизъюнкцию пары ортогональных конъюнкций y z _ y z заменим на их дизъюнкцию с исключением ]

= x _ (y z y z) =

[ применим равносильность A1 _ A2 = A1 A2 A1A2 ïðè A1 = x,

A2 = y z y z ]

= x y z y z x (y z y z) = x y z y z x y z x y z =

[ заменим каждую переменную с инверсией a равносильной формулой a 1, раскроем скобки и удалим пары одинаковых конъюнкций ]

Конъюнкции здесь и во всех последующих задачах пронумерованы согласно представлению полинома Жегалкина в форме с коэффициентами.

5) Получим совершенную ДНФ по таблице истинности.

СовДНФ = x y z _ x y z _ x y z _ x y z _ x y z _ x y z:

6) Получим полином Жегалкина по совершенной ДНФ.

СовДНФ = x y z _ x y z _ x y z _ x y z _ x y z _ x y z =

[ заменим все знаки дизъюнкции на знаки дизъюнкции с исключением ]

= x y z x y z x y z x y z x y z x y z =

[ заменим каждую переменную с инверсией a равносильной формулой a 1, раскроем скобки и удалим пары одинаковых конъюнкций ]

=(x 1) (y 1) z (x 1) y (z 1) x (y 1) (z 1)

x (y 1) z x y (z 1) x y z =

157

7) Получим полином Жегалкина по таблице истинности . Используем метод неопределенных коэффициентов, последовательно вычисляя коэффициенты полинома и подставляя их в остальные уравнения. Вектор коэффициентов полинома выпишем под таблицей.

8) Получим ДНФ0 по формуле (F ) подстановкой кратчайших ДНФ элементарных булевых функций.

(F ) = (x # z) (x y) = (x # z)(x y) _ (x # z) (x y) =

= x z x y _ (x _ z)(x _ y) = x y z _ x _ x y _ x z _ y z = = x y z _ x _ y z = ÄÍÔ0:

40) Получим полином Жегалкина функции по ДНФ 0 (как в задаче 4).

9) Получим ДНФ00 по формуле (F ) разложением Шеннона.

(F ) = (x # z) (x y) = x[(1 # z) (0 y)] _ x [(0 # z) (1 y)] =

= x [0 0] _ x [z y] = x _ x [z(1 y) _ z(0 y)] = = x _ x y z _ x y z = ÄÍÔ0:

400) Получим полином Жегалкина функции по ДНФ 00 (аналогично зада- че 4 и учитывая, что все конъюнкции попарно ортогональны).

159

12 15) Определим, принадлежит ли функция замкнутым классам T 0, T 1, S è M, по таблице истинности.

x y z f(x; y; z)

Число единиц в столбце значений функции не равно числу нулей, значит, выполняется достаточное условие несамодвойственности, f(x; y; z) 2= S.

16)Определим, принадлежит ли функция классу L по полиному Жегалкина. P = z y x xz xy, степень полинома равна двум, значит, функция нелинейна, f(x; y; z) 2= L.

17)Определим, образует ли функция f(x; y; z) функционально полную

систему. Из задач 12) 16) следует, что вектор непринадлежности функции

замкнутым классам имеет вид:

T 0 T 1 L S M

Функция не образует функционально полную систему по теореме ПостаЯблонского, так как принадлежит классам T 0 è T 1.

160