![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Предикат есть функция, определенная на некотором множестве и принимающая одно из двух значений: истина (И) или ложь (Л).
Из простых предикатов с помощью логических операций можно строить и более сложные предикаты.
Пусть P (x 1 ,…,xk)- предикат, определенный на множестве D; é P ùозначает множество истинности предиката Р, т.е. множество всех наборов (a 1 ,…,ak) длины k элементов множества D, на которых предикат Р принимает значение И.
Пусть Р(x 1 ,…,xk) и R(x 1 ,…,xk) - два предиката, определенных на множестве D. Тогда é Р ù é R ù, é P ùé R ù, D k \ é Р ù есть множества истинности предикатов
Р V R, Р & R, ù Р соответственно.
Пусть P(x,x 1 ,…,xk) есть (k+1)-местный предикат, определенный на множестве D. Запись ($ х) Р(х,х1,...,хk) будем понимать как "существует такой элемент х из D, для которого P(x,xl,...,xk) истинно"; ("x) P (x,x 1 ,…,xk) - "для всех х из D P(x,xl,...,xk) истинно". Скажем, что предикаты
Q(xl,...,xk) = ($ х)Р(x,x 1 ,…,xk),
R (x 1 ,…,xk) = (" х)Р(x,x 1 ,…,xk)
получены из предиката P(x,x1,...,xk) навешиванием квантора соответственно существования и общности на предикат P(x,xl,...,xk) по переменной х. Переменная х в выражении (Qx)P(x,xl,...,xk) находится в области действия квантора (Qx). Навешивание квантора существования или квантора общности по некоторой переменной на (k+l)-местный предикат, содержащий эту переменную, приводит к другому предикату, местность которого на единицу меньше.
Переменная х, находящаяся в области действия квантора (Qx), называется связанной. В противном случае переменная х свободна.
Пример. D = {0,1,2,...} - множество натуральных чисел. Определим на множестве D следующие предикаты:
Рr(х) - х есть простое число;
Ev(x) - число х четно;
Div(x,y) - число х делит число у;
х = у - число х равно числу у;
х £ у - число х меньше или равно числу у;
х = 2 - число х совпадает с двойкой;
Q(x,y) есть ù (х = 1) & ù (x = у) & Div(x,y);
Р(у) есть ($ x) Q (x, y).
Тогда ($ х)Рr(х) - истинное, (" х)Рr(х) - ложное, Р (2) - ложное, Р(4) - истинное высказывания.
Пусть D = {a l ,a 2 ,...,ak} - конечное множество из k элементов и Р(х) - предикат, определенный на D.
Утверждение. Справедливы следующие равенства:
($ x) Р (x) = Р (a 1) V Р(а2) V... V P(ak).
(" x) Р (х) = P (a 1) & Р(а2) &... & P(ak).
Доказательство. Установим первое равенство. Пусть ($ х) Р(х) истинно. Тогда существует х = аi Î D, для которого P (а i) истинно. Отсюда P(a 1 ) V... V P(ak) истинно.
Пусть Р(a 1 ) V... V P(ak) истинно. Тогда для некоторого i, 1 £ i £ k, P (ai) истинно; поэтому существует x = а i Î D, для которого Р (аi) истинно, отсюда
($ х)Р(х) истинно.
Установим второе равенство. Пусть (" х)Р(х) истинно. Тогда для всякого х из D Р(х) истинно, т.е. истинны P(a 1 ),...,P(ak), откуда истинно P(a 1 ) &... & P(ak). Пусть теперь P(a 1 ) &... & P(ak) истинно, т.е. истинны Р(а 1 ),...,P(ak). Отсюда получаем, что для всякого x из D Р(х) истинно, т.е. (" х)Р(х) истинно.
Утверждение доказано.
Аналогично доказываются следующие равенства.
($ x)P(x,x 1 ,...,xk) =
(" x)P(x,x 1 ,...,xk) =
Переменная х может стоять на любом аргументном месте предиката Р. Если кванторов несколько, то они элиминируются (устраняются) постепенно. Например,
(" x)($ y) P (x,y)=("x)(
Замечание. Пусть D есть некоторое множество и множество К Í D n. Проекция К на оси i1,...,ip есть множество
Проекция множества К на оси il,...,ip может быть получена вычеркиванием (стиранием) во всех наборах (x1,...,,...,,... ,хn) из К всех координат, кроме
Пусть P (x 1 ,…,xk,x) - (k+1)-местный предикат, определенный на множес-тве D. Пусть k -местный предикат
Q (x 1 ,…,xk) = ($ x) P (x 1 ,…,xk,x).
Пусть é P ù = {(x 1,... ,xk,x) Î Dk+1: P(x 1 ,...,xk,x) истинно} и é Q ù = {(x 1,…, xk) Î D k: Q (x 1,…, xk) истинно} есть множества истинности предикатов Р и Q. Тогда é Q ù= é P ù.
Таков теоретико-множественный смысл квантора существования.
Дата публикования: 2015-01-23; Прочитано: 314 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!