Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«Омский государственный технический университет»

Математическая логика и теория алгоритмов

Методические указания

к выполнению практических работ

Омск

Издательство ОмГТУ

2009

Составитель Л. А. Денисова, канд. техн. наук, доц. кафедры «Автоматизированные системы обработки информации и управления»

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

Приведены материалы по основным разделам математической логики и теории алгоритмов, необходимые для освоения общепрофессиональных и специальных дисциплин студентами направления подготовки 23010062 – «Информатика и вычислительная техника».

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

Печатается по решению редакционно-издательского совета

Омского госу­дар­ственного технического университета

© ГОУ ВПО «Омский государственный технический университет», 2009

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 5

Тема 1. Логика высказываний 5

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

1.2. Формулы логики высказываний. Следование и равносильность формул 6

1.3. Отыскание нормальных форм формул логики высказываний 8

1.4. Тождественно истинные и тождественно ложные формулы. Проблема разрешимости 10

1.5. Формализация рассуждений. Правильные рассуждения 12

1.6. Задания 13

Варианты индивидуальных заданий 13

Тема 2. ЛОГИКА ПРЕДИКАТОВ 16

2.1. Определение предиката. Кванторы. Формулы логики предикатов 16

2.2. Приведенные и предваренные нормальные формулы 18

2.3. Выражение суждения в виде формулы логики предикатов 20

2.4. Задания 21

Тема 3. ФОРМАЛЬНЫЕ АКСИОМАТИЧЕСКИЕ ТЕОРИИ 23

3.1. Построение формализованного исчисления высказываний 23

3.2. Автоматическое доказательство теорем. Метод резолюций 26

3.3. Задания 28

Тема 4. НЕЧЕТКАЯ ЛОГИКА 31

4.1 Основные понятия нечетких множеств 31

4.2 Элементы нечеткой логики 31

4.3. Задания 34

Тема 5. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ 34

5.1. Понятие алгоритма 34

5.2. Машина Тьюринга 34

5.3. Задания 38

Список литературы 39

ВВЕДЕНИЕ

Математическая логика, как и теория алгоритмов, возникла в связи с внутренними проблемами математики, с изучением границ применимости ее теорий и методов. В настоящее время эти взаимосвязанные между собой теории получили развитие в так называемой компьютерной математике (computer science). Вот некоторые направления их использования в прикладных областях:

– при проектировании элементной базы компьютеров используется математический аппарат логики высказываний;

– в основе алгоритмических языков лежат теория алгоритмов, теория формальных систем, логика предикатов;

– тестирование программ основано на логическом анализе их структуры;

– доказательство корректности программ базируется на теории логического вывода;

– в экспертных системах используются формально-логические выводы для имитации деятельности экспертов;

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