Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Тавтологии алгебры высказываний

Тавтологии алгебры высказываний


О значении тавтологий в логике


Тавтологии представляют собой схемы построения истинных высказываний, независимо от содержания и истинности составляющих высказываний. Так, если для установления того, истинны или нет высказывания "Саратов основан в 1590 году", "Солнце вращается вокруг Земли", необходимо обладать специальными знаниями или заглянуть в специальную литературу, то для выяснения значения истинности высказываний "Треугольник [math]ABC[/math] прямоугольный, или треугольник [math]ABC[/math] не прямоугольный", "Неверно, что информация о наследственных признаках хранится в генах, и эта информация в генах не хранится" уже не нужно обладать знаниями ни в математике, ни в генетике. Вывод об истинности последних высказываний делаем, исходя не из их содержания, а из их формы, структуры. Структура первого из последних высказываний выражается формулой [math]X\lor\lnot X[/math], а второго — формулой [math]\lnot(X\land\lnot X)[/math]. Легко убедиться в том, что обе эти формулы суть тавтологии. Данные формулы дают две схемы построения всегда истинных высказываний. И такова каждая формула, являющаяся тавтологией. Но главное значение тавтологий не в этом.


Основное значение тавтологий состоит в том, что некоторые из них предоставляют правильные способы построения умозаключений, т.е. такие способы, которые от истинных посылок всегда приводят к истинным выводам. А ведь именно такие рассуждения углубляют наши знания и обогащают их истинными сведениями. В частности, любая тавтология алгебры высказываний вида [math]F\to G[/math] соответствует некоторой общей схеме логического умозаключения. Поясним сказанное на примере следующей тавтологии указанного вида (внешние скобки опущены):


[math]\bigl((\lnot X\to Y)\land(\lnot X\to\lnot Y)\bigr)\to X.[/math]

(Проверьте, действительно ли данная формула является тавтологией.) Попытаемся выяснить, какой схеме логического умозаключения она соответствует. Схема логического умозаключения, описываемая данной тавтологией, часто используется в математических доказательствах. Она состоит в следующем. Допустим, что требуется доказать истинность некоторого утверждения [math]A[/math]. Предполагается, что истинно его отрицание [math]\lnot A[/math]. Затем доказывается, что имеется некоторое такое утверждение В, для которого истинными являются оба утверждения [math]\lnot A\to B[/math] и [math]\lnot A\to\lnot B[/math]. Доказательства истинности этих импликаций зависят от содержания высказываний [math]A[/math] и [math]B[/math] и устанавливаются на основании методов и законов той математической теории, к которой они относятся. Считаем, что истинность утверждений [math]\lnot A\to B[/math] и [math]\lnot A\to\lnot B[/math] установлена. Одновременный вывод двух утверждений [math]B[/math] и [math]\lnot B[/math] — противоречие, абсурд. Тогда утверждаем, что истинно высказывание [math]A[/math]. Такой метод доказательства называется методом приведения к абсурду.


Термин "тавтология" имеет греческое происхождение, составлен из двух слов ταντοζ (то же самое) и λογοζ (слово) и означает повторение одного и того же определения, суждения иными, близкими по смыслу словами. В тавтологиях, относящихся к математической логике, заключительной логической связкой является эквивалентность [math]\leftrightarrow[/math]. Например, тавтология


[math]\bigl(P\land(Q\lor R)\bigr)\leftrightarrow \bigl((P\land Q)\lor(P\land R)\bigr)[/math]

выражает одинаковость форм (формул) в ее левой и правой частях, т.е. имеется в виду семантическая одинаковость, выражаемая разными словами — формами (формулами). Совершенно аналогично в этом смысле арифметическое тождество [math]x(y+z)=xy+xz[/math], которое отражает ту же внутреннюю сущность посредством разных слов. И каждое из этих двух выражений является объективным законом, действующим каждый в своей сфере: первый — в сфере мыслительных процессов, второй — в сфере чисел. Каждый из этих законов несет объективную информацию об определенной части окружающего нас мира. Труднее в этом смысле истолковать тавтологии вида [math]P\lor\lnot P,[/math] [math]P\to P,[/math] [math]P\to(Q\to P)[/math] и т.п., но на них данный термин просто распространяется.




Основные тавтологии в математической логике


