Исчисление высказываний

.

В этой работе мы рассмотрим исчисление высказываний как инструмент для определения истинности утверждений. Затем мы рассмотрим расширение исчисление высказываний до исчисления предикатов. Это расширение позволит нам строить рассуждения над целым рядом конструкций таких, как циклы. Мы также рассмотрим идеи эквивалентности, общезначимости или тавтологии для доказательства.

Начало исчисления высказываний было положено работами Джоржа Буля. Подметив сходство в свойствах логических операций ОR и AND со свойствами арифметических операций умножения и сложения, он создал исчисление для вычисления истиности утверждений подобно тому, как правила арифметических операций позволяют вычислять значения арифметических выражений. В созданном им исчислении Буль обозначил символами как отдельные утверждения, так и целые конструкции из утверждений.

Любое высказывание в этом исчислении может иметь одно из двух значений: истина (true) или ложь (false). Ниже приведены примеры утверждений:

Сумма двух сторон треугольника больше или равна третьей стороне этого треугольника.

2х2=4.

“Каждый охотник желает знать, где сидят фазаны” (первые буквы слов в этой фразе определяют порядок цветов в спектре слева направо).

Для того, чтобы строго определить способ записи подобных утверждений Буль предложил понятие высказывания.

В таблице 5.1. перечислены названия и обозначения всех логических операций, используемых в высказываниях.

Таблица 5.1.

Определение 5.1. Высказывание - выражение, построенное по следующим правилам:

true и false - высказывания;

Любая переменная типа {true, false} - высказывание (такой тип называют boolean);

Если р - высказывание, то (Øр) - высказывание;

Если p и q - высказывание, то (pÚq), (pÙq), (pÞq), (pÛq) - высказывания.

Обратите внимание на способ определения высказывания, а именно, на пункты 3 и 4 определения 5.1. Эти пункты определяют высказывание через уже существующие высказывания. С таким приемом, когда определяемое понятие определяют, используя само это понятие, мы встретимся еще не раз. Этот прием называется рекурсией.

Может возникнуть опасение “порочного круга” в таком определении. Однако, в силу пунктов 1 и 2, где понятие высказывания определяется через понятия логического значения и переменной логического типа, “зацикливания” не происходит.

Примеры 5.1.

Пусть p,q и r - переменные типа boolean.

Тогда приведенные ниже выражения - это высказывания:

То, что выражения 1,2,3,4,5 - высказывания, следует из пунктов 1,2,3 определения 5.1. Для выражений 9,10 - это следует из пунктов 2 и 4. Для выражений 9, 10 - это следует из пункта 2 и последовательного применения пункта 4 определения.

Например:

