Д.В. Гринченков

С.И. Потоцкий

МАТЕМАТИЧЕСКАЯ

ЛОГИКА

И ТЕОРИЯ АЛГОРИТМОВ

ДЛЯ ПРОГРАММИСТОВ

Допущено Министерством образования и науки

Российской Федерации

в качестве учебного пособия

для студентов высших учебных заведений,

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

УДК 510.5(075.8) ББК 22.12я73 Г85 Рецензенты:

В.А. Волосухин, проректор по научной работе ФГОУ ВПО «Новочеркасская государственная мелиоративная академия», засл. деятель науки РФ, д-р техн. наук, проф., В.В. Изранцев, проректор по научной работе АНО «Международный банковский институт» (г. Санкт-Петербург), заведующий кафедрой прикладной информатики, д-р техн. наук, проф.

Гринченков Д.В.

Г85 Математическая логика и теория алгоритмов для программистов : учебное пособие / Д.В. Гринченков, С.И. Потоцкий. — М. : КНОРУС, 2010. — 208 с.

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

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

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

УДК 510.5(075.8) ББК 22.12я Гринченков Дмитрий Валерьевич Потоцкий Сергей Иванович

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

И ТЕОРИЯ АЛГОРИТМОВ ДЛЯ ПРОГРАММИСТОВ

Изд. № 1746. Подписано в печать 19.08.2009. Формат 6090/16.

Гарнитура «NewtonC». Печать офсетная.

Усл. печ. л. 13,0. Уч.изд. л. 8,3. Тираж 3000 экз. Заказ № ООО «Издательство КноРус».

129110, Москва, ул. Большая Переяславская, 46, стр. 7.

Тел.: (495) 680-7254, 680-0671, 680-1278.

E-mail: [email protected] http://www.knorus.ru Отпечатано в ОАО «ИПК «Ульяновский Дом печати».

432980, г. Ульяновск, ул. Гончарова, 14.

© Гринченков Д.В., Потоцкий С.И., © ЗАО «МЦФЭР», ISBN 9785406001202 © ООО «Издательство КноРус», ОГЛАВЛЕнИЕ Введение..................................... Глава 1. Теория множеств........................... 1.1. Основные понятия теории множеств.................... 1.1.1. Множества, способы задания множеств............... 1.1.2. Основные операции над множествами и их свойства...... 1.2. Прямое произведение множеств..................... Глава 2. Основные положения булевой алгебры.............. 2.1. Булева алгебра и ее применение...................... 2.1.1. Определение булевой алгебры................... 2.1.2. Области применения булевой алгебры.............. 2.1.3. Высказывания............................. 2.2. Функции алгебры логики.......................... 2.2.1. Понятие функции и способы ее задания............. 2.2.2. Элементарные логические операции............... 2.2.3. Свойства основных логических функций............. 2.2.4. Задание функции формулой. Эквивалентные преобразования логических выражений............. 2.2.5. Двойственные функции....................... 2.3. Специальные разложения логических функций............ 2.3.1. Конъюнктивная и дизъюнктивная нормальные формы.... 2.3.2. Совершенно нормальные конъюнктивная и дизъюнктивная формы...................... 2.4. Минимизация булевых функций..................... 2.4.1. Понятие минимизации........................ 2.4.2. Метод неопределенных коэффициентов............. 2.4.3. Метод Квайна — Мак Класки.................... 2.4.4. Метод карт Карно........................... 2.5. Полнота и замкнутость множества булевых функций......... 2.5.1. Понятие функционально полной системы............ 2.5.2. Алгебра Жегалкина.......................... 2.5.3. Замыкание и замкнутые классы.................. Глава 3. Математическая логика...................... 3.1. Общие сведения о формальных и аксиоматических системах.... 3.2. Исчисление высказываний......................... 3.3. Методы, используемые для определения общезначимости формул исчисления высказываний................... 3.3.1. Алгоритм редукции.......................... 4 • Оглавление Глава 4. Расширения традиционной логики................ 4.1. Общие положения модальной логики предикатов........... 4.2. Трехзначная семантика для модальной логики предикатов...... 4.3. Семантика возможных миров и четырехзначная логика....... Глава 5. Теория алгоритмов......................... 5.5. Сравнительный анализ основных моделей представления Глава 6. Нечеткие множества и выводы.................. 6.1. Обозначение нечетких множеств и функция принадлежности... Глава 7. Логическое программирование и язык Пролог......... 7.1. Основная идея логического программирования и история 7.13. Примеры использования Пролога для решения 7.13.1. Экспертные системы и управление стратегией вывода... Глава 8. Задачи и примеры их решения................... 8.1. Теория множеств и булева алгебра................... 8.6.2. Ответы на вопросы и задачи для самостоятельного Приложение 1. ОСНОВНЫЕ ЛОГИЧЕСКИЕ ФУНКЦИИ......... Приложение 2. СВОЙСТВА ОСНОВНЫХ   Приложение 3. ПРАВИЛА ЭКВИВАЛЕНТНЫХ   Библиографический список......................... Математическая логика (ее называют также формальной логикой, теорией доказательств) изучает законы и формы корректных человеческих рассуждений.

Этот раздел математики имеет особое значение в изучении математических наук.

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

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

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

В математике же можно провести множество экспериментов, которые подтвердят некоторый факт, но математическим законом он будет признан только после того, как будет приведено строгое формальное доказательство. Поэтому можно сказать, что главная цель математической логики — дать точное и адекватное определение понятия «математическое доказательство».

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

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

Пример. Рассмотрим цепочку логических рассуждений:

Посылка 1: из А следует В.

Посылка 2: из С следует А.

Вывод: из С следует В.

Эта цепочка рассуждений может иметь практически любое содержание. Например:

1. Все слоны серые. Джамбо — слон. Следовательно, Джамбо серый.

2. Все студенты сдали сессию. Петров — студент. Следовательно, Петров сдал сессию и т. п.

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

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

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

Считается, что первые работы по логике появились в V в. до н. э.

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

Развитие математики выявило недостатки логики, разработанной Аристотилем, и потребовало дальнейшего ее развития. Идея о поВведение строении логики на математической основе была предложена немецким математиком Г. Лейбницем, который считал, что основные понятия логики возможно обозначить символами, соединяющимися по особым правилам, что позволит всякое рассуждение заменить вычислением.

Первая реализация идей Лейбница принадлежит английскому ученому Дж. Булю (середина XIX в.), создавшему алгебру, в которой буквами обозначены высказывания (повествовательные предложения, о которых можно сказать, что они истинны или ложны). Его алгебра получила название алгебры высказываний. Введение в логику символических обозначений послужило основой для создания новой науки — математической логики. Применение математики к логике позволило представить логические теории в новой удобной форме и использовать вычислительный аппарат в решении задач, ранее практически недоступных человеческому мышлению, что существенно расширило область логических исследований.

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