Дискретная математика. Сергиевская И.М. - 11 стр.

       Результаты можно занести в первую строку таблицы
Поста. Остальные функции исследуются аналогично.
       Построим таблицу Поста:
           T0      T1      S      M       L
 x⊕ y      +        -      -       -      +
 x∧ y      +       +       -      +        -
   1        -      +       -      +       +
В каждом столбце таблицы имеется минус, следовательно,
система A функционально полна.
       Минимальная функционально полная система называется
базисом пространства булевых функций.

                3. Элементы комбинаторики.
Основные задачи теории выборок. Формула включения и исклю-
чения. Задача о беспорядках. Рекуррентные соотношения.
Литература: [1], с. 53-70; [5], пп. 5.1, 5.3, 5.5.

   4. Элементы теории графов. Оптимизация на графах.
       Графы. Основные понятия. Изоморфизм графов. Задание
графа с помощью булевых матриц. Утверждения о степенях вер-
шин. Алгоритм построения графа с заданным набором степеней
вершин. Алгоритм нахождения кратчайших путей. Маршруты,
цепи, циклы. Связность. Планарность.
Литература: [1], с. 11-14; [3], части 5, 6; [4], гл. 6,7; [5], гл. 7-9.

      Рассмотрим граф G , изображенный на рисунке. На
примере этого графа рассмотрим некоторые понятия теории
графов.




                                  11