WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 || 3 | 4 |   ...   | 7 |

§5. Понятие замкнутого класса. Замкнутость классов T0, T1 и L.

1°. Понятие замкнутого класса.

Определение 1. Пусть A P2. Тогда замыканием A называется множество всех функций алгебры логики, которые можно выразить формулами над A.

Обозначение: [A].

Имеют место следующие свойства:

1) [A] A;

2) A B [A] [B], причём, если в левой части импликации строгое вложение, то из него вовсе не следует строгое вложение в правой части — верно лишь A B [A] [B];

3) [[A]] = [A].

Определение 2. Система функций алгебры логики A называется полной, если [A] = P2.

Определение 3. Пусть A P2. Тогда система A называется замкнутым классом, если замыкание A совпадает с самим A: [A] = A.

Утверждение. Пусть A — замкнутый класс, A P2 и B A. Тогда B — неполная система (подмножество неполной системы будет также неполной системой).

Доказательство. B A [B] [A] = A P2 [B] P2. Следовательно, B — неполная система. Утверждение доказано.

2°. Примеры замкнутых классов.

Класс T0 = {f (x1, …, xn) | f (0, …, 0) = 0}.

Классу T0 принадлежат, например, функции 0, x, xy, x y, x y.

Классу T0 не принадлежат функции 1, x, x y, x | y, x y, x ~ y.

Подсчитаем число функций в классе T0. Для этого построим следующую таблицу:

x1 … xn 0 … 0 0.

… … … }2n -Все функции, принадлежащие указанному классу, принимают на нулевом наборе нулевое значение. Таким образом, всего функций в классе T0 столько, сколько существует булевых векторов длины 2n – 1 (первый разряд вектора длины 2n необходимо равен нулю), то есть n n T0 = 22 -1 = 22.

Теорема 6. Класс T0 —замкнутый.

Доказательство. Пусть {f (x1,…, xn), g1(y11,…, y1m ),…, gn(yn1,…, ynm )} T0. Рассмотрим 1 n функцию h(y1,…, yr )= f (g1(y11,…, y1m ),…, gn(yn1,…, ynm )). Среди переменных функций gi 1 n могут встречаться и одинаковые, поэтому в качестве переменных функции h возьмём все различные из них. Тогда h (0, …, 0) = f (g1 (0, …, 0), …, gn (0, …, 0)) = f (0, …, 0) = 0, следовательно, функция h также сохраняет ноль. Рассмотрен только частный случай (без переменных в качестве аргументов). Однако, поскольку тождественная функция сохраняет ноль, подстановка простых переменных эквивалентна подстановке тождественной функции, теорема доказана.

Класс T1 = {f (x1, …, xn) | f (1, 1, …, 1) = 1}.

Классу T1 принадлежат функции 1, x, xy, x y, x y, x ~ y.

Классу T1 не принадлежат функции 0, x, x y, x | y, x y.

Теорема 7. Класс T1 замкнут.

Доказательство повторяет доказательство аналогичной теоремы для класса T0.

Класс L линейных функций.

Определение 4. Функция алгебры логики f (x1, …, xn) называется линейной, если f (x1, …, xn) = a0 a1 x1 … an xn, где ai {0, 1}.

Иными словами, в полиноме линейной функции нет слагаемых, содержащих конъюнкцию.

Классу L принадлежат функции 0, 1, x = x 1, x ~ y, x y.

Классу L не принадлежат функции xy, x y, x y, x | y, x y.

Теорема 8. Класс L замкнут.

Доказательство. Поскольку тождественная функция — линейная, достаточно (как и в теоремах 6 и 7) рассмотреть только случай подстановки в формулы функций: пусть f (x1, …, xn) L и gi L. Достаточно доказать, что f (g1, …, gn)L. Действительно, если не учитывать слагаемых с коэффициентами ai = 0, то всякую линейную функцию можно представить в виде xi xi … xi a0. Если теперь вместо каждого xi подставить линейное выражение, 1 2 k j то получится снова линейное выражение (или константа единица или нуль).

§6. Двойственность. Класс самодвойственных функций, его замкнутость.

1°. Двойственность.

Определение 1. Функцией, двойственной к функции алгебры логики f (x1, …, xn), назы вается функция f (x1,…, xn )= f (x1,…, xn).

Теорема 9 (принцип двойственности). Пусть (y1,…, ym)= f (g1(y11,…, y1k ),…, gn(yn1,…, ynk )).

1 n Тогда (y1,…, ym)= f (g1(y11,…, y1k ),…, gn(yn1,…, ynk )).