(pÞ(qÙ(rÛp))

rÞp - высказывание по пункту 4. Обозначим его s₁.

(qÙs₁) - высказывание опять по пункту 4. Обозначим его s₂ .

(pÞs₂) - высказывание по тому же самому пункту 4.

Пример 5.2. Ниже приведенные выражения не являются высказываниями.

(pq)

(pq) Øр

Выражение 1 не является таковым, потому что имена двух переменных стоят рядом и не разделены знаком логической операции.

Выражение 2 не является высказыванием, во-первых, потому, что (pq) - не высказывание; во-вторых, потому, что выражение sØр , - где s и p - высказывания, не удовлетворяет ни одному из 4-х пунктов определения 5.1.

Особое внимание следует обратить на скобки. Их можно опускать если это не вносит неоднозначности. Например, вместо (Øр) можно писать Øр, а вместо (pÚq) - pÚq. Однако, невнимательное обращение со скобками может привести к неоднозначности. Например, выражение pÚqÙr можно трактовать либо как ((pÚ)qÙr), либо (pÚ(qÙr)). Для того, чтобы избежать такой неоднозначности, пяти логическим операциям приписывается приоритет, который учитывается при вычислении значения выражения. Операция отрицания Ø - имеет наивысший приоритет, за ней следует Ù, потом следует Ú, Þ и Û в том порядке как они указаны. Поэтому, выражение pÚqÙr должно трактоваться только как (pÚ(qÙr)).

5.1.1. Утверждения на русском языке в форме высказываний.

Не любое предложение на русском языке может быть выражено в виде высказывания. Например, приглашения типа “Войдите”, команды типа “Стой”, “Сидеть”, вопросы типа “Ты был сегодня на лекции Смелянского?” нельзя представить в виде высказываний. Тем не менее, существует значительное множество предложений, называемых утверждениями, которые можно представить в виде либо высказываний, либо предикатов (о последних мы поговорим позднее).

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

Например, если обозначить утверждение “Вася доволен” буквой р, то высказыванием Øр можно представить следующее утверждение:

“Вася не доволен”.

“Это не тот случай, когда Вася доволен”.

“Вася будет не доволен”.

“Вася был не доволен”.

Обратите внимание, исчисление высказываний не охватывает временной аспект фразы. Аналогично, нижеприведенные утверждения можно записать в виде высказывания pÙq, придав надлежащие значения переменным p и q :

10 £x£100

Петя племянник Васи.

Вася дядя Петра.

Хотя декабристы обличали рабовладельчество, многие из них имели крепостных.

Первое из этих предложений состоит из двух фраз: ”Число х больше либо равно 10” и “Число х меньше либо равно 100”. Однако, эти фразы “спрятаны” с помощью математических обозначений.

Вторая и третья фразы содержат в неявном виде два утверждения. Первое: У Васи есть или брат, или сестра. Вторая: У этого брата или у этой сестры есть сын Петя.

Слово “хотя” в четвертой фразе играет роль союза “и” и выполняет роль противопоставления.

При использовании логической операции Ú в высказываниях могут возникнуть трудности, связанные с неоднозначностью союза “или” в русском языке. Когда мать говорит сыну: “Я куплю тебе конфету или жвачку”, как правило, она имеет ввиду только одно из двух. Когда преподаватель говорит, что он допустит до экзамена только тех студентов кто сдаст реферат или зачет, то, конечно, он не прогонит студента, который сдаст и зачет и реферат.

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

В высказывании pÞq , р называется причиной, q - следствием, а само высказывание - импликацией или следованием. Примером импликации может служить фраза

“Если ты будешь читать по одной страничке в день, то ты научишься читать”.

Если обозначить слова “ты будешь читать хотя бы по одной страничке в день” как p, а “ты научишься читать”, как q, то эту фразу можно записать как

pÞq

Это же высказывание будет соответствовать и фразе

“Ты научишься читать, если ты будешь читать хотя бы по одной страничке в день”.

Однако, в использовании “если” в русском языке есть тонкости. Например, рассмотрим фразы:

“Я куплю билет, если в этом кинотеатре идет “Анаконда”.

“Я куплю билет, только если в этом кинотеатре идет “Анаконда”.

Если обозначить буквой p слова “Я куплю билет”, а буквой s - “в этом кинотеатре идет “Анаконда”, то первой фразе будет соответствовать выражение

sÞp,

поскольку не ясно, что будет делать говорящий, если в кинотеатре идет “Терминатор”.

Второй фразе соответствует выражение

pÞs

т.к. она утверждает, что я могу купить билет только при одном условии - в кинотеатре идет “Анаконда”.

Другим важным свойством импликации является то, что между p и q в действительности не предполагается никакой причинно-следственной связи.

Например, фразе

“Если 1+1=2 , то Солнце - центр Солнечной системы”

соответствует выражение

pÞq

Однако, ясно, что между двумя фактами “1+1=2” и “Солнце - центр Солнечной системы” нет связи. Таким образом, причинно-следственная связь - еще один пример, выразимый в естественном языке и не охватываемый в исчислении высказываний.

Выражение pÛq используется, когда одно высказывание имплицирует другое и наоборот. Например, если АВС - треугольник со сторонами а, b, c, то a²+b²=c² тогда и только тогда, когда АВС - прямоугольный.

Если обозначить p - a²+b²=c², q - АВС - прямоугольный, то вся фраза может быть записана как

pÛq,

т.е. pÞq и qÞp истинны одновременно.

Вычисление истиности высказываний.

В главе 1 мы уже сталкивались с понятием состояния набора переменных.

Определение 5.2. Пусть p_1…….p_n - набор всех переменных типа boolean, встречающихся в некотором высказывании. Тогда множество конкретных значений этих пременных называется их состоянием.

Рассмотрим выражение pÚq . Набор его переменных { p, q }. Поскольку каждая из переменных может принимать только одно из двух значений true, или false , то все множество возможных состояний для этого набора состоит из 4-х пар:

(T,T), (T,F), (F,T), (F,F).

(Везде далее мы будем использовать в этой главе сокращения Т вместо true, F вместо false). Теперь для каждого состояния достаточно указать значение этого выражения и функция pÚq будет определена. Это делается с помощью, так называемых, таблиц истиности. Ниже показана таблица истиности для pÚq (Таблица 5.2.).

Таблица 5.2.

Таблица истиности для pÚq

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

В таблице 5.3. приведены таблицы истиности для всех операций исчисления высказываний.

Таблица 5.3.

Таблица истиности для а) - отрицания, б) - коньюнкции,