Приведем некоторые основные тавтологии, выражающие свойства логических операций, а также тавтологии, на которых основаны некоторые схемы математических доказательств.


Теорема 3.1. Следующие формулы алгебры высказываний являются тавтологиями:


а) закон исключенного третьего [math]P\lor\lnot P[/math];
б) закон отрицания противоречия [math]\lnot(P\land\lnot P)[/math];
в) закон двойного отрицания [math]\lnot\lnot P\leftrightarrow P[/math];
г) закон тождества [math]P\to P[/math];
д) закон контрапозиции [math](P\to Q)\leftrightarrow(\lnot Q\to\lnot P)[/math];
е) закон силлогизма (правило цепного заключения) [math]((P\to Q)\land(Q\to R))\to (P\to R)[/math];
ж) закон противоположности [math](P\leftrightarrow Q)\leftrightarrow (\lnot P\leftrightarrow\lnot Q)[/math];
з) правило добавления антецедента ("истина из чего угодно") [math]P\to(Q\to P)[/math];
и) правило "из ложного что угодно" [math]\lnot P\to(P\to Q)[/math];
к) правило "модус поненс" (лат. modus ponens) [math](P\land(P\to Q))\to Q[/math];
л) правило "модус толленс" (лат. modus tollens) [math]((P\to Q)\land\lnot Q)\to\lnot P[/math];
м) правило перестановки посылок [math](P\to (Q\to R))\leftrightarrow (Q\to (P\to R))[/math];
н) правило объединения (и разъединения) посылок [math](P\to (Q\to R))\leftrightarrow ((P\land Q)\to R)[/math];
о) правило разбора случаев [math]((P\to R)\land (Q\to R))\leftrightarrow ((P\lor Q)\to R)[/math];
п) правило приведения к абсурду [math]((\lnot P\to Q)\land (\lnot P\to\lnot Q))\to P,~ (\lnot P\to (Q\land\to Q))\to P[/math].

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


л) Изучая тавтологии, важно уяснить, что имеется простой и надежный алгоритм (общий метод), позволяющий для любой формулы логики высказываний дать ответ на вопрос, является она тавтологией логики высказываний или нет — этот алгоритм состоит в построении ее таблицы истинности. Составим таблицу истинности для правила "модус толленс" [math]((P\to Q)\land\lnot Q)\to\lnot P:[/math]


[math]\begin{array}{|c|c||c|c|c|c|c|}\hline \lambda(P)& \lambda(Q)& \lambda(P\to Q)& \lambda(\lnot Q)& \lambda((P\to Q)\land\lnot Q)& \lambda(\lnot P)& \lambda(F) \\\hline 0&0&1&1&1&1&1\\ 0&1&1&0&0&1&1\\ 1&0&0&1&0&0&1\\ 1&1&1&0&0&0&1 \\\hline \end{array}[/math]

Последний столбец таблицы, состоящий из значений истинности данной формулы, содержит лишь единицы. Это означает, что данная формула — тавтология.


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


Покажем, что левая часть данной эквивалентности обращается в ложное высказывание тогда и только тогда, когда в ложное высказывание обращается формула, стоящая в правой части эквивалентности. Действительно, формула [math]P\to(Q\to R)[/math] превращается в ложное высказывание, если и только если [math]\lambda(P)=1,[/math] [math]\lambda(Q\to R)=0[/math]. В свою очередь, [math]\lambda(Q\to R)=0[/math] тогда и только тогда, когда [math]\lambda(Q)=1[/math] и [math]\lambda(R)=0[/math]. Итак, [math]\lambda(P\to (Q\to R))=0[/math] в том и только в том случае, когда [math]\lambda(P)=1,[/math] [math]\lambda(Q)=1,[/math] [math]\lambda(R)=0[/math]. С другой стороны, формула [math](P\land Q)\to R[/math] обращается в ложное высказывание, если и только если [math]\lambda(P\land Q)=1[/math] и [math]\lambda(R)=0[/math]. В свою очередь, [math]\lambda(P\land Q)=1[/math] тогда и только тогда, когда [math]\lambda(P)=1[/math] и [math]\lambda(Q)=1[/math]. Итак, [math]\lambda((P\land Q)\to R)=0[/math] в том и только в том случае, когда [math]\lambda(P)=1,[/math] [math]\lambda(Q)=1[/math] и [math]\lambda(R)=0[/math]. Доказанное означает, что правая и левая части эквивалентности одновременно превращаются либо в истинные высказывания, либо в ложные. Следовательно, по определению эквивалентности вся формула всегда превращается в истинное высказывание, т.е. является тавтологией.


