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

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

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

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


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

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


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


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


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


\bigl((\lnot X\to Y)\land(\lnot X\to\lnot Y)\bigr)\to X.

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


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


\bigl(P\land(Q\lor R)\bigr)\leftrightarrow \bigl((P\land Q)\lor(P\land R)\bigr)

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




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


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


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


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

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


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


\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}

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


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


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


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




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


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


а) законы идемпотентности (P\land P)\leftrightarrow P,~ (P\lor P)\leftrightarrow P;
б) законы упрощения (P\land Q)\to P,~ P\to (P\lor Q);
в) законы коммутативности (P\land Q)\leftrightarrow (Q\land P),~ (P\lor Q)\leftrightarrow (Q\lor P);
г) законы ассоциативности (P\land (Q\land R)) \leftrightarrow ((P\land Q)\land R),~ (P\lor (Q\lor R)) \leftrightarrow ((P\lor Q)\lor R);
д) законы дистрибутивности (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));
е) законы поглощения (P\land (P\lor Q)) \leftrightarrow P,~ (P\lor (P\land Q))\leftrightarrow P;
ж) законы де Моргана \lnot(P\land Q)\leftrightarrow (\lnot P\lor\lnot Q),~ \lnot(P\lor Q)\leftrightarrow (\lnot P\land\lnot Q).

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


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




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


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


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



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


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


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



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


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


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


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


\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.

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



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


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


\bigl(X\lor (X_1\land X_2)\bigr)\to \bigl(X\land\lnot (X_1\land X_2)\bigr).

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


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


(X_1\lor X_2)\to \bigl((X_1\lor X_2)\land\lnot Z\bigr).

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




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


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


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


(X_2\land\lnot X_2)\to \bigl(Y\to (X_1\land\lnot X_2)\bigr).

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


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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

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


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

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