3.7. Общезначимость и выполнимость формул

 

 

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

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

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

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

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

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

Определение 6. Формула А логики предикатов называется тождественно ложной (невыполнимой),  если она  тождественно ложна на всякой области (на всякой модели).

Например, формула  является тождественно ложной (невыполнимой) формулой логики предикатов.

Из приведенных определений с очевидностью следует:

1. Если формула А общезначима, то она и выполнима на всякой области (модели).

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

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

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

5. Для того, чтобы формула А логики предикатов была общезначима, необходимо и достаточно, чтобы ее отрицание было не выполнимо.

6. Для того, чтобы формула А логики предикатов была выполнимой, необходимо и достаточно, чтобы формула  была не общезначима.

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

Заметим, что общезначимую формулу называют логическим законом.

Приведем соответствующие примеры:

1. Формула  выполнима.

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

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

Легко установить связь между общезначимостью и выполнимостью формул логики предикатов.

Теорема 1. Для того, чтобы формула А была общезначима, необходимо и достаточно, чтобы её отрицание было не выполнимо.

Теорема 2. Для того, чтобы формула А была выполнимой, необходимо и достаточно, чтобы её отрицание было не общезначимо.