в) - импликации, г) - эквивалентности.

Следует прокоментировать таблицу истиности для импликации в состоянии p=F , q=T. Вспомним наш пример,

если

Это высказывание не содержит утверждения, что если “Анаконда” не идет в этом кинотеатре, то я не куплю билет. Таким образом, даже если p=F, т.е. “Анаконда” не идет в этом кинотеатре, я могу купить билет.

Таблица истиности может быть построена для высказывания любой сложности. Например, рассмотрим выражение

(pÚq) ÞØp

Построим сначала таблицу истиности для (pÚq), обозначив это выражение через s, затем построим таблицу истиности для Øp, обозначив это выражение через r, и, наконец, построим таблицу истиности для sÞr. В таблице 5.4. показан этот процесс.

Таблица 5.4.

Таблица истиности для выражения (pÚq) ÞØp.

Нетрудно видеть, что число строк в таблице истиности растет как степень 2 от числа переменных в выражении. Один из способов сокращать число строк - опускать те состояния, которые не влияют на результат. Например, в выражении pÚq , если p=T, то не важно какое значение у q, - значение всего выражения будет T. В таблице 5.5. показано применение этого приема.

Таблица 5.5.

Вычисление значения выражения (pÙq) Þ(rÚ(pÞS)),

не используя незначащие состояния.

Нетрудно видеть, вычисление “в лоб” таблицы истиности для этого выражения потребовало бы таблицы из 2⁴=16 строк. Используя прием незначащих состояний, удается сократить число рассматриваемых состояний до 5.

Тавтология.

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

Определение 5.2. Тавтология - высказывание, значение которого - Т на любом состоянии переменных этого выражения. Противоречие - высказывание, значение которого - F, на любом состоянии переменных этого выражения.

Для доказательства утверждения, что некоторое выражение - тавтология, у нас пока есть только таблицы истиности. Докажем, что pÚØp - тавтология. Ниже показана таблица истиности для pÚØp (Таблица 5.6.)

Таблица 5.6.

Таблица истиности для pÚØp

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

Рассуждения с помощью исчисления высказываний.

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

Эквивалентность.

Рассмотрим высказывание

(pÚq)Ù(pÚØq).

Его таблица истиности представлена в таблице 5.7.

Таблица 5.7.

Таблица истиности для (pÚq)Ù(pÚØq)

нетрудно заметить, что последний столбец в этой таблице совпадает со столбцом для p. Поэтому, можно сказать, что с этой точки зрения выражение (pÚq)Ù(pÚØq) эквивалентно p, и везде, где мы встретим это выражение, мы можем его заменить на p.

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

Определение 5.3. Два высказывания называются эквивалентными, если они на одних и тех же состояниях своих переменных принимают одни и те же значения.

