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

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

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

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


Логическое следование формул

Логическое следование формул


Раздел алгебры высказываний, изучающий закономерности логического следования, логического умозаключения, является ее сердцевиной. Именно в этом разделе на данном уровне развития математической логики решается основная задача логики, состоящая в нахождении общих способов установления связей логических значений одних высказываний с логическими значениями других высказываний на основании исследования формальной структуры высказываний. Одно из важнейших предназначений логики состоит в том, чтобы устанавливать, что из чего следует, т.е. устанавливать структуры высказываний, связанных отношением логического следования (часть общего назначения математики, по выражению Н.Винера, "находить порядок в хаосе, который нас окружает"). Знание этих закономерностей необходимо прежде всего самой математической науке. С помощью таких знаний происходит доказательство математических теорем и, следовательно, развитие математики. Это знание важно и для других наук, для систематизации научного знания вообще; да и в повседневной жизни оно служит инструментом рассуждений, обоснований и доказательств.


Понятие логического следствия


Когда говорят, что из одного или нескольких предложений A_1,A_2,\ldots,A_m следует предложение B, то подразумевают следующее: всякий раз, когда окажутся истинными все предложения A_1,A_2,\ldots,A_m, истинным будет и предложение B. Вот примеры таких следований: "Если летом я устроюсь на временную работу (утверждение A), то у меня будут заработанные деньги (утверждение B)", "Если у меня будут заработанные деньги (утверждение B), то я куплю видеомагнитофон (утверждение C", "Если днем я не приготовлю уроки на завтра (утверждение A_1), и если вечером я пойду в кино (утверждение A_2), то завтра я буду не готов к занятиям (утверждение D)". Установление справедливости приведенных суждений не относится к компетенции математической логики, а осуществляется на основе анализа их содержания и смысла.


Задача математической логики (в частности, алгебры высказываний) в вопросах логического следования состоит в том, чтобы указать такие формы высказываний A_1,A_2,\ldots,A_m,B, когда последнее высказывание непременно было бы следствием m первых, независимо от конкретного содержания всех этих высказываний. Формы высказываний выражаются, как нам известно, формулами алгебры высказываний. Итак, теория логического следования (в рамках алгебры высказываний) должна изучать закономерности образования формул F_1,F_2, \ldots,F_m,H, по которым первые m из них связаны с последней отношением логического следования.


Вернемся к двум первым суждениям, приведенным в начале пункта: A\to B и B\to C. Вынесем относительно них следующее умозаключение: "Если A\to B и B\to C, то A\to C". Формулировка данного суждения без использования математической символики будет, конечно, неуклюжа. Поэтому сформулируем его так: "Если высказывание A\to B верно и высказывание B\to C верно, то верно и высказывание A\to C". Нет никаких сомнений в том, что высказанное суждение справедливо. Более того, мы осознаем его справедливость, даже не интересуясь содержанием простейших высказываний A,\,B и C. Значит, высказывание, имеющее форму X\to Z, следует из двух высказываний, имеющих формы X\to Y и Y\to Z, независимо от того, каковы высказывания X,\,Y и Z.


Перейдем теперь к точному определению понятия логического следствия и к изучению свойств этого понятия.




Определение 6.1. Формула H(X_1,\ldots,X_n) называется логическим следствием формул F_1(X_1,\ldots,X_n),\ldots, F_m(X_1,\ldots,X_n), если формула H(X_1,\ldots,X_n) превращается в истинное высказывание при всякой такой подстановке вместо всех ее пропозициональных переменных { X_1,\ldots,X_n} конкретных высказываний, при которой в истинное высказывание превращаются все формулы F_1(X_1,\ldots,X_n),\ldots, F_m(X_1,\ldots,X_n). То, что формула H является логическим следствием формул F_1,\ldots,F_m, записывается так: F_1,\ldots,F_m\vDash H. Формулы F_1,\ldots,F_m называются посылками для логического следствия H.


Таким образом, F_1,\ldots,F_m\vDash H, если для любых высказываний A_1,\ldots,A_n из


