Определение 9.3

1. Подформулой элементарной формулы А называется сама формула А.

2. Подформулами любой формулы вида AB, A v B, A ® B называется сама эта формула и все подформулы формул А и В.

3. Подформулами любой формулы вида ` A, " xA, $ xA называются сама эта формула и все подформулы формулы А.

Пользуясь определением 9.3, нетрудно выписать все подформулы любой заданной формулы. Так, подформулами формулы (9.1) будут она сама и формулы:

$ x ₁ p ₁(x ₂, x ₁) v " x ₂ , ,

" x ₂ , p ₁(x ₂, x ₁), p ₂(x ₁, x ₂), $ x ₁ p ₁(x ₂, x ₁).

Из рассмотренных в 9.2 правил получения предикатов на множестве М из заданных предикатов видно, что любая формула А алгебры предикатов сигнатуры σ является предикатом на алгебраической системе М (σ), зависящим лишь от тех предметных переменных, которые имеют свободное вхождение в А. Если такими переменными являются x ₁, …, x_n, то формулу А иногда записывают в виде A (x ₁, …, x_n). Заменив свободные вхождения переменных в формуле А элементами из М (одинаковыми для всех вхождений одной переменной), мы получим высказывание, значение которого можно вычислить, исходя из значений элементарных высказываний и используя определение логических операций. Значения этих высказываний называются значениями формулы А на М (σ) при соответствующих значениях переменных.

Определение 9.4. Формула А алгебры предикатов сигнатуры σ называется выполнимой на алгебраической системе М (σ), если она принимает значение «и» хотя бы при одном наборе из М для переменных, имеющих свободное вхождение в А. В противном случае формула А называется ложной на М (σ). Формула А называется истинной на М (σ), если она принимает значение «и» при любых наборах значений из М для переменных, имеющих свободные вхождения в А.

Определение 9.5. Формула алгебры предикатов сигнатуры σ называется выполнимой, тождественно истинной или тождественно ложной, если она соответственно выполнима хотя бы на одной алгебраической системе, истинна на всех системах или ложна на всех системах сигнатуры σ.

Тождественную истинность (ложность) формулы А обозначают в виде А º и (А º л).

Дата добавления: 2014-12-29