Математическая логика и теория алгоритмов, Галиев Ш.И., 2002

Математическая логика и теория алгоритмов, Галиев Ш.И., 2002.

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




Понятие предиката.
Логика предикатов представляет собой развитие логики высказываний. Она содержит в себе всю логику высказываний, т.е. элементарные высказывания, рассматриваемые как величины, которые принимают значения И либо Л. Но помимо этого, язык логики предикатов вводит в рассмотрение утверждения, отнесенные к предметам, т.е. производится более детальный анализ предложений. Рассмотрение логики предикатов вызвано тем, что логика высказываний не позволяет моделировать рассуждения всех видов, в частности рассуждении с использованием понятии «каждый», «некоторый». Отметим, что логика предикатов тоже не охватывает всевозможных случаев рассуждений, например, когда нужно исследовать рассуждения, истинность которых зависит от времени или вводятся понятия «должно быть» и «может быть» и т.п.; подробнее см. главу 5.

Пусть М- некоторое множество предметов, а1, а2,...- какие-то определенные предметы (элементы) из этого множества. Тогда через А(а2) будем обозначать некоторое высказывание о предмете a1 а через А(а2) - то же высказывание о предмете а2. Например, если М есть множество всех натуральных чисел и a1=3, а2=8, то A(ai) может обозначать высказывание "3-простое число", тогда А(а2) будет обозначать "8-простое число".

Как и в логике высказываний, будем рассматривать эти высказывания только с той точки зрения, что они представляют либо истину, либо ложь, обозначаемые соответственно И и Л. При этом значения высказывания А(а1) и А(а2) могут быть разными или нет в зависимости от выбранных предметов а1 и а2. Следовательно, в отличие от алгебры высказываний будем считать, что значения И и Л ставятся в соответствие определенным предметам или группам предметов.

ОГЛАВЛЕНИЕ.
ВВЕДЕНИЕ.
Глава 1. ЛОГИКА ВЫСКАЗЫВАНИЙ.
§1. Высказывание. Логические операции.
§2. Пропозициональные буквы, связки и формы (формулы логики высказываний). Построение таблиц истинности.
§3. Упрощения в записях пропозициональных форм.
§4. Тавтологии (общезначимые формулы). Противоречия.
§5. Равносильность пропозициональных форм
§6. Важнейшие пары равносильных пропозициональных форм.
§7. Зависимости между пропозициональными связками.
§8. Нормальные формы.
§9. Совершенные нормальные формы.
§10. Булева (переключательная) функция.
§11. Приложение алгебры высказываний к анализу и синтезу контактных (переключательных) схем.
§12. Приложение алгебры высказываний к анализу и синтезу схем из функциональных элементов.
§13. Вопросы и темы для самопроверки.
§14. Упражнения.
Глава 2. ЛОГИКА ПРЕДИКАТОВ.
§1. Понятие предиката.
§2. Кванторы.
§3. Формулы логики предикатов.
§4. Интерпретация. Модель.
§5. Свойства формул в данной интерпретации.
§6. Логически общезначимые формулы. Выполнимые и равносильные формулы.
§7. Правила перенесения отрицания через кванторы.
§8. Правила перестановки кванторов.
§9. Правила переименования связанных переменных.
§10. Правила вынесения кванторов за скобки. Предваренная нормальная форма.
§11. Вопросы и темы для самопроверки.
§12. Упражнения.
Глава 3. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ И МЕТОД РЕЗОЛЮЦИЙ.
§1. Логическое следствие и проблема дедукции в логике высказываний.
§2. Резольвента дизъюнктов логики высказываний.
§3. Метод резолюции в логике высказываний.
§4. Метод насыщения уровня.
§5. Стратегия вычёркивания.
§6. Лок-резолюция.
§7. Метод резолюции для хорновских дизъюнктов.
§8. Преобразование формул логики предикатов. Сколемовская стандартная форма.
§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. Временные (темпоральные) логики.
§8. Вопросы и темы для самопроверки.
§9. Упражнения.
Глава 6. ТЕОРИЯ АЛГОРИТМОВ.
§1. Неформальное понятие алгоритма.
§2. Алфавит, слова, алгоритм в алфавите. Вполне эквивалентные алгоритмы.
§3. Нормальный алгоритм (алгоритм А.А. Маркова).
§4. Функции частично вычислимые и вычислимые по Маркову.
§5. Замыкание, распространение нормального алгоритма.
§6. Операции над нормальными алгоритмами.
§7. Машина Тьюринга.
§8. Задание машины Тьюринга.
§9. Алгоритм Тьюринга. Вычислимость по Тьюрингу.
§10. Связь между машинами Тьюринга и нормальными алгоритмами.
§11. Основная гипотеза теории алгоритмов (принцип нормализации или тезис Черча).
§12. Проблема алгоритмической неразрешимости.
§13. Примеры алгоритмически неразрешимых массовых проблем.
§14. Сведения любого преобразования слов в алфавите к вычислению значений целочисленных функций.
§15. Примитивно рекурсивные и общерекурсивные функции.
§16. Примитивно рекурсивность некоторых функций. Частично рекурсивные функции.
§17. Ламбда исчисление.
§18. Основные результаты.
§19. Вопросы и темы для самопроверки.
§20. Упражнения.
Глава 7. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ С ПОМОЩЬЮ АЛГОРИТМОВ.
§1. Понятие о сложности вычислений.
§2. Временная сложность вычислений (алгоритма).
§3. Полиномиальные алгоритмы и задачи. Класс Р.
§4. NP класс.
§5. NP-полные и NP-трудные задачи.
§6. Класс Е.
§7. Емкостная (ленточная) сложность алгоритма.
§8. Вопросы и темы для самопроверки.
§9. Упражнения.
ЛИТЕРАТУРА.
ПРИЛОЖЕНИЯ.
Варианты типового задания Тесты для самоконтроля.
Тест по логике высказываний (тест № 1).
Тест по логике предикатов (тест № 2).
Тест по логическому следствию и методу резолюций (тест № 3).
Тест по дедуктивным теориям (тест № 4).
Тест по теории алгоритмов (тест № 5).
Тест по неклассическим логикам и сложности вычислений (тест №6).
Ответы к тестам самоконтроля.



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

Скачать djvu
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - djvu - Яндекс.Диск.




Теги: учебник по математике :: математика :: Галиев