\lambda\bigl(F_1(A_1,\ldots,A_n)\bigr)=1,\quad \ldots,\quad \lambda\bigl(F_m(A_1,\ldots,A_n)\bigr)=1 следует \lambda\bigl(H(A_1,\ldots,A_n)\bigr)=1.

Наконец можно и так сказать о логическом следствии. Составим таблицы истинности для формул F_1,\ldots,F_m,H. Предположим, что если в какой-то строке таблицы все формулы F_1,\ldots,F_m принимают значение 1, то в этой строке непременно и формула H принимает значение 1. Это и будет означать, что H является логическим следствием формул F_1,\ldots,F_m.


Из сформулированного определения вытекает четкий алгоритм проверки формул на логическое следование (далее приводится в виде схемы). Рассмотрим его действие для случая, например, трех формул-посылок, зависящих от трех переменных:


F_1(X,Y,Z),\, F_2(X,Y,Z),\, F_3(X,Y,Z) \vDash H(X,Y,Z).

Все эти формулы должны быть заданы таблицей своих значений:


\begin{array}{|c|c|c||c|c|c|c|}\hline X& Y& Z& F_1(X,Y,Z)& F_2(X,Y,Z)& F_3(X,Y,Z)& H(X,Y,Z)\\\hline 0&0&0& \alpha_0& \beta_0& \gamma_0& \xi_0\\ 0&0&1& \alpha_1& \beta_1& \gamma_1& \xi_1\\ 0&1&0& \alpha_2& \beta_2& \gamma_2& \xi_2\\ 0&1&1& \alpha_3& \beta_3& \gamma_3& \xi_3\\ 1&0&0& \alpha_4& \beta_4& \gamma_4& \xi_4\\ 1&0&1& \alpha_5& \beta_5& \gamma_5& \xi_5\\ 1&2&0& \alpha_6& \beta_6& \gamma_6& \xi_6\\ 1&1&1& \alpha_7& \beta_7& \gamma_7& \xi_7\\\hline \end{array}



Алгоритм проверки формул на логическое следование


Алгоритм действует следующим образом. Он просматривает последовательно по строкам таблицы значений формул F_1,F_2,F_3,H. Если хотя бы один элемент нулевой строки \alpha_0,\beta_0,\gamma_0 равен 0, то без просмотра значения формулы H в этой строке (т. е. числа \xi_0) происходит переход к просмотру следующей строки \alpha_1,\beta_1,\gamma_1. Если все элементы \alpha_0,\beta_0,\gamma_0 нулевой строки равны 1, то просматривается значение \xi_0 формулы H в этой строке. При \xi_0=0 выдается результат: формула H не является логическим следствием формул F_1,F_2,F_3. При \xi_0=1 происходит переход к просмотру следующей строки \alpha_1,\beta_1,\gamma_1. И так далее. Если после просмотра последней строки \alpha_7,\beta_7,\gamma_7,\xi_7 должен произойти переход к просмотру следующей строки, то это означает, что определение логического следования выполнено и формула H является логическим следствием формул F_1,F_2,F_3.


Пример 6.2. По таблице истинности нескольких формул попытаемся определить, какие из них следуют из каких:


\begin{array}{|c||c|c|c||c|c|c|c|}\hline \mathsf{H^{\underline{\circ}}}& \lambda(X)& \lambda(Y)& \lambda(Z)& \lambda((X\land Y)\to\lnot Z)& \lambda(\lnot Y)& \lambda(X\to Z)& \lambda(\lnot(X\land Y))\\\hline 1& 0& 0& 0& 1& 1& 1& 1\\ 2& 0& 0& 1& 1& 1& 1& 1\\ 3& 0& 1& 0& 1& 0& 1& 1\\ 4& 0& 1& 1& 1& 0& 1& 1\\ 5& 1& 0& 0& 1& 1& 0& 1\\ 6& 1& 0& 1& 1& 1& 1& 1\\ 7& 1& 1& 0& 1& 0& 0& 0\\ 8& 1& 1& 1& 0& 0& 1& 0\\\hline \end{array}

