Предлагаемое учебное пособие (2-ое изд., стереотип.) составляет основу комплекта по курсу математической логики и теории алгоритмов, в который также входит сборник задач (Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов).

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

Введение. Математическая логика в системе современного образования.
Логика и интуиция. Логика традиционная и математическая логика. Немного истории. Математическая логика - логика или математика? Математическая логика в обучении математике. Математическая логика и современные ЭВМ.
Глава I. Алгебра высказываний.
§ 1. Высказывания и операции над ними.
Понятие высказывания. Отрицание высказывания. Конъюнкция двух высказываний. Дизъюнкция двух высказываний. Импликация двух высказываний. Эквивалентность двух высказываний. Союзы языка и логические операции (язык и логика). Общий взгляд на логические операции.
§2. Формулы алгебры высказываний.
Конструирование сложных высказываний. Понятие формулы алгебры высказываний. Логическое значение составного высказывания. Составление таблиц истинности для формул. Классификация формул алгебры высказываний. Мышление и математическая логика
§ 3. Тавтологии алгебры высказываний.
О значении тавтологий. Основные тавтологии. Основные правила получения тавтологии.
§ 4. Логическая равносильность формул.
Понятие равносильности формул. Признак равносильности формул. Примеры равносильных формул. Равносильные преобразования формул. Равносильности в логике и тождества в алгебре.
§ 5. Нормальные формы для формул алгебры высказываний.
Понятие нормальных форм. Совершенные нормальные формы. Представление формул алгебры высказываний совершенными дизъюнктивными нормальными (СДН) формами. Представление формул алгебры высказываний совершенными конъюнктивными нормальными (СКН) формами. Два способа приведения формулы алгебры высказываний к совершенной нормальной форме
§ 6. Логическое следование формул.
Понятие логического следствия. Признаки логического следствия. Два свойства логического следования. Следование и равносильность формул. Правила логических умозаключений. Еще один способ проверки логического следования. Нахождение следствий из данных посылок. Нахождение посылок для данного следствия.
§ 7. Приложение алгебры высказываний к логико-математической практике.
Прямая и обратная теоремы. Необходимые и достаточные условия. Противоположная и обратная противоположной теоремы. Закон контрапозиции. Модификация структуры математической теоремы. Методы доказательства математических теорем. Дедуктивные и индуктивные умозаключения. Правильные и неправильные дедуктивные умозаключения. Решение логических задач. Принцип полной дизъюнкции. Одно обобщение принципа полной дизъюнкции.
Глава II. Булевы функции.
§8. Множества, отношения, функции.
Понятие множества. Включение и равенство множеств. Операции над множествами. Бинарные отношения и функции. Понятие ларного отношения.
§ 9. Булевы функции от одного и двух аргументов.
Происхождение булевых функций. Булевы функции от одного аргумента. Булевы функции от двух аргументов. Свойства дизъюнкции, конъюнкции и отрицания. Свойства эквивалентности, импликации и отрицания. Выражение одних булевых функций через другие
§ 10. Булевы функции от п аргументов.
Понятие булевой функции. Число булевых функций. Выражение булевых функций через конъюнкцию, дизъюнкцию и отрицание. Булевы функции и формулы алгебры высказываний. Нормальные формы булевых функций.
§ 11. Системы булевых функций.
Полные системы булевых функций. Специальные классы булевых функций. Теорема Поста о полноте системы булевых функций
§ 12. Применение булевых функций к релейно-контактным схемам.
Идея применения. Две основные задачи теории релейно-контактных схем.
§ 13. Релейно-контактные схемы в ЭВМ.
Двоичный полусумматор. Одноразрядный двоичный сумматор. Шифратор и дешифратор.
§ 14. О некоторых других приложениях теории булевых функций.
Диагностика (распознавание) заболеваний. Распознавание образов.
Глава III. Формализованное исчисление высказываний.
§ 15. Система аксиом и теория формального вывода.
Начало аксиоматической теории высказываний: первоначальные понятия, система аксиом, правило вывода. Понятие вывода и его свойства. Теорема о дедукции и следствия из неё. Применение теоремы о дедукции. Производные правила вывода
§ 16. Полнота и другие свойства формализованного исчисления высказываний
Доказуемость формулы и ее тождественная истинность (синтаксис и семантика). Лемма о выводимости. Полнота формализованного исчисления высказываний. Теорема адекватности. Непротиворечивость формализованного исчисления высказываний. Разрешимость формализованного исчисления высказываний
§ 17. Независимость системы аксиом формализованного исчисления высказываний.
Понятие независимости. Независимость аксиомы (А1). Независимость аксиомы (А2). Независимость аксиомы (A3). Независимость системы аксиом
Глава IV. Логика предикатов.
§ 18. Основные понятия, связанные с предикатами.
Понятие предиката. Классификация предикатов. Множество истинности предиката. Равносильность и следование предикатов
§ 19. Логические операции над предикатами.
Отрицание предиката. Конъюнкция двух предикатов. Дизай перейти на страницу дикатов. Свойства отрицания, конъюнкции и дизъюнкции. Импликация и эквивалентность двух предикатов.
§ 20. Кванторные операции над предикатами.
Квантор общности. Квантор существования. Численные кванторы. Ограниченные кванторы. Логический квадрат
§ 21. Формулы логики предикатов.
Понятие формулы логики предикатов. Классификация формул логики предикатов. Тавтологии логики предикатов
§ 22. Равносильные преобразования формул и логическое следование формул логики предикатов
Понятие равносильности формул. Приведенная форма для формул логики предикатов. Предваренная нормальная форма для формул логики предикатов. Логическое следование формул логики предикатов
§ 23. Проблемы разрешения для обще значимости и выполнимости формул.
Постановка проблемы и ее неразрешимость в общем виде. Решение проблемы для формул на конечных множествах. Пример формулы, выполнимой на бесконечном множестве и невыполнимой ни на каком конечном множестве. Проблема разрешения выполнимости: влияние мощности множества и структуры формулы. Решение проблемы для формул, содержащих только одноместные предикатные переменные. Проблема разрешения общезначимости и мощность множества, на котором рассматривается формула. Решение проблемы для V-формул и 3-формул
§ 24. Применение логики предикатов к логико-математической практике.
Запись на языке логики предикатов различных предложении. Сравнение логики предикатов и логики высказываний. Строение математических теорем. Методы рассуждений: аристотелева силлогистика. Аристотелева силлогистика и логика предикатов. Теоретико-множественная интерпретация аристотелевой силлогистики. О других методах рассуждений. Принцип полной дизъюнкции в предикатной форме. Метод (полной) математической индукции Необходимые и достаточные условия. Логика предикатов и алгебра множеств.
§ 25. Формализованное исчисление предикатов.
Первоначальные понятия (язык формализованного исчисления предикатов). Система аксиом исчисления предикатов. Правила вывода. Теория формального вывода.
Глава V. Неформальные аксиоматические теории.
§ 26. Аксиоматический метод в математике и аксиоматические теории.
Понятие аксиоматической теории. Как возникают аксиоматические теории. Примеры аксиоматических теорий. Интерпретации и модели аксиоматической теории.
§ 27. Свойства аксиоматических теорий.
Непротиворечивость. Категоричность. Независимость системы аксиом. Полнота.
Глава VI. Формальные аксиоматические теории.
§ 28. О формальных аксиоматических теориях.
Об истории идеи формальной аксиоматической теории. Понятие формальной аксиоматической теории. Язык и метаязык, теоремы и метатеоремы формальной теории. Интерпретации и модели формальной теории. Семантическая выводимость. Метаматематика (свойства формальных аксиоматических теорий) . Формализованное исчисление высказываний как формальная аксиоматическая теория.Формализация теории аристотелевых силлогизмов.
§ 29. Свойства формализованного исчисления предикатов.
Оправданность аксиоматизации.Непротиворечивость формализованного исчисления предикатов. Теорема Гёделя о существовании модели. Полнота и адекватность формализованного исчисления предикатов. Неполнота формализованного исчисления предикатов в абсолютном и узком смыслах.Теорема компактности.
§ 30. Формальные теории первого порядка.
Теории первого порядка с равенством. О формальных теориях множеств. О формальной арифметике. О формальных теориях числовых систем.О формальной геометрии. О формальном математическом анализе. Обший взгляд на процесс формализации математической теории.О границах аксиоматического метода, метода формализации и логики.
Глава VII. Элементы теории алгоритмов.
§31. Интуитивное представление об алгоритмах.
Алгоритмы вокруг нас. Неформальное понятие алгоритма. Необходимость уточнения понятия алгоритма.
§ 32. Машины Тьюринга.
Определение машины Тьюринга.Применение машин Тьюринга к словам. Конструирование машин Тьюринга. Вычислимые по Тьюрингу функции. Правильная вычислимость функций на машине Тьюринга. Композиция машин Тьюринга. Тезис Тьюринга (основная гипотеза теории алгоритмов) . Машины Тьюринга и современные электронно-вычислительные машины.
§ 33. Рекурсивные функции.
Происхождение рекурсивных функций. Основные понятия теории рекурсивных функций и тезис Черча. Примитивно рекурсивные функции. Примитивная рекурсивность предикатов. Вычислимость по Тьюрингу примитивно рекурсивных функций. Функции Аккермана. Оператор минимизации. Общерекурсивные и частично рекурсивные функции. Вычислимость по Тьюрингу частично рекурсивных функций. Частичная рекурсивность функций, вычислимых по Тьюрингу.
§34. Нормальные алгоритмы Маркова.
Марковские подстановки. Нормальные алгоритмы и их применение к словам. Нормально вычислимые функции и принцип нормализации Маркова. Совпадение класса всех нормально вычислимых функций с классом всех функций, вычислимых по Тьюрингу. Эквивалентность различных теорий алгоритмов.
§ 35. Разрешимость и перечислимость множеств.
§ 36. Неразрешимые алгоритмические проблемы.
Нумерация алгоритмов. Нумерация машин Тьюринга. Существование невычислимых по Тьюрингу функций. Проблемы распознавания самоприменимости и применимости. Алгоритмически неразрешимые проблемы в обшей теории алгоритмов. Теорема Раиса. Другие примеры алгоритмической неразрешимости.
§ 37. Теорема Гёделя о неполноте формальной арифметики.
Формальные аксиоматические теории и натуральные числа. Формальная арифметика и ее свойства. Теорема Гёделя о неполноте. Гёдель и его роль в математической логике XX в. .
Глава VIII. Математическая логика и компьютеры, информатика, искусственный интеллект.
* § 38. Математическая логика и программное обеспечение компьютеров.
Теория алгоритмов и математическая логика - фундаментальная основа программирования. Описание компьютерных программ с помощью математической логики. Описание программирования и анализ его концепций с помощью математической логики. Верификация (доказательство правильности) программ с помощью математической логики.
§ 39. Применение компьютеров для доказательства теорем математической логики.
Программа «Логик-теоретик» и программы, близкие к ней. Метод резолюций для доказательства теорем исчисления высказываний и исчисления предикатов.
§ 40. От математической логики к логическому программированию.
Возникновение языка ПРОЛОГ и его развитие. Общая характеристика языка ПРОЛОГ. Краткое описание языка ПРОЛОГ и примеры. Сферы применения языка ПРОЛОГ.
§41. Математическая логика и информатика.
Общее понятие о базе данных. Реляционная база данных и логика запросов в ней.
§ 42. Математическая логика и системы искусственного интеллекта История развития и предмет искусственного интеллекта как науки. Представление знаний в системах искусственного интеллекта. Экспертные системы. Язык ПРОЛОГ в системах искусственного интеллекта. Может ли машина мыслить.
Заключение: Всесильна ли логика в познании законов мышления?
Список литературы.

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

