Элементы логики

Предположение примера выразим формулой:

(AB)(BC)A.

Доведем, при истинности такого условия истинным будет высказывание C. Превратим (AB)(BC)A к ДНФ:

(AB)(BC)A  (AB)(BC)A  A(AB)(BC) 

 (AA)(AB)(BC)  (AB)(BC) 

 (ABB)(ABC)  ABC.

Следовательно, имеем, что истинной является формула ABC. Но она истинна лишь тогда, когда каждый сомножитель истинен. Отсюда высказывание C является истинным.

Таким образом, из истинности формул (AB), (BC) и A выплывает истинность C. В таком случае C называется логическим выводом этих формул.

Определение. Формула Y называется логическим выводом формул X1, X2, ., Xn, если из истинности X1X2.Xn выплывает истинность формулы Y. Формулы X1, X2, ., Xn называются предпосылками Y.

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

Теорема 1. Формула Y является логическим выводом формул X1, X2, ., Xn тогда и только затем, когда формула (X1X2.Xn)Y является тавтологией.

Доведение. 1 (Необходимость). Допустимо, что формула Y является логическим выводом формул X1, X2, ., Xn. Если при некоторых значениях букв в формулах X1, X2, ., Xn хотя бы одна из них ошибочная, то за определением импликации (X1X2.Xn)Y истинная. Если же при некоторых значениях букв в формулах X1, X2, ., Xn все они истинны, X1X2.Xn также истинная. Но формула Y является логическим выводом формул X1, X2, ., Xn, потому она также истинная. Тогда истинная и формула (X1X2.Xn)Y. Следовательно, при любых значениях букв (X1X2.Xn)Y истинная, то есть является тавтологией.

2 (Достаточность). Допустимо, что (X1X2.Xn)Y является тавтологией. Тогда если при каких-то значениях букв в формулах X1, X2, ., Xn все они истинны, то Y также истинная, то есть есть их логическим выводом.

Теорема 2. Формула Y является логическим выводом формул X1, X2, ., Xn тогда и только затем, когда формула (X1X2.XnY) есть суперечнистю.Доведення. За теоремой 1, формула Y является логическим выводом формул X1, X2, ., Xn тогда и только затем, когда формула (X1X2.Xn)Y является тавтологией. Отсюда Y является логическим выводом формул X1, X2, ., Xn тогда и только затем, когда отрицание ((X1X2.Xn)Y)является противоречием. Но

((X1X2.Xn)Y)  ((X1X2.Xn)Y) 

 ((X1X2.Xn))Y  X1X2.XnY.

Таким образом, утверждение теоремы истинно.

Рассмотрим пример применения приведенных теорем. Докажем, что формула B является логическим выводом формул AB и A. Превратим формулу (AB)AB:

(AB)AB  (AB)AB  (AAB)(BAB)  00  0.

Следовательно, формула (AB)AB противоречивая, и за теоремой 2 формула B является логическим выводом формул AB и A.



Вернуться назад