Лекция №11. Тема: логика предикатов.

Предикат – функция область изменения (задания), которой есть набор значений каких-либо переменных аргументов х₁... х_n, а область значений состоит из двух понятий: «ложь, истина».

 

Чтобы задать n местный предикат P(x₁, x₂, … x_n) следует указать множество X₁, X₂, …, X_n области изменения переменных x₁, x₂, … x_n. Множество точки зрения предикат определяется заданием подмножества m в декартовом произведении:

M x_1* x_2* … _*x_n.

Итак, к-местный предикат P^k(x₁, x₂, … x_n) есть функция переменные которой принимают разные значения из некоторого множества M^k, а сама она принимает только два значения: истинно (1) или ложь (0), т.е.

P^k(x₁, x₂, … x_n)

M^k → {1;0}

 

Чтобы задать к-местный предикат следует задать множество (x₁… x_n), где х_i есть область изменения переменных (x₁, x₂, … x_k).

Предикат называется разрешенным, если существует такие наборы конкретных элементов х_i, который превращает предикат в истинное высказывание, т.е.

P(x₁, x₂, … x_к) = 1.

 

Предикаты могут быть:

· Нульместные, т.е. в множестве х_i нет не одного элемента P₀=(0)

· Одноместные, т.е. в множестве только одна переменная Р₁=(x₁)

· Двуместные, т.е. в множестве содержатся две переменные.

 

 

Также могут применяться операции алгебры логики:

§ конъюнкция

§ дизъюнкция

§ импликация

§ эквиваленция

§ отрицание

 

Например, множество (x₁, x₂, х₃) и существует предикат (P₁, Р₂).

 

 

Лекция №12. Тема: Кванторы.

 

1. Квантор общности Ұ – «любое, для каждого»

Ұ х (Z(x)) – для любого х существует Z(x).

2. Квантор существования - «существует»: (Z(x))

Например, «для каждого х существует y, равный х²» записывается так:

Ұх (y = х²).

Переменная, к которым относиться квантор называется связанным.

Примеры применения кванторов:

1) х*х = х² Ұ (х)(х*х = х²) = истинно (1)

2) х+2 = 7 Ұ (х)(х+2 = 7) = ложь (0)

 

Пусть A и B формулы алгебры логики, причем нет таких переменных, которые были бы связанны в одной формуле и свободны в другой, тогда:

A = x₁ x₂ x₃, B = x₁ x₂ x₃

(A B), (A B), (A → B), (A ↔ B) – тоже формулы.

 

Правила переходов от одних формул к другим:

o перенос квантора через отрицание. Пусть А – формула, где х – свободная переменная, тогда

_ _ _

Ұх (А(х)) ≡ х (А(х))

_ _

х (А(х)) ≡ Ұх (А(х))

 

Перенос квантора через отрицание.

________ ___

(Ұх)(Ұ(х)) ≡ ( х)V(х)

____

х(V(х)) ≡ (Vх)(V(х))

 

Вынос квантора за скобки:

( х)(V(х) B) ≡ х(V(х)) B

( х)(V(х) B) ≡ ( х)(Vх) B

(Vх)(V(х) B) ≡ (Vх)(V(х)) B

(Vх)(V(х) B) ≡ (Vх)(V(х) B)

 

 

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

В исчислении предикатов указывается некоторая совокупность формул, которые называются аксиомами и составляют аксиоматическую теорию, а также указывается конечное множество отношений между формулами, составляются правила вывода.

 

 

Аксиомы исчисления:

1) А → (B → А)

2) (А→ (B → C)) → ((А → B) → (A → C)

_ _ _

3) (B → А) → ((B → А) → (A → C))

4) (V x₁)A(х_i) → A(х_j), где A(х_i) не содержит x_j

5) A(х_i) → ( x_j) A(х_i), где A(х_i) не содержит x_j