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

                     классы
                                T0     T1     S     M      L
         функции
              f1 � y � 1        +         +   +     +      +
            f 2 � xy � z        –         +   –     –      –
              f3 � x � y        –         –   –     –      –


      В каждом столбце таблицы стоит знак «–». Поэтому, согласно крите-
рию Поста, система функций полная.
      Базисом является функция 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) « � » через « � ».

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



                                     53