Математическая логика и теория алгоритмов
Покупка
Основная коллекция
Издательство:
Сибирский федеральный университет
Автор:
Михальченко Галина Ефимовна
Год издания: 2018
Кол-во страниц: 74
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-7638-3932-6
Артикул: 764372.01.99
Кратко изложен теоретический материал по дисциплине «Математическая логика и теория алгоритмов», приведены примеры решения типовых задач, представлены задачи различной сложности для решения на практических занятиях и самостоятельной работы. Предназначено для студентов направления 09.03.02 «Информационные системы и технологии», а также других направлений (09.03.04 «Программная инженерия», 27.03.03 «Системный анализ и управление», 27.03.04 «Управление в технических системах»).
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 09.03.02: Информационные системы и технологии
- 09.03.04: Программная инженерия
- 27.03.03: Системный анализ и управление
- 27.03.04: Управление в технических системах
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.
Кратко изложен теоретический материал по дисциплине «Математическая логика и теория алгоритмов», приведены примеры решения типовых задач, представлены задачи различной сложности для решения на практических занятиях и самостоятельной работы. Г. Е. Михальченко МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Учебное пособие ИНСТИТУТ КОСМИЧЕСКИХ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
Министерство науки и высшего образования Российской Федерации Сибирский федеральный университет Г. Е. Михальченко МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Учебное пособие Красноярск СФУ 2018
УДК 510.6(07) ББК 22.122я73 М693 Р е ц е н з е н т ы: А. К. Шлепкин, доктор физико-математических наук, профессор кафедры «Высшая математика и компьютерное моделирование» КрасГАУ; Н. Г. Сучкова, кандидат физико-математических наук, доцент кафедры «Прикладная математика и компьютерная безопасность» ИКИТ СФУ Михальченко, Г. Е. М693 Математическая логика и теория алгоритмов : учеб. пособие / Г. Е. Михальченко. – Красноярск : Сиб. федер. ун-т, 2018. – 74 с. ISBN 978-5-7638-3932-6 Кратко изложен теоретический материал по дисциплине «Математическая логика и теория алгоритмов», приведены примеры решения типовых задач, представлены задачи различной сложности для решения на практических занятиях и самостоятельной работы. Предназначено для студентов направления 09.03.02 «Информационные системы и технологии», а также других направлений (09.03.04 «Программная инженерия», 27.03.03 «Системный анализ и управление», 27.03.04 «Управление в технических системах»). Электронный вариант издания см.: УДК 510.6(07) http://catalog.sfu-kras.ru ББК 22.122я73 ISBN 978-5-7638-3932-6 © Сибирский федеральный университет, 2018
Алгебра высказываний 3 ОГЛАВЛЕНИЕ Введение .......................................................................................................... 4 Глава 1. Алгебра высказываний ................................................................ 5 1.1. Высказывания и операции с ними .......................................................... 5 1.2. Формулы алгебры высказываний ........................................................... 7 1.3. Отношения логического следования и равносильности ...................... 9 1.4. Свойства операций с высказываниями .................................................. 12 1.5. Нормальные формы формул алгебры высказываний ........................... 13 Задачи к главе 1. Алгебра высказываний ..................................................... 19 Глава 2. Булевы функции ............................................................................ 23 2.1. Определение и свойства булевых функций ........................................... 23 2.2. Нормальные формы булевых функций .................................................. 25 2.3. Классы функций, сохраняющих постоянные (P0, P1) ........................... 26 2.4. Класс самодвойственных функций (S) ................................................... 26 2.5. Алгебра и полином Жегалкина ............................................................... 28 2.6. Класс линейных функций (L) .................................................................. 30 2.7. Класс монотонных функций (M) ............................................................ 32 2.8. Полнота систем булевых функций ......................................................... 34 2.9. Булевы функции и релейно-контактные схемы .................................... 38 2.10. Релейно-контактные схемы в ЭВМ ...................................................... 41 Задачи к главе 2. Булевы функции ................................................................ 44 Глава 3. Логика предикатов ....................................................................... 48 3.1. Понятие предиката. Множество истинности предиката. Виды предикатов ............................................................................................. 48 3.2. Операции над предикатами и их свойства ............................................ 49 3.3. Формулы логики предикатов и их виды ................................................ 52 3.4. Равносильность формул логики предикатов ......................................... 53 3.5. Нормальные формы формул логики предикатов .................................. 55 3.6. Логическое следование формул. Правило резолюций ......................... 57 Задачи к главе 3. Логика предикатов ............................................................ 58 Глава 4. Элементы теории алгоритмов .................................................... 62 4.1. Машины Тьюринга ................................................................................... 62 4.2. Рекурсивные функции ............................................................................. 66 Задачи к главе 4. Машины Тьюринга ............................................................ 69 Заключение ..................................................................................................... 72 Библиографический список ........................................................................ 73
ВВЕДЕНИЕ Математическая логика, как и классическая, исследует процессы умозаключений и позволяет из истинности одних суждений делать выводы об истинности или ложности других независимо от их конкретного содержания. Использование в логике математических методов (алгебраизация логики и построение логических исчислений) стало началом развития математической логики – новой области математики. Основная задача математической логики – это формализация знаний и рассуждений. Математика является наукой, в которой все утверждения доказываются с помощью умозаключений, поэтому математическая логика, по существу, – наука о математике. Математическая логика дала средства для построения логических теорий и вычислительный аппарат для решения задач. Она нашла широкое применение в различных областях науки и техники (например, в лингвистике, в теории релейно-контактных схем, в экономике, в вычислительной технике, в информационных системах и др.). Понятия математической логики лежат в основе таких ее приложений, как базы данных, экспертные системы, системы логического программирования. Эти же понятия становятся методологической основой описания анализа и моделирования автоматизированных интегрированных производств. Применение в логике математических методов становится возможным тогда, когда суждения формулируются на некотором точном языке. На практике множество элементарных логических операций является обязательной частью набора инструкций всех современных микропроцессоров и, соответственно, входит в языки программирования. Это важнейшее практическое приложение методов математической логики.
Алгебра высказываний 5 ГЛАВА 1. АЛГЕБРА ВЫСКАЗЫВАНИЙ 1.1. Высказывания и операции с ними В известном труде Аристотеля «Органон» (IV в. до н. э.) есть раздел о правильных умозаключениях «Силлогистика». До XVII века в Европе логика развивалась на основе логики Аристотеля. Попытку превратить логику в математическую науку в XVII веке предпринял Готфрид Вильгельм Лейбниц (1646–1716), но решительного успеха не добился. Однако в современной математической логике его конструктивный подход отражается в применении так называемых таблиц истинности. Современный вид математическая логика приобрела в 80-е годы XIX века в трудах Готлиба Фреге (1848–1925). Он построил аксиоматику логики высказываний, ввел понятие предиката и др. Определение. Высказыванием называется повествовательное предложение, которое может быть либо истинным, либо ложным. Истина («И» или «1») и ложь («Л» или «0») называются истинностными значениями высказываний. Высказывания обозначаются буквами A, B, C, …; их истинностные значения [A], [B], [C], … соответственно. Таким образом, [A] = 1, если истинное высказывание; 0, если ложное высказывание. A A Примеры: 1) A – «2 – простое число», [A] = 1; 2) B – «Cолнце светит» [B] = 1, если солнце светит; 3) C – «x + y > 1» – не высказывание; 4) D – «3 < 1», [D] = 0. Приведенные высказывания нельзя разбить на части, также являющиеся высказываниями. Высказывания «Неверно, что 3 < 1» или «2 – простое число», или «3 < 1» таковыми не являются. Высказывания, построенные из простых с помощью связок «не», «и», «или» и сочетаний «если ..., то ...», «... тогда и только тогда, когда ...» носят специальные названия. Приведем соответствующие определения. Определение. Отрицанием высказывания A называется высказывание A («Не A», «Неверно, что A»), которое истинно тогда, когда A ложно и ложно тогда, когда A истинно. Данное и следующие далее определения удобно приводить с помощью так называемой таблицы истинности. Для отрицания она имеет вид
Глава 1 6 A A 0 1 1 0 Если A – «2 – простое число», то A – «Неверно, что 2 – простое число» или «2 не является простым числом». Если B – «Солнце светит», то B – «Неверно, что солнце светит» или «Солнце не светит». Определение. Конъюнкцией высказываний A и B называется высказывание A ˄ B («A и B»), которое истинно тогда и только тогда, когда истинны оба высказывания. Таблица истинности операции конъюнкции имеет вид A B A B 0 0 0 0 1 0 1 0 0 1 1 1 Пример. Если A – «2 – простое число», B – «Солнце светит», то A ˄ B – «2 – простое число и солнце светит». Определение. Дизъюнкцией высказываний A и B называется высказывание A ˅ B («A или B»), которое ложно тогда и только тогда, когда ложны оба высказывания. Таблица истинности операции дизъюнкции имеет вид A B A B 0 0 0 0 1 1 1 0 1 1 1 1 Определение. Импликацией высказываний A и B называется высказывание A → B («Если A, то B», или «Из A следует B»), которое ложно тогда и только тогда, когда A истинно, а B ложно. При этом A называется посылкой, B – следствием или заключением. Таблица истинности операции импликации имеет вид A B A → B 0 0 1 0 1 1 1 0 0 1 1 1 Пример. Предложение «Если я лягу поздно, то встану тоже поздно» является импликацией высказываний «Я лягу поздно» и «Я встану поздно».
Алгебра высказываний 7 Определение. Эквиваленцией высказываний A и B называется высказывание A ↔ B («A тогда и только тогда, когда B», или «A необходимо и достаточно для B»), которое истинно только тогда, когда оба высказывания имеют одинаковые истинностные значения. Таблица истинности операции эквиваленции имеет вид A B A ↔ B 0 0 1 0 1 0 1 0 0 1 1 1 Пример. Определить истинностное значение высказывания A B C , если [A] = 0, [B] = 1, [C] = 0. Решение. Из определения конъюнкции высказываний следует, что [B ˄C] = 0. Из определения отрицания высказывания следует, что [ B C ] = 1. Из определения операции эквиваленции следует, что [ A B C ] = 0. Коротко эти рассуждения можно записать так: A 0 ↔ 0 B C 1 0 0 1 Пример. Определить истинностное значение высказывания (P ˅ Q) → (R ↔ S ), если [P] = 1, [Q] = 0, [R] = 0, [S] = 0. Решение. (P ˅ Q) 1 0 1 1 → 0 (R ↔ S ), 0 0 0 1 0 1.2. Формулы алгебры высказываний Определение. Пропозициональной переменной называется переменная, обозначающая высказывания. Обозначения – P, Q, R, … A, B, C, … X, Y, … .
Глава 1 8 Определение. 1. Пропозициональная переменная является формулой. 2. Если F и G – формулы, то формулами также являются ( F ), (F ˄ G), (F ˅ G), (F → G), (F ↔ G), 3. Других формул нет. Примеры: 1) ((X ˅ Y) → Z), ((( X ) → Y) ↔ X) – формулы; 2) (Z ˅ (X ˄ Y)) и ((Z ˅ X) ˄ Y) – разные формулы; 3) Z → X ˅ Y – не формула. Далее рассмотрим классификацию формул алгебры высказываний, для чего понадобится понятие интерпретации формулы. Определение. Говорят, что задана интерпретация I = (A1, A2, …, An) формулы F(X1, X2, …, Xn), если в ней переменные заменяют определенными высказываниями: X1 = A1, X2 = A2, …, Xn = An. Высказывание, полученное в результате интерпретации, будем обозначать F(I) = F (A1, A2, …, An). Формулы алгебры высказываний делятся на четыре (иногда на три) вида, в зависимости от истинностных значений высказываний, которые можно получить в результате интерпретаций этих формул. Определение. Формула F называется тавтологией (|= F) или тождественно истинной, если при любой интерпретации I она становится истинным высказыванием I ([F(I)] = 1). Пример. Показать, что тавтологиями являются формулы X ˅ X , (X ˄ Y) → X. Решение. Достаточно составить их таблицы истинности: X X X X 0 1 1 1 0 1 X Y X ˄ Y (X ˄ Y) → X 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1
Алгебра высказываний 9 Определение. Формула F называется выполнимой, если существует такая её интерпретация I, в результате которой она становится истинным высказыванием I ([F(I)] = 1). Составив таблицу истинности для формулы (X ˅ Y) → X, можно убедиться в том, что она выполнима. Определение. Формула F называется опровержимой, если существует такая её интерпретация I, в результате которой она становится ложным высказыванием I ([F(I)] = 0). Приведенная выше выполнимая формула одновременно является и опровержимой (нужно взять интерпретации, при которых [X] = 0, [Y] = 1). Определение. Формула F называется противоречием или тождественно ложной, если при любой интерпретации I она становится ложным высказыванием I ([F(I)] = 0). Упражнение. Показать, что противоречиями являются формулы , ( ) . X X X Y X Приведем теоремы, полезные для отыскания тавтологий. Теорема. Если формула F – тавтология, то формула F – противоречие и наоборот. Теорема (правило заключения). Если формулы F и F → G – тавтологии, то формула G также является тавтологией. Доказательство: Проведем доказательство от противного то есть предположим, что G не является тавтологией. Тогда существует такая интерпретация I0, при которой [G(I0)] = 0. Так как [F(I0)] = 1, то [F(I0) → G(I0)] = 0. Это противоречит условию теоремы о том, что F → G тавтология. Значит наше предположение неверно и G – тавтология. Теорема доказана. Теорема (правило подстановки). Если формула F(…, X, …), содержащая переменную X, является тавтологией, то формула F(…, G, …), полученная подстановкой в формулу F вместо переменной X любой формулы G, также является тавтологией. 1.3. Отношения логического следования и равносильности Рассмотрим отношение логического следования между формулами алгебры высказываний.
Глава 1 10 Определение. Формула G логически следует из формулы F, если при всех интерпретациях I, при которых F(I) истинно, G(I) также истинно. При этом пишут F => G. Пример. Доказать, что (X ˄ Y) ˄ Z => X. Доказательство следует из того, что конъюнкция (X ˄ Y) ˄ Z истинна тогда и только тогда, когда истинны все ее компоненты, значит, когда истинно X. Пример. Доказать, что P → Q => P ˅ Q. Данное отношение между формулами становится очевидным, если построить таблицы истинности для обеих формул: P Q P → Q P P Q 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 Теорема. Из F логически следует G тогда и только тогда, когда тавтологией является импликация F → G. Доказательство: 1. Пусть F => G. Тогда для каждой интерпретации I, такой что [F(I)] = 1, имеем [G(I)] = 1. Поэтому [F(I) → G(I)] = 1, то есть |= F → G. 2. Пусть |= F → G. Тогда для тех I, для которых [F(I)] = 1, также [G(I)] = 1. По определению логического следования это означает, что F => G. Теорема доказана. Данное выше определение понятия логического следования обобщается следующим образом. Определение. Формула G логически следует из формул F1, F2, …, Fk. (F1, F2, …, Fk => G), если при всех интерпретациях, при которых истинны F1(I), F2(I), …, Fk(I), истинно высказывание G(I). Теорема. Из F1, F2, …, Fk логически следует G тогда и только тогда, когда тавтологией является импликация (((F1 ˄ F2) ˄ …) ˄ Fk) → G. Рассмотрим пример применения на практике понятия логического следования. Пример. Верно ли рассуждение? Если я пойду завтра на первое занятие, то должен буду встать рано, а если я пойду вечером на танцы, то лягу спать поздно. Если я лягу спать поздно, а встану рано, то я буду вынужден довольствоваться пятью часами сна. Я не в состоянии обойтись пятью часами сна. Следовательно, я должен или пропустить завтра первое занятие, или не ходить на танцы.