Рассмотрим формулы X,\,Z,\,(X\land Y)\to\lnot Z,\,\lnot Y. Из таблицы видно, что имеется только одна строка (6-я), в которой первые три формулы принимают значение 1. В этой строке и формула \lnot Y также принимает значение 1. Следовательно, X,\,Z,\,(X\land Y)\to\lnot Z\vDash\lnot Y.


Теперь рассматриваем формулы (X\land Y)\to\lnot Z,~ X\to Z,~ \lnot(X\land Y). Из таблицы видно, что имеется точно пять строк, в которых первые две формулы принимают значение 1, а именно 1-я, 2-я, 3-я, 4-я и 6-я. В этих строках третья формула также принимает значение 1. Следовательно,


(X\land Y)\to\lnot Z,\quad X\to Z\vDash\lnot(X\land Y).

Предлагается, глядя на таблицу, обнаружить еще какие-нибудь логические следствия одних формул из других.




Признаки логического следствия


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


Теорема 6.3 (признак логического следствия). Формула Нбудет логическим следствием формулы F тогда и только тогда, когда формула F\to H является тавтологией: F\vDash H\Leftrightarrow\vDash F\to H.


Доказательство. Необходимость. Дано: F(X_1,\ldots,X_n)\vDash H(X_1,\ldots,X_n), т.е. если для набора высказываний A_1,\ldots,A_n имеет место \lambda\bigl(F(A_1,\ldots,A_n)\bigr)=1, то \lambda\bigl(H(A_1,\ldots,A_n)\bigr)=1. Тогда для любого набора высказываний A_1,\ldots,A_n имеет место равенство


\lambda\bigl(F(A_1,\ldots,A_n)\bigr)\to \lambda \bigl(H(A_1,\ldots,A_n)\bigr),

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


Достаточность. Дано: \vDash F\to H. Тогда: \lambda\bigl(F(A_1,\ldots,A_n)\bigr)\to H(A_1,\ldots,A_n)=1 для любых высказываний A_1,\ldots,A_n, откуда в силу равенства (1.4)


\lambda\bigl(F(A_1,\ldots,A_n)\bigr)\to \lambda\bigl(H(A_1,\ldots,A_n)\bigr)=1.

Предположим теперь, что \lambda\bigl(F(A_1, \ldots, A_n)\bigr)=1. Тогда: 1\to \lambda\bigl(H(A_1, \ldots, A_n)\bigr)=1, откуда (на основании определения 1.7) \lambda\bigl(H(A_1,\ldots,A_n)\bigr)=1, ибо в противном случае 1\to 0=1 — противоречие. Но это значит (по определению 6.1 логического следствия), что F\vDash H.


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




Теорема 6.4. Для любых формул F_1,F_1,\ldots,F_m,H~(m \geqslant 2) следующие утверждения равносильны:


а) F_1,F_1,\ldots,F_m\vDash H;
б) F_1\land F_1\land \ldots\land F_m\vDash H;
в) \vDash (F_1\land F_1\land \ldots\land F_m)\to H.

Доказательство. Утверждения б) и в) равносильны на основании предыдущей теоремы. Докажем равносильность утверждений а) и б).


а) \Rightarrow б). Дано: F_1,F_2, \ldots,F_m \vDash H. Покажем, что F_1\land F_2\land \ldots\land F_m\vDash H. Пусть A_1,\ldots,A_n — такие конкретные высказывания, что


\lambda\bigl( F_1(A_1,\ldots,A_n)\land \ldots\land F_m(A_1,\ldots,A_n)\bigr)=1.
(6.1)
Тогда по равенству (1.2)
\lambda\bigl( F_1(A_1,\ldots,A_n)\bigr)\land \ldots\land \lambda\bigl(F_m(A_1,\ldots,A_n)\bigr)=1.
(6.2)
Отсюда по определению 1.3
\lambda\bigl( F_1(A_1,\ldots,A_n)\bigr)=1,\quad \ldots,\quad \lambda\bigl(F_m(A_1,\ldots,A_n)\bigr)=1.
(6.3)