1 n Доказательство. Рассмотрим (y1,… ym )= f (g1(y11,…, y1k ),…, gn(yn1,…, ynk ))= 1 n = f(g1(y11,…, y1k ),…, gn(yn1,…, ynk ))= f(g1(y11,…, y1k ),…, gn(yn1,…, ynk ))= 1 n 1 n = f (g1(y11,…, y1k ),…, gn(yn1,…, ynk )).

1 n Теорема доказана.

Следствие. Пусть функция (y1, …, ym) реализуется формулой над A = {f1, f2, …}. Тогда если в этой формуле всюду заменить вхождения fi на fi*, то получится формула, реализующая * (y1, …, ym).

Утверждение. Для любой функции алгебры логики f (x1, …, xn) справедливо равенство f (x1, …, xn)=f** (x1, …, xn).

Доказательство. f = [f (x1,…, xn)] = f (x1,…, xn)= f (x1,…, xn), и утверждение доказано.

2°. Класс S самодвойственных функций.

Определение 2. Функция алгебры логики f (x1, …, xn) называется самодвойственной, если f (x1, …, xn) = f* (x1, …, xn).

Иначе говоря, S = {f | f = f*}.

Классу S принадлежат функции 1, x + y + z x, x, x y z a, m(x, y, z)= xy yz zx = 0, x + y + z 1.

Классу S не принадлежат функции 0 ( f (x) 0 f (x)= f (x) 1), 1, x y (поскольку (x y) = x y = x y x y ), xy.

Теорема 10. Класс S замкнут.

Доказательство. Пусть f (x1, …, xn) S, i gi(yi1,…, yik ) S, i = 1, 2, …, n и i = f (g1(y11,…, y1k ),…, gn(yn1,…, ynk )).

1 n Тогда из принципа двойственности следует, что = f (g1(y11,…, y1k ),…, gn(yn1,…, ynk )) = f (g1 (…), …, gn (…)).

1 n Таким образом, мы получили, что = * и S. Теорема доказана.

§7. Класс монотонных функций, его замкнутость.

~ ~ Определение 1. Пусть = (1,2,…,n) и = (1, 2,…, n). Тогда ~ ~ i(i i ).

Замечание. Существуют наборы, для которых неприменимо отношение упорядоченности, определённое выше. Так, например, наборы (0, 0, 1) и (0, 1, 0) несравнимы.

Определение 2. Функция алгебры логики f (x1, …, xn) называется монотонной, если для ~ ~ любых двух сравнимых наборов и выполняется импликация ~ ~ ~ ~ f ( ) f ().

Класс M всех монотонных функций.

Классу M принадлежат функции 0, 1, x, xy, x y, m (x, y, z) = xy yz zx.

Классу M не принадлежат функции x, x | y, x y, x y, x ~ y, x y.

Теорема 11. Класс M замкнут.

Доказательство. Поскольку тождественная функция монотонна, достаточно проверить лишь случай суперпозиции функций. Пусть f (x1, …, xn) M, для любого j gj (y1, …, ym)M и (y1, …, ym) = f (g1 (y1, …, ym), …, gn (y1, …, ym)).

~ ~ ~ ~ Рассмотрим произвольные наборы = (1,…,m), = (1,…, m) такие, что. Обозначим ~ ~ gi( )=, gi()= i.

i ~ ~ Тогда для любого i имеем gi M и gi( ) gi(), то есть i( i ). Обозначим i ~ ~ = (1,,…, ), = (1,2,…,n).

2 n ~ ~ ~ ~ Тогда по определению и, в силу монотонности функции f, f ( ) f ( ). Но ~ ~ ~ ~ ( )= f (1,…, )= f ( ), ()= f (1,…,n)= f ( ), n ~ ~ ~ ~ и неравенство f ( ) f ( ) ( ) (), следовательно, Ф M. Теорема доказана.

§8. Лемма о несамодвойственной функции.

Лемма (о несамодвойственной функции). Из любой несамодвойственной функции алгебры логики f (x1, …, xn), подставляя вместо всех переменных функции x и x, можно получить (x) const.

~ Доказательство. Пусть f S. Тогда f (x1,…, xn) f (x1,…, xn) = (1,…,n):

f (1,…,n) f (1,…,n) f (1,…,n)= f (1,…,n).

Построим функцию (x) так: (x) = f (x 1, …, x n). Действительно, (0) = f (1, …, n), (1)= f (1,… ) n и (0) = (1) (x) = const. Заметим, что подстановка удовлетворяет условию теоремы, так x, = как x = x, = 1. Лемма доказана.

