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

       Множества и их спецификации. Операции над множест-
вами. Диаграммы Эйлера-Венна. Мощность множества. Конеч-
ные и счетные множества. Отношения. Свойства отношений.
Операции над отношениями. Отношение эквивалентности. Раз-
биения и отношение эквивалентности. Отношения частичного и
строгого порядка. Функции и отображения. Инъекция,
сюръекция, суперпозиция, биекция, обратные функции.
Литература: [1], с. 5-10; [3], часть 2; [4], гл. 1-3; [5], гл. 1.

   2. Булевы алгебры. Элементы математической логики.
         Булевы функции. Способы задания. Существенные и
фиктивные переменные. Булевы формулы. Основные свойства
логических операций. Совершенные нормальные формы. Поли-
ном Жегалкина. Замкнутые классы функций. Функционально
полные системы. Теоремы о функциональной полноте. Примеры
функционально-полных базисов. Проблема минимизации
булевых функций. Схемы из функциональных элементов.
Конечные автоматы. Формальные теории. Понятие высказыва-
ния. Тавтологии. Исчисление высказываний. Логика предикатов.
Литература: [1], с. 14-53; [2], гл. 3,8; [3], части 1,4; [4], гл. 4, 5;
[5], гл. 3,4.

Эквивалентность булевых формул.
           Булевы функции могут быть заданы либо с помощью
таблиц истинности (единственным образом), либо с помощью
логических формул (неединственным образом). Если таблицы
истинности двух булевых формул совпадают, то эти формулы
эквивалентны и определяют одну и ту же булеву функцию.
Пример. Проверить эквивалентность булевых формул:
x → ( y → z ) = ( x → y) → ( x → z ) .
           Построим       таблицу   истинности для  функции
 f ( x, y ) = x → ( y → z ) .

   x     y     z        y→z           x → ( y → z)
                                  4