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

При изучении данной темы следует обратить внимание на то, что алгебра высказываний является частным примером булевой алгебры и провести аналогию между логическими и теоретико-множественными операциями.

Следует изучить основные логические операции (связки), понятие полной системы связок, понятие формулы алгебры, высказываний, основные равносильные формулы. Показать, как высказываниям в естественном и математическом языке могут быть поставлены в соответствие логические формулы. Рассмотреть основное понятие – понятие логической функции и уяснить связь между формулами и функциями алгебры высказываний. Изучить логические отношения между высказываниями (отношение следования, отношение эквивалентности и отношение несовместимости), а также способы проверки правильности рассуждений.

Рассмотреть, как проблема определения типа формулы (проблема разрешимости) может быть решена с помощью приведения формулы к нормальным формам (НФ) и определить конструктивно понятие совершенной нормальной формы формулы алгебры высказываний (СНФ).

Изучить построение формулы алгебры высказываний по заданной функции.

Выяснить возможность моделирования формул алгебры высказываний релейно-контактными схемами, а также какие задачи при этом могут быть решены.

Рассмотреть формальную аксиоматическую систему, адекватную алгебре высказываний – исчисление высказываний; основные проблемы формальной логической системы, как они решаются и как она может быть применена к конкретной научной области.

Далее изучается логика предикатов, которая включает в себя алгебру высказываний как составную часть. Рассматриваются операции над предикатами, кванторы общности и существования, применение кванторов в математических науках.

Изучив данную тему студент должен:

· Знать:

– все понятия, перечисленные выше, связанные с ними свойства, соотношения, теоремы;

– рассматриваемые в теории проблемы и способы их решения.

· Уметь:

– применять язык, методы и средства математической логики в математических дисциплинах и в прикладных дисциплинах.

Планы практических занятий по теме 2

1. Логические операции. Формулы алгебры высказываний. Равносильность формул. Полные системы связок.

2. Логические функции. Связь с формулами алгебры высказываний. Существенные и фиктивные переменные.

3. Логические отношения. Проверка правильности рассуждений.

4. Нормальные формы алгебры высказываний. Установление типа формулы.

5. Совершенные нормальные формы. Построение формулы алгебры высказываний по заданной функции.

6. Алгебра высказываний и релейно-контактные схемы. Упрощение схем.

7. Исчисление высказываний: алфавит, формулы, аксиомы, правила вывода. Проблемы непротиворечивости, полноты и независимости системы аксиом.

8. Логика предикатов. Операции над предикатами. Кванторы.

Рекомендации по выполнению конкретных заданий, вопросы и тесты для самопроверки содержатся в учебно-практи-ческих пособиях:

Дискретная математика. – М. : МГУЭСИ, 2009. (Авторы Э.Л. Балюкевич, Л.Ф. Ковалёва, А.Н. Романников.) / Литература 1 /

Математическая логика и теория алгоритмов. – М. : МГУЭСИ, 2009. (Гриф УМО Минобрнауки РФ.) (Авторы Э.Л. Балюкевич, Л.Ф. Ковалёва.) / Литература 2 /