1 Кубенский А.А. Дискретная математика. Глава 2. Элементы математической логики Исчисление предикатов Распространяем понятие логической формулы на объекты, отличные от истинностных значений И и Л. Строим формулы из элементарных объектов предметной области. константыa, b, c, … переменныеx, y, z, … функции разной арностиf, g, +, … Терм – константа, переменная или применение функции к термам, например: a + bf (g (x + 1), x) предикаты разной арностиP, Q,

2 Кубенский А.А. Дискретная математика. Глава 2. Элементы математической логики Логическое следствие и эквивалентность Понятия логического следствия и эквивалентности формул можно перенести в исчисление предикатов: Формула B является логическим следствием формулы A, если в любой интерпретации, в которой истинна A формула B также истинна. A B Формулы A и B эквивалентны, если A B и B A. Для эквивалентного преобразования формул можно, помимо уже имеющихся эквивалентностей, использовать следующие: 1. x( F(x)) x(F(x)) x( F(x)) x(F(x)) 3. x(F(x) G(x)) x(F(x)) x(G(x)) x(F(x) G(x)) x(F(x)) x(G(x)) 4. x(F(x) G(x)) x(F(x)) x(G(x)) x(F(x)) x(G(x)) x(F(x) G(x)) 2. x y (F(x, y)) y x (F(x, y)) x y (F(x, y)) y x (F(x, y)) Заметьте, что следующие формулы НЕ эквивалентны, и ни одна из них НЕ является следствием другой: x y (F(x, y)) y x (F(x, y)) и Пример: x y (x < y) x y ( (x y)) x ( y (x y)) x ( y (x y)) здесь все формулы истинны в стандартной арифметической интерпретации; однако формула y x (x < y) - ложна.