§9. Лемма о немонотонной функции.

Лемма (о немонотонной функции). Из любой немонотонной функции алгебры логики f (x1, …, xn), подставляя вместо всех переменных функции x, 0, 1, можно получить функцию (x) x.

~ Доказательство. Пусть f M. Тогда существуют такие наборы = (1,…,n) и ~ ~ ~ ~ ~ ~ ~ = (1,…, n), что < (то есть j (j j) и ) и f ( )> f (). Выделим те разряды ~ ~ ~ i1, …, ik наборов и, в которых они различаются. Очевидно, в наборе эти разряды ~ равны 0, а в наборе — 1. Рассмотрим последовательность наборов ~ ~ ~ ~ 0,1,2,…,k ~ ~ ~ ~ ~ ~ ~ ~ таких, что = 0 < 1 < 2 < … < k =, где i +1 получается из i заменой одного из нулей, ~ ~ расположенного в одной из позиций i1, …, ik, на единицу (при этом наборы i и i+1 — со~ ~ ~ ~ ~ ~ седние). Поскольку f ( )= 1, а f ()= 0, среди наборов 0,1,2,…,k найдутся два сосед~ ~ ~ ~ них i и i +1, такие что f (i)= 1 и f (i+1)= 0. Пусть они различаются в r-ом разряде:

~ ~ i = (1,2,…,r -1,0,r +1,…,n), i+1 = (1,2,…,r-1,1,r+1,…,n). Тогда определим функцию ~ (x) так: (x) = f (1, 2, …, r – 1, x, r + 1, …, n). Действительно, тогда (0)= f (i)= 1, ~ (1)= f (i+1)= 0 и (x) x. Лемма доказана.

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

Лемма (о нелинейной функции). Из любой нелинейной функции алгебры логики f (x1, …, xn), подставляя вместо всех переменных x, x, y, y, 0, 1, можно получить (x, y) = x·y или (x, y)= x y.

Доказательство. Пусть f (x1, …, xn) L. Рассмотрим полином Жегалкина этой функции.

Из её нелинейности следует, что в нём присутствуют слагаемые вида xi xi …. Не ограни1 чивая общности рассуждений, будем считать, что присутствует произведение x1 · x2 · …. Таким образом, полином Жегалкина этой функции выглядит так:

f (x1, …, xn) = x1 · x2 · P1 (x3, …, xn) x1 · P2 (x3, …, xn) x2 · P3 (x3, …, xn) P4 (x3, …, xn), причем P1 (x3, …, xn) 0.

Иначе говоря, a3, a4, …, an E2 = {0, 1} такие, что P1 (a3, a4, …, an) = 1. Рассмотрим вспомогательную функцию f (x1, x2, a3, a4, …, an) = x1 x2 · 1 x1 · b x2 · c d. Тогда функция f (x с, y b, a3, a4, …, an) = (x c)(y b) (x c)b (y b)c d = xy, bc d = = xy x · b y · c b · c x · b b · c y · c b · c d = xy (bc d) =.

xy, bc d = Лемма доказана.

§11. Теорема Поста о полноте системы функций алгебры логики.

Теорема 12 (теорема Поста). Система функций алгебры логики A = {f1, f2, …} является полной в P2 тогда и только тогда, когда она не содержится целиком ни в одном из следующих классов: T0, T1, S, L, M.

Доказательство. Необходимость. Пусть A — полная система, N — любой из классов T0, T1, S, L, M и пусть A N. Тогда [A] [N] = N P2 и [A] P2. Полученное противоречие завершает обоснование необходимости.

Достаточность. Пусть A T0, A T1, A M, A L, A S. Тогда в A существуют функции f0 T0, f1 T1, fM M, fL L, fS S. Достаточно показать, что [A] [f0, f1, fM, fL, fS] = P2. Разобьём доказательство на три части: получение отрицания, констант и конъюнкции.

a) Получение x. Рассмотрим функцию f0 (x1, …, xn) T0 и введём функцию 0 (x) = = f0 (x, x, …, x). Так как функция f0 не сохраняет нуль, 0 (0) = f (0, 0, …, 0) = 1. Возможны два случая: либо 0(x)= x, либо 0 (x) 1. Рассмотрим функцию f1 (x1, …, xn) T1 и аналогичным образом введём функцию 1 (x) = f1 (x, x, …, x). Так как функция f1 не сохраняет единицу, 1 (1) = f (1, 1, …, 1) = 0. Возможны также два случая: либо 1(x)= x, либо 1 (x) 0. Если хотя бы в одном случае получилось искомое отрицание, пункт завершён. Если же в обоих случаях получились константы, то согласно лемме о немонотонной функции, подставляя в функцию fM M вместо всех переменных константы и тождественные функции, можно получить отрицание.

