Е. А. Леснова. МАТЕМАТИЧЕСКАЯ ЛОГИКА Шпаргалка
2 Публикуется с разрешения правообладателя: Литературного агентства «Научная книга» Заведующая редакцией: Елистратова М. В. Выпускающий редактор: Юрова Д. А. Корректор: Гончарова Л. М. Леснова Е. А. МАТЕМАТИЧЕСКАЯ ЛОГИКА ШПАРГАЛКА, с. 64 Предлагаемая нами шпаргалка по курсу «Математическая логика» предназначена для студентов технических специальностей средних и высших учебных заведений. Материал, содержащийся в книге, подобран таким образом, чтобы студент мог без труда подготовиться к экзамену или зачету и успешно сдать его.
3 Содержание 1. Чем занимается и что изучает математическая логика. Высказывания. Логические связки Логические операции над высказываниями: отрицание, дизъюнкция, конъюнкция, импликация Эквиваленция. Примеры операций над высказываниями Предикаты. Логические операции над предикатами Понятие формулы логики предикатов, значения и равносильность. Логические следования Общезначимость формул логики предикатов Неклассические логики Модальная логика Категорические высказывания. Суть категорических высказываний Тавтологии. Аксиомы Теорема дедукции. Следствие из теоремы дедукции. Метод дедукции Четыре случая из метода дедукции. Начальное понятие вывода Два правила вывода. Аксиомы логики высказываний. Принцип резолюции Доказательство некоторых законов логики Доказательство некоторых логических следствий Проблемы непротиворечивости, полноты, разрешимости теории Машины с оракулом. Вычислимость с оракулом Частичная функция, вычислимая относительно всюду определенных функций. Относительная вычислимость Оценка скорости роста. Функция Аккермана Вычислимые функции. Разрешимые множества. Перечислимые неотделимые множества Перечислимые неразрешимые множества. Перечислимость и вычислимость Универсальные функции. Диагональная конструкция Простые множества: конструкция Поста Главные универсальные функции. Теорема Вычислимые последовательности вычислимых функций. Главные универсальные множества Предваренные нормальные формы (лемма и предложение) Нормальная форма Сколема. Правило С Теорема Геделя о полноте Теория первого порядка с равенством Понятие относительного алгоритма, или алгоритма с оракулом Аксиома универсальной функции Влияние теории алгоритмов на алгоритмическую практику (формализация алгоритма, алгоритмические проблемы в математике) Вычислительные и порождающие модели. Смешанные вычисления
4 17. Понятие алгоритма и его характерные черты. Характеристики сложности алгоритмов. Примеры простых алгоритмов Конечные детерминированные автоматы Вероятностные алгоритмы Два подхода меры сложности алгоритма. Расчет трудоемкости алгоритма и временные оценки Метод прямого определения среднего времени. Классификация алгоритмов по виду функции трудоемкости Разрешимые и перечислимые множества Уточнение понятия алгоритма Алгоритмическая разрешимость. Вычислимые функции Машина Тьюринга. Реализация алгоритма в машине Тьюринга Нормальные алгоритмы Маркова Неразрешимые алгоритмические проблемы. Проблемы распознавания, эквивалентности Метод резолюций и его сравнение с методом естественного вывода Сколемизация и сколемовские функции. Теорема Эрбрана, первая и вторая формы Теорема об унификации Рекурсивные функции. Примитивно-рекурсивные функции. Оператор минимизации Тезис Черча. Примитивно-рекурсивные множества Частично-рекурсивные функции. Другие виды рекурсии Счетные множества Сложные и сложносокращенные виды силлогизма. Условные и условно-категорические силлогизмы Виды разделительных силлогизмов Определение счетных множеств Метод цифр Канторовский диагональный метод Трансцендентные действительные числа Абстрактные множества Индукция. Научная индукция. Индукция по мнению Ф. Бэкона Структура доказательства. Виды доказательства
5 1а 1. Чем занимается и что изучает математическая логика. Высказывания. Логические связки Логика изучает мышление. Есть и другие науки, которые имеют его своим предметом исследования, например психология и физиология. Однако в логической науке мышлением интересуются лишь постольку, поскольку оно занимается рассуждением, доказательством, обоснованием своих утверждений и выводов. Она, таким образом, является наукой о законах мышления. Ее называют также наукой о выводном знании, наукой о доказательствах. Логика исследует сцепление мыслей между собой, их необходимые связи: обязательность, непреложность следования выводов из каких-либо суждений или, наоборот, несовместимость тех или иных высказываний. Важную роль в логике играет понятие формы мышления. Логику можно даже называть наукой о формах мысли. Нельзя объяснить в нескольких словах, что они собой представляют. Например, возьмем две пары таких суждений (1 и 2). 1. Некоторые розы красные. Все розы цветы. 2. Некоторые озера соленые. Все озера водоемы. Можно ли сделать из них какие-либо выводы? Вдумавшись в их смысл, можно заключить, что из пары (1): «Некоторые цветы красные», а из пары (2) «Некоторые водоемы соленые». В целом получается два рассуждения; их называют умозаключениями, причем данная, взятая нами для примера разновидность их, называется в логике силлогизмом. В полном виде эти умозаключения записываются следующим образом. 1. Некоторые розы красные. Все розы цветы. Некоторые цветы красные. 2. Некоторые озера соленые. Все озера водоемы. Некоторые водоемы соленые. В каждом из них сначала какой-то части предметов (некоторые розы, некоторые озера) приписывается одно свойство, потом им же (но уже не части, а всем) приписывается еще одно свойство. Это позволяет делать выводы о наличии связи между самими этими свойствами. Достаточно указать, что сформулированные рассуждения по некоторым чертам сходны между собой, это означает, что у них одинаковая форма в логическом смысле этого слова. Благодаря ей мы сможем, опираясь на одну лишь интуитивно ощущаемую аналогию с предыдущими примерами, делать заключения и из других, подобных по форме высказываний. Для того чтобы не писать «истина» и «ложь» («true» и «false»), часто используют лишь начальные буквы этих слов. А еще чаще просто 1 и 0. Логические связки: 1) и: союзу и соответствует логическая связка конъюнкция А В эта связка применяется при переводе на формальный язык утверждений следующего вида: 2а 2. Логические операции над высказываниями: отрицание, дизъюнкция, конъюнкция, импликация 1. Отрицание. Отрицанием высказывания Х называется новое высказывание, которое является истинным, если высказывание Х ложно, и ложным, если высказывание Х истинно. Отрицательные высказывания обозначаются Х _, (или Х) и считается «не Х» или «неверно, что Х». Логические значения высказывания Х _ можно описать с помощью таблицы: Таблицу такого вида принято называть таблицей истинности. _ X X Пусть Х высказывание. Так как Х также является высказыванием, то можно образовать отрицание высказывания Х, т.е. высказывание Х, которое называется двойным отрицанием Х. Ясно, что логические значения высказываний Х и Х совпадают. Например, для высказывания «Река Волхов вытекает из озера Ильмень» отрицанием будет высказывание «Неверно, что река Волхов вытекает из озера Ильмень» или «Река Волхов не вытекает из озера Ильмень», а двойным отрицанием будет высказывание «Неверно, что река Волхов не вытекает из озера Ильмень». 2. Конъюнкция (логическое умножение). Конъюнкцией двух высказываний, y называется новое высказывание, которое считается истинным, если оба высказывания, y истинны, и ложным, если хотя бы одно из них ложно. Конъюнкция высказываний, y обозначается символом х&y или (y), читается «и y». Выражения, y называются членами конъюнкции. Логическое значение конъюнкции описывается следующей таблицей истинности: y &y
6 1б а) т.е. А и В; б) как А так и В; в) А вместе с В ; г) не только А, но и В; д) А, хотя и В. Утверждение А В истинно в том, и только в том случае, когда истины и А и В и ложно во всех остальных случаях, 2) или: АВ эта связка применяется при переводе на формальный язык утверждений следующего вида: а) либо А либо В; в) А или В или оба вместе. Дизъюнкция высказываний считается истиной, если истинно хотя бы одно входящее в нее высказывание, ложно тогда, когда оба ложны; 3) не: A _ отрицание эта связка применяется при переводе на формальный язык утверждений следующего вида: не А; а) А не верно; б) А не может быть; в) не А истина; г) А ложно; 4) если то: А В импликация эта связка применяется при переводе на формальный язык утверждений следующего вида: а) А влечет за собой В; б) А есть достаточное условие для В; в) В есть необходимое условие, что А; 5) тогда и только тогда А В эквиваленция (эквивалентность) эта связка применяется при переводе на формальный язык утверждений следующего вида: а) А есть необходимое и достаточно условие для В; б) А если только В; г) если А, то В и обратно. 2б Например, для высказываний «6 делится на 2», «6 делится на 3» их конъюнкция будет высказывание «6 делится на 2 и 6 делится на 3», которое, очевидно, истинно. Из определения операции конъюнкции видно, что союз «и» в алгебре логики употребляется в том же смысле, что и в повседневной жизни. Но в обыденной речи не принято соединять союзом «и» два высказывания, далеких друг от друга по содержанию, а в алгебре логики рассматривается конъюнкция двух любых высказываний. 3. Дизъюнкция (логическое сложение). Дизъюнкцией двух высказываний, y называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний, y истинно, и ложным, если они оба ложны. Дизъюнкция высказываний, y обозначается символом y, читается «или y». Высказывания, y называются членами дизъюнкции. y y Импликация. Импликацией двух высказываний,y называется новое высказывание, которое считается ложным, если истинно, а y ложно, и истинным во всех остальных случаях. Импликация высказываний, y обозначается символом y,читается «если, то y» или «из следует y».высказывание называют условием или посылкой, высказывание y следствием или заключением, высказывание y следованием или импликацией. y y
7 3a 3. Эквиваленция. Примеры операций над высказываниями Эквиваленция. Эквиваленцией (или эквивалентностью) двух высказываний, y называется новое высказывание, которое считается истинным, когда оба высказывания, y либо одновременно истины, либо одновременно ложны, и ложным во всех остальных случаях. Эквиваленция высказываний, y обозначается символом y, читается «для того, чтобы необходимо и достаточно, чтобы у y или, тогда и только тогда, когда y». Высказывания, y называются членами эквиваленции. Логические значения операции эквиваленции описываются следующей таблицей истинности: y y Эквивалентность играет важную роль в математических доказательствах. Известно, что значительное число теорем формулируется в форме необходимых и достаточных условий, т.е. в форме эквивалентности. В этом случае, зная об истинности или ложности одного из двух членов эквивалентности и доказав истинность самой эквивалентности, мы заключаем об истинности или ложности второго члена эквивалентности. Пример 1 А = «Я пойду в театр» В = «Я встречу друга» Решение A B = «Я пойду в театр, хотя и встречу друга» AB = «Либо я пойду в театр, либо я встречу друга» А= «Я не пойду в театр» A B = «Я встречу друга при условии, что пойду в театр» A B = «Я пойду в театр, если только я встречу друга» Всякое сложное предложение, которое состоит из простых, можно представить в символической форме, в результате получаем формулу. На каждом наборе значений переменных формула принимает некоторые значения, значит, всякую формулу в логике высказываний можно рассматривать как функцию. 4a 4. Предикаты. Логические операции над предикатами Логика предикатов, как и традиционная формальная логика, расчленяет элементарное высказывание на субъект (буквально подлежащее, хотя оно и может играть роль дополнения) и предикат (буквально сказуемое, хотя оно может играть и роль определения). Субъект это то, о чем что-то утверждается в высказывании; предикат это то, что утверждается о субъекте. Предикаты делятся на два класса: а) одноместные предикаты; б) двуместные предикаты. Одноместным предикатом P() называется произвольная функция переменного X, определяющая на множестве М и принимающая значения множества . Множество М, на котором определен предикат, принимает значение «истина», называется множеством истинности предиката P(), т.е. множество истинности предиката P() это множество Jp = Двуместным предикатом P() называется функция двух переменных, y, определенная на множестве М = = ММ 2 и принимающая значения из множества . Конъюнкцией двух предикатов P() и Q() называется новый предикат P()&Q(), который принимает значение «истина» при тех и только тех значениях M, при которых каждый из предикатов принимает значение «истина», и принимает «ложь» во всех остальных случаях. Очевидно, что областью истинности предиката P()&Q() является общая часть областей истинности предикатов P() и Q(), т.е. пересечение Jp Jq. Дизъюнкцией двух предикатов P() и Q() называется новый предикат P()Q(), который принимает значение «ложь» при тех и только тех значениях M, при которых каждый из предикатов принимает значение «ложь», и принимает значение «истина» во всех остальных случаях. Отрицанием предиката P() называется новый предикат P(), который принимает значения «истина» при всех значениях M, при которых предикат P() принимает значения «ложь», и принимает значения «ложь» при тех значениях M, при которых предикат P() принимает значения «истина». Из этого определения следует, что Jp = M/ Jp = C Jp. Импликацией предикатов P() и Q() называется новый предикат P() Q(), который является ложным при тех и только тех значениях M, при которых одновременно P() принимает значения «истина», а Q() значение «ложь», и принимает значения «истина» во всех остальных случаях. 7
8 3б Пример 2 Рассмотрим сложное высказывание: «Если применить стальные конструкции, то масса снижается и стоимость увеличивается. Стальные конструкции не применяются, а масса снижается». Решение Этому высказыванию соответствует следующая формула: (A В C)&( А B) _ Вычислим значение этой _ формулы: В&C = 1; A В&C = 2; А=3; А&B = 4; (A В&C)&( А&B) = 5. Если имеется некоторая формула, то можно построить соответствующее предложение, заменяя буквы простыми предложениями. Пример 3 А = «Идет снег», В = «2 2 = 4», С = «Я хочу домой» (A В C)&( А B) _ = «Если идет снег, то 2 2 = 4 не смотря на то, что я хочу домой. Не только снег идет, но и 2 2 = 4». Истинность высказываний определяется только таблицей и не связана с содержанием конкретных простых высказываний. A B C Л Л Л Л И И Л Л Л Л И Л И И Л Л Л И Л Л И И И И Л И И И И И И И И Л Л Л Л Л Л Л И Л И Л Л Л Л Л И И Л Л Л Л Л Л И И И И Л Л Л Л 4б Пусть имеется предикат P(), определенный на множестве М. Если а некоторый элемент из множества М, то подстановка его вместо х в предикатах P() превращает этот предикат в высказывание P(а). Такое высказывание называется единичным. Наряду с образованием из предикатов единичных высказываний в логике предикатов рассматриваются еще две операции, которые превращают одноместный предикат в высказывание. Квантор всеобщности. Пусть P() предикат, определенный на множестве М. Под высказыванием х P() понимают высказывание, истинное, когда P() истинно для каждого элемента х из множества М, и ложное в противном случае. Это высказывание уже не зависит от х. Квантор существования. Пусть P() предикат, определенный на множестве М. Под высказыванием х P() понимают высказывание, которое является истинным, если существует элемент M, для которого P() истинно, и ложным в противном случае. Это высказывание уже не зависит от х. 8
9 5а 5. Понятие формулы логики предикатов, значения и равносильность. Логические следования 1. Каждое высказывание, как переменное, так и постоянное, является формулой (элементарной). 2. Если F (,, ) n местная предикатная переменная или постоянный предикат, а 1, 2,, n предметные переменные или предикатные постоянные (не обязательно все разные), то F ( 1, 2,, )) есть формула. 3. Если А и В формулы, причем такие, что одна и та же предметная переменная не является в одной из них связанной, а в другой свободной, то слова АВ, А В, А В есть формулы. В этих формулах те переменные, которые в исходных формулах были свободными, являются свободными, а те, которые были связанными, являются связанными. 4. Если А формула, то А формула, и характер предметных переменных при переходе от формулы А к формуле А не меняется. 5. Если А() формула, в которую предметная переменная входит свободно, то слова A и A ( ) ( ) являются формулами, причем предметная переменная входит в них связанно. 6. Всякое слово, отличное от тех, которые названы формулами в пунктах 1 5, не являются формулой. Значение формулы логики предикатов О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество М, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики предикатов зависит от значений трех видов переменных: 1) значений входящих в формулу переменных высказываний; 2) значений свободных предметных переменных на множестве М; 3) значений предикатных переменных. В качестве примера рассмотрим формулу: yz ( Py (, ) Py (, ) (1), в которой двуместный предикат P(, y) определен на множестве М М, где М = . В формулу (1) входит переменный предикат P(, y), предметные переменные, y, z, две из которых y и z связаны кванторами, а свободна. Возьмем за конкретное значение предикат P(, y), фиксированный предикат P 0 (, y): «< y», а свободной переменной придадим значение 0 = 5М. Тогда при значениях y, меньших 0 = 5, предикат P 0 ( 0, y) принимает значение «ложь», а импликация P(, y) P(y, z) при всех zм принимает значения «истина», т.е. высказывание y z(p0(, y) P0(y, z)) имеет значение «истина». 6а 6. Общезначимость формул логики предикатов Предикат логическая функция, аргументы которой могут принимать значения из некоторой предметной функции, а сама функция может принимать значение «истина» либо «ложь». Если переменная одна, то предикат одноместный, две двухместный и т.д. Нульместный предикат, то есть предикат, не содержащий переменных высказывание. Операции Из элементарных (атомарных) предикатов с помощью логических операций можно получить сложные предикаты. Здесь уместно сделать важное содержательное замечание: язык предикатов наиболее приближенный к естественным языкам формальный математический (логический) язык. В логике предикатов к операциям, имеющим место в логике высказываний, добавляются операции навешивания кванторов. квантор общности. P ( ) «для всех х P()». квантор существования. P «есть такие х, что P()». (! или 1 существует и притом единственный). ( ) Кванторы связывают соответствующие переменные. Связанные переменные можно воспринимать как константы, а несвязанные переменные свободные переменные как собственно переменные. Содержательные примеры предикатов: R() х любит кашу (одноместный предикат). R все любят кашу (нульместный предикат высказывание). ( ) R некоторые (есть такие) х любят кашу. ( ) L(, y) х любит y (двухместный предикат). Ly y (, ) существует, который любит всех y. (C() O()) все студенты C() отличники O(). некоторые студенты C() отличники O(). Здесь есть повод поразмышлять об использовании операций и & в двух последних высказываниях. ( C ( ) O ( )) Для конечных областей можно операции навешивания кванторов выразить через конъюнкцию и дизъюнкцию. Пусть х , P() = P(a 1 ) P(a 2 ). P(a n ), P() = P(a 1 ) P(a 2 ). P(a n ). Общезначными называются формулы, которые истинны при каждом приписывании значений входящих в них связанных переменных и предикатов. Обозначение: = Для доказательства общезначимости формул используется аппарат логики высказываний, дополненный теоремами для выражений, содержащих квантор: 1) пусть Q() формула, свободная для y, тогда: 9
10 5б Равносильные формулы логики предикатов Определение 1. Две формулы логики предикатов А и В называются равносильными на области М, если они принимают одинаковые логические значения при всех значениях входящих в них переменных, отнесенных к области М. Определение 2. Две формулы логики предикатов А и В называются равносильными, если они равносильны на всякой области (АВ). Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов. Пусть A() и B() переменные предикаты, а С переменное высказывание. Тогда: 1) A() A(); 2) A() A(); 3) A() A(); 4) A() A(); 5) A() B() [A() B()]; 6) C B() [C B()]; 7) C B() [C B()]; 8) C B() [C B()]; 9) [B() C] B() C; 10) [A() B()] A() B(); 11) [C B()] C B(); 12) [C B()] C. B(); 13) A() yb(y) y[a() B(y); 14) [C B()] C B(); 15) [B() C] B() C. Логические следования Говорят, что формула В логически следует из формулы А, и пишут таким образом: А В, если В = «истина» на всех наборах переменных, на которых А = «истина», А В тогда и только тогда, когда импликация является тавтологией = А В. Логическое следование означает, что из истинности А следует истинность В, но если А = «ложь», то из этого ничего не следует (т.е. из В ничего утверждать нельзя). Формула В логически следует из множества формул. А 1, А 2,, А n B. Если из истинности всех А i следует истинность В. Это можно записать следующим образом: А 1 А 2 А m В Установить, является ли формула логическим следованием, можно, доказав соответствующую тавтологию. 6б а) I= ; Q( ) Q( y) б) I = Q(y) Q(). 2) пусть R формула, не содержащая свободных вхождений переменной. Q() произвольная формула, тогда: а) если =R Q(), то =R Q(); б) если =Q() R, то =R. Следствие из 1-й и 2-й теоремы: формула =Q() тогда и только тогда, когда = Q(). Правило универсальной конкретизации (УК): из формулы Q(), которая свободна для y, выводится Q() Q(y), подставленной Q() переменой y. Правило универсального обобщения (УО): если Q() не имеет свободных вхождений, то из нее выводится Q() Q()). Правило экзистенциальной конкретизации (ЭК) позволяет перейти от формулы P() P(α), α где неизвестный, но вполне определенный элемент, такой, что если P(α) истина, то P(α) тоже истина. Правило экзистенциального обобщения (ЭО) позволяет перейти от формулы P(α) P(). Рассмотрим пример логического вывода в логике предикатов: 1) (P() y(q(y) R(, y))); 2) (P() y(s(y) R(, y))). На естественном языке заключение можно сформулировать: (Q() (S()) 1) «некоторые студенты выполнили все задания»; 2) «ни один студент не выполнил графики»; 3) заключение: «следовательно, ни одно задание не являлось графиком». 10