матлогика_методичка. Методические указания к выполнению практических работ Омск Издательство Омгту 2009
 Скачать 0.58 Mb.
|
|
Федеральное агентство по образованию  Государственное образовательное учреждение высшего профессионального образования «Омский государственный технический университет»  Математическая логика и теория алгоритмов Методические указания к выполнению практических работ Омск Издательство ОмГТУ 2009 Составитель Л. А. Денисова, канд. техн. наук, доц. кафедры «Автоматизированные системы обработки информации и управления» Данные методические указания предназначены для обеспечения практических занятий по дисциплине «Математическая логика и теория алгоритмов» и предлагаются в качестве установочных рекомендаций студентам, использующим дистанционные технологии обучения. Приведены материалы по основным разделам математической логики и теории алгоритмов, необходимые для освоения общепрофессиональных и специальных дисциплин студентами направления подготовки 23010062 – «Информатика и вычислительная техника». Изложены краткие сведения по основам логики высказываний, логики предикатов, формальных аксиоматических теорий и теории алгоритмов. Рассмотрены типовые примеры и приведены указания к выполнению практических работ, даны индивидуальные задания для самостоятельной работы по вариантам. Печатается по решению редакционно-издательского совета Омского государственного технического университета © ГОУ ВПО «Омский государственный технический университет», 2009 СОДЕРЖАНИЕ ВВЕДЕНИЕ 5 Тема 1. ЛОГИКА ВЫСКАЗЫВАНИЙ 5 1.1. Логические операции над высказываниями 5 1.2. Формулы логики высказываний. Следование и равносильность формул 6 1.3. Отыскание нормальных форм формул логики высказываний 8 1.4. Тождественно истинные и тождественно ложные формулы. Проблема разрешимости 11 1.5. Формализация рассуждений. Правильные рассуждения 12 1.6. Задания 13 Варианты индивидуальных заданий 13 Тема 2. ЛОГИКА ПРЕДИКАТОВ 16 2.1. Определение предиката. Кванторы. Формулы логики предикатов 16 2.2. Приведенные и предваренные нормальные формулы 19 2.3. Выражение суждения в виде формулы логики предикатов 20 2.4. Задания 21 Тема 3. ФОРМАЛЬНЫЕ АКСИОМАТИЧЕСКИЕ ТЕОРИИ 24 3.1. Построение формализованного исчисления высказываний 24 3.2. Автоматическое доказательство теорем. Метод резолюций 27 3.3. Задания 29 Тема 4. НЕЧЕТКАЯ ЛОГИКА 32 4.1 Основные понятия нечетких множеств 32 4.2 Элементы нечеткой логики 33 4.3. Задания 35 Тема 5. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ 35 5.1. Понятие алгоритма 35 5.2. Машина Тьюринга 35 5.3. Задания 39 Список литературы 40 ВВЕДЕНИЕМатематическая логика, как и теория алгоритмов, возникла в связи с внутренними проблемами математики, с изучением границ применимости ее теорий и методов. В настоящее время эти взаимосвязанные между собой теории получили развитие в так называемой компьютерной математике (computer science). Вот некоторые направления их использования в прикладных областях: – при проектировании элементной базы компьютеров используется математический аппарат логики высказываний; – в основе алгоритмических языков лежат теория алгоритмов, теория формальных систем, логика предикатов; – тестирование программ основано на логическом анализе их структуры; – доказательство корректности программ базируется на теории логического вывода; – в экспертных системах используются формально-логические выводы для имитации деятельности экспертов; – автоматизация доказательства теорем основана на методе резолюций, изучаемом в курсе логики. Тема 1. ЛОГИКА ВЫСКАЗЫВАНИЙ1.1. Логические операции над высказываниямиВысказыванием называется предложение, представляющее собой такое утверждение, относительно которого можно судить, истинно оно или ложно. Высказывание не может быть одновременно истинным и ложным. По совокупности всех высказываний определяется функция истинности, принимающая значения в двухэлементном множестве {0, 1}:  Значение (P) называется значением истинности высказывания P. Символ λ обычно опускают. Это связанно с тем, что в алгебре высказываний полностью отвлекаются от содержания высказываний, а изучают их только в связи с их свойством быть истинными или ложными. Поэтому каждое ложное высказывание можно рассматривать как элемент 0, а истинное – как элемент 1 и писать вместо λ(Р) = 0 или λ(Р) = 1 только Р = 0 или Р = 1. Над высказываниями определяются следующие основные операции (логические связки), которые позволяют из имеющихся операций строить новые:
Операция отрицания определяется следующим образом: если P истинно, то P ложно и наоборот. Остальные операции определяются по таблице 1 (таблице истинности соответствующих операций). Таблица 1
Следует обратить внимание, что конъюнкция PQ истинна тогда и только тогда, когда P и Q одновременно истинны, а в остальных случаях ложна. Конъюнкцию называют логическим произведением. Дизъюнкция PQ ложна тогда и только тогда, когда P и Q одновременно ложны, а в остальных случаях истинна. Дизъюнкцию называют логической суммой. Импликация PQ ложна тогда и только тогда, когда P= 1, а Q= 0. Импликация играет важную роль в логике высказываний. При учете смыслового содержания высказывания (а не только значений истинности) оборот “если, то” подразумевает причинно-следственную связь. Истинность импликации означает лишь то, что если истинна посылка, то истинно и заключение. При ложной посылке заключение всегда истинно. Эквивалентность PQ истинна тогда и только тогда, когда значения истинности P и Q совпадают. С помощью логических операций можно из простых высказываний строить формулы логики высказываний, представляющие составные высказывания. | ||||||||||||||||||||||||||||||||||||