Логика предикатов (стр. 4 из 7)

Правая часть последней равносильности, согласно смыслу символа

, представляет не что иное, как формулу

(s x₁)...(s x_p) B(

, ..., , x₁, ..., x_p),

отнесённую к полю

.

Таким образом, мы доказали, что формула U(

, ..., ) сохраняет своё значение, если её отнести к полю , и теорема, таким образом, доказана.

С л е д с т в и е. Если формула U, содержащая только предикаты, зависящие от одного переменного, является тождественно истинной для всякого поля, не превышающего

элементов, где n – число предикатов в U, то формула U тождественно истинна (т. е. истинна для любого поля). В самом деле допустим, что U не является тождественно истинной формулой. В таком случае её отрицание выполнимо на некотором поле. Так как также удовлетворяет условиям теоремы, то найдётся поле, содержащее не более элементов, на котором формула выполнима. Следовательно, U не может быть истинной на этом поле, что противоречит условию. Итак, предположение, что U не является тождественно истинной, приводит к противоречию, что и требовалось доказать.

§2. Практика по решению проблемы разрешимости формул,

содержащих предикаты от одного переменного

Доказанная (в предыдущем параграфе) теорема позволяет решать проблему разрешимости для формул, содержащих только предикаты, зависящие от одного переменного. Из следствия видно, что для того, чтобы установить, является ли формула U тождественно истинной или нет, достаточно проверить, является ли она тождественно истинной для всякого поля, содержащего не более чем

элементов.

Заметим, что достаточно проверить, является ли данная формула U тождественно истинной на поле, состоящем ровно из

элементов. Это следует из того, что для формул рассматриваемого типа имеет место следующее: если формула U тождественно истинна на некотором поле, то она тождественно истинна на всякой его части.

Рассмотрим произвольное поле, содержащее ровно

элементов: , , ..., . Легко видеть, что всякая формула, имеющая вид:

("x) B(x),

отнесённая к данному полю, равносильна формуле

B(

) & B( ) & ... & B( ).

А формула, имеющая вид:

(

x) B(x),

равносильна формуле

B(

) B( ) ... B( ).

В таком случае произвольная формула U, отнесённая к полю {

, ..., }, равносильна формуле , в которой все кванторы заменены операциями логического произведения и логической суммы. Если в U входили только предикаты A₁, ..., A_n, зависящие от одного переменного, то представляет собой формулу, образованную только операциями алгебры высказываний над выражениями A_i(x_j), 1 ?i?n, 1 ?j? . Так как предикаты A_i(x) совершенно произвольны, то выражения A_i(x_j) представляют собой совершенно произвольные высказывания. Формулу тогда можно рассматривать как формулу алгебры высказываний, у которой A_i(x_j) являются элементарными переменными высказываниями. Тогда вопрос о тождественной истинности U на поле , , ..., оказывается эквивалентным вопросу о тождественной истинности , как формулы алгебры высказываний с переменными высказываниями A_i(x_j).

Заметим, что формула алгебра высказываний

по существу не зависит от того, каковы элементы поля { , ..., }, а зависит только от их числа, так как если мы возьмём другое поле { ¢, ..., ¢}, то в произойдёт только перемена обозначений переменных высказываний A_i(x_j) на A_i(x_j¢). В силу этого мы можем сказать, что если тождественно истинна, как формула алгебры высказываний, то формула U тождественно истинна на любом поле из p элементов, и обратно. С другой стороны, был получен конструктивный способ определять – является произвольная формула алгебры высказываний тождественно истинной или нет. Применяя этот критерий, мы можем установить, будет ли произвольная формула U, содержащая только предикаты от одного переменного, тождественно истинной на любом поле, содержащем p = элементов. В таком случае в силу высказанного выше положения мы можем решить также и вопрос о том, будет формула U тождественно истинной или нет.

Разберём это конкретно на примерах.

П Р И М Е Р 1: Итак, пусть дана формула U, имеющая вид:

("x)[P(x)

( P(x))],

отнесённая к некоторому полю L. Для того, чтобы установить тождественную истинность этой формулы, нам достаточно проверить, является ли она тождественно истинной на поле, содержащем ровно

элементов (см. выше). В данном случае число предикатов (n) равно 2, т.е. L может быть представлено как { a₁, a₂, a₃, a₄ }.

Легко видеть, что формула U равносильна: ("x)[P(x)

(Q(x) P(x))], которая, отнесённая к полю L, равносильна : [P( ) (Q( ) P( ))] [P( ) (Q( ) P( ))] [P( ) (Q( ) P( ))] [P( ) (Q( ) P( ))].