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

Если F(X) нелинейна, то из нее путем подстановки вместо аргументов-констант переменных (x, y, not x, not y) иожно получить: конъюнкцию этих переменных, дизъюнкцию этих переменных, отрицание конъюнкции, отрицание дизъюнкции.

F = 1 + x1+x3+x1x3+x1x2x3 = x1x3(1+x2) +x3+x1+1

F(x1,0,x3) = x1x3+x3+1

___

F(x0y) = (xy)

Лекция 9: «Продолжение темы Классы функций»

Доказательство леммы 3

F(x₁…x_n) = x₁x₂ (f1(x₁…x_n)) + x₁f₂(x₁…x_n) + x₂f₃(x₁…x_n) + f₄(x₁…x_n)

Вместо x₁…x_n ставим константы a₁…a_n, такие, что

f1(a₁…a_n) = 1

1. A = B = 0

F(x₁x₂…a₃…a_n) = x₁x₂ + C = {x₁x₂, если с = 0 и NOT(x₁x₂, если с = 1)

Аналогично получаем дизъюнкцию и ее отрицание.

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

Система функций полна тогда и только тогда, когда она не находится ни в одном из пяти важнейших замкнутых классов, а именно S, M, L, T₀, T₁.

1. Необходимо.

Дана полная система функций. Отсюда следует, что она не принадлежит никакому замкнутому классу (см. выше).

Доказательство следует из того факта, что по определению и по тому, что мы доказали, что все важнейшие классы замкнуты. Если предположить, что система целиком входит в один из замкнутых классов, то

[S] = [B] = B

Но S - множество всех булевых функций, а B – не всех.

Получили противоречие.

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

Дано

S Ë {S, M, L, T₀, T₁}

Каждая функция (f с индексами 1…5) не принадлежит каждому соответствующему ей важнейшему замкнутому классу.

1. Получение констант.

F1(00…0) = 1

a) F(111) = 1

b) F(111) = 0

F(xxxx) = 1

F2(111) = 0

2. Получение отрицаний

Из F4 по лемме 2 мы можем получить отрицание.

3. Используя F5 по лемме 3 получаем xy, x V y, not(xy), not(x V y)

Лекция 10: «Функциональные элементы. Логические схемы»

.

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

Каждый вход – аргумент функции.

Выход – булева функция от аргументов.

Из функциональных элементов можно строить по правилам их соединения схемы (логические сети).

Два и более входов можно отождествлять.

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

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

Число функциональных переменных считаем сколь угодно большим.

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

Очевидно, чтобы базис был полным, необходимо и достаточно, чтобы система функций, реализуемых элементами базиса, была полной.

Пример полного базиса.

- Конъюнктор

- Дизъюнктор

- Инвертор

Чтобы построить минимальную функциональную схему для функции на конъюнкторах, дизъюнкторах и инверторах, которая реализует эту функцию, нужно

1. Найти минимальную ДНФ.

2. Для любой из минимальных ДНФ (их может быть много) попробовать упростить формула с помощью вынесения за скобки общего множителя.