Но поскольку по условию F_1, F_2, \ldots, F_m\vDash H, то отсюда следует. что \lambda\bigl(H(A_1,\ldots,A_n)\bigr)=1. Следовательно, F_1\land F_2\land \ldots\land F_m\vDash H.


б) \Rightarrow а). Дано: F_1\land F_2\land \ldots\land F_m\vDash H. Покажем, что F_1, F_2, \ldots, F_m\vDash H. Предположим, что справедливы все соотношения (6.3) для некоторых A_1,\ldots,A_n. Тогда имеет место соотношение (6.2), из которого на основании равенства (1.2) приходим к соотношению (6.1). Из последнего на основании условия F_1\land F_2\land \ldots\land F_m\vDash H заключаем: \lambda\bigl(H(A_1,\ldots,A_n)\bigr)=1. Но это и означает, что F_1, F_2, \ldots, F_m\vDash H.




Два свойства логического следования


Свойства, формулируемые в теореме 6.5, используются для доказательства того, что какая-то формула является логическим следствием некоторых формул (см. пример 6.2).


Теорема 6.5. Отношение логического следования между формулами алгебры высказываний обладает следующими свойствами:


а) F_1, F_2, \ldots, F_m\vDash F_i для i=1,3,\ldots,m;
б) если F_1, F_2, \ldots, F_m\vDash G_i для j=1,2,\ldots,p и G_1,G_2,\ldots,G_p\vDash H, то F_1, F_2, \ldots, F_m\vDash H.

Доказательство. а) Фактически это свойство состоит в следующем: F_i\vDash F_i. Оно непосредственно вытекает из определения 6.1 логического следования и означает, что отношение логического следования рефлексивно.


б) В частном случае при m=p=1 данное свойство утверждает: если F\vDash G и G\vDash H, то F\vDash H. Другими словами, отношение логического следования транзитивно. Докажем исходное утверждение. Строим таблицу истинности для всех формул, указанных в утверждении б), перечислив все пропозициональные переменные X_1,X_2,\ldots,X_n, входящие хотя бы в одну из этих формул. Рассмотрим какую-нибудь строку этой таблицы, в которой каждая формула F_1,F_2,\ldots,F_m получает истинностное значение, равное 1. Тогда на основании условий каждая из формул G_1,G_2,\ldots,G_p также принимает истинностное значение, равное 1. Следовательно, и H имеет значение 1. Таким образом, для всякого набора истинностных значений переменных X_1,X_2,\ldots,X_n, для которого каждая формула F_1,F_2,\ldots,F_m принимает значение 1, формула Я также принимает значение 1. Это означает, что F_1,F_2,\ldots,F_m\vDash H.




Следование и равносильность формул


Если говорить о следовании из одной формулы другой, то получаем бинарное отношение на совокупности всех формул алгебры высказываний. Две формулы F и H (в указанном порядке) находятся в данном отношении, если F\vDash H.


Ранее рассмотрены бинарные отношения равносильности на совокупности всех формул алгебры высказываний. Две формулы F и H (в указанном порядке) находятся в этом отношении, если F\cong H. Там же (следствие 4.3) установлено, что отношение равносильности формул есть отношение эквивалентности. Установим взаимосвязь между отношением равносильности и отношением следования.


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


F\cong H\quad \Rightarrow\quad F\vDash H и H\vDash F.

Доказательство. Необходимость. Дано: F\cong H. По определению равносильности обе формулы F(X_1,\ldots,X_n) и H(X_1,\ldots,X_n) для любых конкретных высказываний A_1,\ldots,A_n превращаются в высказывания F(A_1,\ldots,A_n) и H(A_1,\ldots,A_n), которые одновременно либо оба истинны, либо оба ложны. А раз так, то каждое из высказываний


F(A_1,\ldots,A_n)\to H(A_1,\ldots,A_n) и H(A_1,\ldots,A_n)\to F(A_1,\ldots,A_n)