Тавтологии, собранные в теореме 3.1, лежат в основе многих математических рассуждений, что уже обсуждалось в начале этой лекции относительно тавтологии теоремы 3.1, пункт п). Применение некоторых других тавтологий в процессе математических рассуждений рассмотрено в следующих лекций. Тавтологии последующих теорем данного параграфа выражают свойства логических операций.




Свойства конъюнкции и дизъюнкции


Теорема 3.2 (свойства конъюнкции и дизъюнкции). Следующие формулы алгебры высказываний являются тавтологиями:


а) законы идемпотентности [math](P\land P)\leftrightarrow P,~ (P\lor P)\leftrightarrow P[/math];
б) законы упрощения [math](P\land Q)\to P,~ P\to (P\lor Q)[/math];
в) законы коммутативности [math](P\land Q)\leftrightarrow (Q\land P),~ (P\lor Q)\leftrightarrow (Q\lor P)[/math];
г) законы ассоциативности [math](P\land (Q\land R)) \leftrightarrow ((P\land Q)\land R),~ (P\lor (Q\lor R)) \leftrightarrow ((P\lor Q)\lor R)[/math];
д) законы дистрибутивности [math](P\land (Q\lor R)) \leftrightarrow ((P\land Q)\lor (P\land R)),~ (P\lor (Q\land R))\leftrightarrow ((P\lor Q)\land (P\lor R))[/math];
е) законы поглощения [math](P\land (P\lor Q)) \leftrightarrow P,~ (P\lor (P\land Q))\leftrightarrow P[/math];
ж) законы де Моргана [math]\lnot(P\land Q)\leftrightarrow (\lnot P\lor\lnot Q),~ \lnot(P\lor Q)\leftrightarrow (\lnot P\land\lnot Q)[/math].

Доказательство. Докажем для примера, что первый закон де Моргана (см. формулу 3.2, ж)) является тавтологией. Пусть [math]A[/math] и [math]B[/math] — произвольные конкретные высказывания. Рассмотрим два составных высказывания [math]\lnot(A\land B)[/math] и [math]\lnot A\land\lnot B[/math], получающиеся из частей данной эквивалентности при замене пропозициональных переменных [math]P[/math] и [math]Q[/math] конкретными высказываниями [math]A[/math] и [math]B[/math] соответственно. Предположим, во-первых, что высказывание [math]\lnot(A\land B)[/math] истинно. Тогда конъюнкция [math]A\land B[/math] ложна; следовательно, по меньшей мере одно из высказываний [math]A[/math] или [math]B[/math] ложно. Но в таком случае хотя бы одно из высказываний [math]\lnot A[/math] или [math]\lnot B[/math] истинно, следовательно, их дизъюнкция [math]\lnot A\lor\lnot B[/math] истинна. Предположим, во-вторых, что высказывание [math]\lnot(A\land B)[/math] ложно. Тогда конъюнкция [math]A\land B[/math] истинна. Следовательно, оба высказывания [math]A[/math] и [math]B[/math] истинны, а их отрицания [math]\lnot A[/math] и [math]\lnot B[/math] оба ложны, т. е. дизъюнкция [math]\lnot A\lor\lnot B[/math] ложна. Таким образом, для любых двух высказываний значения частей рассматриваемой эквивалентности совпадают. Следовательно, формула тождественно истинна.


Рекомендуется доказать самостоятельно тождественную истинность остальных формул теоремы 3.2, а также формул следующих далее теорем 3.3 и 3.4.




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


Теорема 3.3 (свойства импликации и эквивалентности). Следующие формулы алгебры высказываний являются тавтологиями:


