close

Вход

Забыли?

вход по аккаунту

?

PDF

код для вставкиСкачать
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
Санкт-Петербургский государственный университет
аэрокосмического приборостроения
Д. В. Бутенина, В. М. Лагодинский
МАТЕМАТИЧЕСКАЯ ЛОГИКА
Учебное пособие
Санкт-Петербург
2011
УДК 510.6
ББК 22.12
Б93
Рецензенты:
доктор физико-математических наук, профессор Российского
государственного педагогического университета В. Д. Будаев;
кандидат физико-математических наук Ю. А. Гусман
Утверждено
редакционно-издательским советом университета
в качестве учебного пособия
Бутенина, Д. В., Лагодинский, В. М.
Б93 Математическая логика: учебное пособие / Д. В. Бутенина,
В. М. Лагодинский. – СПб.: ГУАП, 2011. – 52 с.: ил.
ISBN 978-5-8088-0667-2
В учебном пособии дано краткое изложение основ теории множеств, алгебры высказываний, исчисления высказываний, логики
предикатов и исчисления предикатов. Приведены варианты контрольных работ.
Учебное пособие предназначено для самостоятельного изучения
математической логики студентами заочной формы обучения направления “Информатика и вычислительная техника”. Оно могут быть
полезны также студентам заочной и очной формы обучения других
специальностей при изучении дисциплин со схожей тематикой.
Учебное издание
Бутенина Дина Викторовна
Лагодинский Владимир Меерович
УДК 510.6
ББК 22.12
МАТЕМАТИЧЕСКАЯ ЛОГИКА
Учебное пособие
Редактор В. П. Зуева
Верстальщик С. Б. Мацапура
Сдано в набор 25.10.11. Подписано к печати 15.11.11.
Формат 60×84 1/16. Бумага офсетная. Усл. печ. л. 3,0.
Уч.-изд. л. 3,25. Тираж 100 экз. Заказ № 442.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
ISBN 978-5-8088-0667-2
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения (ГУАП), 2011
© Д. В. Бутенина, В. М. Лагодинский., 2011
Введение
Предмет математической логики и
ее использование в инженерной практике
выпускников СПбГУАП
Логику принято определять как науку о законах мышления. Но
механика – наука о законах движения – утверждает, например, что
любое тело с массой m под действием силы F движется с ускорением
a=F/m. Вряд ли кто-нибудь станет утверждать, что любой человек
всегда мыслит логично. Более того, если бы это было так, человек
не смог бы открыть ничего принципиально нового, не следующего
автоматически из старого. Кроме того, такое определение относит
логику к наукам о человеке, делает ее разделом психологии человека. Но почему и для чего человек размышляет? Размышляя, человек или ищет причину, если известно следствие (этим занимаются,
например, следователи и исследователи), или ищет следствие по
известной причине для того, чтобы затем действовать целесообразно, т. е. либо теоретически выводит причину из следствия, либо
наоборот.
Но и животные обычно действуют целесообразно. Используют
ли они логику? Известно, что шимпанзе, увидев подвешенный банан и груду ящиков, сначала отходит в сторону, принимает позу
роденовского мыслителя, а через некоторое время ставит ящики
один на другой под бананом и добирается до него. Это нельзя объяснить случайностью или рефлексами и даже опытом. Но другие
животные руководствуются безусловными и условными рефлексами и опытом, и их поведение тоже целесообразно. И даже растения
живут ‘‘разумно’’: осенью сбрасывают листья, яркими цветами
привлекают насекомых, а некоторые насекомых едят.
Несколько другое определение представляет логику ‘‘как науку
о правильных способах рассуждения, т. е. таких способах рассуждения, при которых из верных исходных положений получаются
верные результаты’’ [1]. С этим можно согласиться, но возникает
вопрос: почему эти способы приводят к верным результатам? И что
такое эти верные результаты?
Очевидно, верные результаты – это такие результаты, которые
соответствуют реальному миру, который нас окружает. Иначе говоря, эти способы рассуждения правильны потому, что точно соответствуют реальному миру, его самым основным законам. Можно сказать, следовательно, что законы логики отображают самые основные
3
законы реального мира – законы причинно-следственных связей,
а не устройство мозга человека. Рассуждают люди и (может быть)
иногда человекообразные обезьяны, вряд ли рассуждают другие
животные, и уж точно не рассуждают растения. Но в ‘‘устройстве’’
их всех отражены законы причинно-следственных связей явлений
реального мира, важных для их жизнедеятельности. Для растений
и низкоорганизованных животных цепочек причинно связанных
жизненно важных явлений немного, и они могут быть отражены в
их генах. Для более высокоорганизованных животных (таких, как
хищные млекопитающие или приматы) их гораздо больше, и они
отражены в тех связях, которые существуют в их мозгу и могут меняться в течение жизни под воздействием личного опыта.
Человек в своей жизни сталкивается с таким разнообразием
жизненно важных для него явлений, что и в мозгу его не могут
храниться все их цепочки. Человек формирует эти цепочки по
мере надобности в процессе размышлений по законам причинноследственных связей реального мира.
Мысли выражаются предложениями и целыми последовательностями предложений на каком-либо языке. Предложения состоят
из слов, которые соединяются в предложения по законам данного языка. Эти законы изучает лингвистика. Известный лингвист
Л. В. Щерба предлагал студентам проанализировать ‘‘фразу’’:
‘‘Глокая куздра штеко будланула бокра и курдячит бокренка’’. Есть
ли смысл в этой фразе? Оказывается, есть! Он заключается в тех
частях слов, которые играют, казалось бы, служебную роль: окончаниях и суффиксах, а также в союзе ‘‘и’’. Корни слов могут быть
разными, но смысл, связь этих слов в едином утверждении одна и
та же. И эта связь (выражаемая в каждом языке своими средствами) отображает отношения между объектами, реальными или воображаемыми. Эти отношения могут быть самыми разнообразными,
и человек познает эти отношения, вырабатывая понятия, создавая
слова для обозначения этих понятий. Рассуждения человека, если
они правильны, связывают эти слова, т. е. понятия, по определенным законам, которые отображают законы реального мира. Следовательно, изучая законы правильного мышления, мы изучаем
законы реального мира, именно законы причинно-следственных
связей в реальном мире.
Итак, логика – это наука о причинно-следственных связях. Обязательно ли это связи реального мира? В принципе, необязательно.
Логика – наука теоретическая. Мы можем конструировать (выдумывать) любые причинно-следственные связи, и некоторые логики
4
этим занимаются. Чаще, однако, ‘‘искаженные’’ миры придумывают писатели-фантасты (например, ‘‘Обмен разумов’’ и ‘‘Оптимальный вариант’’ Роберта Шекли или ‘‘Конец Вечности’’ Айзека
Азимова). При чтении этих произведений ощущаются трудности,
испытываемые авторами при стараниях свести концы с концами,
и, в то же время, читая эти произведения мы обращаем больше,
чем обычно, внимания на логику нашего мира. Очевидно, именно
логика запрещает путешествия в прошлое. Вспомним, как в сериале “Остаться в живых” Хьюго и Майлс, попав в 1977 г. из 2004 г.,
мучительно размышляют, что будет, если сейчас Хьюго застрелит
Майлса.
Конечно, основные законы реального мира знать необходимо
любому человеку. Но они кажутся такими естественными: из двух
противоположных утверждений одно обязательно истинно, два
противоположных утверждения не могут быть истинными одновременно – казалось бы, каждый человек в своих рассуждениях руководствуется этими законами. Но иногда рассуждения, кажущиеся
вполне логичными, приводят к парадоксам. С древности известны
апории Зенона об Ахиллесе, который якобы никогда не догонит черепаху, о стреле и другие. Парадокс ‘‘Лжец’’ состоит в следующем:
некто говорит, что он всегда лжет. Солгал он или сказал правду?
Существование парадоксов показывает, что рассуждать правильно
не так просто. Особенно трудно рассуждать, если требуется учесть
очень много различных сведений и/или связи между ними сложны
и многочисленны.
Необходимость изучения способов правильного мышления была
осознана еще в древнем мире. По-видимому, это произошло благодаря появлению судопроизводства. Вина подсудимого должна быть
доказана. Но что это значит? Виновность подсудимого должна следовать по законам логики из показаний свидетелей и из вещественных улик.
Теоретическая наука также зародилась в древности. Шарообразность Земли была доказана наблюдениями лунных затмений:
тень Земли на Луне имеет круглую форму; но только шарообразные
предметы всегда отбрасывают круглую тень, следовательно, Земля – шар. Эвклид построил геометрию, сформулировав небольшое
количество аксиом и логически выведя из них много теорем. Такой способ построения теории давно признан идеальным. Философ
Спиноза в аксиоматическом виде построил свою ‘‘Этику’’, а физик
и математик Ньютон – механику, которую теперь называют классической, или ньютоновской.
5
Еще до новой эры было осознано, что правила рассуждений,
которые приводят к верным результатам, не зависят от предмета
этих рассуждений. Это позволило Аристотелю построить логику
как формальную теорию. Последующее развитие математики, вопервых, потребовало выяснения основ этой науки, во-вторых, показало возможность построения логики как математической науки. Впервые мысль о возможности математизации логики высказал немецкий математик Лейбниц в восемнадцатом веке. Но реализовать эту идею удалось только в девятнадцатом веке английскому
математику Д. Булю. С тех пор математическая логика развилась
в самостоятельную математическую науку. Более того, математическая логика стала играть роль метаматематики, т. е. науки, занимающейся законами построения всей математики. Символика
математической логики стала широко использоваться во всех математических науках. Крупный вклад в развитие математической
логики внесли выдающийся немецкий математик Д. Гильберт и такие математики, как Пост, Черч, Тьюринг, Гедель. После появления современных вычислительных машин математическая логика
стала необходимой для разработки их программного обеспечения,
языков программирования. Большое значение приобрел один из
разделов математической логики – теория алгоритмов. Это определяет необходимость знания основ математической логики для современного инженера, специальность которого связана с программированием и разработкой устройств автоматики.
1. Элементы теории множеств
Теория множеств [2] является основой всех разделов современной математики, а ее основы заложил немецкий математик Георг
Кантор. Главная заслуга Г. Кантора состоит в открытии принципов
обращения с бесконечными множествами. В математической логике такие множества встречаются редко, но язык теории множеств в
ней широко используется.
Понятие множества является одним из основных понятий в математике и поэтому обычно не определяется. Его можно лишь пояснить
как совокупность объектов произвольной природы, которые называются элементами этого множества. Элементами множества A могут
быть и другие множества, с одним ограничением: множество A не может включать себя в качестве элемента. Тот факт, что объект a является элементом множества A, обозначается следующим образом: aA.
6
Множество может быть задано перечислением всех его элементов, если этих элементов не слишком много, в фигурных скобках.
Например, множество, содержащее лишь числа 1 и 2, может быть
задано формулой: M={1; 2}.
Очевидно, этот способ непригоден, если множество содержит
много элементов, тем более, если их число бесконечно. В этом случае множество задают, определяя признак, по которому элементы
включаются в данное множество. Например, множество точек отрезка [a, b] можно обозначить как
M = {x Î R:a £ x £ b}.
Здесь R – множество вещественных чисел. Другие числовые множества: N – множество натуральных чисел (в настоящее время к
этому множеству обычно относят все целые неотрицательные числа:
ìm
ü
0; 1; 2...); Z – множество всех целых чисел; Q = ïí : m,n Î Z,n ¹ 0ïý –
îïï n
þïï
множество всех рациональных чисел. Множества A и B называются
равными, если они состоят из одних и тех же элементов. Множество
А называется подмножеством множества B (это обозначается формулой A⊆B), если любой элемент множества A является также элементом множества B. Отсюда следует, что для доказательства равенства двух множеств A=B достаточно доказать, что одновременно
A⊆B и B⊆A. Очевидно, любое множество является подмножеством
самого себя: A⊆A. Бывает заранее неизвестно, содержит ли некоторое множество хотя бы один элемент. В связи с этим вводится понятие пустого множества, не содержащего элементов. Это множество
обозначается символом Ø. Пустое множество по определению считается подмножеством любого множества. Любое подмножество
множества A, кроме его самого и пустого множества, называется
собственным подмножеством множества A.
Символом A∪B обозначается объединение множеств A и B, т. е.
множество элементов, каждый из которых является элементом
хотя бы одного из множеств A или B. Символом A∩B обозначается
пересечение множеств A и B, т. е. множество элементов, каждый
из которых является элементом и множества A, и множества B.
Символом A обозначается множество элементов, не принадлежащих множеству A. Это основные операции теории множеств. Кроме
того, используются операции: A \ B = A Ç B – разность множеств A
и B, т. е. множество элементов множества A, не принадлежащих
множеству B, и A∆B=(A\B)∪(B\A) – симметризованная разность
7
множеств A и B, т. е. множество элементов, принадлежащих или
множеству A, либо множеству B, но не им обоим.
Произведением множеств A1×A2×...×An называется множество
упорядоченных наборов (a1; a2; ...; an), где ai Î Ai , i = 1, 2, n. Среди множеств A1 могут быть и одинаковые, тогда используют показатель степени, например A×A=A2. Чаще всего рассматривается
множество пар:
P = {(a1; a2 ) : a1 Î A, a2 Î A}.
Любое подмножество R Í P называется отношением на множестве A. Если пара (a1; a2 ) Î R , то говорят, что a1 и a2 находятся в отношении R. Часто этот факт обозначают формулой: a1Ra2, например, отношение равенства: a1=a2. Отношения могут обладать (или
не обладать) следующими свойствами.
1) Рефлексивность: aRa при всех a (если отношение R рефлексивно, то любой элемент находится в этом отношении к самому
себе).
2) Симметричность: если aRb, то bRa.
3) Антисимметричность: если aRb и bRa, то a=b (a и b – один и
тот же элемент).
4) Транзитивность: если aRb и bRc, то aRc.
Если отношение R рефлексивно, симметрично и транзитивно,
то оно называется отношением эквивалентности. Такое отношение
разделяет множество, на котором оно определено, на непересекающиеся классы эквивалентности. Например, если для точек плоскости ввести отношение равноудаленности от некоторой одной точки
этой плоскости, то плоскость представляется объединением окружностей с центром в этой точке.
Если отношение рефлексивно, антисимметрично и транзитивно, оно называется отношением (частичного) порядка. Такие отношения часто обозначается так: a  b (читается a предшествует b).
Это можно обозначить и так: b  a. Примеры отношений порядка:
a £ b, A Í B. Но если для любых двух вещественных чисел справедливо либо a≤b, либо b≤a, то существуют такие множества A и B, что
несправедливо ни A⊆B, ни B⊆A. Множество множеств является частично упорядоченным, в нем есть несравнимые элементы. Множество вещественных чисел R является упорядоченным – в нем нет
несравнимых элементов. Множество натуральных чисел является
вполне упорядоченным – в нем есть наименьший элемент.
Если существует правило, которое каждому элементу множества A сопоставляется один из элементов множества B, то говорят,
8
что существует отображение F множества A во множество B и это
обозначается выражением F: A→B. Элемент bB, сопоставляемый
этим отображением элементу aA называется образом элемента a, а
элемент a называется прообразом элемента b. Отображения бывают
трех видов: 1) сюръективные отображения (сюръекции); 2) инъективные отображения (инъекции); 3) биективные отображения.
Отображение F называется сюръекцией, если каждый элемент
множества B имеет хотя бы один прообраз во множестве A. Отображение F называется инъекцией, если каждый элемент множества
B имеет не более одного прообраза во множестве A. Отображение F
называется биекцией, если оно одновременно сюръективно и инъективно. Если отображение F: A→B является биекцией, сопоставляющей элементу aA элемент bB, можно определить обратную
функцию F–1: B→A, которая сопоставляет элементу bB элемент
aA. Если определены отображения F: A→B, сопоставляющее элементу aA элемент bB и G: B→C, сопоставляющее элементу bB
элемент cC, то определено отображение G◦F: A→C, сопоставляющее элементу aA элемент cC, называемое суперпозицией отображений F и G (именно в таком порядке). Затем можно определить
суперпозицию трех функций F, G и H: H◦G◦F и так далее.
Множества A и B называются эквивалентными, если существует
хотя бы одна биекция F: A→B. Еще про такие множества говорят,
что они имеют одинаковую мощность. Понятие мощности – это
обобщение числа элементов на бесконечные множества. Если множество A – конечное, т. е. содержит лишь конечное число элементов, то эквивалентным ему может быть лишь конечное множество.
Если множество A содержит подмножество, эквивалентное множеству B, то его мощность не меньше мощности множества B. Если
множество A содержит подмножество, эквивалентное множеству
B, и одновременно множество B содержит подмножество, эквивалентное множеству A, то множества A и B эквивалентны друг другу
(теорема Кантора-Бернштейна [2]) и, следовательно, имеют одинаковую мощность.
Любое множество, эквивалентное множеству N, называется
счетным. Легко доказать счетность множества целых чисел Z и
множества четных чисел. В любом бесконечном множестве содержится счетное подмножество, т. е. мощность счетного множества
является минимальной для бесконечных множеств. Она обозначается обычно символом ℵ0 (читается: алеф ноль).
Теорема 1. Объединение счетного числа конечных множеств – не
более чем счетно.
9
Теорема 2. Объединение счетного числа счетных множеств не более чем счетно. Доказательства этих теорем в [2].
Из теоремы 2 легко следует счетность множества рациональных
чисел Q.
Но существуют множества, имеющие мощность большую, чем
мощность счетного множества.
Теорема 3. Мощность множества A вещественных чисел на отрезке [0;1] имеет мощность, большую ℵ0.
Доказательство. Множество A содержит подмножество
-1
{n : n Î N}, имеющее мощность ℵ0, поэтому мощность множества A не меньше чем ℵ0. Предположим, что она равна ℵ0. Тогда
все элементы множества A можно перенумеровать, и расположить
их в виде бесконечной последовательности:
1) 0,a11a12a13...; 2) 0,a21a22a23...; 3) 0,a31a32a33...;...
n) 0,an1an2an3...;...,
где aij – цифры 0, 1, 2,..., 9. Теперь покажем, что в противоречии
с предположением эта последовательность содержит не все элементы множества A. В частности, она не содержит число, которое имеет вид 0,b1b2b3, где bi – цифры 0, 1, 2,..., 9, если b1 – любая цифра, кроме a11, b2 – любая цифра, кроме a22, и так далее.
Тогда от первого числа последовательности оно отличается первой
цифрой после запятой, от второго – второй цифрой после запятой
и так далее. Итак, мощность множества A больше ℵ0. Теорема
доказана.
Мощность этого множества носит название мощности континуума и обозначается обычно символом c. Можно показать (см. [2]),
что мощность точек любого промежутка числовой прямой и всей
прямой R равна c. Более того, можно показать [2], что мощность
множества Rn тоже равна c.
Существуют и множества с мощностями, большими c. Можно
показать [2], что мощность множества подмножеств множества A
строго больше мощности множества A. Мощность множества отображений множества A во множество B также строго больше мощностей обоих этих множеств. Таким образом, существуют множества как угодно большой мощности.
Остается нерешенной проблема: существуют ли множества мощности, промежуточной между ℵ0 и c? Известно лишь, что ни положительный, ни отрицательный ответ на этот вопрос не противоречит всей современной теории множеств.
10
2. Алгебра (логика) высказываний
Алгебра или логика высказываний – это простейшая теория математической логики. Основное понятие этой теории – высказывание. Высказывание – это повествовательное предложение, о котором, хотя бы в принципе, можно сказать, истинно оно или ложно
(конечно, эта фраза не является математически корректным определением: основные понятия любой теории не определяются, иначе
они определялись бы через другие понятия, т. е. не были бы основными). Например: ‘‘Волга впадает в Каспийское море’’, ‘‘2=3’’ –
высказывания, причем первое – истинное, а второе – ложное, Но
фраза: ‘‘Сумма корней приведенного квадратного уравнения равна
свободному члену’’ высказыванием не является, поскольку бывают
уравнения этого типа, для которых это справедливо, но для других
это неправильно. Математическая логика не интересуется конкретным содержанием высказывания, высказывания рассматриваются
как переменные x, y, z, …, которые могут принимать только два
значения: истина (и) и ложь (л) или 1 и 0 соответственно.
Логические связки и логические функции
Из одного или нескольких высказываний можно получить другое высказывание, используя логические связки:  (конъюнкция,
логическое умножение, и),  (дизъюнкция, логическое сложение,
неисключающее или), ¬ (отрицание, не), → (импликация), ↓(стрелка Пирса), | (штрих Шеффера), ⊕ (символ Жегалкина, исключающее или, сложение по модулю 2), ~ (эквиваленция), \ (логическое
вычитание) и это высказывание называется логической функцией
исходных высказываний. Таким образом, логическая функция n
исходных высказываний является отображением множества Fn
во множество F, где F – множество, состоящее из двух элементов:
F={0; 1}. Нетрудно установить, что всего таких функций может
n
быть 22 (доказательство предоставляется читателю в качестве
упражнения).
Рассмотрим все логические функции одной логической переменной f(x). Их удобно представить в виде следующей таблицы (таблицы истинности):
x
f0
f1
f2
f3
0
0
0
1
1
1
0
1
0
1
11
Функция f0 называется тождественно ложной или тождественно нулевой: f0(x)≡0, функция f1 осуществляет тождественное
отображение множества F: f1(x)=x при всех значениях x, функция
f2 переставляет элементы множества F, она является отрицанием:
f2 (x) = x при всех значениях x, функция f3 называется тождественно истинной или тождественно единичной: f3(x)≡1.
Теперь рассмотрим все возможные функции двух логических пе2
ременных fi(x,y), i=0,1,...,15 (число таких функций равно 22 = 16 ).
Будем придерживаться определенного порядка как для наборов
значений переменных, так и в нумерации логических функций.
Этот порядок соответствует двоичной системе счисления. Получаем следующую таблицу:
Таблица 1
x
y
f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Каждая из этих функций имеет свой логический смысл. Функция f0(x,y) – тождественно ложная функция. Функция f1(x,y) истинна в том и только том случае, когда истинны и x, и y – это конъюнкция: f1(x,y)=xy. Функция f2(x,y) истинна в том и только том
случае, когда истинно x, а y ложно – это логическая разность этих
высказываний: f2(x,y)=x\y. Функция f3(x,y) истинна в том и только том случае, когда истинно x, независимо от y: f3(x,y)=x. Функция f4(x,y) истинна в том и только том случае, когда истинно y, а x
ложно – это логическая разность этих высказываний: f4(x,y)=y\x.
Функция f5(x,y) истинна в том и только том случае, когда истинно y, независимо от x: f5(x,y)=y. Функция f6(x,y) истинна в том и
только том случае, когда либо x истинно, а y ложно, либо, наоборот, y истинно, а x ложно: это сумма по модулю 2 x и y: f6(x,y)=x⊕y.
Функция f7(x,y) ложна в том и только том случае, когда ложны и x,
и y, это дизъюнкция: f7(x,y)=xy. Функция f8(x,y) истинна в том и
только том случае, когда x и y принимают одинаковые значения,
это – эквиваленция: f9(x,y)=x~y. Функция f10(x,y) истинна в том
и только том случае, когда ложно y, это отрицание y: f10 (x, y) = y.
Функция f11(x,y) ложна в том и только том случае, когда x ложно, а y истинно, это импликация: f11(x,y)=y→x. Функция f12(x,y)
12
истинна в том и только том случае, когда ложно x, это отрицание
x: f12 (x, y) = x. Функция f13(x,y) ложна в том и только том случае,
когда x истинно, а y ложно, это – импликация: f13(x,y)=x→y. Функция f14(x,y) ложна в том и только том случае, когда истинны и x,
и y, это – штрих Шеффера: f14(x,y)=x|y. Функция f15(x,y) истинна
при любых x и y, это – тождественно истинная функция.
Два первых столбца табл. 1 вместе со столбцом, соответствующим функции fn(x,y) (n=0, 1, …, 15), составляют таблицу истинности функции fn(x,y). Например, таблица истинности импликации f13(x,y)=x→y имеет вид:
x
y x→y
0
0
1
0
1
1
1
0
0
1
1
1
Это определение импликации следует обсудить особо. С точки
зрения логики импликация означает: ``Если x, то y’’. Очевидно,
это истинно, если из истинности x следует истинность y, а из ложности x ложность y, и ложно, если из истинности x следует ложность y. Но совсем не очевидна третья строчка таблицы, которая
гласит, что импликация истинна, если из ложности x следует истинность y. Можно привести такой шуточный пример: если крокодилы летают, то дважды два – пять. Тут действует своеобразная
презумпция истинности: высказывание считается истинным, пока
не доказана его ложность. А чтобы доказать ложность нашего высказывания, необходимо доказать, во-первых, что крокодилы летают, во-вторых, что дважды два не равно пяти. Но первое доказать
невозможно.
Парадоксальный вывод логики: из лжи следует все, что угодно. Из неправильных посылок можно получить правильные заключения. В термодинамике известна формула Карно для предельного коэффициента полезного действия тепловой машины. Эта
формула правильна, хотя Карно получил ее из неверных предположений. Неправильная теория может приводить к результатам,
согласующимся с экспериментом. Поэтому эксперимент не может подтвердить теорию, он может лишь ее опровергнуть. Если
какой-либо вывод теории не согласуется с экспериментом – теория
неверна.
13
По номеру N(f)=n функции fn(x,y) легко определить ее таблицу истинности и наоборот. Для этого надо представить номер n в
двоичной системе счисления, например, 7=4+2+1 в этой системе
изображается в виде 0111 (добавляется 0 слева, чтобы число цифр
было равно четырем). Самая правая цифра соответствует значению
функции при x=1, y=1, вторая справа – при x=1, y=0 и так далее.
Таким образом, простейшая теория математической логики – логика высказываний – основана на определении логических операций
(отрицания, конъюнкции, дизъюнкции, импликации и т. д.) с помощью таблиц истинности.
Можно пойти дальше и определить новые логические функции
трех переменных с помощью таблиц истинности, каждая из которых содержит 9 строк и 4 столбца, например:
x
y
z
f
0
0
0
1
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
Порядок следования наборов значений переменных (строк)
здесь по-прежнему определяется в соответствии с двоичной системой счисления: 000 соответствует нулю, 001 – единице, 010 – двум
и так далее. Функции нумеруются аналогично: f0(x,y,z) – тождественный нуль, в четвертом столбце ее таблицы истинности нули
во всех строках. Чтобы получить таблицу истинности для функции
fn(x,y,z), надо число n представить в виде:
8
n = å α k 2k-1,
k=1
где αk – либо нуль, либо единица. αk и есть то число, которое
должно стоять на пересечении четвертого столбца и k-й строки
в таблице истинности функции fn(x,y,z). Тождественная единица, или тождественно истинная функция имеет индекс 255:
14
f255(x,y,z)≡1. Но любую такую функцию можно определить с помощью суперпозиции функций одной или двух переменных.
Например, пусть
Суперf (x, y) = x Ú y, g(x) = x, h(y, z) = y ® z.
позицию этих функций получим, подставив в функцию f(x,y)
вместо x g(x) = x, вместо y h(y,z)=y→z. В результате получим:
ϕ(x, y, z) = f (g(x), h(y, z)) = x Ú (y ® z) – формулу. Формула может
представлять собой только одну букву (независимую переменную) – такие формулы называются пропозициональными. Если A –
формула, то A – тоже формула. Если A и B – формулы, то AB,
AB, A→B, A⊕B, A↓B, A|B, A\B, A~B –тоже формулы. Других формул в логике высказываний нет. Таким образом, любое выражение, содержащее пропозициональные формулы, разделенные логическими связками, представляет собой формулу, которая представляет собой некоторое сложное высказывание. Для определения
логического смысла этого высказывания необходимо учитывать
правила приоритета логических операций. Именно, вначале выполняются операции, находящиеся под знаком отрицания, конъюнкции, штрихи Шеффера и стрелки Пирса, затем дизъюнкции,
потом импликации, после них сложения по модулю 2 и эквиваленции. Для обеспечения другого порядка вычисления операций
используются скобки. Составим таблицу истинности функции
x Ú (y ® z) :
y ® z x Ú (y ® z)
x
y
z
x
0
0
0
1
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
1
1
1
1
1
0
0
0
1
1
1
0
1
0
1
1
1
1
0
0
0
0
1
1
1
0
1
1
Любой формуле можно сопоставить таблицу истинности, но одна
и та же таблица истинности сопоставляется разным формулам.
Формулы, имеющие одинаковые таблицы истинности, называются
равносильными. На множестве формул это определяет отношение
эквивалентности.
15
Основные равносильности (легко проверяемые по таблицам истинности).
1)  A Ù A º A, A Ú A º A – законы идемпотентности конъюнкции и дизъюнкции.
2)  A Ù 1 º A, A Ú 1 º 1 (1 – истина).
3)  A Ù 0 º 0, A Ú 0 º A (0 – ложь).
4)  A Ù A º 0 (закон противоречия).
5)  A Ú A º 1 (закон исключенного третьего).
6) A º A (закон снятия двойного отрицания).
7)  A Ù (B Ú A) º A, A Ú (B Ù A) º A (законы поглощения).
8)  A º ( A Ù B) Ú ( A Ù B), A º ( A Ú B) Ù ( A Ú B) (формулы расщепления).
Равносильности, выражающие одни логические операции через
другие.
1)  A ~ B º ( A ® B) Ù (B ® A) º ( A Ù B) Ú ( A Ù B) º ( A Ú B) Ù (B Ú A).
2)  A ® B º A Ú B º A Ù B.
3)  A Ú B º A ® B º A Ù B.
4)  A Ù B º A ® B º A Ú B.
5) 
A Ù B º A Ú B – первый закон де Моргана.
6)  A Ú B º A Ù B – второй закон де Моргана.
7)  A Ù B º A Ú B, A Ú B º A Ù B.
Из равносильностей этой группы следует, что всякую формулу
алгебры логики можно заменить равносильной ей формулой, содержащей только две логических операции: конъюнкцию и отрицание или дизъюнкцию и отрицание.
Равносильности, выражающие основные законы алгебры логики.
1)  A Ù B º B Ù A, A Ú B º B Ú A – коммутативность конъюнкции и дизъюнкцци.
2)  A Ù (B Ù C) º ( A Ù B) Ù C, A Ú (B Ú C) º ( A Ú B) Ú C – ассоциативность конъюнкции и дизъюнкции.
3)  A Ù (B Ú C) º ( A Ù B) Ú ( A Ù C) – дистрибутивность конъюнкции относительно дизъюнкции.
4)  A Ú (B Ù C) º ( A Ú B) Ù ( A Ú B) – дистрибутивность дизъюнкции относительно конъюнкции.
Используя равносильности, можно упрощать выражения.
16
Пример 1. Упростить выражение для f (x, y, z) = (y | z) \ (x Ú y) Å (y Ú z).
| z) \ (x Ú y) Å (y Ú z).
Решение.
f (x, y, z) = (y | z) \ (x Ú y) Å (y Ú z) = ((y | z) ® (x Ú y))Å (y Ú z) =
(
)
= y Ù z ® (x Ú y) Å (y Ú z) = ( y Ù z Ú (x Ú y))Å (y Ú z) =
æ
ö÷
çç
÷
= ( y Ù z Ú y)Ú x Å (y Ú z) = çç( y Ú y)Ù (z Ú y) Ú x÷÷÷ Å (y Ú z) =
çç 
÷÷