истинно для любых конкретных высказываний A_1,\ldots,A_n. Это означает, что \vDash F\to H и \vDash H\to F, откуда, по теореме 6.3, F\vDash H и H\vDash F.


Достаточность. Дано: F\vDash H и H\vDash F. Тогда, по теореме 6.3, \vDash F\to H и \vDash H\to F. Поскольку формула F\to H всегда превращается в истинное высказывание и формула H\to F всегда превращается в истинное высказывание, то и их конъюнкция (F\to H)\land (H\to F) является формулой, которая превращается в истинное высказывание всегда, т.е. \vDash(F\to H)\land (H\to F). Но на основании теоремы 4.4, пункт ч),


(F\to H)\land (H\to F)\cong F\leftrightarrow H\,.

Тогда по замечанию 4.7 имеем \vDash F\leftrightarrow H, а по теореме 4.2 F\cong H. Итак, теорема доказана.


Замечание 6.7. Если некоторая формула является тавтологией, то и всякое ее логическое следствие также является тавтологией. Символически это можно записать так: \vDash F и F\vDash H\Rightarrow\vDash H.


Продумайте это утверждение самостоятельно.




Правила логических умозаключений


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


Начнем с тавтологии из теоремы 3.1, пункт к): \vDash(F\land (F\to G))\to G. (На основании замечания 3.7 пропозициональные переменные P и Q заменены произвольными формулами F и G алгебры высказываний.) На основании теоремы 6.4 заключаем, что F,F\to G\vDash G. Полученную схему, или правило вывода (умозаключения), также называют правилом modus ponens.


Правило 6.8 (modus ponens): \frac{F,F\to G}{G}.


Это правило означает, что от утверждения об истинности посылки F с помощью другой посылки F\to G переходят к утверждению об истинности следствия G. Данное правило называют также правилом заключения или отделения (от посылки F\to G с помощью посылки F отделяется заключение G). По теореме 3.5 правилу 6.8 можно придать несколько иной смысл: если формулы, стоящие в числителе, являются тавтологиями, то и формула в знаменателе — также тавтология.


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


Правило 6.9 (modus fallens): \frac{F\to G,\lnot G}{\lnot F}.


Оно называется правилом modus tollens: от отрицания истинности посылки G с помощью посылки F\to G переходят к отрицанию истинности F.


Таким образом, рассмотренные правила вывода 6.8 и 6.9 позволяют в истинной импликации F\to G из истинности посылки F делать вывод об истинности следствия G, а из ложности следствия G — о ложности посылки F.


Укажем еще некоторые правила вывода, применяемые в рассуждениях. Путь их получения состоит в том, что сначала заменяем в соответствующей тавтологии каждую пропозициональную переменную произвольной формулой алгебры высказываний, в результате чего на основании теоремы 3.6 снова получаем тавтологию, а затем от нее по теореме 6.3 переходим к соответствующему правилу вывода (умозаключения), которое и записываем в принятой форме. Так, тавтология теоремы 3.3, пункт б) дает следующее правило вывода:


Правило 6.10 (введения конъюнкции): \frac{F,G}{F\land G}.


Из тавтологий теоремы 3.2, пункт б) приходим к таким правилам вывода:


Правило 6.11 (удаления конъюнкции): \frac{F\land G}{F}\,,~~ \frac{F\land G}{G}.


Правило 6.12 (введения дизъюнкции): \frac{F}{F\land G}\,,~~ \frac{G}{F\land G}.


Смысл названий этих правил виден из характера их действия. Из тавтологии теоремы 3.1, пункт д) получаем правило контрапозиции.


Правило 6.13 (контрапозиции): \frac{F\to G}{\lnot G\to\lnot F}.


Из тавтологии теоремы 3.1, пункт е) вытекает правило цепного заключения (или правило силлогизма).


Правило 6.14 (цепного заключения): \frac{F\to G,G\to H}{F\to H}.


Из тавтологии теоремы 3.1, пункт м) следует правило перестановки посылок.