а) [math]\bigl(P\to (Q\to R)\bigr)\to \bigl((P\to Q)\to (P\to R)\bigr)[/math];
б) [math]P\to \bigl(Q\to (P\land Q)\bigr)[/math];
в) [math](P\to R)\to \bigl((Q\to R)\to ((P\lor Q)\to P)\bigr)[/math];
г) [math](P\to Q)\to \bigl((P\to\lnot Q)\to\lnot P\bigr)[/math];
д) [math]\bigl(\lnot Q\land (P\to Q)\bigr)\to\lnot P[/math];
е) [math]\bigl(\lnot P\land (P\lor Q)\bigr)\to Q[/math];
ж) [math](P\to Q)\to \bigl((P\lor R)\to (Q\lor R)\bigr)[/math];
з) [math](P\to Q)\to \bigl((P\land R)\to (Q\land R)\bigr)[/math];
и) [math](P\to Q)\to \bigl((Q\to R)\to (P\to R)\bigr)[/math];
л) [math](P\to Q)\lor (Q\to P)[/math];
л) [math](\lnot Q\to\lnot P)\to \bigl((\lnot Q\to P)\to Q\bigr)[/math];
м) [math]\bigl((P\to Q)\land (R\to Q)\bigr)\leftrightarrow \bigl((P\lor R)\to Q\bigr)[/math];
н) [math]\bigl((P\to Q)\land (P\to R)\bigr)\leftrightarrow \bigl(P\to (Q\land R)\bigr)[/math];
о) [math]P\leftrightarrow P[/math];
п) [math](P \leftrightarrow Q) \leftrightarrow (Q\leftrightarrow P)[/math];
р) [math]\bigl((P\leftrightarrow Q)\land (Q\leftrightarrow R)\bigr)\to (P \leftrightarrow R)[/math].



Выражение одних логических операций через другие


Теорема 3.4 (выражение одних логических операций через другие). Следующие формулы алгебры высказываний являются тавтологиями:


а) [math](P\to Q) \leftrightarrow (\lnot P\lor Q)[/math];
б) [math](P\to Q) \leftrightarrow \lnot (P\lor\lnot Q)[/math];
в) [math](P\land Q) \leftrightarrow \lnot (\lnot P\lor\lnot Q)[/math];
г) [math](P\land Q) \leftrightarrow \lnot (P\to\lnot Q)[/math];
д) [math](P\lor Q) \leftrightarrow \lnot (\lnot P\land\lnot Q)[/math];
е) [math](P\lor Q) \leftrightarrow (\lnot P\to Q)[/math];
ж) [math](P\leftrightarrow Q) \leftrightarrow \bigl((P\to Q)\land (Q\to P)\bigr)[/math].



Основные правила получения тавтологий


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


Теорема 3.5 (правило заключения). Если формулы [math]F[/math] и [math]F\to H[/math] являются тавтологиями, то формула [math]H[/math] также тавтология. Другими словами, из [math]\vDash F[/math] и [math]\vDash F\to H[/math] следует [math]\vDash H[/math].


Доказательство. Пусть [math]\vDash F(X_1,\ldots,X_n)[/math] и [math]\vDash F(X_1,\ldots,X_n)\to H(X_1,\ldots,X_n)[/math]. Предположим, что формула [math]H(X_1,\ldots,X_n)[/math] не является тавтологией. Это означает, что существуют такие конкретные высказывания [math]A_1,\ldots,A_n[/math], что [math]\lambda\bigl(H(A_1,\ldots,A_n)\bigr)=0[/math]. Поскольку [math]F(X_1,\ldots,X_n)[/math] — тавтология, то для [math]A_1,\ldots,A_n[/math] имеем [math]\lambda\bigl(F(A_1,\ldots,A_n)\bigr)=1[/math]. Вычисляем, пользуясь соотношением (1.4):


[math]\lambda\bigl(F(A_1,\ldots,A_n)\bigr)\to H(A_1,\ldots,A_n)= \lambda\bigl(F(A_1,\ldots,A_n)\bigr)\to \lambda\bigl(H(A_1,\ldots,A_n)\bigr)= 1\to0=0.[/math]

что противоречит тождественной истинности формулы [math]F\to H[/math]. Следовательно, предположение неверно. Тогда [math]\vDash H[/math], что и требовалось доказать.



Правило заключения называется также правилом отделения или правилом "модус поненс" (лат. modus ponens).


