Выполнимость и общезначимость формул

Определение 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. Действительно, .

Если квантор всеобщности применить к конъюнкции любого предиката и его отрицанию , т.е. , то получим тождественно ложную формулу в любой области . Действительно,

В то же время значит, формула является логическим законом.

Рассмотрим еще один пример, показывающий, как с помощью равносильных преобразований устанавливается общезначимость формул логики предикатов:

.

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

Упражнения

1. Являются ли тождественно истинными следующие формулы:

1) ; 2) ;

3) ; 4) ?

2. Привести к предваренной нормальной форме следующие формулы логики предикатов:

1) ; 2) ;

3) ; 4) ;

5) .

3. Какие из приведенных ниже формул являются общезначимыми:

1) ; 2) ;

3) ;

4) ;

5) .