Выполнимость и общезначимость формул
Определение 1. Формула B логики предикатов называется выполнимой в области M, если существуют значения переменных, входящих в эту формулу и принадлежащих множеству M, при которых формула B принимает истинные значения. Это определение очень похоже на то определение, которое мы дали для квантора существования в подразд. 3.1 относительно одного предиката. Данное определение отличается тем, что оно применяется не к отдельному предикату, а к формуле, состоящей из нескольких предикатов.
Определение 2. Формула B называется выполнимой, если существует область, на которой эта формула выполнима.
Это определение не следует понимать так, что если формула выполнима, то она выполнима в любой области. Для выполнимости формулы достаточно существования любой области, на которой она выполнима.
Определение 3. Формула B называется тождественно истинной в области M, если она принимает истинные значения для всех значений переменных, входящих в эту формулу и принадлежащих множеству M.
Это определение по форме похоже на определение 2 подразд. 3.1., но отличается от него тем, что то определение давалось для предиката, а данное – для формулы, т.е. для предложения, состоящего из нескольких предикатов.
Определение 4. Формула B называется общезначимой, если она тождественно истинная на всякой области. Ранее в подразд. 2.9., мы вскользь упомянули о понятии общезначимость и отметили, что его используют иногда для обозначения тождественно истинных формул алгебры логики и обозначают символом ╞. Таким образом, мы видим, что преемственность и аналогия полностью сохраняются. И в алгебре логики, и в логике предикатов термин общезначимость употребляется для обозначения одинаковых по смыслу понятий – тождественно истинных формул. Только в логике предикатов понятие тождественно истинной формулы более широкое, чем в алгебре логики.
Определение 5.
Формула
называется тождественно
ложной в области M,
если она принимает ложные значения для
всех значений переменных, входящих в
эту формулу и принадлежащих множеству
M.
Как нетрудно видеть, это определение с точностью до обозначений совпадает с определением тождественно ложного предиката (определение 2, подразд. 3.1) и тождественно ложной формулы алгебры логики (определение 2, подразд. 1.3).
Из приведенных определений вытекают следующие свойства формул логики предикатов.
1. Если формула B общезначимая, то она и выполнима на всякой области.
2. Если формула B тождественно истинная в области M, то она и выполнима в этой области.
3. Если формула B тождественно ложная в области M, то она и не выполнима в этой области.
4. Если формула B не выполнима, то она тождественно ложна на всякой области.
На основании приведенных определений выделяют два класса формул логики предикатов: выполнимых и не выполнимых формул.
Рассмотрим примеры выполнимых, невыполнимых и общезначимых формул.
Пусть формула
задана в виде:
,
где предикат
означает
и определен на области
,
где
(символ
означает, что рассматриваемая переменная
x
принимает значения от a
до b,
то же самое и для
).
Ясно, что в этом случае формула
тождественно истинная в области M,
а поэтому и выполнима в этой области.
Если же предикат
рассматривать в другой области, например
, где
,
то формула
является тождественно ложной. Поскольку
рассматриваемая формула не является
тождественно истинной на всякой области,
то она и не общезначима.
Рассмотрим другой
пример. Пусть заданы предикаты: P(x)–
“число
кратно 7”, Q(у)
– “число
кратно 3” и
,
определенные в области
,
где
.
На какой области формула
выполнима, невыполнима и является ли
она общезначимой? Дадим ответы на эти
вопросы.
Так как для
предиката P(x)
,
а для предиката Q(x)
,
то для предиката
.
А это означает, что существуют такие
и
,
что среди натуральных чисел N
всегда найдется такое число, при котором
будет истинна формула
.
Это число
.
Например, для чисел
и
существует число
(это же число принадлежит и каждому в
отдельности множеству
и
). Следовательно, рассматриваемая
формула является истинной на множестве
,
т.е. она выполнима в этой области (на
этом множестве), а следовательно, и в
области M.
Кроме того, какие бы числа y и y мы ни взяли соответственно из и для них всегда найдется такое число из , что будет истинна формула , т.е. эта формула тождественно истинная в этой области.
Если же предикат
мы будем рассматривать в области
,
где
,
то формула
является тождественно ложной.
Действительно, среди пар чисел
множества
не найдется ни одной такой пары чисел,
для которой были бы истинны предикаты
.
Следовательно, на множестве
формула
является тождественно ложной, а значит,
и невыполнимой. И, наконец, эта формула
не общезначима, так как. не является
тождественно истинной на всякой области.
Интерес представляют
общезначимые формулы, так как они
являются логическими законами. Такой
простейшей формулой является формула
.
Причем, независимо от конкретного
смыслового содержания предиката
,
эта формула является тождественно
истинной в любой области M.
Действительно,
.
Если квантор
всеобщности применить к конъюнкции
любого предиката
и его отрицанию
,
т.е.
,
то получим тождественно ложную формулу
в любой области
.
Действительно,
В то же время
значит, формула
является логическим законом.
Рассмотрим еще один пример, показывающий, как с помощью равносильных преобразований устанавливается общезначимость формул логики предикатов:
.
Таким образом, мы получили заданную формулу, которая является тождественно истинной для любых двух одноместных предикатов и в любой области (поскольку область заранее не оговаривалась). Значит, формула общезначима.