Второе правило получения тавтологий носит название правила подстановки. Пусть в формуле [math]F[/math] содержится пропозициональная переменная [math]X[/math] (а возможно, и другие пропозициональные переменные), и [math]H[/math]— любая формула. Если в формулу [math]F[/math] вместо символа [math]X[/math] везде, где он входит в [math]F[/math], вставить формулу [math]H[/math], то получим новую формулу. Она обозначается [math]S_{X}^{H}F[/math] называется формулой, полученной из [math]F[/math] в результате подстановки в нее формулы [math]H[/math] вместо пропозициональной переменной [math]X[/math]. Например, если в формулу [math](X\lor Y)\to (X\lor\lnot Y)[/math] вместо переменной [math]Y[/math] подставить формулу [math]X_1\land X_2[/math], то получим


[math]\bigl(X\lor (X_1\land X_2)\bigr)\to \bigl(X\land\lnot (X_1\land X_2)\bigr).[/math]

Если в ту же формулу вместо переменной [math]Y[/math] подставить формулу [math]Z[/math], то произойдет просто замена переменной, в результате которой получится формула [math](X\lor Z)\to (X\land\lnot Z)[/math].


Если формула [math]F[/math] содержит две пропозициональные переменные [math]X[/math] и [math]Y[/math] (а возможно, и еще несколько), то можно определить одновременную подстановку двух формул [math]H[/math] и [math]G[/math] в формулу [math]F[/math] вместо пропозициональных переменных [math]X[/math] и [math]Y[/math] соответственно как одновременную замену символа [math]X[/math] всюду, где он входит в [math]F[/math], формулой [math]H[/math] и символа [math]Y[/math] всюду, где он входит в [math]F[/math], формулой [math]G[/math]. Получающуюся формулу обозначают [math]S_{X,Y}^{H,G}F[/math]. Например, подстановка в формулу [math]X\to (X\land Y)[/math] вместо переменной [math]X[/math] формулы [math]X_1\lor X_2[/math], а вместо переменной [math]Y[/math] формулы [math]\lnot Z[/math] приводит к формуле


[math](X_1\lor X_2)\to \bigl((X_1\lor X_2)\land\lnot Z\bigr).[/math]

Аналогично определяется одновременная подстановка в формулу [math]F[/math] и большего числа формул (трех, четырех и т.д.).




Теорема 3.6 (правило подстановки). Если формула [math]F[/math], содержащая пропозициональную переменную [math]X[/math], является тавтологией, то подстановка в формулу [math]F[/math] вместо переменной [math]X[/math] любой формулы [math]H[/math] снова приводит к тавтологии. Другими словами, из [math]\vDash F[/math] следует [math]\vDash S_{X}^{H}F[/math].


Доказательство. Так как [math]\vDash F(X,Y,\ldots)[/math], то формула [math]F(X,Y,\ldots)[/math] превращается в истинное высказывание при подстановке вместо всех пропозициональных переменных [math]X,Y,\ldots[/math]. любых конкретных высказываний. Истинность получаемого высказывания не зависит от структуры подставляемых вместо [math]X,Y,\ldots[/math] высказываний. В частности, вместо [math]X[/math] может быть подставлено высказывание, которое само является конкретизацией формулы [math]H(Z_1,\ldots,Z_k)[/math] на некотором наборе конкретных высказываний. Но это и означает, что тавтологией будет формула [math]F\bigl(H(Z_1,\ldots,Z_k),\,Y,\ldots\bigr)[/math], т.е. [math]\vDash S_{X}^{H}F[/math], что и требовалось доказать.


Например, если в тавтологии [math]X\to (Y\to X)[/math] выполнить подстановку формулы [math]X_1\land\lnot X_2[/math] вместо переменной [math]X[/math], то получим тавтологию


[math](X_2\land\lnot X_2)\to \bigl(Y\to (X_1\land\lnot X_2)\bigr).[/math]

Замечание 3.7. Отметим, что правило подстановки позволяет рассматривать каждую из тавтологий, приведенных в теоремах 3.1 — 3.4, не как отдельно взятую тавтологию, а как схему образования тавтологий. Значит, каждая из пропозициональных переменных в данных формулах может рассматриваться не как переменная, а как произвольная формула алгебры высказываний. Например, тавтология б) из теоремы 3.3 предоставляет бесконечное множество тавтологий вида [math]\vDash F_1\to \bigl(F_2\to (F_1\land F_3)\bigr)[/math], где [math]F_1,F_2[/math] — произвольные формулы алгебры высказываний.


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


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved