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

                                           105
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________


      В каждом столбце таблицы стоит знак «-». Поэтому, согласно крите-
рию Поста, система функций полная.
      Базисом является функция f 3 , т.к. подсистема {f 3 }- полна в Б.
      Замечание 1. Для исследования полноты вовсе не обязательно за-
полнять все клетки таблицы. Если получили, что одна из функций не при-
надлежит какому – либо из классов, то принадлежность остальных функ-
ций этому классу можно не исследовать.
      Замечание 2. При исследовании полноты системы полезно исполь-
зовать следующее утверждение: если некоторая система функций F со-
держит в себе как часть полную систему функций F1 , F1 ⊂ F , то систе-
ма F полна.
      Например, рассмотренная выше в примере система F является пол-
ной, т.к. содержит в себе полную подсистему {x ↓ y } .
       Замечание 3. Если в одном из столбцов таблицы получены все «+»,
т.е. все функции f i системы F принадлежат какому-то классу, то система
функций не является полной.


                     ЗАДАЧИ И УПРАЖНЕНИЯ
1. Выразить с помощью суперпозиций:
         1) « & »и « → » через « ∨ » и «┐»;
         2) «&» и « ∨ » через → и «┐»;
         3) « ∨ » и « ∧ » через « / »;
         4) «┐» через «→ » и «0»;
         5) «┐» через «⊕ » и «1»;
         6) « ∨ » через « → »;

                          классы
                                      T0         T1     S       M         L
            функции
                 f 1 =y ⊕ 1           +        +        +       +        +
               f 2 =xy → z            —        +        —       —        —
                 f 3 =x ↓ y           —        —        —       —        —


2. Доказать, что нельзя выразить с помощью суперпозиций:
         1) «┐» через «&», «∨», « → » и «~»;
         2) « → » через «&», и «∨».