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

Пример 1. Формула выполнима. Действительно, если Р(х,у) – предикат «х < у», определенный в области М = ЕЕ, где Е = {0,1,2,...,n,...}, то формула тождественно истинная в области М, и, следовательно, выполнима в этой области. Однако, если предикат «х < у» рассматривается в конечной области M₁ = Е₁E₁, где E₁ = {0,1,2,..., k, то формула будет тождественно ложной в области M₁, и, следовательно, не выполнима в области М₁. При этом ясно, что формула не общезначима.
Пример 2. Формула выполнима.
Действительно, если Р(х) – предикат «Число х – четно», определенный в области М = ЕЕ, где Е= {0, 1, 2, ..., n,..., то эта формула тождественно истинная в области М, и, следовательно, выполнима в области М. Однако, если предикат «Число х – четно» рассматривать в области M₁ = Е₁E₁, где Е₁ – множество четных чисел, то формула будет тождественно ложной в области М₁, и, следовательно, не выполнимой.
Пример 3. Формула \ тождественно истинная в любой области М. Значит, она является общезначимой, то есть является логическим законом (закон исключенного третьего).
Пример 4. Формула тождественно ложная в любой области М, и поэтому она не выполнима.
Cвязь между общезначимостью и выполнимостью формул логики предикатов устанавливается с помощью следующих теорем.
Теорема 1. Для того, чтобы формула А была общезначима, необходимо и достаточно, чтобы ее отрицание было не выполнимо.
Доказательство. Необходимость. Пусть формула А общезначима. Тогда, очевидно, – тождественно ложная формула в любой области, и поэтому формула не выполнима.
Достаточность. Пусть формула не выполнима в любой области. Тогда по определению невыполнимой формулы - тождественно ложная в любой области. Значит, формула А - тождественно истинная формула в любой области, и, следовательно, она общезначима.