Логика и интуиция -два противоположных и неразрывно связанных между собой свойства человеческого мышления. Логическое (дедуктивное) мышление отличается тем, что оно от истинных посылок всегда приводит к истинному заключению, не опираясь при этом на опыт, интуицию и другие внешние факторы. Интуиция (от лат. intuitio - «пристальное всматривание») представляет собой способность постижения истины путем прямого ее усмотрения без обоснования с помощью логически строгого доказательства. Таким образом, интуиция является своего рода антиподом, противовесом логики и строгости.

Логическая часть мыслительного процесса протекает на уровне сознания, интуитивная - на подсознательном уровне.
Развитие науки и особенно математики немыслимо без интуиции. Различают два вида интуиции в научном познании1: интуицию-суждение и интуицию-догадку. Интуиция-суждение (или философская интуиция-суждение) характеризуется тем, что в этом случае прямое усмотрение истины, объективной связи вещей осуществляется не просто без логически строгого доказательства, но такого доказательства для данной истины не существует и не может существовать в принципе. Интуиция-суждение осуществляется как единый (единовременный) синтетический целостный акт обобщающего характера. Именно такой характер логически недоказуемых утверждений носят рассматриваемые в теории алгоритмов тезисы Тьюринга, Чёрча и Маркова.

Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Математическая логика и теория алгоритмов, Игошин В.И., 2008 - fileskachat.com, быстрое и бесплатное скачивание.

КАЗАНСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ им. А. Н. Туполева

Ш. И. ГАЛИЕВ

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

УЧЕБНОЕ ПОСОБИЕ

Казань 2002

Галиев Ш. И. Математическая логика и теория алгоритмов. – Казань: Издательство КГТУ им. А. Н. Туполева. 2002. - 270 с.

ISBN 5-93629-031-X

Пособие содержит следующие разделы. Логику высказываний и предикатов с приложениями, в том числе метод резолюций и элементы его реализации в языке ПРОЛОГ. Классические исчисления (высказываний и предикатов) и элементы неклассических логик: трёхзначные и многозначные логики, модальную, временную и нечеткую логики. Теорию алгоритмов: нормальные алгоритмы, машины Тьюринга, рекурсивные функции и их взаимосвязи. Понятие о сложности вычислений, различные (по сложности) классы задач и примеры таких задач.

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

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

ВВЕДЕНИЕ
Глава 1. ЛОГИКА ВЫСКАЗЫВАНИЙ
§ 1. Высказывание. Логические операции
§ 2. Пропозициональные буквы, связки и формы (формулы логики
	высказываний). Построение таблиц истинности
§ 3. Упрощения в записях пропозициональных форм
§ 4. Тавтологии (общезначимые формулы). Противоречия
§ 5. Равносильность пропозициональных форм
	Важнейшие пары равносильных пропозициональных форм
	Зависимости между пропозициональными связками
	Нормальные формы
	Совершенные нормальные формы
