1.1.6. Логическое следствие
Формула
X
алгебры высказываний называется
логическим
следствием формул
X1,
X2,
..., Xn,
если импликация X1X2
...
Xn
X
является тавтологией. В этом случае
говорят, что из X1,
X2,
..., Xn
следует X
и этот факт записывают в виде
.
Рассуждения называются правильными, если из конъюнкции посылок следует заключение. Для определения правильности рассуждений по схеме требуется установить тождественную истинность формулы
X1, X2, ..., Xn X.
Распространенными схемами правильных рассуждений являются следующие:
– условно-категорический силлогизм;
– условно-категорический
силлогизм;
– гипотетический
силлогизм.
Проверка правильности рассуждений или проверка того, что данная формула X является логическим следствием формул X1, X2, ..., Xn осуществляется по следующему алгоритму.
Шаг 1. Образовать конъюнкцию посылок X1, X2, …, Xn.
Шаг 2. Составить импликацию X1 X2 ... Xn X.
Шаг 3. Полученную формулу исследовать на тождественную истинность: если она является тождественно истинной, то X является логическим следствием формул X1, X2, ..., Xn, иначе – не является.
Пример. Если два числа равны, то, как известно, их модули равны. Данные числа не равны. Можно ли из этого заключить, что их модули не равны?
Рассмотрим
следующие элементарные высказывания:
X=
«Два числа равны», Y=
«Модули чисел равны». Тогда высказыванию
«Если два числа равны, то, как известно,
их модули равны» соответствует формула
XY,
высказыванию «Данные числа не равны»
–
,
высказыванию «Модули чисел не равны»
–
.
Заметим, что вопрос задачи сводится к
проверке правильности рассуждений, то
есть является ли
логическим следствием посылок
и X
Y:
.
Составив таблицу истинности формулы (XY) , можно увидеть, что она не является тождественно истинной, следовательно, рассуждения не являются правильными, и утверждение «Модули чисел не равны» не верно.
С помощью СКНФ можно решить более общую задачу построения всех логических следствий из данных посылок.
Алгоритм определения всех логических
следствий из данных посылок
Шаг 1. Образовать конъюнкцию всех посылок X1, X2,..., Xn.
Шаг 2. Полученную конъюнкцию привести к СКНФ.
Шаг 3. Множество всех формул, равносильных следствиям из данных посылок, образуют произведения сомножителей СКНФ, взятых по одному, по два и так далее.
Пример. Найти все следствия из посылок XY иXYX Y.
Образуем конъюнкцию посылок и найдем ее СКНФ.
(X Y)(X Y X Y)(X Y)(X Y)(X Y)
(X Y)(X Y) – СКНФ. Тогда следствиями являются XY; X Y; (X Y)(X Y).
СКНФ позволяет решить и обратную задачу: для данной формулы найти все посылки, логическим следствием которых она является.
Алгоритм определения всех посылок, логическим следствием которых является данная формула
Шаг 1. Данную формулу привести к СКНФ.
Шаг 2. Составить ее произведения с каждым из недостающих до соответствующей полной СКНФ множителей – по одному, по два и так далее (под полной понимается СКНФ тождественно ложной формулы с теми же переменными).
Пример. Следствием каких посылок является импликация XY?
Для
импликации XY
СКНФ имеет вид
.
Соответствующая полная СКНФ имеет вид
.
Образуем всевозможные произведения с недостающими сомножителями:
(X Y)(X Y) Y;
(X Y)(X Y) XY;
(X Y)(X Y) X;
(X Y)( X Y) (X Y) XY;
(X Y)( X Y) (X Y) XY;
(X Y) (X Y) (X Y) XY;
(X Y)( X Y) (X Y) (X Y) 0.