Правило 6.15 (перестановки посылок): \frac{F\to(G\to H)}{G\to(F\to H)}.


Наконец, из тавтологии теоремы 3.1, пункт н) получаем следующие правила:


Правила 6.16 (объединения и разъединения посылок): \frac{F\to(G\to H)}{(F\land G)\to H}\,,~~ \frac{(F\land G)\to H}{F\to (G\to H)}.


Правило 6.17 (расширенной контрапозиции): \frac{(F\land G)\to H}{(F\land\lnot H)\to\lnot G}.


Аналогично формулируются другие правила вывода тавтологий, что рекомендуется проделать самостоятельно.


На правила 6.8–6.17 можно смотреть с двух точек зрения. Во-первых, каждое из них представляет собой утверждение следующего типа: формула, записанная в знаменателе, является логическим следствием всех формул, записанных в числителе данного правила. Во-вторых, каждое из этих правил можно рассматривать как правило получения новой тавтологии из уже имеющихся: если все формулы, записанные в числителе, являются тавтологиями, то тавтологией будет и формула, записанная в знаменателе правила (для доказательства этого утверждения примените замечание 6.7).




Способ проверки логического следования


Требуется выяснить, является ли формула H(X_1,\ldots,X_n) логическим следствием формул


F_1(X_1,\ldots,X_n),\ldots, F_m(X_1,\ldots,X_n), то есть F_1,F_2,\ldots,F_m\vDash H.

Предположим, что H не есть логическое следствие формул F_1,F_2,\ldots,F_m. Значит, существуют такие конкретные высказывания A_1,\ldots,A_m, что высказывание H(A_1,\ldots,A_m) ложно, в то время как все высказывания F_1(A_1,\ldots,A_m),\ldots, F_m(A_1,\ldots,A_m) истинны. Если при этом удается найти распределение нулей и единиц между значениями переменных { X_1,\ldots,X_n}, соответствующее сделанному предположению, то предположение верно. Если же возникает противоречие, то предположение неверно. Посмотрим на примерах, как это делается.




Пример 6.18. Выясните, выполняется ли логическое следование


X\to (\lnot Y\lor Z),~ \lnot X,~ Y\to Z\vDash X\lor Z\,.

Допустим, что существуют такие конкретные высказывания A,B,C, что


\lambda\bigl(A\to (\lnot B\lor C)\bigr)=1,~ \lambda(\lnot A)=1,~ \lambda(B\to C)=1, но \lambda(A\lor C)=0.

Тогда из последнего соотношения получаем \lambda(A)=0,~ \lambda(C)=0, что не противоречит соотношению \lambda(\lnot A)=1. Далее, соотношение \lambda(B\to C)=1 дает \lambda(B)=0 (так как \lambda(C)=0). Наконец, вычислив при данных значениях A,\,B и C значение \lambda(A\to (\lnot B\lor C)), убеждаемся что оно равно 1, а это находится в полном соответствии с допущением. Следовательно, приходим к выводу: если высказывания A,B,C таковы, что \lambda(A)= \lambda(B)= \lambda(C)=0, то при подстановке X=A, Y=B, Z=C формулы-посылки примут значение 1, а формула X\lor Z примет значение 0. Значит, формула X\lor Z не выводима из формул X\to(\lnot Y\to Z), \lnot X,~ Y\to Z.




Нахождение следствий из данных посылок


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


Теорема 6.19. Формула H(X_1,\ldots,X_n), не являющаяся тавтологией, тогда и только тогда будет логическим следствием формул F_1(X_1,\ldots,X_n),\ldots, F_m(X_1,\ldots,X_n), не все из которых являются тавтологиями, когда все совершенные дизъюнктивные одночлены из разложения формулы Не совершенную конъюнктивную нормальную форму входят в совершенную конъюнктивную нормальную форму формулы


F_1(X_1,\ldots,X_n)\land \ldots\land F_m(X_1,\ldots,X_n).

