 |
Логическое следование формул
|
|
|
|
Раздел алгебры высказываний, изучающий закономерности логического следования, логического умозаключения, является ее сердцевиной. Именно в этом разделе на данном уровне развития математической логики решается основная задача логики, состоящая в нахождении общих способов установления связей логических значений одних высказываний с логическими значениями других высказываний на основании исследования формальной структуры высказываний. Одно из важнейших предназначений логики состоит в том, чтобы устанавливать, что из чего следует, т.е. устанавливать структуры высказываний, связанных отношением логического следования (часть общего назначения математики, по выражению Н.Винера, "находить порядок в хаосе, который нас окружает"). Знание этих закономерностей необходимо прежде всего самой математической науке. С помощью таких знаний происходит доказательство математических теорем и, следовательно, развитие математики. Это знание важно и для других наук, для систематизации научного знания вообще; да и в повседневной жизни оно служит инструментом рассуждений, обоснований и доказательств.
ПОНЯТИЕ ЛОГИЧЕСКОГО СЛЕДСТВИЯ
Когда говорят, что из одного или нескольких предложений 
следует предложение 
, то подразумевают следующее: всякий раз, когда окажутся истинными все предложения , истинным будет и предложение . Вот примеры таких следований: "Если летом я устроюсь на временную работу (утверждение 
), то у меня будут заработанные деньги (утверждение )", "Если у меня будут заработанные деньги (утверждение ), то я куплю видеомагнитофон (утверждение 
", "Если днем я не приготовлю уроки на завтра (утверждение 
), и если вечером я пойду в кино (утверждение 
), то завтра я буду не готов к занятиям (утверждение 
)". Установление справедливости приведенных суждений не относится к компетенции математической логики, а осуществляется на основе анализа их содержания и смысла.
|
|
|
Задача математической логики (в частности, алгебры высказываний) в вопросах логического следования состоит в том, чтобы указать такие формы высказываний 
, когда последнее высказывание непременно было бы следствием 
первых, независимо от конкретного содержания всех этих высказываний. Формы высказываний выражаются, как нам известно, формулами алгебры высказываний. Итак, теория логического следования (в рамках алгебры высказываний) должна изучать закономерности образования формул 
, по которым первые из них связаны с последней отношением логического следования.
Вернемся к двум первым суждениям, приведенным в начале пункта: 
и 
. Вынесем относительно них следующее умозаключение: "Если и , то 
". Формулировка данного суждения без использования математической символики будет, конечно, неуклюжа. Поэтому сформулируем его так: "Если высказывание верно и высказывание 
верно, то верно и высказывание ". Нет никаких сомнений в том, что высказанное суждение справедливо. Более того, мы осознаем его справедливость, даже не интересуясь содержанием простейших высказываний 
и . Значит, высказывание, имеющее форму 
, следует из двух высказываний, имеющих формы 
и 
, независимо от того, каковы высказывания 
и 
.
Перейдем теперь к точному определению понятия логического следствия и к изучению свойств этого понятия.
Опр 1. Формула 
называется логическим следствием формул 
, если формула превращается в истинное высказывание при всякой такой подстановке вместо всех ее пропозициональных переменных 
конкретных высказываний, при которой в истинное высказывание превращаются все формулы 
. То, что формула 
является логическим следствием формул 
, записывается так: 
.
|
|
|
Формулы называются посылками для логического следствия .
Таким образом, , если для любых высказываний 
из 
следует 
.
Наконец можно и так сказать о логическом следствии. Составим таблицы истинности для формул 
. Предположим, что если в какой-то строке таблицы все формулы принимают значение 1, то в этой строке непременно и формула принимает значение 1. Это и будет означать, что является логическим следствием формул .
Из сформулированного определения вытекает четкий алгоритм проверки формул на логическое следование (далее приводится в виде схемы).
Рассмотрим его действие для случая, например, трех формул-посылок, зависящих от трех переменных:
Все эти формулы должны быть заданы таблицей своих значений:
АЛГОРИТМ ПРОВЕРКИ ФОРМУЛ НА ЛОГИЧЕСКОЕ СЛЕДОВАНИЕ
Алгоритм действует следующим образом. Он просматривает последовательно по строкам таблицы значений формул 
. Если хотя бы один элемент нулевой строки 
равен 0, то без просмотра значения формулы в этой строке (т. е. числа 
) происходит переход к просмотру следующей строки 
. Если все элементы нулевой строки равны 1, то просматривается значение формулы в этой строке. При 
выдается результат: формула не является логическим следствием формул 
. При 
происходит переход к просмотру следующей строки . И так далее. Если после просмотра последней строки 
должен произойти переход к просмотру следующей строки, то это означает, что определение логического следования выполнено и формула является логическим следствием формул .
Пример 2. По таблице истинности нескольких формул попытаемся определить, какие из них следуют из каких:
Рассмотрим формулы 
. Из таблицы видно, что имеется только одна строка (6-я), в которой первые три формулы принимают значение 1. В этой строке и формула 
также принимает значение 1. Следовательно, 
.
Теперь рассматриваем формулы 
. Из таблицы видно, что имеется точно пять строк, в которых первые две формулы принимают значение 1, а именно 1-я, 2-я, 3-я, 4-я и 6-я. В этих строках третья формула также принимает значение 1. Следовательно,
|
|
|
Предлагается, глядя на таблицу, обнаружить еще какие-нибудь логические следствия одних формул из других.
ПРИЗНАКИ ЛОГИЧЕСКОГО СЛЕДСТВИЯ
То, что некоторая формула является логическим следствием каких-то формул, можно выразить так же, сказав, что подходящая формула является тавтологией. В этом существо признаков, о которых пойдет речь в настоящем пункте, чем еще раз подчеркивается важное значение тавтологий.
Теорема 12 (признак логического следствия). Формула Н будет логическим следствием формулы 
тогда и только тогда, когда формула 
является тавтологией: 
.
Доказательство. Необходимость. Дано: 
, т.е. если для набора высказываний имеет место 
, то . Тогда для любого набора высказываний имеет место равенство
поскольку равенство нулю возможно лишь в том случае, когда и 
, но такая ситуация исключена условием. Следовательно, на основании равенства (1.4) 
для любых высказываний . Это означает, что формула 
— тавтология, т.е. 
.
Достаточность. Дано: . Тогда: 
для любых высказываний , откуда в силу равенства (1.4)
Предположим теперь, что . Тогда: 
, откуда (на основании определения 1.7) , ибо в противном случае 
— противоречие. Но это значит (по определению 6.1 логического следствия), что 
.
Следующая теорема дает признаки того, что формула является логическим следствием двух или большего количества формул.
Теорема 13. Для любых формул 
следующие утверждения равносильны:
а) 
;
б) 
;
в) 
.
Доказательство. Утверждения б) и в) равносильны на основании предыдущей теоремы. Докажем равносильность утверждений а) и б).
а) 
б). Дано: 
. Покажем, что 
.
Пусть 
— такие конкретные высказывания, что
 (6.1)
|
Тогда по равенству (1.2)
 (6.2)
|
Отсюда по определению 1.3
 (6.3)
|
Но поскольку по условию , то отсюда следует. что . Следовательно, .
б) а). Дано: . Покажем, что . Предположим, что справедливы все соотношения (6.3) для некоторых . Тогда имеет место соотношение (6.2), из которого на основании равенства (1.2) приходим к соотношению (6.1). Из последнего на основании условия заключаем: . Но это и означает, что .
|
|
|
|
|
|
