Учебное пособие Владивосток Издательский дом Дальневосточного федерального университета 2013 ббк 22. 12 К 93

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

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. Формула тождественно ложная в любой области М, поэтому не выполнима.