Дискретная математика. Элементы теории задачи и упражнения. Часть 2. Булгакова И.Н - 58 стр.

                                           104
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
      В силу критерия Поста для полноты системы F= {f 1 , f 2 ,...} необхо-
димо и достаточно, чтобы хотя бы в одной клетке каждого столбца стоял
знак «-».
      Система (множество) булевых функций называется базисом, если
она полна и любая ее подсистема не является полной на множестве буле-
вых функций.
              1                               2                                 3

   y      y       1    f1            x    y       z   xy   f2        x      y       x∨y      f3
   0      1       1    0             0    0       0   0    1
   1      0       1    1             0    0       1   0    1         0      0        0       1
                                     0    1       0   0    1         0      1        1       0
                                     0    1       1   0    1         1      0        1       0
                                     1    0       0   0    1         1      1        1       0
                                     1    0       1   0    1
                                     1    1       0   1    0
                                     1    1       1   1    1

      Для выделения базиса из полной системы функций F ={f 1 , f 2 , f 3 ,...}
нужно упорядочить по числу функций множество подсистем системы F:
                      {f 1 }, {f 2 }, ...,{f 1 , f 2 }{
                                                      , f1 , f 3 }, ... .
и, начиная с первой, исследовать их на полноту. Первая из полных в этой
последовательности подсистем будет базисом.

    Пример.         Исследовать        полноту     системы        функций
F ={y ⊕ 1; x ↓ y; xy → z} и, если она полна, выделить из нее базис.
        Решение. Пусть f 1 = y ⊕ 1 , f 2 = xy → z , f 3 = x ↓ y .
        Составим таблицы истинности для заданных функций:
        Исследуем функцию f 2 =xy → z на принадлежность классам T0 ,
T1 , S , M , L .:
         f 2 ∉T0 , т.к. f 2 (0,0 ) =1; f 2 ∈T1 , т.к. f 2 (1,1) =1;
         f 2 ∉ S 1 , т.к. на противоположных наборах (000) и (111) функция
принимает одинаковое значение, равное 1.
         f 2 ∉M 1 , т.к. есть предшествующие наборы, например (000) ≤(110),
на которых f 2 (0,0,0 ) =1 , f 2 (1,1,0 =0 ),где неравенство 1 ≤0 ложное,
f 2 ∉L1 ,т.к. f 2 = xy → z = xy ∨ z = xy ∨ z = xy & z = xy (z ⊕ 1) = xyz ⊕ xy ⊕ 1.
         Аналогично исследуем функции f 1 и f 3 на принадлежность классам
T0 , T1 , S 1 , M 1 , L1 .
         Заполним таблицу