Функции алгебры логики. Стасюк В.В. - 23 стр.

                                            0    0     0     1      0      1
                                            0    1     1     0      1      1
                                            1    0     0     1      0      0
                                            1    1     1     0      1      0

Из таблицы выбираем набор x = 0 и u = 1 , на котором f 0 (0,1) = 1 . Тогда a = f1 (0,1) = 0 ,
b = f 2 (0,1) = 1 , c = f3 (0,1) = 1 и
                                       ϕ ( y, z ) = f (0, y, z ,1) = yz ⊕ z ⊕ 1 .
Таким образом, функция

                 ψ ( y, z ) = ϕ ( y ⊕ 1, z ⊕ 0) ⊕ 0 ⋅ 1 ⊕ 1 = ϕ ( y , z ) = f (0, y , z ,1) = yz ⊕ z = yz

реализует требуемую конъюнкцию.
      Обладая необходимым инструментарием, докажем теперь основной критерий функ-
циональной полноты, критерий в котором сформулированы необходимые и достаточные ус-
ловия полноты в Pn системы функций.

       Теорема 16 (Поста о функциональной полноте). Система булевых функций F полна
в Pn тогда и только тогда, когда она не содержится целиком ни в одном из пяти основных
замкнутых классов T0 , T1 , T∗ , T≤ , TL .

Доказательство. Необходимость. Пусть [ F ] = Pn и пусть F ⊂ T , где T — некоторый один
из пяти перечисленных замкнутых классов. Тогда, пользуясь определением и свойством 3
замыкания, имеем
                                 Pn = [ F ] ⊂ [T ] = T ,

откуда T = Pn , что противоречит таблице 5 принадлежности элементарных булевых функций
основным замкнутым классам.
      Достаточность. Пусть система булевых функций F не содержится целиком ни в од-
ном из пяти классов T0 , T1 , T∗ , T≤ , TL . Тогда система F содержит хотя бы одну функцию f 0 ,
не сохраняющую нуль, хотя бы одну функцию f1 , не сохраняющую единицу, хотя бы одну
несамодвойственную функцию f∗ , хотя бы одну немонотонную функцию f ≤ и хотя бы одну
нелинейную функцию f L . Функции f 0 , f1 , f∗ , f ≤ и f L не обязательно должны быть различ-
ны и не обязательно исчерпывают систему F . Например, если в F содержится штрих Шеф-
фера, то его можно использовать в качестве всех пяти функций одновременно.
         Покажем, что отрицание и конъюнкция реализуются в виде формул над системой
F ′ = { f 0 , f1 , f∗ , f ≤ , f L } ⊂ F . Тем самым, в силу критерия полноты, теорема будет доказана.
Реализацию проведем в три этапа: на первом строятся формулы, реализующие константы 0 и
1. На втором этапе строится формула, реализующая отрицание. На третьем этапе строится
формула, реализующая конъюнкцию.
       Этап 1. Построим формулу реализующую 1. Пусть ϕ ( x) = f 0 ( x,..., x) ∉ T0 . Тогда

                                                ϕ (0) = f 0 (0,..., 0) = 1 .

Возможны два случая: ϕ (1) = 1 и ϕ (1) = 0 .
Случай 1. ϕ (1) = 1 . Тогда ϕ ( x) = 1 . То есть формула ϕ реализует 1.