÷ø
çè 1
(
)
= (x Ú y Ú z) Å (y Ú z) = x Ú y Ú z Å y Ú z = x Ù y Ù z Å y Ù z =
= y Ù z Ù (x Å 1) = y Ù z Ù x = y Ú z Ù x = (y | z) Ù x.
Формула называется тавтологией (тождественно истинной),
если она принимает значение 1 при всех значениях входящих в нее
переменных. Формула называется противоречивой или тождественно ложной, если она принимает значение 0 при всех значениях входящих в нее переменных. Формула называется выполнимой,
если хотя бы при одном наборе значений переменных она принимает значение 1.
Основные тавтологии (логические законы):
1)  A Ú A – закон исключенного третьего (tertium nondatum).
2)  A ® A.
3)  A ® (B ® A).
4)  ( A ® B) ® ((B ® C) ® ( A ® C)) – цепное рассуждение.
Итак, в математической логике все множество высказываний
отображается на множество, состоящее из двух элементов: 0 и 1, и
на этом множестве определяются три операции: одна унарная (отрицание) и две бинарных (конъюнкция и дизъюнкция), которые не
выводят элементы из этого множества.
Булевы алгебры
Любое множество M, содержащее (может быть, наряду с другими) два выделенных элемента 0 и 1, на котором определены одна
унарная операция (обозначим ее через ¬) и две бинарные операции
(обозначим их через + и ×), такие, что справедливы следующие равенства:
a+b=b+a
– коммутативные законы,
1.
a ´b = b´a
17
2.
a + (b + c) = (a + b) + c
– ассоциативные законы,
a ´(b ´ c) = (a ´ b) ´ c
3.
(a + b) ´ c = (a ´ c) + (b ´ c)
– дистрибутивные законы,
(a ´ b) + c = (a + c) ´(b + c)
4.
a+a=a
– законы идемпотентности,
a´a = a
5.
a + b = a´b
a´b = a + b
– законы де Моргана,
6. a = a – закон двойного отрицания,
a + (a ´ b) = a
– законы поглощения,
7.
a ´(a + b) = a
8. a + 0 = a, a + 1 = 1, a ´0 = 0, a ´1 = a – особые свойства элементов 0 и 1, называется алгеброй Буля или булевой алгеброй.
Поскольку все эти законы справедливы для логических операций ¬, , , алгебра логики является интерпретацией булевой алгебры. Но у последней есть и другие интерпретации. Рассмотрим,
например, множество M подмножеств какого-либо множества E.
В множестве M содержится элемент Ø (пустое множество), играющий роль нуля, множество E, играющее роль единицы, и определены операции C (дополнение), ∩ (пересечение множеств) и ∪ (объединение множеств), для которых справедливы перечисленные
законы. Следовательно, множество M с операциями C, ∪, ∩ представляет собой булеву алгебру.
Двойственность
На множестве логических функций можно ввести отношение
двойственности: функция f(x, y, z, …) называется двойственной
функции g(x, y, z,…) (это обозначается: f(x, y, z, …)≡g*(x, y, z, …)),
если справедлива равносильность: f (x, y, z,) º g(x, y, z,). Отношение двойственности симметрично: если f(x, y, z,…)≡g*(x, y, z,
…), то и g(x, y, z, …)≡f*(x, y, z, …), но не транзитивно. В следующей
таблице друг под другом расположены двойственные друг другу
функции.
18
0 x
x x  y x ↓ y x →y x ~ y
1 x
x xy x|y y\x x⊕y
Из таблицы видно, что существуют функции, двойственные
сами себе. Такие функции называют самодвойственными.
Пример 2. Найти выражение для f*(x,y,z), если f (x, y, z) = ((x ~ y) ~ (y ® z)
z) = ((x ~ y) ~ (y ® z)) Ù (y Ú z).
Решение. f * (x, y, z) = ((x Å y) Å (z \ y)) Ú (y Ù z).
Нормальные формы
ìïx, σ = 0,
Введем обозначение: xσ = ïí
Формула x1σ1 Ù x2σ2 Ù  Ù xnσn ,
ïïx, σ = 1.
î
где σ={σ1, σ2,..., σn} – какой-нибудь двоичный набор, а среди переменных xi могут быть совпадающие, называется элементарной
конъюнкцией, или конъюнктом. Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой
(ДНФ). Если ДНФ удовлетворяет следующим условиям совершенства: все логические слагаемые в ДНФ различны, каждое слагаемое содержит все переменные, ни одно логическое слагаемое не
содержит xi и x одновременно и ни одно логическое слагаемое не
содержит одно и то же переменное дважды, такая ДНФ называется совершенной дизъюнктивной нормальной формой (СДНФ). Для
всякой функции алгебры логики f(x1, x2,..., xn), не равной тождественно нулю, справедливо ее представление в виде СДНФ:
ÑÄÍÔ f =
Ú
σ
σ
x1 1 Ù x2 2 Ù  Ù xnσn
f (σ1, σ2 ,¼,σn )=1
(дизъюнкция по всем наборам переменных, при которых функция
принимает значение 1). Тождественно ложная функция не имеет
СДНФ.
Формула x1σ1 Ú x2σ2 Ú  Ú xnσn , называется элементарной дизъюнкцией, или дизъюнктом. Всякая конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ).
Если КНФ удовлетворяет следующим условиям совершенства: все
логические сомножители в КНФ различны, каждый сомножитель
содержит все переменные, ни один логический сомножитель не содержит xi и x одновременно и ни один логический сомножитель не
содержит одно и то же переменное дважды, такая КНФ называется совершенной конъюнктивной нормальной формой (СКНФ). Для
всякой функции алгебры логики f(x1, x2,..., xn), не равной тождественно единице, справедливо ее представление в виде СКНФ:
19
ÑÊÍÔ f =
σ
Ù
f (σ1, σ ,σn )=0
σ
x1 1 Ú x2 2 Ú  Ú xnσn
(конъюнкция по всем наборам переменных, при которых функция
принимает значение 0). Тождественно истинная функция не имеет
СКНФ.
Значение СДНФ и СКНФ состоит в том, что равносильные формулы имеют одинаковые СДНФ и СКНФ (с точностью до порядка
следования конъюнктов и дизъюнктов). Для получения СДНФ и
СКНФ строится таблица истинности функции, например:
x
y
z
f
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
0
Из таблицы видно, что значение 1 эта функция принимает, если
x=y=0, или x=1, y=z=0 или x=y=1, z=0. Для всех остальных наборов значений переменных эта функция принимает значение 0. Отсюда получаем:
СДНФ f = (x Ù y Ù z) Ú (x Ù y Ù z) Ú (x Ù y Ù z) Ú (x Ù y Ù z),
СКНФ f = (x Ú y Ú z) Ù (x Ú y Ú z) Ù (x Ú y Ú z) Ù (x Ú y Ú z).
Но среди ДНФ могут быть и такие, которые содержат меньше
переменных, чем СДНФ. Такие ДНФ целесообразно использовать
при реализации логических функций в виде переключательных
устройств или в машинных программах. Будем называть импликантой формулы A такую элементарную конъюнкцию B, которая,
во-первых, содержит каждую из переменных не более чем один раз
(т. е. является правильной), во-вторых, удовлетворяет уравнению
A Ù B = B. Импликанта называется простой, если после удаления
из нее любой переменной она перестает быть импликантой. Дизъюнкция простых импликант называется сокращенной ДНФ. Со20
кращенная ДНФ может содержать лишние импликанты, удаление
которых не меняет таблицы истинности. Если их удалить, получается ДНФ, которая называется тупиковой. Тупиковая ДНФ, содержащая наименьшее число вхождений переменных, называется
минимальной ДНФ (МДНФ).
Для получения сокращенной ДНФ используются две операции:
1) неполное склеивание A Ù x Ú A Ù x º A Ù (x Ú x) Ú A Ù x Ú A Ù x;
2) элементарное поглощение A Ù xσ Ú A º A Ù (xσ Ú 1) º A, σ Î {0,1}.
Например, рассмотрим функцию с приведенной ранее таблицей
истинности (знаки конъюнкции опускаем, как это обычно и делается):
f = xyz Ú xyz Ú xyz Ú xyz º
º xz(y Ú y) Ú yz(x Ú x) Ú xy(z Ú z) Ú xyz Ú xyz Ú xyz Ú xyz º
º xz Ú yz Ú xy Ú xyz Ú xyz Ú xyz Ú xyz º
º xz(1 Ú y) Ú yz(1 Ú x) Ú xy(1 Ú z) Ú xyz º
º xz Ú yz(1 Ú x) Ú xy º xz Ú yz Ú xy.
Таким образом, импликантами этой формулы являются конъюнкты: xyz, xyz, xyz, xyz, xz, yz, xy, причем лишь три последних
импликанты являются простыми. Сокращенная ДНФ имеет вид:
f = xz Ú yz Ú xy. Для получения минимальной ДНФ из сокращенной используем матрицу Квайна:
xyz
xyz
xyz
xyz
xy
–
*
*
–
xz
*
–
*
–
yz
–
*
–
*
В тупиковую ДНФ выбирается минимальное число простых
импликант, дизъюнкция которых сохраняет таблицу истинности
функции, т. е. каждый столбец матрицы Квайна содержит по крайней мере одну звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных импликант. Затем из тупиковой
ДНФ выбирается минимальная ДНФ. В нашем случае тупиковая
ДНФ равна xz Ú yz, она же будет равна МДНФ.
21
Полиномы Жегалкина
Существует и другой, отличный от СДНФ и СКНФ стандартный
способ представления логических функций. Любая логическая
функция (в том числе тождественно ложная и тождественно истинная функции) может быть представлена в виде полинома Жегалкина:
f (x1, x2 ,, xk ) = Å
i1i2ik
ai1i2ik xi1 xi2  xik ,
где коэффициенты ai1i2ik имеют значения 0 или 1. Для примера
снова рассмотрим функцию
f = xyz Ú xyz Ú xyz Ú xyz.
Поскольку A Å B º ( A Ú B) \ ( A Ù B) и конъюнкция любых двух
конъюнктов, входящих в f равна нулю, знаки дизъюнкции в выражении функции f можно заменить на ⊕:
f = xyz Å xyz Å xyz Å xyz.
Кроме того, воспользуемся тем, что a º a Å 1:
f = xy(z Å 1) Å x(y Å 1)z Å x(y Å 1)(z Å 1) Å (x Å 1)(y Å 1)z º
º xyz Å xy Å xyz Å xz Å xyz Å xy Å xz Å x Å xyz Å xz Å yz Å z.
Поскольку a⊕a≡0, окончательно получаем:
f=xz⊕yz⊕x⊕z.
Заметим, что xz Å yz Å x Å z º xz Ú yz.
Полные системы функций и базисы
Как уже говорилось, логические функции можно определять
с помощью суперпозиций: подставив в функцию f(x,y) вместо x
функцию g(x,y), а вместо y функцию h(x,y), получим, вообще говоря, новую функцию F(x,y)=f(g(x,y), h(x,y)). Такой набор логических функций {f, g, h, …}, что с помощью суперпозиций функций
из этого набора можно получить любую логическую функцию, называется полной системой функций. Очевидно, такие системы существуют, например, система всех логических функций. Однако
поскольку любую логическую функцию можно представить либо в
виде СДНФ, либо в виде СКНФ, либо и в том, и в другом виде, полной системой функций является уже набор из трех функций: отрицание, конъюнкция и дизъюнкция. Поскольку любую функцию
22
можно представить в виде полинома Жегалкина, полной системой
функций является набор из сложения по модулю 2, конъюнкции
и единицы. Но конъюнкцию можно представить в виде суперпозиции отрицания и дизъюнкции: x Ù y º x Ú y, а дизъюнкцию – в виде
суперпозиции отрицания и конъюнкции: x Ú y º x Ù y. Поэтому наборы из отрицания и конъюнкции и отрицания и дизъюнкции –
тоже полные системы функций. Но если из любого из этих наборов
исключить хотя бы одну функцию, этот набор перестанет быть полной системой функций – эти полные системы функций являются
минимальными, т. е. базисами. Базисами являются еще два набора,
каждый из которых состоит только из одной функции. Это базис
Пирса, включающий лишь стрелку Пирса ( x ¯ x º x Ú x º x ) и базис
Шеффера, включающий только штрих Шеффера ( x | x º x Ù x º x ).
На множестве логических функций выделяют функционально
замкнутые классы функций, (замкнутые относительно суперпозиций, классы Поста): если функции f, g, h, … принадлежат к одному классу Поста, то и любая их суперпозиция принадлежит этому
классу Поста. Этих классов пять. Рассмотрим эти классы.
1. P0 – класс функций, сохраняющих ноль, т. е. если
f (x1, x2, , xn ) Î P0 , то f(0, 0, …, 0)=0. Очевидно, к этому классу принадлежат тождественный нуль, f(x)=x, конъюнкция, дизъюнкция,
вычитание и сложение по модулю 2, но не принадлежат тождественная единица, отрицание, импликация, стрелка Пирса, штрих
Шеффера и эквиваленция.
2. P1 – класс функций, сохраняющих единицу, т. е. если
f (x1, x2, , xn ) Î P1, то f(1, 1, …, 1)=1. Очевидно, к этому классу принадлежат тождественная единица, f (x) º x, конъюнкция, дизъюнкция, импликация и эквиваленция, но не принадлежат тождественный нуль, отрицание, вычитание, стрелка Пирса, штрих
Шеффера и сложение по модулю 2.
3. S – класс самодвойственных функций, т. е. если
f (x1, x2, , xn ) Î S, то f*(x1, x2,..., xn)≡f(x1, x2,..., xn). Очевидно, к
этому классу принадлежат функции f(x)≡x и отрицание f (x) º x и
не принадлежат все остальные функции.
4. L – класс линейных функций, т. е. если f (x1, x2, , xn ) Î L, то
f (x1, x2, , xn ) = a0 Å a1x1 Å a2 x2 Å  Å an xn , где a1, a2,..., an – коэффициенты, каждый из которых равен либо 0, либо 1. Очевидно, к
этому классу принадлежат тождественная единица, тождественный нуль, f(x)≡x, f (x) º x и не принадлежат все остальные функции.
23
5. M – класс монотонных функций. Для определения этого класса надо ввести отношение частичного порядка на множестве наборов значений переменных. Для двух наборов s1={a1, a2,..., an},
s2={b1, b2,..., bn} выполнено отношение предшествования s1  s2 ,
если ai≤bi, i=1,2,...,n. Функция f (s) Î M, если s1  s2 ® f (s1 ) £ f (s2 ).
Очевидно, к этому классу принадлежат тождественные нуль и единица, функция f(x)≡x, конъюнкция и дизъюнкция и не принадлежат все остальные функции.
Нетрудно доказать функциональную замкнутость каждого из
этих классов (доказательство предоставляется читателю).
Теорема Поста. Для того чтобы набор функций был полной системой функций, необходимо и достаточно, чтобы он не содержался целиком ни в одном из классов Поста.
Секвенции
Отношение равносильности, введенное на множестве формул
алгебры логики, является отношением эквивалентности. Это отношение делит множество всех возможных высказываний на классы
эквивалентности: высказывания, относящиеся к одному классу,
утверждают, в сущности, одно и то же, хотя, возможно, другими
словами. Но в рассуждениях часто устанавливается, что из одного
высказывания логически следует другое, причем из второго высказывания первое может и не следовать. Например, из высказывания
‘‘Число N делится на 6’’ следует высказывание ‘‘Число N делится
на 3’’, но не наоборот. Отношение логического следования является отношением частичного порядка. Пусть Γ={A1, A2,..., An} – набор формул, B – формула. Выражение Γ|=B называется секвенцией.
Секвенция называется истинной, если на всех наборах значений
переменных, на которых истинна каждая из формул набора Γ, истинна и формула B. Если набор Γ пуст, и секвенция имеет вид |=B,
она называется тавтологией. Такая секвенция истинна в том и
только том случае, если B – тождественно истинная формула. Наоборот, выражение Γ|= указывает на то, что набор формул Γ противоречив.
Иначе говоря, секвенция Γ|=B означает, что из истинности высказываний A1, A2,..., An (в совокупности) следует истинность высказывания B (набор Γ={A1, A2,..., An} и формула B связаны отношением следования). Необходимо специально рассмотреть случай,
когда не существует таких наборов значений переменных, при которых каждое из высказываний A1, A2,..., An истинно. В этом случае секвенция Γ|=B истинна при любом B. Здесь полная аналогия с
24
импликацией. Конечно, истинность такой секвенции не доказывает истинность B.
Свойства знака следования |=. Пусть Γ={A1,..., An} – список
формул, B1,..., Bk, C – формулы.
1. A1,..., An|= Ai при i=1,..., n (элементарные следствия).
2. Если Γ|= C, то Γ, B1,..., Bk|= C (добавление допущений).
3. Если Γ|= Bi при i=1,..., k и B1,..., Bk|= C, то Γ|= C (доказательство с помощью лемм) [3].
Для доказательства истинности секвенций можно использовать табличный метод. Докажем, например, истинность секвенции
(a Ù b) ® b, b Ú (a Ù c) |= (a ® b) Ú (a Ù c). При этом удобнее будет обозначать отрицание знаком Ø . Кроме того, значения переменных
будем записывать под самими переменными, а значения функций
под знаками функций. Строчки, соответствующие тем наборам
переменных, при которых каждая из формул набора в левой части
принимает значение 1, будем подчеркивать:
(a
0
0
0
0
1
1
1
1
∧ b) → ¬
0 0 1 1
0 0 1 1
0 1 1 0
0 1 1 0
0 0 1 1
0 0 1 1
1 0 0 1
1 1 0 0
b,
0
0
1
1
0
0
1
1
b
0
0
1
1
0
0
1
1
∨
0
0
1
1
0
1
1
1
(a
0
0
0
0
1
1
1
1
∧
0
0
0
0
0
1
0
1
c)
0
1
0
1
0
1
0
1
=
(a
0
0
0
0
1
1
1
1
→
1
1
1
1
1
1
0
0
¬
1
1
0
0
1
1
0
0
b)
0
0
1
1
0
0
1
1
∨
1
1
1
1
1
1
0
1
(a
0
0
0
0
1
1
1
1
∧
0
0
0
0
0
0
0
1
c)
0
1
0
1
0
1
0
1
Видно, что в пересечениях подчеркнутых строк с выделенными
столбцами везде стоят единицы. Следовательно, секвенция доказана.
Часто для доказательства секвенций удобнее пользоваться свойствами знака следования и следующими правилами введения и
удаления логических знаков, которые легко доказываются табличным способом.
Знак Правило введения
®
Γ, A |= B тогда и только тогда,
когда Γ |= A ® B
Ù
A, B |= A Ù B
Правило удаления
A, A ® B |= B
A Ù B |= A
A Ù B |= B
25
Ú
A |= A Ú B
Если Γ, A |= C и Γ, B |= C ,
то Γ, A Ú B |= C
B |= A Ú B
Если Γ, A |= B и Γ, A |= B , то
A |= A
Γ |= A
A, A |= B
(для любого B )
~
A ® B, B ® A |= A ~ B
A ~ B |= A ® B
A ~ B |= B ® A
Правила преобразования списков допущений
Пусть Γ, Γ1, Γ2 – списки формул, A, B, C – формулы и Γ|=C. Следующие списки допущений равносильны:
1) Γ1, A, B, Γ2 и Γ1, B, A, Γ2 (правило перестановки),
2) Γ1, A, A, Γ2 и Γ1, A, Γ2 (правило сокращения),
3)  Γ1, A, B, Γ2 и Γ1, A Ù B (правила объединения и расщепления).
Пример. Доказательство тавтологии |= ( A ® B) ~ (B ® A) с помощью свойств символа следования, правил введения и удаления
знаков логических операций и правил преобразования списков допущений.
1)  A ® B, B, A |= B – свойство 1;
2)  A ® B, B, A |= B – свойство 2, удаление →;
3)  A ® B, B |= A – введение ¬, 1, 2;
4)  A ® B |= B ® A – введение →, 3;
5)  |= ( A ® B) ® (B ® A) – введение →, 4;
6)  B ® A, A, B |= A – свойство 1;
7)  B ® A, A, B |= A – свойство 2, удаление →;
8)  B ® A, A |= B 9)  B ® A, A |= B 10)  B ® A |= A ® B 11)  |= (B ® A) ® ( A ® B) 12)  |= ( A ® B) ~ (B ® A) – введение ¬, 6, 7;
– свойство 3, удаление ¬;
– введение →, 9;
– введение →, 10;
– свойство 3, введение ~, 5, 11.
Метод резолюций
Для доказательства тавтологий существует метод, называемый методом резолюций. Этот метод основан на истинности двух
секвенций 1) A, A Ú B |= B и 2) A Ú B, A Ú C |= B Ú C. Докажем пер26
вую секвенцию. Эта секвенция истинна, если при всех наборов
значений переменных, при которых истинна каждая из формул
A и A Ú B, истинна и формула B. Но если истинна формула A, то
формула A ложна, поэтому, если истинны и A, и A Ú B, то истинна
формула B. Доказательство второй секвенции: среди наборов значений переменных есть такие, при которых формула A истинна, и
такие, при которых она ложна. Других нет, поскольку A Ú A º 1 .
Но при тех наборах значений переменных, при которых формула A
истинна, формула A∨B истинна при любых B, а формула A Ú C истинна, только если истинна формула C. Наоборот, при тех наборах
значений переменных, при которых формула A ложна, формула
A Ú C обязательно истинна, а формула A∨B истинна только, если
истинна B. Таким образом, из истинности обеих этих формул следует, что хотя бы одна из формул B или C истинна. Эти секвенции и
называют резолюциями.
Рассмотрим метод резолюций на примере доказательства следующей тавтологии:
|= ( A ® B) Ù (C ® D) ® ( A Ú C ® B Ú D).
Тавтология будет доказана, если доказать тождественную ложность противоположного высказывания:
( A ® B) Ù (C ® D) ® ( A Ú C ® B Ú D) |=
Сначала мы преобразуем формулу в левой части, чтобы получить ее КНФ:
( A ® B) Ù (C ® D) ® ( A Ú C ® B Ú D) º
º ( A ® B) Ù (C ® D) Ú ( A Ú C ® B Ú D) º
º ( A ® B) Ù (C ® D) Ù A Ú C Ú B Ú D º
º ( A Ú B) Ù (C Ú D) Ù ( A Ú C) Ù B Ù D.
При этих преобразованиях использовались законы де Моргана,
снятие двойного отрицания и равносильность a ® b º a Ú b. В результате получилась КНФ формулы в левой части. Для доказательства тождественной ложности этой формулы достаточно доказать
противоречивость списка допущений:
1)  A Ú B; 2)  C Ú D; 3)  A Ú C; 4)  B; 5)  D (формулы нумеруем для
удобства ссылок), т. е. наличие в нем взаимно противоположных
высказываний.
27
Рассмотрев этот список, видим, что в нем нет очевидных противоречий. Однако используя резолюцию первого типа, получаем, что
из формул A Ú B и B следует формула A. Это записываем в виде:
resB ( A Ú B, B) = A.
Добавляем формулу A в список допущений:
1)  A Ú B, 2)  C Ú D, 3)  A Ú C, 4)  B, 5)  D, 6)  A.
Обозреваем этот список, и в нем не обнаруживаем очевидных
противоречий. Снова используем резолюцию первого типа и получаем, что из формул A Ú C и A следует формула C. Записываем:
res A ( A Ú C, A) = C.
Добавляем и эту формулу в список допущений:
1)  A Ú B, 2)  C Ú D, 3)  A Ú C, 4)  B, 5)  D, 6)  A, 7)  C.
Явных противоречий в этом списке также нет, поэтому опять
применяем резолюцию первого типа, на этот раз к формулам C Ú D
и C, из которой следует, что
resC (C Ú D, C) = D.
Пополнив список допущений последней формулой, получим:
1)  A Ú B, 2)  C Ú D, 3)  A Ú C, 4)  B, 5)  D, 6)  A, 7)  C, 8)  D.
Теперь очевидно, что список допущений противоречив – противоречат друг другу допущения 5) и 8). Тавтология доказана.
3. Исчисления высказываний
Как уже говорилось, алгебра высказываний основывается на
определениях логических операций с помощью таблиц истинности.
Тем самым эта логическая теория имеет частный, не вполне формальный характер. В то же время в современной математике (и физике)
идеальным считается построение теории как формальной теории на
основе аксиоматического метода, для чего необходимы:
1) явная формулировка аксиом теории;
2) явная формулировка правил вывода, используемых для последовательного построения теории;
3) использование искусственно построенного формального языка для изложения всех утверждений теории.
28
В этом разделе рассматриваются аксиоматические логические
теории, называемые исчислениями высказываний. Значение этих
теорий состоит в том, что они являются простейшими моделями
аксиоматических теорий и позволяют изучить и сформулировать
свойства и правила построения аксиоматических теорий.
В исчислении высказываний не используются таблицы истинности, а за истинные принимаются либо некоторые формулы, либо
секвенции.
Множество символов (‘‘абстрактных букв’’), используемых в теории, называется ее алфавитом. Алфавит исчисления высказываний σ состоит из объединения четырех множеств: σ=σ1∪σ2∪σ3∪σ4,
где σ1={a, b,..., z, A1, B2,..., Zn} σ2={, , →, ¬}, σ3={(,),,}, σ4={|–}.
Других символов алфавит исчисления высказываний не содержит.
Буквы множества σ1 называются пропозициональными переменными. Символ |– называется символом следования. Конечный ряд написанных друг за другом букв называется словом в этом алфавите.
Формулой исчисления высказываний называется слово алфавита, удовлетворяющее следующим условиям:
1) пропозициональная переменная является формулой, которая
называется элементарной, или атомарной.
2) если A и B – формулы, то ( A Ù B),( A Ú B),( A ® B) и A – тоже
формулы.
Никаких других формул нет, поэтому слово ( A Ú B) Ù C – не формула, так как не имеет внешних скобок, однако принято внешние
скобки опускать, и тогда ( A Ú B) Ù C – тоже формула.
Различных исчислений высказываний существует много. Все
они делятся на два типа: исчисления гильбертовского типа (по имени крупнейшего немецкого математика конца девятнадцатого –
начала двадцатого века Д. Гильберта) и исчисления генценовского
типа (по имени немецкого математика и логика первой половины
двадцатого века Г. Генцена). В исчислениях гильбертовского типа
много аксиом и мало (основных) правил вывода, а в исчислениях
генценовского типа – наоборот.
Начнем с исчисления высказываний гильбертовского типа, которое будем обозначать ИВ. Это исчисление определяется следующей схемой аксиом, которая состоит из одиннадцати формул, разделенных на четыре группы.
I.
A1. A ® (B ® A);
II.
A2. ( A ® (B ® C)) ® (( A ® B) ® ( A ® C));
A3. A Ù B ® A;
29
III
A4.
A5.
A6.
A7.
A8. ( A ® C) ® ((B ® C) ® ( A Ú B ® C));
IV
A9. ( A ® B) ® (B ® A);
A10. A ® A;
A Ù B ® B;
(C ® A) ® ((C ® B) ® (C ® A Ù B));
A ® A Ú B;
B ® A Ú B;
A11. A ® A.
Легко проверить, что все эти формулы являются тавтологиями
алгебры высказываний. Каждая из этих формул представляет собой не одну аксиому, а бесконечное множество аксиом, поскольку в
результате подстановки в эти формулы вместо пропозициональных
переменных любых формул получаются аксиомы.
Выводом формулы B из набора формул Γ={A1, A2,..., An} в исчислении высказываний ИВ называется конечная последовательность
формул B1, B2,..., Bm, такая, что каждая из формул последовательности либо есть одна из формул набора Γ, либо аксиома, либо получается из предыдущих с помощью правил вывода, а последней является формула Bm=B. Если такой вывод существует, это записывается в виде секвенции: Γ|–B. Формула B в этом случае называется
выводимой из набора Γ. Если набор Γ пуст, такая секвенция записывается в виде |–B, и формула B называется доказуемой или теоремой. Тогда вывод обычно называют доказательством теоремы.
Основное правило вывода в ИВ всего одно: правило простого заключения: если в выводе есть формулы A и A→C, то в вывод можно
добавить формулу C. Аналогичное правило известно с древности,
его латинское название ‘‘modus ponens’’ (сокращенно MP).
В качестве примера рассмотрим доказательство теоремы |–F→F.
1) (F→((F→F)→F))→((F→(F→F))→(F→F));
2) F→((F→F)→F);
3) (F→(F→F))→(F→F);
4) F→(F→F);
5) F→F.
Формула 1) представляет собой схему A2, в которой вместо A
подставлено F, вместо B – формула F→F, вместо C – формула F.
Формула 2) представляет собой схему A1 с той же подстановкой.
Формула 3) получена из формул 1) и 2) по правилу MP. Формула 4)
получена из схемы 1 подстановкой формулы F вместо A и B. Формула 5) получена по правилу MP из формул 4) и 3).
30
Формальный вывод секвенции A→B, B→C|–A→C.
1) A→B
– допущение;
2) B→C
– допущение;
3) (B→C)→(A→(B→C))
– A1;
4) A→(B→C)
– MP 2, 3;
5) (A→( B→C))→ ((A→B)→ (A→C))
– A2;
6) (A→B)→ (A→C)
– MP 4, 5;
7) (A→C)
– MP 1, 6.
Построение выводов бывает достаточно сложным. Его часто облегчает следующая теорема [4].
Теорема о дедукции. Если A1, A2, …, An–1, An|–G, то A1, A2, …,
An–1|– An→G. В частности, если F |–G, то |–F→G.
Рассмотрим теперь другое исчисление высказываний, которое
обозначают обычно ИС. Это исчисление генценовского типа, в нем
одна схема аксиом A|–A и много правил вывода. Выводом секвенции
A|–B из набора секвенций {F1|–G1, F2|–G2,..., Fn|–Gn} в этом исчислении называется последовательность секвенций, каждая из которых либо представляет собой аксиому, либо секвенцию из исходного набора, либо получается из предыдущих секвенций с помощью
правил вывода этого исчисления.
Основные правила вывода:
1) 
Γ |- A, Γ |- B
(введение );
Γ |- A Ù B
2)
Γ |- ( A Ù B) Γ |- ( A Ù B)
(удаление );
,
Γ |- A
Γ |- B
3) 
Γ |- A
Γ |- B
(введение );
,
Γ |- ( A Ú B) Γ |- ( A Ú B)
4) 
Γ, A |- C; Γ, B |- C; Γ |- ( A Ú B)
(удаление , разбор случаев);
Γ |- C
5) 
Γ, A |- B
(введение →);
Γ |- ( A ® B)
6)
Γ1 |- A, Γ2 |- ( A ® B)
(удаление →);
Γ1, Γ2 |- B
7) 
Γ, A |(удаление ¬, или доказательство от противного);
Γ |- A
31
8) 
Γ |- A, Γ |- A
(выведение противоречия);
Γ |-
9) 
Γ, A, B, Γ1 |- C
(перестановка посылок);
Γ, B, A, Γ1 |- C
Γ |- A
(утончение, или правило лишней посылки).
Γ, B |- A
Пример 3. Вывод в ИС секвенции A, A→B, B→C, C→D|–D.
1) A|–A – аксиома,
2) A→B|– A→B – аксиома;
3) A, A→B|–B – удаление →, 1, 2;
4) B→C|– B→C – аксиома;
5) A, A→B, B→C|–C – удаление →, 3, 4;
6) C→D|– C→D – аксиома;
7) A, A→B, B→C, C→D|–D – удаление →, 5, 6.
10) 
Полнота, разрешимость и непротиворечивость
исчисления высказываний. Независимость системы аксиом
исчисления высказываний
Исчисление высказываний полно (обладает свойством полноты), если всякая доказуемая в этом исчислении формула является
тождественно истинной формулой (тавтологией) алгебры высказываний, и наоборот, любая тавтология алгебры высказываний является доказуемой формулой этого исчисления, т. е. |–F~|=F. Существуют доказательства [1], что исчисления ИВ и ИС полны.
Аксиоматическая теория называется разрешимой, если существует алгоритм, позволяющий для любого утверждения, сформулированного в терминах этой теории, ответить на вопрос, является ли это утверждение теоремой этой теории. Для доказательства
разрешимости исчисления высказываний надо предъявить такой
алгоритм. И он действительно существует и состоит в составлении
таблицы истинности формулы. Если она содержит лишь единицы,
то является тавтологией, а значит, поскольку исчисление полно,
теоремой исчисления. Если есть хотя бы один ноль, это не тавтология, следовательно, не теорема.
Аксиоматическая теория называется непротиворечивой, если
ни для какого утверждения A, сформулированного в терминах этой
теории, само утверждение A и его опровержение A не могут быть
одновременно теоремами этой теории. Можно показать [1], что исчисления ИВ и ИС непротиворечивы.
32
Система аксиом называется независимой, если ни одну из аксиом этой системы нельзя вывести из остальных. Системы аксиом исчислений ИВ и ИС независимы [1].
4. Логика предикатов
Высказывание с точки зрения исчисления высказываний – предельно простой объект, оно имеет лишь одну характеристику, оно
может либо истинным, либо ложным. Высказывания совершенно
не структурированы. Но реальные суждения всегда говорят что-то
о чем-то или ком-то. Главные члены предложения – подлежащее и
сказуемое. Подлежащее означает тот объект, о котором говорится
в предложении, а сказуемое – то, что в предложении говорится об
этом объекте. Сказуемое иначе называется предикатом.
В математической логике определенным на множествах
M1, M2,..., Mn n-местным предикатом называется выражение
Pn(x1, x2,..., xn), содержащее n переменных x1, x2,..., xn, и превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств M1, M2,..., Mn соответственно. Переменные x1, x2,..., xn называют предметными, а
элементы множеств M1, M2,..., Mn – конкретными предметами.
Всякий n-местный предикат, определенный на множествах
M1, M2,..., Mn, является функцией n аргументов, заданной на этих
множествах и принимающей значения во множестве всех высказываний.
Рассмотрим пример. Предложение “Река x впадает в Каспийское
море” является одноместным предикатом, определенным на множестве всех названий рек. Подставив вместо x названия “Волга”,
“Урал” или “Терек”, получим истинные высказывания, а подставив
“Днепр”, “Нил” или “Ориноко”, получим ложные высказывания.
Примером двухместного предиката является неравенство
x2+y2<9. Этот предикат задан на двух экземплярах множества вещественных чисел R. Он превращается в истинное высказывание, в
частности, при x=1, y=2, а в ложное – при x=2, y=3.
Классификация предикатов
Предикат Pn(x1, x2,..., xn), определенный на множествах
M1, M2,..., Mn, называется a) тождественно истинным, если при
любой подстановке вместо переменных x1, x2,..., xn любых кон33
кретных предметов a1, a2,..., an из множеств M1, M2,..., Mn соответственно он превращается в истинное высказывание; b) тождественно ложным, если при любой подстановке вместо переменных
x1, x2,..., xn любых конкретных предметов a1, a2,..., an из множеств M1, M2,..., Mn соответственно он превращается в ложное
высказывание; c) выполнимым (опровержимым), если существует
по крайней мере один набор конкретных предметов a1, a2,..., an из
множеств M1, M2,..., Mn, при подстановке которых вместо соответствующих предметных переменных в этот предикат он превратится
в истинное (ложное) высказывание.
Например, предикат x2≥0, определенный на множестве вещественных чисел R, является тождественно истинным, предикат
sinx>1, определенный на R, является тождественно ложным, а
предикат “Город x расположен на берегу Волги” является выполнимым и одновременно опровержимым.
Множество истинности предиката
Множеством истинности предиката Pn(x1, x2,..., xn),
определенного на множествах M1, M2,..., Mn, называется совокупность всех упорядоченных наборов конкретных предметов
a1, a2,..., an из множеств M1, M2,..., Mn соответственно, таких, что
Pn(a1, a2,..., an) – истинное высказывание.
Обозначим множество истинности предиката Pn(x1, x2,..., xn)
через P+. Таким образом, P+={(a1, a2,..., an): P(a1, a2,..., an)=1}.
Равносильность и следование предикатов
Два n-местных предиката Pn(x1, x2,..., xn) и Qn(x1, x2,..., xn),
заданных над одними и теми же множествами M1, M2,..., Mn,
называются равносильными, если набор конкретных предметов
a1, a2,..., an из множеств M1, M2,..., Mn соответственно превращает первый предикат в истинное высказывание Pn(a1, a2,..., an)
в том и только том случае, когда этот же набор превращает второй
предикат в истинное высказывание Qn(a1, a2,..., an). Иначе говоря,
предикаты равносильны, если их множества истинности совпадают: P+ = Q+.
Например, равносильны предикаты: x+y>5 и x>5–y.
Предикат Qn(x1, x2,..., xn), заданный над множествами
M1, M2,..., Mn, называется следствием предиката Pn(x1, x2,..., xn),
заданного над теми же множествами, если он превращается в истинное высказывание в наборах значений предметных переменных из
34
соответствующих множеств, на которых в истинное высказывание
превращается предикат Pn(x1, x2,..., xn). Иначе говоря, P+ Í Q+ .
Например, предикат x2>4 является следствием предиката x>2,
но эти предикаты не равносильны, поскольку первое неравенство
справедливо и при x<–2.
Логические операции над предикатами
Отрицанием предиката Pn(x1, x2,..., xn), заданного над множествами M1, M2,..., Mn, называется новый предикат, заданный над
n
теми же множествами, обозначаемый P (x1, x2 ,, xn ) (читается:
“неверно, что Pn(x1, x2,..., xn)”), который превращается в истинное высказывание при всех тех и только тех значениях предметных
переменных, при которых предикат Pn(x1, x2,..., xn) превращается
в ложное высказывание.
Например, предикат x≥3 является отрицанием предиката x<3.
Для предиката Pn(x1, x2,..., xn), определенного на множествах
n
M1, M2,..., Mn, множество истинности предиката P (x1, x2 ,, xn )
является дополнением множества истинности предиката
+
Pn(x1, x2,..., xn): (P ) = (M1 ´ M2 ´´ Mn ) \ P+ .
Конъюнкцией n-местного предиката Pn(x1, x2,..., xn), определенного на множествах M1, M2,..., Mn, и m-местного предиката
Qm(y1, y2,..., ym), определенного на множествах N1, N2,..., Nm,
называется новый (n+m)-местный предикат, определенный
на множествах M1, M2,..., Mn, N1, N2,..., Nm, обозначаемый
Pn (x1, x2 ,, xn ) Ù Qm (y1, y2 ,, ym ) (читается “ Pn(x1, x2,..., xn) и
Qm (y1, y2 ,, ym ) ”), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных,
при которых оба исходных предиката превращаются в истинные
высказывания.
Например, конъюнкцией предикатов x>3 и x<10 является предикат 3<x<10.
Дизъюнкцией n-местного предиката Pn(x1, x2,..., xn), определенного на множествах M1, M2,..., Mn, и m-местного предиката
Qm (y1, y2 ,, ym ) , определенного на множествах N1, N2,..., Nm,
называется новый (n+m)-местный предикат, определенный
на множествах M1, M2,..., Mn, N1, N2,..., Nm, обозначаемый
Pn (x1, x2 ,, xn ) Ú Qm (y1, y2 ,, ym ) (читается “ Pn(x1, x2,..., xn) или
Qm (y1, y2 ,, ym ) ”), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных,
при которых хотя бы один из исходных предикатов превращается в
истинное высказывание.
35
Например, дизъюнкцией предикатов x>3 и x<10 является предикат “x>3 или x<10”.
Импликация Pn(x1, x2,..., xn)→Qm(y1, y2,..., ym) определяется как такой предикат, что для любых предметов
a1 Î M1, a2 Î M2 ,, an Î Mn , b1 Î N1, b2 Î N2 ,, bn Î Nn
высказывание Pn(a1, a2,..., an)→Qm(b1, b2,..., bm) является импликацией высказываний Pn(a1, a2,..., an) и Qm(b1, b2,..., bm).
Например, импликацией предикатов x>10 и x>1 является предикат “Если x>10, то и x>1”.
Эквиваленция Pn(x1, x2,..., xn) ~ Qm(y1, y2,..., ym) определяется как такой предикат, что для любых предметов
a1 Î M1, a2 Î M2 ,, an Î Mn , b1 Î N1, b2 Î N2 ,, bn Î Nn
высказывание Pn(a1, a2,..., an) ~ Qm(b1, b2,..., bm) является эквиваленцией высказываний Pn(a1, a2,..., an) и Qm(b1, b2,..., bm).
Например, эквиваленцией предикатов x>10 и 10<x является
предикат “Если и только если x<10, то 10>x”.
Кванторные операции над предикатами
Операцией связывания квантором общности по переменной
x называется правило, по которому каждому одноместному предикату P1(x), определенному на множестве M, ставится в соответствие высказывание ("x) P1 (x) (читается “для всякого xP1(x)”),
которое истинно в том и только том случае, когда предикат P1(x)
тождественно истиннен, и ложно в противоположном случае,
а n-местному (n>1) предикату Pn(x1, x2,..., xn), определенному на множествах M1, M2,..., Mn, ставится в соответствие новый (n-1)-местный предикат, обозначаемый ("x1 ) Pn (x1, x2 ,, xn )
(читается “для всех x1 Pn(x1, x2,..., xn)”), который для любых
предметов a2 Î M2 , , an Î Mn превращается в высказывание
("x1 ) Pn (x1, a2 ,, an ), истинное в том и только том случае, когда одноместный предикат Pn(x1, a2,..., an), определенный на множестве
M1, тождественно истиннен и ложное в противоположном случае.
Операцией связывания квантором существования по переменной x называется правило, по которому каждому одноместному
предикату P1(x), определенному на множестве M, ставится в соответствие высказывание ($x) P1 (x) (читается “существует x, такое,
что P1(x) ”), которое ложно в том и только том случае, когда предикат P1(x) тождественно ложен, и истинно в противоположном
случае, а n-местному (n≥2) предикату Pn(x1, x2,..., xn), определенному на множествах M1, M2,..., Mn, ставится в соответствие новый
(n-1)-местный предикат, обозначаемый ($x1 ) Pn (x1, x2 ,, xn ) (чита36
ется “существует x1, такое, что Pn(x1, x2,..., xn)”), который для любых предметов a2 Î M2 , , an Î Mn превращается в высказывание
($x1 ) Pn (x1, a2 ,, an ), ложное в том и только том случае, когда одноместный предикат Pn(x1, a2,..., an), определенный на множестве
M1, тождественно ложен и истинное в противоположном случае.
В выражениях типа ("x1 ) Pn (x1, x2 ,, xn ) и ($x1 ) Pn (x1, x2 ,, xn )
переменная x1 называется связанной. Остальные переменные называются свободными.
Формулы логики предикатов
Алфавит логики предикатов состоит из следующих символов:
предметные переменные: x, y, z, xi , yi , zi (i Î N);
нульместные предикатные переменные: P, Q, R, Pi , Qi , Ri (i Î N);
n-местные предикатные переменные: Pn (,…,), Qn (,…,), R n (,…,), Pin (,…,),
n
,), R (,…,), Pin (,…,), Qin (,…,), Rin (,…,)(i Î N); с указанием числа свободных мест
в них;
символы логических операций: ¬, , , ~;
кванторы: ∀, ∃;
вспомогательные символы: (, ),,.
Каждая нульместная предикатная переменная есть формула, если Pn(,...,)– n-местная предикатная переменная, то
Pn(x1, x2,..., xn) – формула, в которой все переменные x1, x2,..., xn
свободны, если F – формула, то F – тоже формула, свободные (связанные) предметные в этой формуле те же, что и в формуле F; если
F1, F2 – формулы, то выражения F1F2, F1F2, F1→F2, F1~F2 также являются формулами, при этом предметные переменные, свободные (связанные) хотя бы в одной из формул F1, F2, являются
свободными (связанными) и в новых формулах; если F – формула, а
x – предметная переменная, входящая в F свободно, то выражения
(∀x)(F) и (∃x)(F) – тоже формулы, в которых переменная x связанная, а все остальные предметные переменные, входящие в формулу
F свободно или связанно, остаются и в новых формулах такими же.
Никаких других формул логики предикатов нет.
Если в формулу логики предикатов вместо каждой предикатной переменной подставить конкретный предикат, определенный
на некотором множестве M, то формула превратится в конкретный
предикат, определенный на множестве M. Если исходная формула
замкнута, то полученный предикат будет нульместным, т. е. высказыванием, а если открыта, то полученный предикат будет зависеть
от некоторых предметных переменных. Если теперь подставить
37
вместо них конкретные предметы из множества M, то получится
конкретное высказывание.
Превращение формулы логики предикатов в высказывание этим
способом и само получаемое высказывание называется интерпретацией этой формулы на множестве M.
Формула логики предикатов называется выполнимой (опровержимой) на множестве M, если при некоторой подстановке вместо
предикатных переменных конкретных предикатов, заданных на
этом множестве, она превращается в выполнимый (опровержимый) предикат.
Формула логики предикатов называется тождественно истинной (тождественно ложной) на множестве M, если при всякой
подстановке вместо предикатных переменных любых конкретных
предикатов, заданных на этом множестве, она превращается в тождественно истинный (тождественно ложный) предикат.
Формула логики предикатов называется общезначимой, или
тавтологией (тождественно ложной или противоречием), если
при всякой подстановке вместо предикатных переменных любых
конкретных предикатов, заданных на каких угодно множествах,
она превращается в тождественно истинный (тождественно ложный) предикат.
Например, формула P(x) Ù ("y)(P(y)) является противоречием
(тождественно ложной).
Тавтологии логики предикатов
Нахождение тавтологий является одной из важнейших задач
логики предикатов, как и логики высказываний. Но если в логике высказываний имеется общий метод определения, является ли
данная формула тавтологией (таблицы истинности), то в логике
предикатов такого метода не существует, поскольку каждое высказывание имеет только одно из значений: “истина” или “ложь”,
а значение предиката зависит от выбора значений его предметных
переменных, который можно (вообще говоря) сделать бесконечным
числом способов. Простейшие тавтологии логики предикатов получаются из тавтологий логики высказываний.
Всякая формула, получающаяся из тавтологии логики высказываний заменой входящих в нее пропозициональных переменных
произвольными предикатными переменными, является тавтологией логики предикатов.
Специфичны для логики предикатов тавтологии, которые являются выражениями, содержащими кванторы.
38
Законы де Моргана для кванторов. Следующие формулы являются тавтологиями логики предикатов:
1)  ("x)(P(x) ~ ($x)(P(x));
2)  ($x)(P(x) ~ ("x)(P(x).
Следствия этих формул:
1)  ("x)(P(x)) ~ ($x)(P(x));
2)  ($x)(P(x)) ~ ("x) P(x).
Законы пронесения кванторов через конъюнкцию и дизъюнкцию. Следующие формулы являются тавтологиями логики предикатов:
1)  ("x)(P(x) Ù Q(x)) ~ ("x)(P(x)) Ù ("x)(Q(x));
2)  ($x)(P(x) Ú Q(x)) ~ ($x)(P(x)) Ú ($x)(Q(x));
3)  ("x)(P(x) Ú Q) ~ ("x)(P(x)) Ú Q;
4)  ($x)(P(x) Ù Q) ~ ($x)(P(x)) Ù Q.
Законы пронесения кванторов через импликацию. Следующие
формулы являются тавтологиями логики предикатов:
1)  ("x)(P(x) ® Q) ~ (($x)(P(x)) ® Q);
2)  ($x)(P(x) ® Q) ~ (("x)(P(x)) ® Q);
3)  ("x)(Q ® P(x)) ~ (Q ® ("x)(P(x)));
4)  ($x)(Q ® P(x)) ~ (Q ® ($x)(P(x))).
Законы удаления квантора общности и введения квантора существования. Следующие формулы являются тавтологиями логики предикатов:
1)  ("x)(P(x)) ® P(y);
2)  P(y) ® ($x)(P(x)).
Законы коммутативности для кванторов. Следующие формулы являются тавтологиями логики предикатов:
1)  ("x)("y)(P(x, y)) ~ ("y)("x)(P(x, y));
2)  ($x)($y)(P(x, y)) ~ ($y)($x)(P(x, y));
3)  ($x)("y)(P(x, y)) ® ("y)($x)(P(x, y)).
Равносильные преобразования формул
логики предикатов
Две формулы логики предикатов F и G называются равносильными на множестве M, если при любой подстановке в эти формулы вместо предикатных переменных любых конкретных предикатов, формулы превращаются в равносильные предикаты. Если две
формулы равносильны на любых множествах, то они называются
равносильными. Равносильность обозначается так: F≡G. Переход от
39
одной равносильной формулы к другой называется равносильным
преобразованием исходной формулы. Формулы F и G равносильны,
если формула F~G – тавтология. Например, (∀x)(∀y)(P(x, y))≡(∀y)
(∀x)(P(x, y)).
Логическое следование логики предикатов
Формула G логики предикатов называется логическим следствием формулы F, если при всякой интерпретации, при которой F
превращается в тождественно истинный предикат, формула G также превращается в тождественно истинный предикат. Это обозначается записью: F|=G. Как и в алгебре высказываний, если и только
если F|=G, то |=F→G. Две формулы равносильны тогда и только тогда, когда каждая из них является логическим следствием другой.
Но возможны случаи, когда логическим следствием формулы является неравносильная ей формула, например:
($x)(P(x) Ù Q(x)) |= ($x)(P(x)) Ù ($y)(Q(y)).
Правило удаления квантора общности (правило универсальной
конкретизации):
("x) F (x) |= F (y).
Правило введения квантора существования (правило экзистенциального обобщения):
F (y) |= ($x) F (x).
В этих правилах предполагается, что переменная y не входит в
формулу F(x) свободно.
Проблема разрешимости для общезначимости и
выполнимости формул логики предикатов
В логике предикатов, в отличие от алгебры высказываний, не
существует алгоритма, позволяющего для каждой формулы определить, будет ли она выполнимой или общезначимой. Это было доказано в 1936 г. американским математиком А. Чёрчем. Проблема
разрешимости в логике предикатов допускает решение лишь для
некоторых частных видов формул. Задача о выполнимости или общезначимости формул логики предикатов на конечном множестве
сводится к задаче о выполнимости или тождественной истинности
алгебры высказываний, которая разрешима.
40
Применение логики предикатов
к логико-математической практике
Применение логики предикатов к построению определений математических понятий и доказательств математических теорем позволяет проводить более сложные доказательства и в результате получать более тонкие заключения. Перевод расплывчатой словесной
формулировки на строгий, не допускающий противоречивых толкований язык логики предикатов способствует четкости и ясности
мышления. Приведем пример.
Определение предела последовательности “Число a называется
пределом последовательности {an}, если для всякого положительного числа ε >0 существует такое натуральное число n0, что для
всякого натурального n, большего n0, |an– a|<ε” на языке логики
предикатов записывается так:
îïð
a = lim an Û ("ε)[ε > 0 ® ($n0 )(n0 Î N Ù ("n)(n > n0 ®| an - a |< ε))].
Короче это можно записать так:
îïð
a = lim an Û ("ε > 0)($n0 Î N)("n > n0 )(| an - a |< ε).
Утверждение “Число a не является пределом последовательности {an}” означает, что существует такое положительное число ε,
что для всякого натурального n0 найдется такое натуральное n>n0,
что |an– a|≥ε. На языке логики предикатов это запишется так:
($ε > 0)(n0 Î N)($n > n0 )(| an - a |³ ε).
Теоремы математики допускают формулировки в виде условных предложений. Часто в теореме можно выделить три части:
условие теоремы – предикат P(x), заданный на множестве M1,
заключение теоремы – предикат Q(x), заданный на множестве
M2, разъяснительная часть, описывающая множества объектов,
о которых идет речь в теореме. Строение теоремы может быть таким: “Если любой элемент x из множества M обладает свойством
P(x), то он обладает свойством Q(x)”. Теорема формулируется так:
("x Î M)(P(x) ® Q(x)). Например, теорема о конечных приращениях (теорема Лагранжа) гласит: “Если f(x) непрерывна на [a, b] и
дифференцируема на (a, b), то найдется на (a, b) такая точка c, что
f (b) - f (a) = f ¢(c)(b - a). ” Пусть предикат P(a,b,x) выражает свойство
функции y=f(x) быть непрерывной на [a, b] и дифференцируемой на
41
(a, b), а Q(a, b, x) = (f (b) - f (a) = f ¢(c)(b - a)). Тогда теорема Лагранжа
может быть сформулирована так: ($c Î (a, b))(P(a, b, x) ® Q(a, b, x)).
5. Формализованное исчисление предикатов
Задача формализованного исчисления предикатов та же, что и
формализованного исчисления высказываний – дать аксиоматическую теорию совокупности всех общезначимых формул (тавтологий) логики предикатов, т. е. изучить способы вывода (доказательства) всех таких формул, исходя из выбранной системы аксиом
и с использованием выбранных правил вывода. Здесь приводится
краткое описание этого исчисления.
Алфавит исчисления предикатов состоит из предметных переменных x1, x2,..., предметных констант c1, c2,..., предикатных
букв P1n , P2n ,, функциональных букв f1n , f2n ,, знаков логических связок ¬, , , →, кванторов ∀, ∃ и скобок (, ). Верхние индексы предикатных и функциональных букв указывают число
аргументов.
Термами являются отдельно взятые предметные переменные и
константы, а также выражения вида f n(t1,..., tn), где f n – n-местный
функциональный символ, t1,..., tn – термы.
Формула исчисления предикатов определяется следующим образом:
1) если Pn – предикатная буква, t1,..., tn – термы, то Pn(t1,..., tn) –
формула, при этом все вхождения переменных в эту формулу называются свободными;
2) если F1,F2 – формулы, то формулами являются F1,(F1 ® F2 ),(F1 Ù F2 ),(F
,(F1 ® F2 ),(F1 Ù F2 ),(F1 Ú F2 ) – тоже формулы;
3) если F(x) – формула, содержащая свободные вхождения переменной x, то ("x)(F (x)) и ($x)(F (x)) – формулы, при этом вхождения
переменной x в них называются связанными, вхождения же всех
остальных предметных переменных в эти формулы остаются свободными (связанными), если они были свободными (связанными) в
формуле F(x), которая называется областью действия квантора;
4) никаких других формул нет.
Совокупность G={c1, c2,...: f1, f2: P1, P2,...} называется сигнатурой данного исчисления предикатов.
Система аксиом исчисления предикатов состоит из двух групп:
первая – это аксиомы исчисления высказываний ИВ, а вторая
включает следующие аксиомы:
42
PA1 ("x)(F (x)) ® F (y);
PA2 F (y) ® ($x)(F (x));
где F(x) – любая формула, содержащая свободные вхождения x,
причем ни одно из них не находится в области действия квантора
по y (если таковой имеется); формула F(y) получена из формулы
F(x) заменой всех свободных вхождений x на y.
Правила вывода. К правилу вывода MP из исчисления высказываний добавляются еще два правила вывода:
F ® G (x)
" -правило, или правило обобщения
;
F ® ("x)(G (x))
G (x) ® F
$ -правило, или правило конкретизации
при усло($x)(G (x)) ® F
вии, что G(x) содержит свободные вхождения x, а F не содержит.
Формула G называется выводимой из гипотез F1,..., Fm с фиксированными вхождениями в гипотезы свободных переменных,
если существует такая конечная последовательность формул
B1, B2,..., Bk=G, каждая формула которой является либо аксиомой, либо гипотезой, либо получена из предыдущих формул последовательности по одному из правил вывода (сама эта последовательность называется выводом G из гипотез F1,..., Fm). При этом,
если Bi есть первая гипотеза, встречающаяся в выводе, то дальше
в этом выводе не могут быть использованы " - и $ -правила вывода
по любой переменной x, которая входит свободно хотя бы в одну из
гипотез. Обозначение используется то же, что и в исчислении высказываний: F1,..., Fm|–G. Если гипотезы отсутствуют, то говорят,
что G выводима из аксиом (или просто выводима), и называют G
теоремой исчисления предикатов и пишут |–G.
Свойства формализованного исчисления предикатов
Поскольку не является разрешимой логика предикатов, то и исчисление предикатов не является разрешимой теорией.
Другим важнейшим требованием, предъявляемым к аксиоматической теории, является ее непротиворечивость. В непротиворечивой теории невозможно доказательство истинности какого-либо
утверждения и его отрицания одновременно. Однако доказательство этого свойства теории весьма сложно (и из-за бесконечности
утверждений теории, и из-за отсутствия точного понятия доказательства). Поэтому в математике более естественным считается
другой признак непротиворечивости теории.
43
Формальная теория T есть теория множества M(T) всех своих
моделей, поэтому она семантически (т. е. по смыслу) непротиворечива, если и только если M (T) ¹ Æ, т. е. существует хотя бы
одна ее содержательная модель (интерпретация). Исчисление
предикатов семантически непротиворечиво.
Неприятие
современниками
неевклидовой
геометрии
Лобачевского-Бояи объясняется тем, что законность этой теории
обосновывалась отсутствием в ней противоречий, ее модели были
построены значительно позже. Но развитие математической логики привело и к доказательству формальной (синтаксической) непротиворечивости исчисления предикатов.
Логическая система называется полной в узком смысле, если
нельзя без противоречия присоединить к ее аксиомам в качестве
новой аксиомы никакую не выводимую в ней формулу так, чтобы полученная при этом система была бы непротиворечивой. В
отличие от исчисления высказываний исчисление предикатов не
является теорией, полной в узком смысле. К его аксиомам можно
присоединить без противоречия недоказуемую в ней формулу (∃x)
(F(x))→(∀x)(F(x)). Содержательный смысл этой формулы состоит
в том, что все предметы тождественны. Эта формула ложна, если
область определения предиката F (x) содержит больше, чем один
предмет, но истинна для одноэлементных множеств. Однако логически ниоткуда не следует, что существуют многоэлементные множества.
Логическая система называется полной в широком смысле, если
любая тождественно истинная формула в ней доказуема. Исчисление предикатов полно в широком смысле.
Ни одна из аксиом исчисления предикатов не выводима из других. Это означает, что система аксиом исчисления предикатов независима.
44
Заключение
Логика, опыт и интуиция
Нужно теперь признать, что, хотя логика необходима для познания реального мира, она все же недостаточна. Логика связывает
факты, которые дает опыт, эксперимент. Но для построения теории
необходим еще и набор аксиом. Аксиомы не могут быть получены
только логикой – они не могут (по определению) быть доказаны. Но
они не могут быть взяты непосредственно из опыта.
Все выводимые формулы исчисления предикатов представляют собой тождественно истинные высказывания. Обратно, каждая
тождественно истинная формула выводима в исчислении предикатов. Отсюда следует, что в исчислении предикатов нельзя вывести
никакое содержательное по существу высказывание, в частности,
математическое. Но если к аксиомам исчисления предикатов присоединить какие-либо невыводимые формулы в качестве новых аксиом, то получится новое исчисление, в котором выводимы, помимо тождественно истинных формул, и другие формулы. Так строятся различные математические теории, например, арифметика,
теория чисел, геометрия, теория множеств.
Возникает естественный вопрос: как выбрать эти новые аксиомы, если они невыводимы?
Великий голландский философ Б.Спиноза учил, что существуют три пути (способа) познания: а) интуитивный, б) логический и
в) чувственный. При этом первый – высший, а третий – низший.
Но интуиция по Спинозе – это не мгновенное озарение (таково обыденное понимание этого слова), а целостное усмотрение истины,
вытекающее из всех знаний познающего субъекта, несводимое к
логике. Нельзя логически доказать, что А.С. Пушкин – великий
поэт, тем не менее мы это хорошо знаем.
А. Эйнштейн (который хорошо знал и понимал учение Б. Спинозы) говорил, что аксиомы – свободное творение человеческого
сознания и вводятся интуитивно, без опоры на логику. Из аксиом
логически выводятся теоремы, из них – другие теоремы, и если
теория имеет отношение к реальному миру, из этих теорем делаются выводы о свойствах реального мира. Если оказывается, что
на самом деле эти свойства – другие, то теория опровергается. Но
если все выводы теории согласуются с опытом, это еще не означает, вообще говоря, истинности теории. Мы знаем, что импликация
A→B при истинном B истинна независимо от A. Известно, что Кар45
но свою правильную формулу для предельного значения коэффициента полезного действия теплового действия получил из совершенно неправильных теоретических представлений. Система Коперника вначале хуже соответствовала наблюдательным данным,
чем система Птоломея. Вывод о приемлемости новой теории есть
тоже интуитивное умозаключение, и, следовательно, может быть в
дальнейшем опровергнут.
Варианты контрольных работ
Каждый вариант содержит 9 заданий.
1. Доказать равенство множеств.
2. Построить таблицу истинности для логической функции
f(x, y, z).
3. Найти выражение для функции, двойственной функции
f(x, y, z) и определить номер двойственной функции.
4. Упростить выражение для функции f(x, y, z).
5. Найти СДНФ и СКНФ для функции с заданным номером и
упростить по методу Квайна СДНФ.
6. Найти полином Жегалкина для функции с заданным номером.
7. Доказать секвенцию табличным методом.
8. Доказать тавтологию методом резолюций.
9. Проанализировать вывод секвенции.
Вариант 1.
1.  (C∆( A \ C)) \ B = ( A È C) \ B.
2.  f (x, y, z) = (x ¯ y) Ù y ~ z.
3.  f (x, y, z) = ((x. ~ y) ~ (y ¯ z)) Ú (y | z).
4.  f (x, y, z) = (x | y) ¯ (y Ú z) Å (y Ù z).
5.  N (f ) = 120 6.  N (f ) = 198.
7.  (a Ù b) ® b, b Ú (a Ù c) |= (a ® b) Ú (a Ù c).
8.  |= ( A ® B) Ù A ® B.
9. 1)  A Ú B, A |= A Ú B; 4)  A Ú B, B |= A Ú B; 7)  A, B |= A Ù B;
2)  A Ú B, A |= A Ú B; 5)  A Ú B, B |= A Ú B; 8)  A Ú B |= A Ù B;
46
3)  A Ú B |= A; 6)  A Ú B |= B; 9)  |= A Ú B ® A Ù B.
Вариант 2.
1.  B Ç (C∆( A Ç C) = B Ç ( A È C).
2.  f (x, y, z) = (x Å y) Ú (y Ù z).
3.  f (x, y, z) = (x ~ y) ¯ (y Ú z) Å (y Ù z).
4.  f (x, y, z) = (x ¯ y) | (y Ù z) Ù (y Ú z).
5.  N (f ) = 225 6.  N (f ) = 105.
7.  a ® b, b ® c |= (a Ú b) ® (b Ù c).
8.  |= ( A ® B) Ù ( A Ù C ® B Ù C).
9. 1)  A, B |= A Ù B; 4)  A, C |= A Ù C; 7)  A, B Ú C |= ( A Ù B) Ú ( A Ù C).
2)  A Ù B |= ( A Ù B) Ú ( A Ù C); 5)  A Ù C |= ( A Ù B) Ú ( A Ù C);
3)  A, B |= ( A Ù B) Ú ( A Ù C); 6)  A, C |= ( A Ù B) Ú ( A Ù C);
Вариант 3.
1.  ( A∆(B \ A)) \ C = ( A È B) \ C.
2.  f (x, y, z) = (x Å y) Ù y | z.
3.  f (x, y, z) = ((x ® y) Ù (z Å y).
4.  f (x, y, z) = (x ~ y) ~ (y Ú z) Ú (y | z).
5.  N (f ) = 156 6.  N (f ) = 54.
7.  (a Ù b) ® b, b Ú (a Ù c) |= (a ® b) Ú (a Ù c).
8.  |= ( A ® B) Ú (C ® D) ® ( A Ù C ® B Ú D).
9. 1)  A Ú B, A |= A Ú B; 4)  A Ú B, B |= A Ú B; 7)  A, B |= A Ù B;
2)  A Ú B, A |= A Ú B; 5)  A Ú B, B |= A Ú B; 8)  A Ú B |= A Ù B;
3)  A Ú B, A |= A; 6)  A Ú B |= B; 9)  |= A Ú B ® A Ù B.
Вариант 4.
1.  ( A Ç C)∆((C \ B) \ A) = ( A È B) Ç C.
2.  f (x, y, z) = (x | y) Ú y ® z.
47
3.  f (x, y, z) = (x Ù y) ® (y ¯ z) ~ (z Ù y).
4.  f (x, y, z) = (x ¯ y) Å (y ® z) Ú (y Ù z).
5.  N (f ) = 99 6. N (f ) = 154.
7.  a, a Ù c |= (a Ú b Ú c) ® (b Ú c) ® (a Ù b)
8.  |= ( A ® C) Ù (B ® C) ® ( A Ú B ® C).
9. 1)  A, A Ú C |= A Ú (B Ù C); 4)  B, C |= A Ú (B Ù C); 7)  A Ú B, A Ú C |= A Ú (B Ù C).
Ú B, A Ú C |= A Ú (B Ù C).
2)  B, C |= B Ù C; 5)  B, A |= A Ú (B Ù C);
3)  B Ù C |= A Ú (B Ù C); 6)  B, A Ú C |= A Ú (B Ù C);
Вариант 5.
1.  A Ç (B∆ B È C) = ( A Ç (B È Ñ).
2.  f (x, y, z) = (x ¯ y) Ù y ® z.
3.  f (x, y, z) = (x ~ y) ® (y ¯ z) ~ (z Ú y).
4.  f (x, y, z) = (x | y) Å (y ¯ z) ~ (y \ z).
5.  N (f ) = 225 6.  N (f ) = 105.
7.  a ® (b ® a), (a ® b) Ù c |= (a Ú b) ® ((a ® c) ® a).
8.  |= ( A Ù B ® C) ® ( A ® (B ® Ñ)).
9. 1)  A |= A; 4)  A, A |= A; 7)  |= A ~ A.
2)  |= A ® A; 5)  A |= A;
3)  A, A |= A; 6)  |= A ® A;
Вариант 6.
1.  ( A Ç C)∆((B Ç C) \ A) = C Ç (B È A).
2.  f (x, y, z) = (x Å y) Ù y ¯ z.
3.  f (x, y, z) = ((x ¯ y) | (y Ù z) ® (z ® y).
4.  f (x, y, z) = (x | y) ¯ (y Ú z) Ú (y Ù z).
5.  N (f ) = 89 6.  N (f ) = 150.
48
7.  a Ú b, a Ù b |= (a Ú b Ú c) ® (c Ú (a Ù b).
8.  |= ( A ® B) ® (( A ® (B ® Ñ)) ® ( A ® C)).
9. 1)  A |= A Ú (B Ú C); 4)  B |= A Ú (B Ú C); 7)  A Ú B |= A Ú (B Ú C);
2)  B |= B Ú C; 5)  C |= B Ú C; 8)  ( A Ú B) Ú C |= A Ú (B Ú C).
3)  B Ú C |= A Ú (B Ú C); 6)  C |= A Ú (B Ú C);
Вариант 7.
1.  B Ç ( A∆( A \ C)) = B \ ( A Ç C).
2.  f (x, y, z) = (x ~ y) Ú y | z.
3.  f (x, y, z) = (x | y) ¯ (y Ù z) ® (z Ú y).
4.  f (x, y, z) = (x Å y) ® (y | z) Ù (y ¯ z)
5.  N (f ) = 86 6.  N (f ) = 149.
7.  a ® b, b ® c |= (a ® b) ® (b Ù c) Ú (b ® c) Ú (b Ú a).
8.  |= ( A Ù B ® Ñ) ® ( A Ù C ® B).
9. 1)  |= A Ú A; – теорема 5)  B |= A Ú B; 9)  A |= A Ù B ® A Ú B;
2)  A Ù B, A, B |= A Ù B; 6)  A, A Ù B |= A Ú B; 10)  A Ú A |= A Ù B ® A Ú B;
Ú A |= A Ù B ® A Ú B;
3)  A Ù B, A, B |= A Ù B; 7)  A |= A Ù B ® A Ú B; 11)  |= A Ù B ® A Ú B.
4)  A, A Ù B |= B; 8)  A, A Ù B |= A Ú B;
Вариант 8.
1.  B Ç (C∆( A \ C)) = B Ç (C È A).
2.  f (x, y, z) = (x ~ y) Ù y ® z.
3.  f (x, y, z) = ((x ~ y) Ú (y | z)) Ù (z ® y).
4.  f (x, y, z) = (x ~ y) Å (y ¯ z) Ú (y | z).
5.  N (f ) = 210 6.  N (f ) = 101.
7.  a ® b, c ® a |= b ® (a Ú c).
8.  |= ( A Ù C ® B) ® ( A Ù B ® Ñ).
9. 1)  A ® B, B ® C, A |= B; 5)  ( A ® B) Ù ( B ® C) |= A ® B;
49
2)  A ® B, B ® C, A |= B ® C; 6)  ( A ® B) Ù ( B ® C) |= B ® C;
3)  A ® B, B ® C, A |= C; 7)  ( A ® B) Ù ( B ® C) |= A ® C;
4)  A ® B, B ® C |= A ® C; 8)  |= ( A ® B) Ù ( B ® C) ® ( A ® B).
Вариант 9.
1.  B Ç ( A∆( A \ C)) = B \ ( A Ç C).
2.  f (x, y, z) = (x | y) Ú y Å z.
3.  f (x, y, z) = ((x | y) Ù (y Ú z)) Ù (z Å y).
4.  f (x, y, z) = (y Ù z) \ (x Å y) ¯ (y ~ z).
5.  N (f ) = 54 6.  N (f ) = 120.
7.  ((a ® b) Ù (a ® b) ® a, (a Ú b) ® (b Ù c) |= (a ® b) Ú b ® c.
8.  |= ( A ® (B ® C)) ® ( A Ù B ® Ñ).
9. 1)  A Ú A, A |= A Ú A; 5)  A Ú A, A |= A Ú A;
2)  A Ú A, A |= A Ú A; 6)  A Ú A |= A;
3)  A Ú A |= A; 7)  |= A Ú A;
4)  A Ú A, A |= A Ú A; 8)  |= A Ú A.
Вариант 10.
1.  ( A∆( A Ç C)) \ B = ( A È C) \ B.
2.  f (x, y, z) = (x ~ y) Ù y | z.
3.  f (x, y, z) = ((x ¯ y) | (y Ú z)) Ù z Ù y.
4.  f (x, y, z) = (y Ù z) Å (x ® y) ~ (y Ù z).
5.  N (f ) = 147 6.  N (f ) = 210.
7.  c ® (a Ú b), c ® (a Ù b) |= a Ú b Ú (a Ù b).
8.  |= ( A ® B) Ù (C ® B) ® ( A Ú C ® B).
9. 1)  A, A Ù B |= A; 5)  B, A Ù B |= B;
2)  A, A Ù B |= A; 6)  B |= A Ù B;
3)  A |= A Ù B; 7)  A Ú B |= A Ù B;
4)  B, A Ù B |= B; 8)  |= A Ú B ® A Ù B.
50
Библиографический список
Основной
1. Игошин В. И. Математическая логика и теория алгоритмов.
М.: ACADEMIA, 2004. 447 с.
2. Брудно А. Л. Теория функций действительного переменного.
М.: Наука, 1971, 120 с.
3. Лексаченко В. А. Логика, множества, вероятность: учеб. пособие ГУАП. СПб.,
4. Шапорев С. Д. Математическая логика: Курс лекций и практических занятий. СПб.: БХВ-Петербург, 2007. 410 с.
Дополнительный
1. Пенроуз Р. Новый ум короля. О компьютерах, мышлении и
законах физики. В серии “Синергетика: от прошлого к будущему”.
М.: УРСС, 2005. 398 с.
2. Смаллиан Р. М. Как же называется эта книга? М.: Издательский дом Мещерякова, 2007. 272 с.
3. Ивин А. А. Искусство правильно мыслить. М.: 1990. 130 с.
51
Содержание
Введение.................................................................................... Предмет математической логики и ее использование в инженерной
практике выпускников СПбГУАП................................................. 1. Элементы теории множеств....................................................... 2. Алгебра (логика) высказываний................................................ Логические связки и логические функции................................. Булевы алгебры..................................................................... Двойственность...................................................................... Нормальные формы................................................................ Полиномы Жегалкина............................................................ Полные системы функций и базисы.......................................... Секвенции............................................................................. Правила преобразования списков допущений............................. Метод резолюций................................................................... 3. Исчисления высказываний....................................................... Полнота, разрешимость и непротиворечивость исчисления
высказываний. Независимость системы аксиом исчисления
высказываний........................................................................ 4. Логика предикатов.................................................................. Классификация предикатов..................................................... Множество истинности предиката............................................ Равносильность и следование предикатов.................................. Логические операции над предикатами..................................... Кванторные операции над предикатами..................................... Формулы логики предикатов................................................... Тавтологии логики предикатов................................................. Равносильные преобразования формул логики предикатов.......... Логическое следование логики предикатов................................ Проблема разрешимости для общезначимости и выполнимости
формул логики предикатов...................................................... Применение логики предикатов к логико-математической
практике .............................................................................. 5. Формализованное исчисление предикатов................................... Свойства формализованного исчисления предикатов................... Заключение ............................................................................... Логика, опыт и интуиция............................................................. Варианты контрольных работ....................................................... Библиографический список ......................................................... 52
3
3
6
11
11
17
18
19
22
22
24
26
26
28
32
33
33
34
34
35
36
37
38
39
40
40
41
42
43
45
45
46
51
Документ
Категория
Без категории
Просмотров
5
Размер файла
925 Кб
Теги
pdf
1/--страниц
Пожаловаться на содержимое документа