Доказательство. Необходимость. Дано: F_1,\ldots,F_m\vDash H.Тогда, по теореме 6.4, F_1\land \ldots\land F_m\vDash H. Найдем для формул F_1\land \ldots\land F_m и H их совершенные конъюнктивные нормальные формы. Такая форма для каждой не тождественно истинной формулы существует и единственна с точностью до порядка совершенных дизъюнктивных одночленов в конъюнкции (см. теорему 5.5). Пусть D_1\land \ldots\land D_k — СКН-формадля формулы F_1\land \ldots\land F_m, а H_1\land \ldots\land H_{\ell} — СКН-форма для формулы H. Тогда:


F_1\land \ldots\land F_m\cong D_1\land \ldots\land D_k,\quad H\cong H_1\land \ldots\land H_{\ell}

Допустим, что заключение теоремы не выполняется, т. е. среди совершенных дизъюнктивных одночленов H_1,\ldots,H_{\ell} имеется такой, которого нет среди совершенных дизъюнктивных одночленов D_1,\ldots,D_k. He нарушая общности (ввиду несущественности порядка вхождения одночленов H_1,\ldots,H_{\ell}, в СКН-форму H_1\land \ldots\land H_{\ell}, можем считать, что таким одночленом является, например, H_1. Итак,


H_1(X_1,\ldots,X_n) \not\cong D_1(X_1,\ldots,X_n),~ \ldots,~ H_{\ell}(X_1,\ldots,X_n) \not\cong D_{k}(X_1,\ldots,X_n).

Тогда существует единственный (с точки зрения логических значений) набор A_1,\ldots,A_n, на котором совершенный дизъюнктивный одночлен H_1(X_1,\ldots,X_n) принимает значение 0: \lambda\bigl(H_1(X_1,\ldots,X_n)\bigr)=0, откуда


\lambda\bigl(H(A_1,\ldots,A_n)\bigr)=0.
(1)

Этот набор выбирается следующим образом. Если переменная X_i входит в H_1 без знака отрицания, то A_i таково, что \lambda(A_i)=0; если X_i входит в H_1 со знаком отрицания, то A_i таково, что \lambda(A_i)=1 (1 \leqslant i \leqslant n). Каждый из совершенных дизъюнктивных одночленов D_1,\ldots,D_k в силу его отличия от совершенного дизъюнктивного одночлена H_1 обращается на данном наборе в 1 (почему?):


\lambda\bigl(D_1(A_1,\ldots,A_n)\bigr)=1,~ \ldots,~ \lambda\bigl(D_k(A_1, \ldots,A_n)\bigr)=1. Тогда \lambda\bigl(D_1(A_1,\ldots,A_n) \land \ldots\land D_k(A_1,\ldots,A_n)\bigr)=1,

откуда, в силу равносильности D_1\land \ldots\land D_k\cong F_1\land \ldots\land F_m получаем


\lambda\bigl(F_1(A_1,\ldots,A_n)\land \ldots\land F_m(A_1,\ldots,A_n)\bigr)=1

Следовательно, \lambda\bigl(F_1(A_1,\ldots,A_n)\bigr)\land \ldots\land \lambda\bigl(F_m(A_1,\ldots,A_n)\bigr)=1. а значит,


\lambda\bigl(F_1(A_1,\ldots,A_n)\bigr)=1,\quad \ldots,\quad \lambda\bigl(F_m(A_1,\ldots,A_n)\bigr)=1.
(2)

Соотношения (1) и (2) противоречат условию: F_1,\ldots,F_m\vDash H. Следовательно, в СКН-форме формулы H нет ни одного совершенного дизъюнктивного одночлена, который отсутствовал бы в СКН-форме формулы F_1\land \ldots\land F_m.


Достаточность. Пусть D_1\land \ldots\land D_k — СКН-форма формулы F_1\land \ldots\land F_m. Тогда F_1\land \ldots\land F_m\cong D_1\land \ldots\land D_k. Пусть далее H\cong D_{i1}\land \ldots\land D_{is}, где 1 \leqslant i_1,\ldots,i_s \leqslant k и i_1,\ldots,i_s попарно различны. Тогда ясно, что если при некоторой подстановке формула F_1\land \ldots\land F_m принимает истинное значение, то и равносильная ей формула D_1\land \ldots\land D_k также принимает значение 1. Следовательно, и все члены D_{1}\land \ldots\land D_{k} последней конъюнкции принимают значение 1, включая члены D_{i1}\land \ldots\land D_{is}. Но тогда и конъюнкция D_{i1}\land \ldots\land D_{is}\cong H также принимает значение 1. Значит, F_1,\ldots,F_m\cong H.


Эта теорема определяет следующее правило (алгоритм) для нахождения всех (неравносильных) формул, являющихся логическими следствиями из посылок F_1,\ldots,F_m:)


