Математическая логика и теория алгоритмов. Стенюшкина В.А. - 34 стр.

      11 Интерпретация исчисления предикатов

      11.1  Интерпретация        исчисления     предикатов     в    алгебру
      высказываний

      Интерпретация ИП в алгебру высказываний определяется заданием мно-
жества M - области интерпретации и последующим приписыванием в качестве
значений:
      ─ каждой предметной константе и каждой свободной переменной кон-
кретного элемента из M;
      ─ каждой n – местной предикатной или функциональной переменной
конкретного n – местного предиката или соответственно функтора на M;
      ─ каждой связке и каждому квантору – соответствующих логических
операций ( с сохранением приоритета).
      В результате интерпретации формула становится высказыванием, истин-
ностное значение которого вычисляется в соответствии со структурой формулы
и определением логических операций.
      Формула называется истинной в данной интерпретации, если соответст
вующее ей высказывание истинно; ложной – в противном случае.
      Заметим, что истинностное значение формулы зависит от выбора множе-
ства M. Так, формула (∃x1Р(x1)→∀x2Р(x2)) истинна во всех интерпретациях, где
M - одноэлементное множество, и не во всех, в противном случае.

      11.2 Равносильности

      Две формулы ИП называются равносильными, если они имеют одинако-
вые истинностные значения во всех интерпретациях. Запись: F = G («F равно-
сильно G»).
      Имеет место следующие равносильности:
      1) ∀x F(x) = ∃ x  F(x) ,  ∀ x F(x)= ∀ x  F(x);
      2) ∀x(F(x) ∧ G(x)) = ∀xF (x) ∧ ∀xG(x), ∃x(F(x) ∨ G(x))=∃F(x) ∨ ∃xG(x);
      3)∀x ∀y F(x, y) =∀y ∀ x F(x, y), ∃ x ∃y F(x, y)= ∃y∃ x F(x, y);
      4)∀x (F(x)∧С) = ∀x F(x) ∧ С, ∀x (F(x) ∨ С)= ∀x F(x) ∨ С;
      5)∃x (F(x)∧С) = ∃ x F(x) ∧ С, ∃ x (F(x) ∨ С) = ∃ x F(x) ∨ С;
      6)С → ∀x F(x) = ∀x ( С → F(x)), С→ ∃ x F(x) = ∃ x (С → F(x)).
      Эти равносильности называются также законами логики предикатов. Фо-
рмула С не содержит вхождений переменной x.
      Применяются, как и прежде. синтаксические сокращения: F↔G: = (F→
G) ∧ (G→ F), F→ G: =  F∨ С.
      Раннее отмеченные законы F=F, (F∨С)=F∧G, (F∧G)= F∨G здесь
тоже имеют место и используются.
      С помощью равносильностей можно преобразовывать формулы.