Игошин Математическая логика и теория алгоритмов (1019110), страница 14
Текст из файла (страница 14)
Предлагается, глядя на таблицу, обнаружить еше какие-нибудь логические следствия одних формул из других (см. также Задачник, № 1.34). 56 ЦГ,(Ан ..., А„) л ... н Г (А„..., А„)) = 1. Тогда по равенству (1.2) к(Г~(Аь ..., А,)) л ... л Х(Г (Аь ..., А„)) = 1. Отсюда по определению 1.3 (6.1) (6.2) Ц.Е;(Ан ..., А„)) = 1, ..., 2.(Г (Аь ..., А„)) = 1. (6.3) 57 Признаки логического следствия. То, что некоторая формула является логическим следствием каких-то формул, можно выразить так же, сказав, что подходящая формула является тавтологией. В этом существо признаков, о которых пойдет речь в настоящем пункте, чем еше раз подчеркивается важное значение тавтологий.
Теорема б.З (признак логического следствия). Формула Н будет логическим следствием формулы Гтогда и только тогда, когда формула Г-+ Нявляется тавтологией: Г~ Н <=о à — > Н. Д о к а з а т е л ь с т в о. Необходимость. Дано: Г(Хь ..., Х„) ~ Н(Хь „., Х„), т.е. если для набора высказываний Аь ..., А„имеет место ЦГ(Аь ..., А„)) = 1, то 2.(Н(Аь ..., А„)) = !. Тогда для любого набора высказываний А„..., А„имеет место равенство ЦГ(Аь ..., А„)) — > -+ ).(Н(Аь ..., А„)) = 1, поскольку равенство нулю возможно лишь в том случае, когда ЦГ(Ао ..., А„)) = 1 и ЦН(Аь ..., А„)) = О, но такая ситуация исключена условием. Следовательно, на основании равенства (1.4) 2(Г(Аь ..., А„) -ь Н(А„..., А„)) = 1 для любых высказываний А„..., А„.
Это означает, что формула Г(Хь ..., Х„) — ь — > Н(Хь ..., Х„) — тавтология, т.е. ~ Г-ь Н. Достаточмость. Дано: ~ Г-ь Н. Тогда: к(Е(Аь ..., А„) — ь Н(Аь ..., А„)) = 1 для любых высказываний Ао ..., А„, откуда в силу равенства (1.4) 7.(Г(Аь ..., А„)) — ь ЦН(А„..., А„)) = 1. Предположим теперь, что ЦГ(Ан ..., А„)) = 1. Тогда: 1 -ь Х(Н(Аь ..., А„)) = 1, откуда (на основании определения 1.7) 2,(Н(Аь ..., А„)) = 1, ибо в противном случае 1 — ь О = 1 — противоречие. Но это значит (по определению 6.1 логического следствия), что г" . Н.
П Следующая теорема дает признаки того, что формула является логическим следствием двух или большего количества формул. Теорема 6.4. Для любых 4ормул Гн Рн ..., с, Н(т > 2) следующие утверждения равносильны: а) Гь Г2, ..., Г. ~ Н; б)Г1лР~л...лр ~Н; в) ~ (Р; л Р~ л ... н Г ) -~ Н. Д о к а з а т е л ь с т в о. Утверждения б) и в) равносильны на основании предыдущей теоремы. Докажем равносильность утверждений а) и б).
а) =ь б) Дано: Рь Г,, ..., Г ~ Н. Покажем, что Р; м Р, л ... н Г ~ Н. Пусть А„..., А„— такие конкретные высказывания, что Но поскольку по условию Гь Гь ..., Г ы Н, то отсюда следует, что ).(Н(Аь ..., А„)) = 1. Следовательно, Г1 н Гг н ... н Г ~ Н. б) =~ а). Дано: Р~ и Гг н ... н Г Н. Покажем, что Г„Гь ..., Г ы Н. Предположим, что справедливы все соотношения (6.3) для некоторых Аь ..., А„. Тогда имеет место соотношение (6.2), из которого на основании равенства (1.2) приходим к соотношению (6.!). Из последнего на основании условия Р; н Г2 н ...
н Г ~ Н заключаем: к(Н(Аь ..., А„)) = !. Но это и означает, что Гь Гь ..., Г„ ~ Н. П Два свойства логического следования. Свойства, формулируемые в теореме 6.5, используются для доказательства того, что какая-то формула является логическим следствием некоторых формул (см. пример 6.2). Теорема 6.5. Отношение логического следования между формулами алгебры высказываний обладает следующими свойствами: а) Гп Гм ..., Г ~ Гн для! = 1, 2, ..., т; б) если Гь Гв ..., Г ~ 6 для у'= 1, 2, ..., р и 6ь 6,, ..., 6, ~ Н, тор'ьГ2,...,Г Н. Д о к а з а т е л ь с т в о. а) Фактически это свойство состоит в следующем: Г; ~ Гь Оно непосредственно вытекает из определения 6.1 логического следования и означает, что отношение логического следования рефлексивно. б) В частном случае при т = р = 1 данное свойство утверждает: если Г ~ 6 и 6 ~ Н, то Г ~ Н.
Другими словами, отношение логического следования транзитивно. Докажем исходное утверждение. Строим таблицу истинности для всех формул, указанных в утверждении б ), перечислив все пропозициональные переменные Хь Хь ..., Х„, входящие хотя бы в одну из этих формул. Рассмотрим какую- нибудь строку этой таблицы, в которой каждая формула Гь Г;, ..., Г получает истинностное значение, равное 1.
Тогда на основании условий каждая из формул 6ь 6„..., 6р также принимает истинностное значение, равное 1. Следовательно, и Нимеет значение 1. Таким образом, для всякого набора истинностных значений переменных Х„Хн ..., Х, лля которого каждая формула Гь Гь ..., Г,„ принимает значение 1, формула Н также принимает значение 1. Это означает, что Гь Гц ..., Г„~ Н. П Следование и равносильность формул.
Если говорить о следовании из одной формулы другой, то получаем бинарное отношение на совокупности всех формул алгебры высказываний. Две формулы Ги Н (в указанном порядке) находятся в данном отношении, если Г Н. В э 4 рассмотрены бинарные отношения равносильности на совокупности всех формул алгебры высказываний. Две формулы Г и Н (в указанном порядке) находятся в этом отношении, если Г и Н. Там же (следствие 4.3) установлено, что отношение равносильности формул есть отношение эквивалентности.
Установим взаимосвязь между отношением равносильности и отношением следования. Теорема б.б. Две формулы алгебры высказываний равносильны пюгда и только тогда, когда каждая из них является логическим следствием другой: Гя Нс=~ Г Ни Н Г. Доказательство. Необходимость. Дано: Ги Н. По определению равносильности обе формулы Г(Хь ..., Х„) и Н(Хь ..., Х.) для любых конкретных высказываний А,, ..., А„превращаются в высказывания Г(А„..., А„) и Н(Аь ..., А„), которые одновременно либо оба истинны, либо оба ложны. А раз так, то каждое из высказываний Г(А„..., А„) — > Н(А„..., А„) и Н(А„..., А„) -э ~ Г(А„..., А„) истинно для любых конкретных высказываний Аь ..., А„. Это означает, что ~ à — > Н и ~ Н -ь Г, откуда, по теореме 6.3, Г ы Н и Н ~ Г.
Достаточность. Дано; Г~ Ни Н ~ Г. Тогда, по теореме 6.3, ~ à — ь -ь Н и ~ Н-+ Е Поскольку формула à — > Н всегда превращается в истинное высказывание и формула Н вЂ” > Г всегда превращается в истинное высказывание, то и их конъюнкция (à — ь Н) и (Н вЂ” > Г) является формулой, которая превращается в истинное высказывание всегда, т.е. ~ (à — > Н) п (Н ь Г). Но на основании теоремы 4.4, ч, (à — > Н) и (Н-ь Г) и Гь-> Н. Тогда по замечанию 4.7 - Г ьь Н, а по теореме 4.2 Гге Н. П Замечание б.7. Если некоторая формула является тавтологией, то и всякое ее логическое следствие также является тавтологией.
Символически это можно записать так: ~ Ги Г ы Н ~ ~ Н. Продумайте зто утверждение самостоятельно. Правила логических умозаключений. Теперь можем рассмотреть примеры структур правильного мышления, т.е. ответить на вопрос, что из чего следует. Начнем с тавтологии из теоремы 3.1, к: ы (Гп (Г-ь 6)) — > 6. (На основании замечания 3.7 пропозициональные переменные Р и Ц заменены произвольными формулами Ги 6 алгебры высказываний.) На основании теоремы 6.4 заключаем, что Г, à — ь 6 ~ 6.
Полученную схему, или правило вывода (умозаключения), также называют правилом тодиз ропепз. Г,à — >6 Нравило б. В (тодиз ропепз): 6 Это правило означает, что от утверждения об истинности посылки Гс помощью другой посылки à — ь 6 переходят к утверждению об истинности следствия 6. Данное правило называют также правилом заключения или отделения (от посылки Г -ь 6 с помощью посылки Готделяется заключение 6). По теореме 3.5 правилу 6.8 можно придать несколько иной смысл: если формулы, стоящие в числителе, являются тавтологиями, то и формула в знаменателе — также тавтология.
Не менее важное и широко применяемое в рассуждениях правило умозаключения получается на основе тавтологии теоремы 3.1, л. à — «6,-6 Правило б.9 (тойиз «оПепз): Оно называется правилом тоИиз гоПепгс от отрицания истинности посылки 6 с помощью посылки à — «6 переходят к отрицанию истинности Е Таким образом, рассмотренные правила вывода 6.8 и 6.9 позволяют в истинной импликации à — «6 из истинности посылки Г делать вывод об истинности следствия 6, а из ложности следствия 6 — о ложности посылки Г. Укажем еще некоторые правила вывода, применяемые в рассуждениях.
Путь их получения состоит в том, что сначала заменяем в соответствующей тавтологии каждую пропозициональную переменную произвольной формулой алгебры высказываний, в результате чего на основании теоремы 3.6 снова получаем тавтологию, а затем от нее по теореме 6.3 переходим к соответствующему правилу вывода (умозаключения), которое и записываем в принятой форме. Так, тавтология теоремы 3.3, б дает следующее правило вывода: Г,6 Правило 6.10 (введения конъюнкции): Глб Из тавтологий теоремы 3.2, б приходим к таким правилам вывода: ГЛ6 Глб Правило 6.11 (удаления конъюнкции): Г 6 Правило 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