§ 10. Булева (переключательная) функция
		Приложение алгебры высказываний к анализу и синтезу
		контактных (переключательных) схем
		Приложение алгебры высказываний к анализу и синтезу схем
		из функциональных элементов
		Упражнения

Глава 2. ЛОГИКА ПРЕДИКАТОВ
§ 1. Понятие предиката
§ 2. Кванторы
§ 3. Формулы логики предикатов
§ 4. Интерпретация. Модель
§ 5. Свойства формул в данной интерпретации
	Логически общезначимые формулы. Выполнимые и
	равносильные формулы
	Правила перенесения отрицания через кванторы
	Правила перестановки кванторов
	Правила переименования связанных переменных
§ 10. Правила вынесения кванторов за скобки. Предваренная
	нормальная форма
§ 11. Вопросы и темы для самопроверки
§ 12. Упражнения

Глава 3. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ И МЕТОД РЕЗОЛЮЦИЙ
§ 1. Логическое следствие и проблема дедукции в логике
	высказываний
§ 2. Резольвента дизъюнктов логики высказываний
§ 3. Метод резолюции в логике высказываний
§ 4. Метод насыщения уровня
	Стратегия вычёркивания
	Лок-резолюция
	Метод резолюции для хорновских дизъюнктов
	Преобразование формул логики предикатов. Сколемовская

