Математическая логика

ДИСКРЕТНАЯ МАТЕМАТИКА Математическая логика Белоусов Иван Николаевич Институт радиоэлектронники и информационных технологий Уральский федеральный университет 27 апреля 2020 Высказывания Логика высказываний —- самый простой раздел математической логики, лежащий в основе всех остальных ее разделов. Основными объектами рассмотрения являются высказывания. Под высказыванием понимают повествовательное предложение, о котором можно сказать одно из двух: истинно оно или ложно. Пусть есть множество высказываний, фраз, принимающих значение "истина" или "ложь". Примером могут быть фразы "сегодня холодно". "Идёт дождь" , "Коля Петров учится в группе Р-23022" , "Президент России поехал в Китай" и др. Будем называть их элементарными высказываниями и обозначать прописными буквами латинского алфавита (A, B, . . . ). При этом отвлечёмся от конкретного смысла высказывания, оставим только его истинностное значение. В исчислении высказываний не рассматриваются утверждения, имеющие значения, отличные от значений «истинно» и «ложно». Не рассматривается и трёхзначная логика, со значениями, скажем «Да», «Нет», «Не знаю». Ответ отличный от «Да» должен быть «Нет». Древние философы называли этот принцип законом исключения третьего. Высказывание – это утверждение, которое может быть только истинно или ложно. Его принято обозначать символами И (от ИСТИНА), или Л (от ЛОЖЬ), или соответственно, 1 (для истинного значения) или 0 (для значения ложь). Значение высказывания зависит от предметной области. Например, высказывание «число 15 — простое» будет истинным в восьмеричной и ложным в десятичной системе счисления. Поэтому весьма важно конкретизировать область на которой определено употребляемое высказывание. Формулы Из элементарных высказываний строятся более сложные высказывания с помощью логических связок "НЕ" , "И" , "ИЛИ" , "ТО ЖЕ, ЧТО" ("ЭКВИВАЛЕНЦИЯ" ), "ИЗ . . . СЛЕДУЕТ . . . " . (". . . ВЛЕЧЁТ . . . " , ". . . ПОТОМУ, ЧТО . . . " .). Эти связки называются сентенциональными. Связки логики высказываний представляют функции истинности или функции алгебры логики. В таб.1.1 представлены логические связки и их обозначения. Таблица1.1 Название Отрицание Конъюнкция Дизъюнкция Импликация Эквивалентность Обозначение Как читается ∧ ∨ → ↔ не и или влечёт эквивалентно Другие обозначения ¬, not, не & , and, и |, or, или ⇒ ⇔, ≈ Определение 1. Отрицанием высказывания p называется высказывание p̄ (или ¬p), которое истинно только тогда, когда p ложно. Пример. Высказывание «Неправда, что идёт снег» является отрицанием высказывания «идёт снег». Определение 2. Конъюнкцией высказываний p и q называется высказывание, которое истинно только тогда, когда p и q истинны, т. е. p = 1 и q = 1. Пример. Чтобы успешно сдать экзамен, нужно иметь при себе зачётку и правильно ответить на вопросы. Для успешной сдачи экзамена нужно выполнить оба условия. Если обозначить как p — «иметь зачётку» и q — «правильно ответить на вопросы», то условием сдачи будет конъюнкция высказываний p ∧ q. Определение 3. Дизъюнкцией высказываний p и q называется высказывание, которое ложно тогда и только тогда, когда оба высказывания ложны, т. е. p = 0 и q = 0. Пример. (7 > 3 или 4 6= 1) = 1; √ (sin 2x имеет период 2π или 2 — рациональное число) = 0. Определение 4. Импликацией высказываний p и q называется высказывание, которое ложно тогда и только тогда, когда p истинно, q ложно, т. е. p = 1 и q = 0 (из p следует q). Пример. Вышеприведённый пример с успешной сдачей экзамена можно записать как p ∧ q → r, где r — «успешно сдать экзамен». Определение 5. Эквиваленцией высказываний p и q называется высказывание, которое истинно только и только тогда, когда значения высказываний p и q совпадают (p эквивалентно q). Пример. «Граф является двудольным тогда и только тогда, когда он не содержит циклов нечётной длины». Если p — высказывание «иметь циклы нечетной длины», q — «граф двудольный», то начальная фраза примера запишется в виде p ↔ q. Значения истинности для бинарных связок представлены в табл.1.2. Таблица 1.2 p 1 1 q 1 1 p̄ 1 1 p∨q 1 1 1 p∧q 1 p→q 1 1 1 p↔q 1 1 С помощью связок можно получать составные высказывания, которым соответствует формула, например, (A ∧ B) → (Ā ∨ B). Такие высказывания называют сложными. Каждое сложное высказывание, как и элементарное принимает значение из множества {0, 1}. В формулах используются скобки для определения порядка выполнения действий. Кроме этого определяют порядок выполнения логических операций в выражении (от наибольшего приоритета к наименьшему): отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность. Пример. Пусть значения элементарных высказываний: p1 = 1, p2 = 0, p3 = 1 и имеется составное высказывание: ((p̄1 ∧ p2 ) → p3 ) ↔ (p̄2 ∨ p̄3 ). Найти значение сложного высказывания. Решение: ((p̄1 ∧ p2 ) → p3 ) ↔ (p̄2 ∨ p̄3 ) = ((0 ∧ 0) → 1) ↔ (1 ∨ 0) = (0 → 1) ↔ 1=1↔1=1 Ответ. Значение сложного высказывания – 1. Итак, словарь исчисления высказываний даёт возможность строить сложные высказывания из простых или элементарных, соединяя последние связками. Получаем формулы, которые являются объектами языка. Аналогия с естественными языками очевидна: фраза — это составное высказывание, построенное по определённым правилам. Совокупность правил построения выглядит так: I Базис. Всякое высказывание является формулой. I Индукционный шаг. Если A и B формулы, то Ā, A ∧ B, A ∨ B, A → B, A ↔ B — формулы. I Ограничение. Формула однозначно получается с помощью правил, описанных в базисе и индукционном шаге. Множество всех формул счётное (можно установить взаимно однозначное соответствие между ним и множеством натуральных чисел), разрешимое (можно достоверно выяснить, является ли данное высказывание формулой или нет). Объектами изучения естественных и формальных языков являются синтаксис и семантика. Синтаксис позволяет распознать фразы среди наборов слов. Семантика придаёт определённое значение фразам. Высказывания либо истинны, либо ложны, значит семантическая область {1, 0}. Семантика есть набор правил интерпретации формул. Интерпретация — это отображение i, сопоставляющее каждому элементарному высказыванию p некоторое значение истинности. Интерпретацию i заданную на множестве элементарных высказываний, можно распространить на множество формул посредством таблиц истинности. Контрольные упражнения. 1. Найти значения следующих формул: a. (p̄1 → (p2 ↔ p3 )) ∧ (p̄1 ∨ p̄2 ∨ p̄3 ), если p1 = 1, p2 = 0, p3 = 1. b. ¬(p1 → (p̄2 → ¬(p3 ↔ (p̄1 ∧ (p2 ∨ p3 ))))), если p1 = 0, p2 = 0, p3 = 1. c. (p1 ∧ p2 ∧ p3) → (p3 ∨ (¬p2 → p1 )), если p1 = 1, p2 = 0, p3 = 0. d. ¬(p1 → ¬(p2 ∨ (¬p3 ∧ p2 ↔ p3 ))), если p1 = 1, p2 = 1, p3 = 1. e. (p1 ∨ ¬p2 ) → (p3 → ¬(p2 → ¬(p1 ∨ ¬p2 ∨ ¬p3 ), если p1 = 0, p2 = 0, p3 = 1. 2. Записать символически высказывания, употребляя буквы для обозначения простых высказываний. Построить таблицы истинности для каждого высказывания: a. Пётр ходит в кино только в том случае, когда там показывают комедию. b. Необходимое и достаточное условие для жизни растений состоит в наличии питательной почвы, чистого воздуха и солнечного света. c. Студент не может заниматься, если он устал или голоден. d. Если Иван выиграет в лотерею, он купит компьютер и будет праздновать всю ночь. e. Если он не выиграет в лотерею или не купит компьютер, то праздновать всю ночь не будет. f. Если Артёму нравятся фиолетовые галстуки, то он популярен и у него много друзей. g. Если Игорь носит желтые ботинки, то он не модный и если он не модный, то у него странные друзья. h. Если он не удачлив, то он и не популярен. i. Он удачлив и богат, следовательно, он популярен. j. Он читает научную литературу и любит фантастику, следовательно, он ученый-фантаст. k. Если он информатик, то он либо работает за компьютером, либо читает книги об ЭВМ. l. Если он или умеет писать или читать, то он грамотный человек. m. Для того, чтобы натуральное число a было нечётным, достаточно, чтобы оно было простым и большим двух. n. Необходимым условием сходимости последовательности S является ограниченность S. o. У меня быстродействующий компьютер и я закончу проект вовремя и сдам экзамен. 3. Сколько строк содержит таблица истинности высказывания, состоящего из n компонентов? Выполнимые и общезначимые формулы Формула семантически выполнима, или просто выполнима, если её можно интерпретировать со значением истина. Например: (p ∧ q) — выполнима. Множество формул называют выполнимым (непротиворечивым), если найдется такая интерпретация, при которой все формулы истины. Если такой интерпретации не находится, то множество невыполнимо (противоречиво). Существуют высказывания, которые истины в любой области. Примером может служить высказывание A ∨ ¬A. Такие высказывания называются общезначимыми, тождествено-истинными или тавтологиями. Отрицание общезначимой формулы является невыполнимая формула или противоречие. Иногда из вида высказывания не ясно, является ли оно тавтологией. Проверка состоит в вычислении значения истинности высказывания на всех наборах значений входящих в него элементарных высказываний. Если формула содержит k различных высказывания, тогда она допускает 2k интерпретаций. Рассмотрев все эти 2k интерпретаций, можно определить какая это формула. Если A — формула, то запись | = A означает, что A — тавтология. Необходимо уметь: I Записывать в формальном виде любое сложное высказывание сформулированное фразами естественного языка. I Определять семантическую область составного высказывания. Определять, является ли данное высказывание тавтологией. I При переходе от высказываний на естественном языке некоторые связки могут иметь другой смысл. Так, связка И обозначает истинность формулы только если истины входящие в неё элементарные высказывания. Поэтому её значение (и смысл) не зависит от порядка элементарных высказываний в формуле (например, во фразе "холодно и идёт дождь" ). Но рассмотрите предложения "он убил и ему стало страшно" или "ему стало страшно, и он убил" . В первом варианте И по значению играет роль условного предложения ("Ему стало страшно, потому что он убил" ). Во втором варианте причина и следствие меняются местами. В логике истина-ложь не всякое предложение имеет смысл. Например, предложение "это предложение ложно" не может быть ни ложным, ни истинным. Существуют парадоксы, т.е. рассуждений, приводящих к противоречиям. Например, парадокс лжеца. Некто говорит «Я лгу». Если при этом он не лжёт, то произнесённое им есть ложь, и поэтому он не лжёт. Если же при этом он говорит правду, то произнесённое им есть истина, и поэтому он лжёт. В любом случае оказывается, что он лжёт и не лжёт одновременно. Контрольные упражнения. 1. Определить, является ли выражения тавтологией? a. r ∧ (p → q) → q b. p ∨ ¬q ∧ r ↔ p c. (p → q) ↔ ¬p ∨ q ∨ r d. (¬p → q) ∧ (¬p → ¬q)) → p e. (p → q) ∧ (q → r) → (p → r) 2. Построить таблицы истинности для следующих выражений: a. ¬r ∧ ¬(¬s ∧ ¬p) → p b. ¬p ↔ q ∧ ¬r c. ((p → q) ∧ (q → r) ∧ p) → (p → r) d. (p → ¬q) ∧ (s ∧ p → s) e. ¬p ∨ (¬(p ∧ s) → (¬s ∧ r)) Алгебраический подход Семантика произвольной формулы исчисления высказываний полностью определяется её таблицей истинности. Разные формулы могут иметь одну и ту же семантику. Для логических формул важно уметь обнаруживать эквивалентность двух различно представленных объектов. Определение 6. Две формулы назовём равносильными, если для любых наборов значений переменных они принимают одинаковые значения. A ≡ B тогда и только тогда, когда | = A ↔ B. Чтобы преобразовать логическую формулу в равносильную полезно знать «замечательные тождества», которые задают различные способы представления объекта. Замечательные тождества. I. Законы булевой алгебры. Математик Джордж Буль (1815–1864) описал алгебру, основанную на операторах И, ИЛИ и НЕ. Закон двойного отрицания (инволюция): ¬¬A ≡ A; Законы коммутативности: A&B ≡ B&A, A ∨ B ≡ B ∨ A; Законы ассоциативности: A&(B&C) ≡ (A&B)&C, A ∨ (B ∨ C) ≡ (A ∨ B) ∨ C; Законы дистрибутивности: A&(B ∨ C) ≡ (A&B) ∨ (A&C), A ∨ (B&C) ≡ (A ∨ B)&(A ∨ C); Свойства констант: A&1 = A, A&0 = 0, A ∨ 1 = 1, A ∨ 0 = A. Закон идемпотентности: A&A ≡ A; A ∨ A ≡ A. II. Законы де Моргана: ¬(A&B) ≡ ¬A ∨ ¬B; ¬(A ∨ B) ≡ ¬A&¬B. III. Другие замечательные тождества. Связь операций: A → B ≡ ¬A ∨ B, A ↔ B ≡ (A → B)&(B → A), A&B ≡ ¬(A → ¬B), A ∨ B ≡ ¬A → B, A → ¬B ≡ B → ¬A. Закон контрапозиции: A → B ≡ ¬B → ¬A. Закон противоположности: A ∨ B ≡ ¬A ∨ ¬B Используя эти равносильности можно по данной формуле построить ей равносильные или эквивалентные. Примеры. a) (A ∨ A)&B ∨ A ≡ A&B ∨ A ≡ A&B ∨ A&1 ≡ A&(B ∨ 1) ≡ A&1 ≡ A. b) B → (¬A&B) ≡ ¬B∨(¬A&B) ≡ (¬B∨¬A)&(¬B∨B) ≡ (¬B∨¬A)&1 ≡ (¬B ∨ ¬A) ≡ ¬(B&A).