Математическая логика и теория алгоритмов. Анкудинов Г.И - 22 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

Импликацией предикатов A(x
1
,x
2
,...,x
n
) и B(x
1
,x
2
,...,x
n
)
называется предикат
I(x
1
,x
2
,...,x
n
) = A(x
1
,x
2
,...,x
n
) → B(x
1
,x
2
,...,x
n
),
который имеет значение ЛОЖЬ на тех и только на тех наборах
аргументов x
1
,x
2
,...,x
n
, на которых A(x
1
,x
2
,...,x
n
) имеет значение
ИСТИНА, а B(x
1
,x
2
,...,x
n
) - значение ЛОЖЬ.
Пусть M(A), M(B) и M(I) множества истинности A(x
1
,x
2
,...,x
n
),
B(x
1
,x
2
,...,x
n
) и I(x
1
,x
2
,...,x
n
), тогда M(I) =
(
)
AM
∪ M(B), где
(
)
AM
-
дополнение множества M(A).
Эквивалентностью предикатов A(x
1
,x
2
,...,x
n
) и B(x
1
,x
2
,...,x
n
)
называется предикат
E(x
1
,x
2
,...,x
n
) = A(x
1
,x
2
,...,x
n
) ↔ B(x
1
,x
2
,...,x
n
),
который имеет значение истина на тех и только на тех наборах
аргументов x
1
,x
2
,...,x
n
, на которых значения истинности A(x
1
,x
2
,...,x
n
)
и B(x
1
,x
2
,...,x
n
) совпадают. Множество истинности M(E) для
эквивалентности предикатов A(x
1
,x
2
,...,x
n
) ↔ B(x
1
,x
2
,...,x
n
) есть
M(E) = [
()
AM
∩
(
)
BM
] ∪ [M(A) ∩ M(B)].
Пример 2.9. Даны универсальное множество M = {a,b,c,d,e,f} и два
подмножества L = {b,c,d} и K = {d,e,f}, и два предиката A(x) и B(x), причем
{x⎟A(x)=И}=L и {x⎟B(x)=И}=K, т.е. L и K являются множествами истинности
предикатов A(x) и B(x) соответственно. Требуется найти множество истинности
эквивалентности E(x)=A(x)↔⎤B(x).
Для решение этой задачи используем определение эквивалентности
предикатов:
{x⎟E(x)=И} = (⎯L∩ K) ∪ (L ∩⎯K) =
({a,e,f} ∩ {d,e,f}) ∪ ({b,c,d} ∩ {a,b,c}) =
{e,f} ∪ {b,c} = {e,f,b,c}.
2.4. Логические операции квантификации
Пусть A(x) – одноместный предикат, определенный на
множестве M. Универсальным высказыванием, соответствующим
106

Страницы