Определение 1. Формула А логики
предикатов называется выполнимой
в области М, если
существуют значения переменных входящих в эту формулу и отнесенных к области М
(иначе – существует модель), при которых формула А принимает истинные значения.
Определение 2. Формула А логики
предикатов называется выполнимой, если существует область, на которой эта
формула выполнима.
Определение 3. Формула А логики
предикатов называется тождественно-истинной
в области М (выполнимой),
если она принимает истинные значения для всех значений переменных, входящих в
эту формулу и отнесенных к этой области.
Определение 4. Формула А логики
предикатов называется общезначимой, если она тождественна истинна на всякой
области (на любой модели).
Общезначимость формулы логики предикатов, например, F
обозначается ├F. Все общезначимые формулы могут быть источниками
новых ├ формул.
Определение 5. Формула А логики
предикатов называется тождественно
ложной в области М, если она принимает ложные
значения для всех значений переменных, входящих в эту формулу и отнесенных к
этой области (иными словами, на данной модели).
Определение 6. Формула А логики
предикатов называется тождественно
ложной (невыполнимой), если она тождественно ложна на всякой области (на
всякой модели).
Например, формула
является тождественно
ложной (невыполнимой) формулой логики предикатов.
Из
приведенных определений с очевидностью следует:
1. Если формула А общезначима, то она и выполнима на всякой области (модели).
2. Если формула А тождественно истинна в области М, то она и выполнима в
этой области .
3. Если формула А
тождественно ложна в области М, то она не выполнима в этой области .
4. Если формула А не выполнима, то она
тождественно ложна на всякой области (на всякой модели).
5. Для того, чтобы
формула А логики предикатов была общезначима, необходимо
и достаточно, чтобы ее отрицание было не выполнимо.
6. Для того, чтобы
формула А логики предикатов была выполнимой, необходимо
и достаточно, чтобы формула
была не общезначима.
В связи с данными определениями
естественно выделить два класса логики формул предикатов: выполнимых и не
выполнимых формул.
Заметим, что общезначимую формулу
называют логическим
законом.
Приведем соответствующие примеры:
1. Формула
выполнима.
2. Формула
тождественно истинна в любой области М. Значит, она является
общезначимой, т. е. является логическим законом (закон исключенного третьего).
3. Формула
тождественно ложна в
любой области М, и поэтому она не выполнима.
Легко установить связь между общезначимостью и выполнимостью формул логики предикатов.
Теорема 1. Для того, чтобы формула
А была общезначима, необходимо и достаточно, чтобы её отрицание было не
выполнимо.
Теорема 2. Для того, чтобы формула
А была выполнимой, необходимо и достаточно, чтобы её отрицание было не общезначимо.