стандартная форма
§ 9. Унификация
§ 10. Метод резолюции в логике предикатов
§ 11. Приложение метода резолюций для анализа силлогизмов
Аристотеля
§ 12. Использование метода резолюций в языке ПРОЛОГ
§ 13. Введение и использование правил в ПРОЛОГе
§ 14. Рекурсивное задание правил в ПРОЛОГе
§ 15. Особенности ПРОЛОГа
§ 16. Вопросы и темы для самопроверки
§ 17. Упражнения
Глава 4. ДЕДУКТИВНЫЕ ТЕОРИИ
§ 1. Понятие об эффективных и полуэффективных процессах
(методах)
§ 2. Дедуктивные теории
§ 3. Свойства дедуктивных теорий
§ 4. Пример полуформальной аксиоматической теории - геометрия
§ 5. Формальные аксиоматические теории
§ 6. Свойства выводимости
§ 7. Исчисление высказываний
§ 8. Некоторые теоремы исчисления высказываний
§ 9. Эквивалентность двух определений непротиворечивости
§ 10. Производные (доказуемые) правила вывода в исчислении
высказываний
§ 11. Свойства исчисления высказываний
§ 12. Другие аксиоматизации исчисления высказываний
§ 13. Теории первого порядка
§ 14. Формальная арифметика (теория S)
§ 15. Свойства теорий первого порядка
§ 16. Значение аксиоматического метода
§ 17. Теория естественного вывода
§ 18. Вопросы и темы для самопроверки
§ 19. Упражнения
Глава 5. НЕКЛАССИЧЕСКИЕ ЛОГИКИ
§ 1. Трёхзначные логики
§ 2. Многозначные логики
§ 3. Понятие нечёткого множества
§ 4. Нечёткие высказывания и максиминные операции над ними
§ 5. Понятие о нечёткой лингвистической логике
§ 6. Модальные логики
§ 7. Временные (темпоральные) логики
§ 9. Упражнения
Глава 6. ТЕОРИЯ АЛГОРИТМОВ
§ 1. Неформальное понятие алгоритма
§ 2. Алфавит, слова, алгоритм в алфавите. Вполне эквивалентные
алгоритмы
§ 3. Нормальный алгоритм (алгоритм А.А.Маркова)
§ 4. Функции частично вычислимые и вычислимые по Маркову

§ 5. Замыкание, распространение нормального алгоритма
§ 6. Операции над нормальными алгоритмами
§ 7. Машина Тьюринга
§ 8. Задание машины Тьюринга
§ 9. Алгоритм Тьюринга. Вычислимость по Тьюрингу
	Связь между машинами Тьюринга и нормальными алгоритмами
	Основная гипотеза теории алгоритмов (принцип нормализации
	или тезис Черча)
	Проблема алгоритмической неразрешимости
	Примеры алгоритмически неразрешимых массовых проблем
	Сведения любого преобразования слов в алфавите к
вычислению значений целочисленных функций
	Примитивно рекурсивные и общерекурсивные функции
	Примитивно рекурсивность некоторых функций. Частично
	рекурсивные функции
	Ламбда исчисление
	Основные результаты
	Вопросы и темы для самопроверки
	Упражнения
