lec11

Пусть Р(x1, x2, … xi, … xn) – n-местный предикат, определённый на S2, зафиксируем в нем значения переменных (x1, x2, … xi-1, xi+1, … xn).

На полученный одноместный предикат Q(xi) навесим квантор всеобщности (или существования) и получим высказывание.

Сопоставление любому набору (x1, x2, … xi-1, xi+1, … xn) значений переменных вполне определённого высказывания – это предикат от (n–1) переменных. Говорят, что это (n–1)-местный предикат получен из исходного предиката Р(x1, x2, … xi, … xn) навешиванием квантора всеобщности (или существования) по xi и обозначают

xi P(x1, x2, … xi-1, xi+1, … xn).

Об xi говорят, что она связана квантором всеобщности.

11

Индуктивная формула исчисления предикатов.

Определение терма:

1)Всякая предметная переменная или предметная константа.

2)если f – функция и η1, η2, … , ηn – термы, то f(η1, η2, … , ηn) – терм.

3)Выражение является термом только, если это следует из правил 1) и 2).

Если Р – предикат, а η1, η2, … , ηn – термы,

то Р(η1, η2, … , ηn) – элементарная формула или атом.

Определение формулы:

1)Всякая элементарная формула является формулой.

2)Если А и В – формулы и х – предметная переменная, то каждое из выражений А о- В; x А(x); x А(x); А (где о- логическая операция) является формулой.

3)Выражение является формулой в том и только в том случае если это следует из правил 1) и 2).

В выражении x А(x) формула А(х) – область действия квантора x.

12

Предметная переменная, входящая в формулу называется свободной если она не следует непосредственно за квантором и не входит в область действия квантора по этой переменной. Все другие переменные, входящие в формулу называются связанными.

В пределе всякая формула без свободных переменных (замкнутая формула) является высказыванием, которое истинно или ложно, а всякая формула со свободными переменными задаёт некоторое отношение в предметной области. Это отношение может быть истинно или ложно в зависимости от значений свободных переменных.

Каждая формула F(P1, … Pm, x1, … xn) в исчислении предикатов задаёт оператор, перерабатывающий систему предикатов P1, … Pm в предикат Pa

x1, … xn, где все эти переменные в формуле являются

Две формулы, которые задают один и тот же предикат будем называть

эквивалентными или равносильными.

13

Закон де Моргана для кванторов (двойственность):

( x Р(x)) ≡ x (Р(x))( x Р(x)) ≡ x Р(x))

Коммутация одноименных кванторов:

x y Р(х,у) ≡ y x Р(х,у)x y Р(х,у) ≡ y x Р(х,у)

Дистрибутивные законы для кванторов:

x (Р(x) Q(x)) ≡ x Р(x) x Q(x)x (Р(x) Q(x)) ≡ x Р(x) x Q(x)

15

Законы ограничения действия для кванторов:

Пример 11.3. Навешивание кванторов на переменные предиката.

D(x1,x2) = “Натуральное число х1 кратно натуральному число х2”. Навесим последовательно на его переменные кванторы:

Пример 11.4. Равносильные преобразования в исчислении предикатов.

x (Р(х) Q(х)) ( x Р(х) x Q(х)) ≡

≡( x ( Р(х) Q(х))) ( ( x Р(х)) x Q(х)) ≡

≡x (Р(х) Q(х)) ( x Р(х)) x Q(х)) ≡

≡x ((Р(х) Р(х)) ( Q(х) Р(х))) x Q(х) ≡

17

Другой способ позволяющий получать предложения состоит в подстановке констант на место свободных вхождений переменных.

Подстановочное множество (или подстановка) есть множество Θ:

Θ = {U1/ƍ1, U2/ƍ2, … , Un/ƍm}

где Ui и ƍi, 1≤i≤n, являются соответственно переменными и термами, причём равенство Ui=Uj влечёт ƍi=ƍj, 1≤i≤j≤m.

Если ω есть какое-либо выражение (атом, терм или формула) то ωΘ обозначает выражение, полученное путём подстановки на места свободных вхождений переменных U1, U2, … , Un соответствующих термов ƍ1, ƍ2, ... ,ƍm.

Пустая подстановка обозначается символом Е={}.

18

Пример 11.4. Композиция подстановок.

Θ = {x/f(y), y/z} Ψ = {x/a, y/b, z/y)

Θ•Ψ = {x/f(y)ψ, y/zψ, x/a, y/b, z/y} – {Ui/ƍiψ : Ui = ƍiψ} – {ϑi/ti : ϑi {U1,U2,… Un}}) = = {x/f(b), y/y, x/a, y/b, z/y} – {y/y} – {x/a, y/b}) = {x/f(b), z/y}

Cвойство ассоциативности подстановок.

Для произвольных подстановок Θ, Ψ, ϒ и для произвольных термов выполняется равенство:

1.Θ•Е = Е•Θ = Θ.

2.(tΘ)Ψ=t(Θ•Ψ).

3.(Θ•Ψ)•ϒ = Θ•(Ψ•ϒ).

20