Другими словами, если эти высказывания имеют одинаковые таблицы истиности, то они эквивалентны. Таким образом, один способ установить эквивалентность двух высказываний - вычислить их таблицы истиности и сравнить. Мы, однако, воспользуемся другим способом.

Теорема 5.1. Два высказывания p и q - эквивалентны (обозначается pºq) тогда и только тогда, когда pÛq - общезначимо.

Доказательство:

Пусть pºq. Значит таблицы истиности для p и q совпадают. Следовательно, на тех состояниях, где p=Т, q=Т также, а где p=F, то и q=F. Отсюда следует, что pÛq всегда Т (поскольку мы имеем либо ТÛТ, либо FÛF), т.е. pÛq - общезначимо или тавтология.

Пусть pÛq -общезначимо. Тогда если p=Т, то q должно быть Т, а если p=F, то и q должно быть F.

Таким образом, на одних и тех же состояниях эти выражения принимают одинаковые значения. Следовательно, таблицы истиности для p и q совпадают. Последнее означает по определению , что pºq.

(Доказательство закончено.)

Эта теорема показывает, что установить эквивалентность можно, доказав общезначимость специального высказывания.

Свойства эквивалентности.

Основные, часто используемые свойства эквивалентности приведены в таблице 5.8.

Таблица 5.8.

Свойства эквивалентности

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

Мы будем использовать эти свойства в разных целях. Коммутативность, например, позволяет нам менять местами элементы высказывания , в целях его упрощения. Ассоциативность позволяет снимать скобки. Например, т.к. pÙ(qÙr) º (pÙq)Ùr , то мы можем просто писать pÙqÙr. Дистрибутивность позволяет собирать подобные члены, подобно тому как мы это делаем в арифметическом выражении. Закон импликации позволяет уходить от операции Þ , используя только операции Ø, Ú, Ù. Для того, чтобы убедиться в правильности этих свойств, достаточно построить их таблицы истиности. Например, в таблице 5.9. показана корректность закона импликации. Остальные свойства читателю предлагается доказать в качестве упражнения.

Таблица 5.9.

Доказательство корректности закона импликации

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

Рассмотрим несколько примеров.

(pÚØq)ÙrÙ(ØpÚq)

(pÚØq)Ù(ØpÚq)Ùr I.1

(ØqÚp)Ù(ØpÚq)Ùr I.2

(qÞp)Ù(pÞq)Ùr V.1

(pÛq)Ùr VI.1

Таким образом

(pÚØq)ÙrÙ(ØpÚq) º (pÛq)Ùr

Другой пример, упростить

pÚ(ØqÞp)ÚØq