Глава 7. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ С ПОМОЩЬЮ
АЛГОРИТМОВ
§ 1. Понятие о сложности вычислений
§ 2. Временная сложность вычислений (алгоритма)
§ 3. Полиномиальные алгоритмы и задачи. Класс Р
§ 4. NP класс
§ 5. NP -полные и NP -трудные задачи
§ 6. Класс Е
§ 7. Емкостная (ленточная) сложность алгоритма
§ 8. Вопросы и темы для самопроверки
§ 9. Упражнения
ЛИТЕРАТУРА
ПРИЛОЖЕНИЯ
Варианты типового задания
Тесты для самоконтроля
Тест по логике высказываний (тест № 1)
Тест по логике предикатов (тест № 2)
Тест по логическому следствию и методу резолюций (тест № 3)
Тест по дедуктивным теориям (тест № 4)
Тест по теории алгоритмов (тест № 5)
Тест по неклассическим логикам и сложности вычислений (тест
Ответы к тестам самоконтроля

ВВЕДЕНИЕ

Логика обычно понимается как наука о способах доказательств и опровержений. Математическая логика – это логика, развиваемая с помощью математических методов.

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

1. Все люди смертны. Сократ – человек. Следовательно, Сократ – смертен.

2. Все котята любят играть. Мура – котенок. Следовательно, Мура любит играть.

Оба эти вывода имеют одну и ту же форму: Все А сутьВ ;С естьА ; следовательно,С естьВ . Эти выводы верны в силу своей формы, независимо от содержания, независимо от того истинны или ложны взятые по себе посылки и заключения. Систематическая формализация и каталогизация правильных способов рассуждений – одна из основных задач логики. Если при этом применяется математический аппарат и исследования посвящены в первую очередь изучению математических рассуждений, то эта логика является математической логикой (формальной логикой). Данное определение не является строгим (точным) определением. Чтобы понять предмет и метод математической логики лучше всего приняться за ее изучение.

Математическая логика начала формироваться давно. Зарождение ее идей и методов происходило в Древней Греции, Древней Индии и Древнем Китае примерно с VI в. до н. э. Уже в этот период ученые пытались расположить цепь математических доказательств в такую цепочку, чтобы переход от одного звена к другому не оставлял сомнений и завоевал всеобщее признание. Уже в самых ранних дошедших до нас рукописях «канон» математического стиля изложения прочно установлен. Впоследствии он получает окончательное завершение у великих классиков: Аристотеля, Евклида, Архимеда. Понятие доказательства у этих авторов уже ничем не отличается от нашего.

Логика как самостоятельная наука берет свое начало в исследованиях Аристотеля (384 – 322 г. до н. э.). Великий философ древности Аристотель осуществляет энциклопедическую систематизацию античных знаний во всех областях существовавшей тогда науки. Логические исследования Аристотеля изложены, в основном, в двух его трудах «Первая аналитика» и «Вторая аналитика», объединенных под общим названием «Органон» (Орудие познания).

Следует особо отметить большое значение для становления и развития математической логики одного из самых блестящих достижений в истории человечества, а именно, превращение геометрии в точную дедуктивную систему в работе Евклида (330 – 275 г. до н. э.) «Начала». Именно этот дедуктивный подход с ясным осознанием целей и методов был положен в основу развития философской и математической мысли последующих столетий.

Также большое значение для становления и развития логики сыграли достижения в алгебре (алгебра Буля) и в других математических дисциплинах, в том числе и вновь в геометрии (создание неевклидовой геометрии - геометрии Лобачевского – Гаусса – Бойяи). Краткий обзор становления математической логики можно найти в .

В формировании и становлении математической логики участвовали многие и многие ученые, как древних времен, так средневековья и последующих времен.

Принципиальное и прикладное значение математической логики

Принципиальное значение математической логики – обоснование математики (анализ основ математики).

Прикладное значение математической логики в настоящее время очень велико. Математическая логика применяется для следующих целей:

анализа и синтеза (построения) цифровых вычислительных машин и других дискретных автоматов, в том числе и интеллектуальных систем;

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

анализа и формализации интуитивного понятия вычислимости;

выяснения существования механических процедур для решения задач определённого типа;

анализа проблем сложности вычислений.

Также математическая логика оказалась тесно связанной и с рядом вопросов лингвистики, экономики, психологии и философии.

В данном пособии излагаются основные понятия математической логики и теории алгоритмов. Материал, изложенный в пособии,

соответствует государственному образовательному стандарту для направления «Информатика и вычислительная техника» и может быть использован для студентов обучающихся по разным специальностям этого направления.

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

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

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

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Кафедра автоматизации обработки информации

Утверждаю:

Зав. каф. АОИ

профессор

Ю.П. Ехлаков

«__» _____________2007 г.

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

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

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

для студентов специальности 230102 –

«Автоматизированные системы обработки информации и управления»

Разработчики:

ст. преподаватель каф. АОИ

Т.О. Перемитина

Томск – 2007

Практическое занятие № 1 «Формулы алгебры высказываний» 3

Практическое занятие № 2 «Равносильные преобразования формул алгебры высказываний» 10

Практическое занятие № 3 «Нормальные формы формул» 12

Практическое занятие № 4 «Логические рассуждения» 14

Практическое занятие № 5 «Формулы логики предикатов» 18

Практическое занятие № 6 «Булевы функции» 23

Практическое занятие № 7 «Частично рекурсивные функции» 28

Практическое занятие № 8 «Машины Тьюринга» 34

Практическое занятие № 1 «Формулы алгебры высказываний»

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

Пример истинного высказывания: "Земля вращается вокруг Солнца". Пример ложного высказывания: "3 > 5". Не всякое предложение является высказыванием, к высказываниям не относятся вопросительные и восклицательные предложения. Не является высказыванием предложение: «Каша – вкусное блюдо», так как не может быть единого мнения о том, истинно оно или ложно. Предложение «Есть жизнь на Марсе» следует считать высказыванием, так как объективно оно либо истинно, либо ложно, хотя никто пока не знает, какое именно.

Поскольку предметом изучения логики являются только значения истинности высказываний, для них вводят буквенные обозначения A, B, … или X,Y...

Считается, что каждое высказывание либо истинно, либо ложно. Для краткости, будем вместо значения истинно писать 1, а вместо значения ложно – 0. Например, X= "Земля вращается вокруг Солнца" иY= "3 > 5", причемX=1 иY= 0. Высказывание не может быть одновременно истинным и ложным.

Высказывания могут быть простыми и составными. Высказывания "Земля вращается вокруг Солнца" и "3 > 5" являются простыми. Составные высказывания образуются из простых с помощью связок естественного (русского) языка НЕ, И, ИЛИ, ЕСЛИ-ТО, ТОГДА-И-ТОЛЬКО-ТОГДА. При использовании буквенных обозначений для высказываний эти связки заменяются специальными математическими символами, которые можно рассматривать как символы логических операций.

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

Отрицанием (инверсией) высказыванияX называется высказывание, истинное тогда и только тогда, когдаX ложно (обозначаетсяили, читается “неX ” или “неверно, чтоX ”).

Конъюнкцией
двух высказываний называется высказывание, истинное тогда и только тогда, когда истинны оба высказыванияX иY . Эта логическая операция соответствует соединению высказываний союзом ”и”.

Дизъюнкцией
двух высказыванийX иY называется высказывание ложное в том и только в том случае, когда оба высказыванияX иY ложны. В разговорной речи этой логической операции соответствует союз “или” (не исключающее “или”).

Импликацией двух высказыванийX и Y называется высказывание, ложное тогда и только тогда, когдаX истинно, аY – ложно (обозначается
; читается “X влечетY ”, “еслиX , тоY ”). Операнды этой операции имеют специальные названия:X – посылка,Y – заключение.

Эквиваленцией двух высказыванийX иY называется высказывание, истинное тогда и только тогда, когда истинностные значенияX иY одинаковы (обозначение:
).

Таблица 1. Логические операции

Операнды логических операций могут принимать только два значения: 1 или 0. Поэтому каждую логическую операцию , &,,,легко задать с помощью таблицы, указав значение результата операции в зависимости от значений операндов. Такая таблица называется таблицей истинности (табл. 2).

Таблица 2. Таблица истинности логических операций

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

Для систематического изучения формул, выражающих высказывания, вводят переменные высказывания P, P 1 , P 2 , ..., P N , принимающие значения из множества {0, 1}.

Формула логики высказываний F (P 1 , P 2 ,..., P N ) называется тавтологией или тождественно истинной , если ее значение для любых значений P 1 , P 2 ,..., P N есть 1 (истина). Формулы, принимающие значение “истина” хотя бы при одном наборе списка переменных, называются выполнимыми . Формулы, принимающие значение “ложь” при любых значениях переменных, называются противоречиями (тождественно ложными, невыполнимыми).

11.1. Понятие об алгоритме и теории алгоритмов

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

В соответствии с ГОСТ 19781-74 «Машины вычислительные. Программное обеспечение. Термины и определения» алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату. При этом предполагается наличие исполнителя алгоритма – такого объекта, который «умеет» выполнять эти действия.

Слово «алгоритм» происходит, как предполагают, от имени среднеазиатского (узбекского) математика XIII века Аль Хорезми (Абу Абдалла Мухаммед ибн Муса ал Хорезми ал Меджуси) – «Algorithmi» в латинской транскрипции, впервые сформулировавшего правила (процедуру) выполнения четырех арифметических действий в десятичной системе счисления.

Пока вычисления были несложными, особой необходимости в алгоритмах не было. Когда появилась потребность в многократных пошаговых процедурах, тогда и появилась теория алгоритмов. Но при еще большем усложнении задач, оказалось, что часть из них невозможно решать алгоритмическим путем. Таковы, например, многие задачи, решаемые «бортовым компьютером» человека – головным мозгом. Решение таких задач основывается на иных принципах – эти принципы использует новая наука – нейроматематика и соответствующие технические средства – нейрокомпьютеры. В этом случае применяются процессы обучения, проб и ошибок – то есть то, чем мы сейчас и занимаемся.

Качество алгоритма определяется его свойствами (характеристиками). К основным свойствам алгоритма относятся :

1. Массовость . Предполагается, что алгоритм может быть пригоден для решения всех задач данного типа. Например, алгоритм для решения системы линейных алгебраических уравнений должен быть применим к системе, состоящей из произвольного числа уравнений.

2. Результативность . Это свойство означает, что алгоритм должен приводить к получению результата за конечное число шагов.

3. Определенность . Предписания, входящие в алгоритм, должны быть точными и понятными. Эта характеристика обеспечивает однозначность результата вычислительного процесса при заданных исходных данных.

4. Дискретность . Это свойство означает, что описываемый алгоритмом процесс и сам алгоритм могут быть разбиты на отдельные элементарные этапы, возможность выполнения которых на ЭВМ у пользователя не вызывает сомнений.

Сегодня на дворе «цифровое тысячелетие» и может создастся впечатление, что алгоритмам подвластны любые задачи. Оказывается, многие задачи не могут быть решены алгоритмически. Это так называемые алгоритмически неразрешимые задачи.

Для доказательства алгоритмической разрешимости или неразрешимости задач необходимы математически строгие и точные средства. В середине 30-х годов прошлого века были предприняты попытки формализовать понятие алгоритма и были предложены различные модели алгоритмов : рекурсивные функции; «машины» – Тьюринга, Поста; нормальные алгорифмы Маркова.

Впоследствии было установлено, что эти и другие модели эквивалентны в том смысле, что классы решаемых ими задач совпадают . Этот факт носит название тезиса Черча. Сейчас это общепризнанно. Формальное определение понятия алгоритма создало предпосылки для разработки теории алгоритма ещё до разработки первых ЭВМ. Прогресс вычислительной техники стимулировал дальнейшее развитие теории алгоритмов. Помимо установления алгоритмической разрешимости задач, теория алгоритмов занимается еще и оценкой сложности алгоритмов в смысле числа шагов (временная сложность) и требуемой памяти (пространственная сложность), а также занимается разработкой эффективных в этом смысле алгоритмов.

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

Поэтому еще одна задача теории алгоритмов – решение вопроса исключения перебора вариантов в комбинаторных алгоритмах. Оценка сложности алгоритмов и создания так называемых эффективных алгоритмов – одна из важнейших задач современной теории алгоритмов.