Читайте также:
|
|
Логические операции квантификации не имеют аналогов в алгебре высказываний. Программа предусматривает изучение операций квантификации квантором общности (или всеобщности) , а также, квантором существования .
Если A(x) – одноместный предикат, определенный на множестве М, то с помощью кванторов можно построить высказывания xA(x) (читается «для всех xA(x)») и xA(x) (читается «существует х, такое что A(x)»). Первое из них называют универсальным, а второе – экзистенциональным.
Универсальное высказывание истинно тогда и только тогда, когда A(x) - тождественно истинный предикат, а экзистенциональное высказывание истинно только тогда, когда A(x) - выполнимый предикат.
Примеры. Высказывание x(x2≥0) – истинно, а x(x2-3x+2=0)- ложно, так как предикат x2>0–тождественно истинный, а предикат x2-3x+2=0 таковым не является. Высказывание x(x2-3x+2=0)истинно, а x(x2=-1) – ложно.
Следует обратить внимание на то, что если предикат A(x) определен на конечном множестве {a1,a2,...,an}, то универсальное высказывание xA(x) равносильно высказыванию A(a1) A(an), а экзистенциональное высказывание x A(x) равносильно высказыванию A(a1) A(an).
При квантификации n–местного предиката A(x1,…,xn), определенного на множествах M1,…,Mn, квантором общности по переменной xi, 1≤x≤n, получаем (n-1)-местный предикат xi A(xi,…,xn), зависящий от переменных
x1,..,xi-1,xi+1,…,xn. Значение предиката xi A(xi,…,xn) от набора значений переменных < α1,.., α i-1, α i+1,…, α n > совпадает со значением универсального высказывания xi A(α1,.., α i-1, xi, α i+1,…, α n)
Пример. Пусть A(x,y)=(xy=0). Квантификация данного предиката по переменной x дает одноместный предикат B(y)= xA(x,y). B(3)= xA(x,3)= x (x×3=0)=0, B(0)= x(x×0=0)=1. Таким образом, квантификация двуместного предиката xy=0 квантором общности по переменной x дала одноместный выполнимый предикат, зависящий от у.
Если A(x,y,z)=(x2+y2+z2=1), то y(x2+y2+z2=1)=C(x,z) – двуместный предикат, зависящий от x,z. нетрудно увидеть, что C(x,z) - тождественно ложный предикат. В самом деле, для любых фиксированных значений x=α, z=β предикат α2+y2+β2=1 одноместный не тождественно истинный. Квантификация его по переменной у квантором общности дает ложное высказывание.
Аналогично квантификация n–местного предиката квантором существования дает (n-1)–местный предикат, вычисление которого от данного набора значений переменных сводится к квантификации одноместного предиката квантором существования.
x(x+y+z=4) = D(y,z) -двуместный тождественно истинный предикат. Здесь, например, D(2,-1)= x(x+2-1=4)=1
y(x2+y2<-1)=F(x) - тождественно ложный предикат.
Очень важно усвоить, что кванторы связывают переменные. Предикаты xiA(x1,…,xn), xiA(x1,…,xn) уже не зависят от переменной xi. Аналогичную ситуацию мы встречали и в других разделах математики. Так, переменная х в выражении связана операцией интегрирования.
Конечно, предикат xi A(x1,…,xn) можно повторно квантифицировать по переменной xj. Если i≠j, то получаем (n-2)–местный предикат xj xiA(x1,…,xn) и т.д. после квантификации n–местного предиката по всем переменным каким-либо квантором получаем высказывание.
Примеры.1. высказывание y z(xy=0) истинно, так как одноместный предикат x(xy=0)выполним и квантификация его квантором существования дает 1.
2. Высказывание x y(x>y) истинно, а y x(x>y) – ложно. Можно рассуждать здесь чисто формально, отмечая, что y (x>y) - тождественно истинный, а x(x>y) - тождественно ложный предикат. Но и здравые соображения человека, знакомого с математикой в рамках средней школы, дают тот же результат. Ведь первое высказывание равносильно утверждению, что не существует наименьшего действительного числа (известная истина),а второе высказывание утверждает как раз противное.
Пример 2 убеждает нас в том, что кванторы общности и существования не перестановочны.
Обратим внимание еще на одну деталь. Высказывания принято считать 0–местными предикатами (это позволяет включить алгебру высказываний в алгебру предикатов). Кроме того, квантификация предиката по переменной, от которой он не зависит, дает предикат, равносильный исходному. Так, например, x(y+z=0) равносильно y+z=0, (2×2=4) равносильно 2×2=4.
Последнее замечание в данном пункте будет касаться очередности выполнения логических операций в алгебре предикатов. Договоренность относительно очередности выполнения операций ù, остается в силе. Кроме того, операции квантификации считаются более «привязанными» к предикатам, чем другие связки, т.е. в выражении xA(x) B(x) нужно сначала квантифицировать предикат A(x), а затем выполнять дизъюнкцию 0-метсного предиката xA(x) и одноместного предиката B(x).
Контрольные вопросы и упражнения
1. Обобщением каких простейших логических операций являются операции квантификации?
2. Построить на множестве целых чисел предикаты:
а) , что ; в) , что ;
б) , что ; г) , что .
3. Пусть «х – целое число», «х – рациональное число». Что означает запись: ?
4. Какой местности и какого типа следующие предикаты, определенные на целых числах:
а) ; г) ;
б) ; д) ;
в) ; е) .
5. Найти значение следующих высказываний, образованных квантификацией предикатов, в которых переменные определены на целых числах:
а) ; г) ;
б) ; д) ;
в) ; е) .
6. Записать на языке предикатов следующие высказывания, введя для простых предикатов соответствующие обозначения:
а) каждое число, кратное 10, кратно 5 и 2;
б) каждая функция , дифференцируемся в точке , непрерывна в точке ;
в) каждая непрерывная на функция – интегрируема на ;
г) диагонали произвольного прямоугольника равны между собой;
д) все числа, кратные 46, кратны 8 и 6, но не всякое число, кратное 8 и 6, кратно 48;
е) все трансцендентные числа – иррациональны, но не все иррациональные числа – трансцендентны;
ж) каждый квадрат является ромбом, но не всякий ромб – квадрат.
7. Даны два предиката и , где переменные определены на множестве . Для следующих предикатов найти равносильные, не содержащие кванторов:
а) ; г) ;
б) ; д) ;
в) ; е) .
Дата добавления: 2015-11-14; просмотров: 180 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Простейшие логические операции над предикатами. | | | Предикатные формулы. |