Следование
[предыдущая глава]  [оглавление]  [следующая глава]

Следование - формула РБА, составленная из двух произвольных формул A и B по схеме:

A & ~B & ~(A & ~B)     (1)

Введем краткое обозначений для такой формулы в виде бинарной операции "", объединяющей формулы A и B. То есть:

A B = A & ~B & ~(A & ~B)     (2)

Левый операнд называется условием (или посылкой), правый - следствием.

Формула (1) состоит из трех замыканий, так что в ней не остается ни одной свободной переменной. Результатом вычисления каждого замыкания может быть только true или false, то же самое можо сказать об операциях "~" и "&". Следовательно, и вся формула (1) дает результат из TF. То есть, она задает предикат.

Правило (1) вычисления следования можно сформулировать словами: следование истинно - это (по определению) значит, что хотя бы иногда условие истинно, а следствие ложно, но не то и другое одновременно.

Формула (3) из теоремы 04.0, а также формула булевой алгебры ~x y = x y позволяют получить новое выражение для следования:

A & ~B & ~(A & ~B) = A & ~B & ~~~(A & ~B) = A & ~B & ~(A & ~B) = A & ~B & (~A B) = A & ~B & (A B)

В результате получим альтернативную формулировку, которая одновременно показывает, чем отличается материальная импликация от следования:

A B = A & ~B & (A B)     (7)

Рассмотрим пример. Пусть даны два предиката:

A(x, y) = (x + y > 10)

B(x, y) = (x + y > 0)

Здесь R - множество действительный чисел. Докажем, что второй предикат "следует" из первого и проиллюстрируем раскрытие всех сокращений:

A B = A & ~B & ~(A & ~B) = xy A(x, y) & xy ~B(x, y) & ~xy (A(x, y) & ~B(x, y))

Первый множитель истинный, поскольку формула A(x, y) истинна по крайней мере для одной комбинации: (_10, 10_). Второй множитель истинный, поскольку формула B(x, y) истинна по крайней мере для одной комбинации: (_−1, −1_). Третий множитель истинный, поскольку величина x + y не может быть одновременно больше 10 и меньше или равно 0.