yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->4.4. Проверял общезначимости формул алгебры предикатов.

Математическая логика

4.4. Проверял общезначимости формул алгебры предикатов.

Проверка ЛОЗ может быть осуществлена сведением к противоречию, т.е. методом редукции. Предполагаем, что существует такая интерпретация формулы Е, на которой она принимает ложное значение, т. е. |E'|=F и пробуем найти такую интерпретацию. Если в результате получаем противоречие, это означает, что таких интерпретаций не существует, и, следовательно, формула логически общезначима.

Пример. Рассмотрим формулу x(A(x)vB) xA(x)vB, где В не зависит от х. Предположим, что |x(A'(x)vB) xA(x)vB|=F. Это возможно, если |x(A'(x)vB) | =T, a |xA(x)vB|=F. Отсюда следует, что |B|=F и |x(A'(x) |=F. Если |x(A'(x) |=F, то х=а, такое, что A'(a)=F.

Формула |Vx(A (x)vB)|=T. Но в области интерпретации данной формулы существует значение х=а для которого A'(a)=F и B=F, так что (A'(a)vB)=F. Тогда, навешивая квантор всеобщности, получаем: |x(A'(x)vB)|=F, что противоречит предположению |(A'(x)vB)|=T.

Проверим выполнение общезначимости в другую сторону. Предположим;

|xA'(x)vBx(A'(x)vB)|=F. Тогда |x(A'(x)vB)|=F, и |xA(x)vB| =Т. Из |x(A`(x)vB)|=F следует, что существует такое х=а, что |A'(a)vB|=F. Отсюда следует, что |A'(a)|=F, |B|=F. Следовательно, в области определения предиката А(х) существует значение х=а, при котором предикат A(a)=F, значит, |xA'(x)|=F. Формула |xA'(x)vF|=F, что противоречит предположению. Следовательно, формула общезначима.

 

26