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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Предикат B(x
1
,x
2
,...,x
n
) называется следствием предиката
A(x
1
,x
2
,...,x
n
), если B(x
1
,x
2
,...,x
n
) удовлетворяется любыми
аргументами, удовлетворяющими A(x
1
, x
2
,...,x
n
).
Пример 2.7. Предикат "n делится на 3" есть следствие предиката "n
делится на 6", где n - целое число.
Два n-местных предиката, определенные на одних и тех же
множествах, равносильны тогда и только тогда, когда каждый из них
является следствием другого.
Предикат называется
а) тождественно истинным, если значение его для любых
аргументов есть "истина";
б) тождественно ложным, если значение его для любых аргументов
есть "ложь";
в) выполнимым, если существует, по крайней мере, одна n-система
его аргументов, для которой значение предиката есть "истина".
Пример 2.8. Предикат "x + y = y + x" является тождественно
истинным, предикат "x + 1= x" – тождественно ложным, предикат "x + y = 5" –
выполнимым.
Каждый тождественно истинный предикат является
выполнимым, но обратное неверно. Каждый выполнимый предикат
будет не тождественно ложным и обратно, каждый не тождественно
ложный предикат будет выполнимым.
Каждому n-местному предикату A(x
1
, x
2
,...,x
n
), определенному
на множествах M
1
,M
2
,...,M
n
соответствует n-отношение R,
являющееся подмножеством декартова произведения M
1
× M
2
× ... ×
M
n
и равное множеству истинности этого предиката
R = { (x
1
, x
2
,...,x
n
) ⎟ A(x
1
, x
2
,...,x
n
) }.
Обратно, каждому n-отношению R между элементами множеств
M
1
,M
2
,...,M
n
соответствует предикат, множество истинности
которого есть R.
104

Страницы