Отрицание получено.

b) Получение констант 0 и 1. Имеем fS S. Согласно лемме о несамодвойственной функции, подставляя вместо всех переменных функции fS отрицание (которое получено в пункте a) и тождественную функцию, можно получить константы:

[fS, x ] [0, 1]. Константы получены.

c) Получение конъюнкции x · y. Имеем функцию fL L. Согласно лемме о нелинейной функции, подставляя в функцию fL вместо всех переменных константы и отрицания (которые были получены на предыдущих шагах доказательства), можно получить либо конъюнкцию, либо отрицание конъюнкции. Однако на первом этапе отрицание уже получено, следовательно, всегда можно получить конъюнкцию:

[fL, 0, 1, x ] [xy, xy ]. Конъюнкция получена.

В результате получено, что [f0, f1, fM, fL, fS ] [x, xy]= P2. Последнее равенство следует из пункта 2 теоремы 4. В силу леммы 2 достаточность доказана.

§12. Теорема о максимальном числе функций в базисе алгебры логики.

Определение. Система функций алгебры логики A P2 называется базисом (в P2), если 1) [A] = P2;

2) f A ([A \ {f}] P2).

Теорема 13. Максимальное число функций в базисе алгебры логики равно 4.

Доказательство. 1) Докажем, что из любой полной системы можно выделить полную подсистему, содержащую не более четырёх функций. Действительно, если A — полная система ([A] = P2), то согласно теореме Поста в ней существуют пять функций f0 T0, f1 T1, fS S, fM M, fL L. По теореме Поста система функций {f0, f1, fS, fM, fL} полна. Рассмотрим функцию f0 (x1, …, xn) T0 (f0 (0, 0, …, 0) = 1). Возможны два случая:

a) f0 (1, 1, …, 1) = 1 f0 S [f0, f1, fL, fM] = P2 и система {f0, f1, fL, fM} полна.

b) f0 (1, 1, …, 1) = 0 f0 M, T1 [f0, fL, fS] = P2 и система {f0, fL, fS} полна.

2) Покажем, что существует базис алгебры логики из четырёх функций. Действительно, рассмотрим систему функций {0, 1, x · y, x y z}. Эта система функций полная, так как 0 T1, S, 1 T0, x · y L, x y z M (0 0 1 = 1, 0 1 1 = 0). Однако, любая её подсистема не полна:

{0, 1, x · y} M {0, 1, x y z} L {0, xy, x y z} T{1, xy, x y z} T1.

Теорема доказана.

§13. Теорема о предполных классах.

1. Предполные классы.

Определение. Пусть A P2. A называется предполным классом, если 1) [A] P2;

2) fP2 ( fA [A{f}] = P2).

Теорема 14. В P2 предполными являются лишь следующие 5 классов: T0, T1, S, L, M.

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

T0 T1 L M S T0 0 xy x y T1 1 xy x y 1 L 1 0 x y M 1 0 xy S x x x xy yz zx 2) Докажем, что все классы — T0, T1, S, L, M являются предполными. Действительно, пусть N {T0, T1, L, M, S} и f N. Тогда система N {f} не содержится ни в одном из пяти классов Поста (так как N не содержится в четырёх из них, а f не содержится в N). Следовательно, система N {f} — полная и N — предполный класс.

3) Пусть A — предполный класс. Тогда [A] P2 N{T0, T1, L, M, S}: A N. Если A N, то f (f N, f A): A {f} N [A {f}] P2. Полученное противоречие завершает доказательство.

2. Результаты Поста.

1) В P2 существует ровно счётное число замкнутых классов.

2) В любом замкнутом классе существует конечный базис.

§14. k-значные функции. Теорема о существовании конечной полной системы в множестве k-значных функций.

1°. k-значные функции. Будем рассматривать конечный алфавит Ek = {0, 1, 2, …, k – 1}.

n Функцией k-значной логики назовём отображение вида f (x1, x2, …, xn): Ek Ek.

Некоторые функции k-значной логики.

1) Константы 0, 1, 2, …, k – 1 (всего — k);

2) Тождественная функция f (x) = x;

Pages:     | 1 || 3 | 4 |   ...   | 7 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.