Операции над предикатами

Определение предиката.

Операции над множествами.

Основные понятия Теории множеств.

Логика предикатов.

Логика предикатов базируется на теории множеств. Основы теории множеств разработал немецкий математик Георг Кантр в 70-ых годах XIX века.

Множество – система, образующаяся из элементов, обладающих некоторыми свойствами и находящихся в некоторых отношениях между собой или с элементами других множеств. Альтернативные названия множеств: класс, совокупность, система.

Множество, не имеющее ни одного элемента, называется пустым множеством.

Знаки отношений между множествами: ∉, ∈, \, ⋂, ∪

Множество обозначается либо буквами, либо перечислением элементов этого множества в фигурных скобках.

Конечное множество N можно задавать перечислением его элементов, при этом порядок записи элементов не существенен.

	A = {a1, a2, … an}; n = 3; M = {a, b, c}; M = {b, c, a};

M = {x:x обладает свойством C}

Любое множество можно так же задавать указанием общего свойства его элементов.

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

· Дополнение L множества M:

L = { x | x ∈ M, x ∉ L}

В мат. логике аналогом дополнения является отрицание.

· Пересечение подмножеств M₁ и M₂ множества M называется совокупность L.

L₁ = M1 ⋂ M2 = {x | x ∈ M, x ∈ M₂}

·

L₁ = M1 ∪ M2 = { x | x ∈ M₁ vx, п. M₂}

Объединение подмножеств M1 и M2:

· Вычитанием множеств называется:

	L = M1 \ M2 = { x | x ∈ M1 и x ∉ M2 }

Примеры:

L = M₁ ∪ M₂ = (M₁ – M₂) ∪ (M₂ \ M₁) ∪ (M₁ ⋂ M₂);

Предикат – выражение, имеющее грамматическую форму высказывания, но содержащее предметные переменные некоторых множеств.

Пример:

«8 – четное число» – является высказыванием

x < 2 5 < 2 -- “0” a + b > 5 a = 1, b = 2 1+2 > 5 – “0”  

«x – четное число» – является предикатом.

P – предикат, P – зависит от N переменных: P = {x_1, x₂, …, x_n} P = P⁽ⁿ⁾(x) (n) – местность предиката. P⁽³⁾(x) = {x₁, x₂, x₃};  

N – местный предикат – предикат, содержащий в себе N переменных.

Два N-местных предиката, определённых на одних и тех же множествах M_1, M₂, …, M_n называются равносильными, если значения их для любых аргументов совпадают. То есть они имеют одно и то же множество истинности.

P₁ = x > 2 P₂ = x – 2 > 0 P₁ ≡ P₂  

Пример равносильных предикатов:

Предикат называется:

a) Тождественно истинным, если значение его для любых аргументов есть истина.

b) Тождественно ложным, если значение его для любых аргументов есть ложь.

c) Выполнимым, если существует хотя-бы одна n-система его аргументов, для которой значение предиката есть истина.

· Все логические операции над высказываниями

· Кванторные операции:

o Квантор всеобщности: ∀

o Квантор существования: ∃

Предикат A(x₁, x₂, …, x_n) можно рассматривать как логическую функцию, определённую на множестве M₁ x M₂ x M₃ x … x M_n и принимающую значения {И, Л};

Рассмотрим предикаты A(x₁, …, x_n), B (x₁, …, x_n) определённые на M₁ x … x M_n:

{(x₁, x₂, …, x_n) | Aч(x₁, x₂, …, x_n) = M₁ x M₂ x … x M_n \ { (x₁, x₂, …, x_n) | A(x₁, x₂, …, x_n) }

Отрицанием предиката A(x₁, x₂, …, x_n) называется новый предикат ⌐A(x₁, x₂, …, x_n), множество истинности которого является дополнением множества истинности предиката A(x₁, x₂, …, x_n).

Там, где предикат A – истинный, предикат ⌐A – ложный.

Конъюнкцией предикатов называется предикат:

C(x₁, x₂, …, x_n) = A(x₁, x₂, …, x_n) & B(x₁, x₂, …, x_n).

Дизъюнкцией предикатов называется предикат:

С(x₁, x₂, …, x_n) = A(x₁, x₂, …, x_n) v B(x₁, x₂, …, x_n).

Импликацией предикатов A и B называется предикат I:

I(x₁, x₂, …, x_n) = A(x₁, x₂, …, x_n) → B(x₁, x₂, …, x_n)

Эквивалентностью предикатов называется предикат E(x₁, x₂, …, x_n), который имеет значение истины на тех и только на тех наборах аргументов (x₁, x₂, …, x_n), на которых значения истинности предикатов A(x₁, x₂, …, x_n) и B(x₁, x₂, …, x_n) совпадают:

E(x₁, x₂, …, x_n) = A(x₁, x₂, …, x_n) ≡ B(x₁, x₂, …, x_n).

Дата добавления: 2014-01-05