Алгебра предикатов билеты

О: Пусть задана некоторая область U – предметная область.
Пусть заданы некоторые переменные x1,x2,..xn, которые называются предметными. Тогда n – местным предикатом P(x1,x2,..xn) мы будем называть отображение мн-ва эл-тов предметной области в множество высказываний.
x1,x2,..,xnU => P(x1,x2,..,xn) - высказывание.
О: 1) (P, U) – называется тождественно истинным, если все прообразы P-1({1})=U
1) (P, U) – называется тождественно ложным, если все прообразы P-1({0})=U
Операции над предикатами
Над множеством предикатов можно ввести те же операции, что и в АВ
P(x1, x2,.., xn), Q(x1, x2,.., xn), U
По опр.:
1) (P)( x1,x2,..xn) =
2) (PQ)( x1,x2,..xn )= P(x1,x2,..xn)Q(x1,x2,..xn)
3) (PQ)( x1,x2,..xn) = P(x1,x2,..xn)Q(x1,x2,..xn)
Т.: Множество n-местных предикатов на предметной области U образует булеву алгебру предикатов (выполняются 19 основных равносильностей):
0.

Змч.:  формула в АВ Ф(x1,.., xn) от n-переменных также является n-местным предикатом. Сами высказывания также можно считать 0-местными предикатами.
Кванторы
Кванторы – это операции понижающие местность предикатов.
Опр. Пусть P(x)- одноместный предикат (). Тогда определим по нему высказывание x P(x) – истина <=> P(x)=1
Опр. Пусть P(x)- одноместный предикат. Определим по нему высказывание x P(x) – ложно <=> P(x)=0
Заметим, что операции кванторы связаны с обычными операциями над предикатами, а именно, если ={ x1,x2,..,xn }, то xP(x)≡P(x1)P(x2)….. P(xn) (P(x)-одноместный предикат)
Аналогично xP(x)≡P(x1) P(x2) ….. P(xn).
Далее, зная операцию фиксации переменных можно определить (n-1) – местный предикат
xiP(x1,x2,.. xi-1,xi,..,xn) и  xiP(x1,x2,.. xi-1,xi,..,xn) по любому конечному предикату на 
xjxiP (x1,x2,..,xn), xixiP(x1,x2,..,xn),
 xj xiP (x1,x2,..,xn), xixiP(x1,x2,..,xn)
D(x1,x2)={натуральное число x1 делится без остатка на натуральное число x2}, =N
x1 D(x1,x2)-каждое натуральное число x1 делится без остатка на натуральное число x2 (переменная x2)

Powered by Drupal - Design by artinet