Лемма о нелинейной функции
Лемма о немонотонной функции
Путем подстановки вместо аргументов-констант и переменной х можно получить not(x).
000 £ 001
F(000) = 1 F(001) = 0
F(00X) = NOT(X)
F(100) = 1
F(110) = 0
100 < 110
F(1,x,0) = NOT(X)
Если 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(x1…xn) = x1x2 (f1(x1…xn)) + x1f2(x1…xn) + x2f3(x1…xn) + f4(x1…xn)
Вместо x1…xn ставим константы a1…an, такие, что
f1(a1…an) = 1
1. A = B = 0
F(x1x2…a3…an) = x1x2 + C = {x1x2, если с = 0 и NOT(x1x2, если с = 1)
Аналогично получаем дизъюнкцию и ее отрицание.
Теорема Поста.
Система функций полна тогда и только тогда, когда она не находится ни в одном из пяти важнейших замкнутых классов, а именно S, M, L, T0, T1.
1. Необходимо.
Дана полная система функций. Отсюда следует, что она не принадлежит никакому замкнутому классу (см. выше).
Доказательство следует из того факта, что по определению и по тому, что мы доказали, что все важнейшие классы замкнуты. Если предположить, что система целиком входит в один из замкнутых классов, то
[S] = [B] = B
Но S - множество всех булевых функций, а B – не всех.
Получили противоречие.
Доказательство дано в виде алгоритма получения из системы S основных элементарных булевых функций, образующих полную систему, значит и эта система будет полна.
Дано
S Ë {S, M, L, T0, T1}
Каждая функция (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: «Функциональные элементы. Логические схемы»
|
Функциональный элемент с n упорядоченными входами и одним выходом
.
При подаче на выходы любой комбинации двоичных сигналов, на выходе также возникает сигнал.
Каждый вход – аргумент функции.
Выход – булева функция от аргументов.
Из функциональных элементов можно строить по правилам их соединения схемы (логические сети).
Два и более входов можно отождествлять.
Возможные соединения функциональных элементов соответствуют булевым функциям и их суперпозициям.
Полный набор булевых функций, который мы будем использовать для построения логических сетей (схем) в какой-нибудь задаче, мы назовем базисом из функциональных элементов.
Число функциональных переменных считаем сколь угодно большим.
Базис называется полным, если с его помощью можно реализовать любую булеву функцию в виде схемы.
Очевидно, чтобы базис был полным, необходимо и достаточно, чтобы система функций, реализуемых элементами базиса, была полной.
Пример полного базиса.
|
- Конъюнктор
|
- Дизъюнктор
- Инвертор
Чтобы построить минимальную функциональную схему для функции на конъюнкторах, дизъюнкторах и инверторах, которая реализует эту функцию, нужно
1. Найти минимальную ДНФ.
2. Для любой из минимальных ДНФ (их может быть много) попробовать упростить формула с помощью вынесения за скобки общего множителя.