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

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