Т. А. Сливина математическая логика и теория алгоритмов

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


§ 4. Общезначимость и выполнимость формул. Проблема разрешимости для общезначимости и выполнимости, неразрешимость ее в общем случае

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

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

1. 
   Если формула А общезначима, то она и выполнима на всякой области.
   
2. 
   Если формула А тождественно истинная в области М, то она и выполнима в этой области.
   
3. 
   Если формула А тождественно ложная в области М, то она не выполнима в этой области.
   
4. 
   Если формула А не выполнима, то она тождественно ложна на всякой области.
   

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