2015-06-28
421
Рассматривая формулы логики предикатов над полем М можно говорить о формулах, равносильных над данным полем, то есть о таких формулах, которые принимают одно и то же значение при замене всех свободных предметных переменных предметами и всех переменных предикатов - определенными.
Пример. Рассмотрим формулы "x W (x) и $x W (x) над полями
М1 = {a} и М2 = {a, b}.
Пусть "x W (x) и $x W (x) даны над полем М1, Значениями переменного предиката W (x) могут быть два определенных предиката A(x) и B(x) (табл. 3.13). Составим истинностную таблицу формул (табл. 3.14).
Таким образом, формулы "x W (x) и $x W (x) равносильны над полем M1.
Таблица 3.13 – Предикаты над М1 Таблица 3.14 – Равносильность над М1
| x | A (x) | B (x) | W (x) | "x W (x) | $x W (x) | |
| a | A (x) | |||||
| B (x) |
Пусть теперь формулы "x W (x) и $x W (x) даны над полем М2. В качестве значений переменного предиката W (x) нужно взять определенные предикаты над полем М2. Таких предикатов существует четыре (табл.3.15). Составив истинностную таблицу формул "x W (x) и $x W (x) (табл.3.16), убеждаемся в их неравносильности над полем М2.
|
|
|
Таблица 3.15- Предикаты над М2 Таблица 3.1- Неравносильность над М2
| x | I1 (x) | I2 (x) | I3 (x) | I4 (x) | W (x) | "x W (x) | $x W (x) | |
| I1 (x) | ||||||||
| a | I2 (x) | |||||||
| I3 (x) | ||||||||
| b | I4 (x) |
Формулы логики предикатов называются равносильными, если они равносильны над любым полем.
Примеры равносильных формул:
1) 
"x W (x) и $x W (x);читается: «высказывание не верно, что для любого х А(х) истинно» эквивалентно высказыванию «найдется х, для которого А(х) ложно»
2) "x W (x) и $x W (x);
3) "x W (x) и $x W (x);
4) "x W (x) и $x W (x).
Докажем равносильность первой пары формул. Пусть М – произвольное поле, а A (x) – некоторый определенный предикат над ним. Подставим вместо переменного предиката W (x) определенный предикат A (x). Пусть высказывание "x A (x) истинное, тогда высказывание "x A(x) ложно. Следовательно, существует предмет a из поля M, что A (a) ложно, тогда A (a) – истинно. Значит, высказывание $x A (x) истинно. Аналогичными рассуждениями получим, что из предположения ложности высказывания "x A (x) следует ложность высказывания $x A (x).
Среди всех формул логики предикатов можно выделить формулы, истинные над любым полем, их называют тождественно-истинными. Например, формула "x W(x) ® $x W(x) является тождественно-истинной.
В общем случае выяснить вопрос, является ли данная формула тождественно-истинной, сложно, так как приходится использовать понятие бесконечности.
