Равносильность и следование предикатов

Определение 4. Предикаты и , заданные на одной и той же предметной области М, равносильны тогда и только тогда, когда их множества истинности совпадают . Утверждение о равносильности двух предикатов Р и Q символически будем записывать так: или .

Отношение равносильности предикатов является отношением эквивалентности, так что совокупность всех п -местных предикатов, определенных на М,распадается на непересекающиеся классы равносильных предикатов (все они определяют одну и ту же функцию, заданную на М и принимающую значения в двухэлементном множестве {0, 1}). Переход от предиката к равносильному ему предикату называется равносильным преобразованием первого. Это понятие очень важно для математики, потому что изучаемые в ней уравнения и неравенства представляют собой частные виды предикатов. Решение уравнения и неравенства есть поиск их множеств истинности. При таком поиске мы проделываем над уравнением и неравенством различные преобразования, и здесь важно, чтобы эти преобразования были равносильными, т. е. чтобы найденное множество оказалось бы множеством истинности именно исходного уравнения или неравенства. Аналогична ситуация при решении систем уравнений или неравенств.

Определение 5. Пусть и – два n -местных предиката от одних и тех же переменных, заданных на одном и том же множестве М. Предикат называется следствием предиката , если для любого набора переменных, на которых предикат является истинным, предикат также истинен. Следствие обозначается как

.

Другими словами (в терминах множеств истинности), можно сказать, что предикат является следствием предиката Р тогда и только тогда, когда .

Пример. Если и , , то но не наоборот.

Теорема. Предикаты и равносильны тогда и только тогда, когда каждый из них есть следствие другого.

Доказательство. Необходимость. , тогда , т.е. и . Из вытекает, что , а из вытекает, что .

Достаточность. Пусть и . Тогда из первого утверждения следует, что , а из второго ‑ . Из этих двух соотношений вытекает, что и .