pÚ(Ø(ØqÚp)ÚØq V.1

pÚ(qÚp)ÚØq VII.1

pÚ(qÚp)ÚØq I.2

(pÚp)Ú(qÚØq) II.2

pÚ(qÚØq) XI.1

pÚT IX.1

TXI.2

Тем самым, мы доказали, что

pÚ(ØqÞp)ÚØqº Т - тавтология.

Упростить

((pÞq)Þp)Þp

(Ø(pÞq)Úp)Þp V.1

(Ø(ØpÚq)Úp)Þp V.1

((Ø(Øp)ÙØq)Úp)Þp IV.1

((pÙØq)Úp)Þp VII.1

(pÚ(pÙØq))Þp I.2

pÞp XI.4

ØpÚp V.1

pÚØp I.2

TIX.1

Таким образом

((pÞq)Þp)Þp - тавтология.

5.2.3. Доказательство: правила вывода.

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

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

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

Таблица 5.10.

Правила вывода

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

Докажем высказывание

[p]

p

Правило I

Первым шагом мы делаем предположение, что р - общезначима. Тогда второй шаг непосредственно следует из первого. Раз мы предположили общезначимость р на первом шаге, то мы используем этот факт на втором. На третьем шаге мы используем правила вывода I, которое устанавливает общезначимость высказывания .

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

Присмотревшись внимательно к правилам вывода, можно увидеть, что они хорошо согласуются с нашей интуицией. Например, возьмём правило VIII. Если на предыдущих шагах была доказана общезначимость высказываний p и q, то очевидно что высказывание - тоже общезначимо.

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

5.2.4. Некоторые приёмы доказательства.

Дедуктивный вывод.

Доказать

[p] - Предположение

[q] - Предположение

р - 1.

- I, 2, 3

- I, 1, 4

Мы предположили общезначимость утверждений p и q и воспользовавшись правилом I. введение .

Использование правила Моdus Рonens. Это правило хорошо работает когда надо доказать высказывания типа “Если в этом кинотеатре дают “Анаконду”, то я куплю билеты.” Если кто-то сделал это утверждение и вы увидели, что в кинотеатре идет “Анаконда”, то вы можете заключить, что этот человек купил билеты.

Доказать

- Предположение

- IX. Удаление , 1

r - IX. Удаление , 1

р - III. Моdus Рonens, 2, 3

pq - IX. Удаление , 1

q - III. Моdus Рonens. 4, 5

- I. Введение , 1, 6

Использование МоdusTollens.

Доказать

- Предположение

pq - IX. Удаление , 1

Øq - IX. Удаление , 1

Øp - III.2. Modus Tollens, 2, 3

- I. Введение, 1, 4

Использование Введения Ø и Удаления Ø .

Докажем

- Предположение

pq - IX. Удаление , 1

Øq - IX. Удаление , 1

[p] - Предположение

q - III. Моdus Ðonens, 4, 2

Øq - 3

F - VI. Удаление , 5, 6

Øp - V. Введение Ø 4, 7

- I. Введение Ø 1, 8

Доказательство от противного.

На использовании правила V. Введение Ø основан часто используемый прием доказательства - доказательство от противного. Мы его уже использовали несколько раз. Его идея состоит в следующем.

Пусть мы хотим доказать общезначимость высказывания Q :

“Треугольник со сторонами 2, 3, 4 - не прямоугольный.”

Предположим, что ØQ - общезначимо, т.е треугольник со сторонами 2, 3, 4 - прямоугольный. Тогда, используя теорему Пифагора, мы можем утверждать, что 4+9=16 , но 4+9 ¹ 16. Отсюда, используя правило VI.1 Удаление Ø , получаем F. Имея F и предположение об общезначимости ØQ, с помощью правила V, получаем общезначимость Ø(ØQ). Откуда, с использованием правила VII из таблицы 5.8., получаем общезначимость Q.

Доказать

- Предположение

- Закон импликации V.1, 1

- Закон Де Моргана IV.1

Øq - IX.2. Удаление , 3

- IX.1. Удаление , 3

- IX.1. Удаление , 5

p - IX.2. Удаление , 6

q - III.1. Моdus Рonens, 6, 7

F - V.1 Удаление Ø , 4, 8

- V. Введение Ø , 1, 9

Пример.

Во вторник, когда случилось ограбление, либо Петров был в операционном зале банка, либо Сидорова в бухгалтерии банка. Петрова никогда не видели в операционном зале без Иванова. Иванов покидал банк во вторник только когда он с Сидоровой ездил на встречу с клиентами. Если в ограблении участвовал Ерошкин, Иванова не было бы в банке. Ограбление произошло во вторник. Мог ли Ерошкин быть грабителем?

Обозначим:

p= Петров был в операционном зале;

q= Cидорова была в бухгалтерии;

s= Иванов был в операционном зале;

h= Ерошкин участвовал в ограблении;

u= Ограбление случилось во вторник.

Тогда исходные утверждения можно записать так:

uÞ(pÚq)

pÞs

ØsÞØq

hÞØs

u

Из 1, 5 п. Modus ponens получаем pÚq

Предположим [q]

Из 3, 7 п. ModusTollens получаем s

Из 7, 8 и “введение Þ“получаем qÞs

Из 4, 10 п. Modus Tollens Øh

Итак, Ерошкин не мог участвовать в ограблении.