2. Математическая логика

2.1. Высказывания

2.2. Логические связки (операции) над высказываниями

2.3. Пропозициональные формулы

2.4. Булевы функции. Таблицы истинности

2.5. Булевы функции одной переменной

2.6. Булевы функции двух переменных

2.7. Существенные и несущественные переменные

2.8. Равносильные формулы. Основные равносильности

2.9. Основные тавтологии

2.10. Основные равносильности

2.11. Понятие двойственной функции

2.12. Некоторые двойственные функции

2.13. Элементарные канонические формы

2.14. Нормальные формы формул

2.15. Приведение формул к нормальным формам

2.16. Минимизация д.н.ф.

2.17. Полные системы функций. Полином Жегалкина

2.18. Функционально замкнутые классы функций

2.19. Понятие алгоритма. Описание машины Тьюринга

2.1. Высказывания

Определение. Высказывание – повествовательное утверждение, которое либо истинно либо ложно (не то и другое одновременно).

Примеры высказываний: «Тише едешь – дальше будешь», «Париж – столица Франции». Но «Как бы чего не вышло» или «Миру – мир» не являются высказываниями.

Определение. Высказывание называется простым (элементарным), если оно рассматривается как одно неделимое целое.

Определение. Сложное высказывание – высказывание, составленное из простых с помощью логических связок.

2.2. Логические связки (операции) над высказываниями

Определение. Конъюнкцией («и») высказываний P и Q называется высказывание, истинное тогда и только тогда, когда оба истинны. Обозначается P&Q.

Таблица истинности: