lec09_1

Лемма 9.4. О нелинейной функции.

Если БФ f (x1,x2,…xn) – нелинейна ( L), то с помощью подстановки вместо переменных x1,x2,…xn величин x, , constant (0 или 1), взятие отрицания от самой функции можно получить конъюнкцию х1 & х2.

(! Возможна формулировка: конъюнкцию или дизъюнкцию).

Доказательство: конструктивно

Представим функцию (x1,x2,…xn) в виде МЖ. Поскольку нелинейна, то найдется в МЖ одночлен – слагаемое, содержащее произведение каких-либо переменных. Пусть, например, х1 & х2. Сгруппируем все слагаемые, содержащие х1 & х2, и вынесем их за скобки. Затем сгруппируем остальные слагаемые, содержащие х1, и вынесем х1 за скобки. Среди остальных сгруппируем слагаемые х2 и вынесем за скобки.

Получим:

(x1,x2,…xn) = х1 х2 0(x3,x4,…xn) х1 (x3,x4,…xn) х2 (x3,x4,…xn)

γ(x3,x4,…xn). 11

Часть 2.

Доказательство теоремы о функциональной полноте.

Теорема 9.1. Поста о функциональной полноте.

Доказательство: .1) продолжение Рассмотрим для а): (x) = f0(x,x…,x). Тогда

(0) = f0(0,0…,0) = 1; (1) = f0(1,1,…,1) = 1. Итак (x) = f0(x,x…,x) 1.

По условию а) f0 T1 и f0(1,1,…,1) = 1.

const «1» получена, то теперь получаем «0». f1 T1 f1(1,1,…,1) = 0.

0 = f1(f0(x,x…,x), f0(x,x…,x), …, f0(x,x…,x)).

Рассмотрим для б): (x) = f0(x,x…,x).

Тогда получаем (0) = f0(0,0…,0) = 1; (1) = f0(1, …, 1) = 0 (x) = .

Применим лемму 9.2 о несамодвойственной функции можно взять fS S, и подставить в нее вместо x1,x2,… xn: x и , и получить const (не ясно «0» или «1»).

Если получаем «0», то const «1» получим так: 1 = (0) = f0(0,0…,0). Если же по лемме 9.2 получаем const «1», то: 0 = (1) = f0(1,1,…,1).

Получили во всех случаях const «0» или «1». Ч.т.д.

19

Теорема 9.1. Поста о функциональной полноте.

Доказательство: . продолжение

2) Покажем, что с помощью функции из можно получить .

Согласно лемме 9.3 о немонотонной функции, взяв fM M, можно, подставив вместо n–1 переменных const (0, 1) (! получены выше), получить .

3) Покажем, что с помощью БФ из можно получить конъюнкцию из x1 & x2.

Согласно лемме 9.3 о нелинейной функции, взяв fL L, можно, подставив в нее вместо переменных x1,x2,… xn: const (0, 1) и, взяв, если нужно, отрицание, получить конъюнкцию x1 & x2.

4) Полнота системы теперь из теоремы 7.1 (о системе сравнения ФПС).

В качестве системы сравнения 1 = {&, } (ФПС 1 доказана – лекция 7.2 Важнейшие ФПС).

Каждая БФ из 1: конъюнкция – x1 & x2 и отрицание – выражаются через БФ системы . – ФПС.