1) составить конъюнкцию F_1\land \ldots\land F_m;

2) найти СКН-форму формулы F_1\land \ldots\land F_m;

3) выписать все совершенные дизъюнктивные одночлены найденной СКН-формы, а также всевозможные конъюнкции этих одночленов. Полученное множество формул и является искомым.




Нахождение посылок для данного следствия


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


Теорема 6.20. Чтобы найти все формулы, логическим следствием каждой из которых будет данная формула G(X_1,\ldots,X_n), нужно действовать по следующему алгоритму. Найти СКН-форму для формулы G(X_1,\ldots,X_n); выявить все совершенные дизъюнктивные одночлены, которые в ней отсутствуют; составить всевозможные конъюнкции формулы G(X_1,\ldots,X_n) с недостающими дизъюнктивными одночленами. Получившаяся совокупность формул (вместе с формулой G) будет искомой (с точностью до равносильности формул).


Доказательство. Ясно, что из каждой формулы этой совокупности будет логически следовать формула G, так как G\land H\vDash G (конъюнкция сильнее каждого из сомножителей). Обратно, покажем, что каждая формула F, из которой логически следует данная формула G, имеет указанный вид, т.е. представляет собой конъюнкцию формулы G и некоторых совершенных дизъюнктивных одночленов, отсутствующих в СКН-форме для G. В самом деле, пусть F\vDash G и


G\cong D_1\land D_2\land \ldots\land D_k — СКН-форма для формулы G(X_1,\ldots,X_n) и
F\cong \Delta_1\land \Delta_2\land \ldots\land \Delta_s — СКН-форма для формулы F(X_1,\ldots,X_n).

По определению логического следования, F\vDash G означает, что если формула F(X_1,\ldots,X_n) на некотором наборе A_1,\ldots,A_n значений пропозициональных переменных приняла значение 1, то и формула G(X_1,\ldots,X_n) на этом наборе примет значение 1. Другими словами, если формула G(X_1,\ldots,X_n) на некотором наборе A_1,\ldots,A_n значений пропозициональных переменных принимает значение 0, то и формула F(X_1,\ldots,X_n) на этом наборе принимает значение 0. Но все наборы значений переменных, на которых G принимает значение 0, находятся во взаимно-однозначном соответствии с совершенными дизъюнктивными одночленами D_1,D_2,\ldots,D_s, образующими СКН-форму для формулы G, т.е. если G(A_1,\ldots,A_n)=0, то D_i(A_1,\ldots,A_n)=0 для некоторого 1 \leqslant i \leqslant k. Следовательно, F(A_1,\ldots,A_n)=0 и значит на этом же наборе принимает значение 0 некоторый совершенный дизъюнктивный одночлен \Delta_i, входящий в ее СКН-форму. Но тогда этот одночлен совпадает с одночленом D_i. Таким образом, каждый совершенный дизъюнктивный одночлен D_i из СКН-формы для G входит в СКН-форму для формулы F, т.е. СКН-форма для F имеет вид:


F\cong D_1\land D_2\land \ldots\land D_k\land \Delta_{k+1}\land \ldots\land \Delta_{s}

где \Delta_{k+2},\ldots,\Delta_{s} — совершенные дизъюнктивные одночлены от переменных { X_1,\ldots,X_n}, не входящие в СКН-форму для формулы G.

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

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


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

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