§ 11. Равносильные преобразования формул

Определение 1. Две формулы F и H логики предикатов называются равносильными на множестве M, если при любой подстановке в эти формулы вместо предикатных переменных любых конкретных предикатов, определенных на М, формулы превращаются в равносильные предикаты.

Определение 2. Если две формулы равносильны на любых множествах, то их будем называть просто равносильными.

Равносильность обозначается .

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

Покажем, что

Вместо предикатных переменных P(x) и Q(x) подставим конкретные предикаты A(x) и B(x), определенные на N.

A(x) = “x – четное число”, B(x) = “x – нечетное число”

Левая часть формулы есть высказывание:

«Каждое число четно или нечетно» (которое истинно).

Правая часть – высказывание:

«Каждое натуральное число четно, либо каждое натуральное нечетно» (которое ложно).

Определение. Формулы F и H равносильны тогда и только тогда, когда формула является тавтологией:

Определение. Приведенной формой для формул логики предикатов называется такая равносильная ей формула, в которой имеются только операции , и знаки отрицания относятся лишь к предикатным переменным и к высказываниям.

Теорема. Для любой формулы логики предикатов существует приведенная форма.

Определение. Предваренной нормальной формой для формулы логики предикатов называется такая ее предваренная форма, в которой все кванторы стоят в ее начале, а область действия каждого из них распространяется до конца формулы, т.е. формула вида , где– один из кванторовили,, а формулаF не содержит кванторов и является приведенной формулой.

Замечание. Кванторы в формуле могут отсутствовать.

Теорема. Для любой формулы логики предикатов существует предваренная нормальная форма.

Примеры:

1. Приведение к нормальной (приведенной) форме.

2. Приведение к предваренной нормальной форме (пнф).

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

§ 12. Общезначимость и выполнимость

Определение 1. Формула    F     логики предикатов называется выполнимой в области М, если существуют значения переменных, входящих в эту формулу и отнесенных к области М, при которых формула   F    принимает истинные значения

Определение 2. Формула    F     называется выполнимой если существует область, на которой эта формула выполнима.

Из определения 2 следует, что если формула выполнима, то это еще не означает, что она выполнима в любой области.

Определение 3. Формула    F     называется тождественно истинной в области М, если она принимает истинные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.

Определение 4. Формула    F     называется общезначимой, если она тождественно истинная на любой области.

Определение 5. Формула    F     называется тождественно ложной в области М, если она принимает ложные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.

Из определений следует:

1. Если    F     общезначима, то она и выполнима на любой области.

2. Если формула    F     тождественно истинная в области М, то она и выполнима в этой области.

3. Если формула   F     тождественно ложная в области М, то она не выполнима в этой области.

4. Если формула    F     не выполнима, то она тождественно ложна на всякой области.

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

Пример 1. Формула    F = выполнима. Действительно, если предикат, определенный в области , где , то формулатождественно истинная в областиМ.

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

Пример 2. Формула      выполнима. Пусть– предикат “числох –четно”, определенный в области , где, то формула тождественно истинная в областиМ. Однако, если предикат “число х – четно” рассматривается в области

    ,где -множество, и, следовательно, невыполнимой.

Пример 3. Формула тождественно истинна в любой областиМ. Значит является общезначимой, т.е. является логическим законом( закон исключенного третьего).

Пример 4. Формула тождественно ложная в любой областиМ, поэтому не выполнима.