Теорема. Пусть Р и Т – предикаты, определённые на одном и том же множестве М. Тогда

ОИ Р&Т = ОИР ОИТ; ОИРÚТ = ОИР ОИТ; ОИ`Р = ОИР ; ОИРÞТ = ОИР ОИТ .

Доказательство. Докажем, например, первое равенство. Пусть аÎОИР&T , тогда Р(а)&Т(а)ºИ по определению, следовательно, Р(а)ºИ и Т(а)ºИ. Следовательно, аÎОИР и аÎОИТ, но тогда аÎОИР ОИТ.

Обратно: пусть аÎОИР ОИТ . Тогда аÎОИР и аÎОИТ , поэтому Р(а)ºИ и Т(а)ºИ; следовательно Р(а)&Т(а)ºИ , т. е. аÎОИР&T . Отсюда ОИР&T = ОИР ОИТ .

Определение. Предикаты Р и Т, имеющие одинаковые области определения, называются равносильными, если ОИР = ОИТ. Обозначение: Р(х) º Т(х). Предикат Т называется следствием предиката Р, если ОИР Ì ОИТ.

Пример.Предикат ( Öх2 > 5) равносилен предикату (½х½> 5). Т.е. Öх2 > 5 º ½х½> 5.

Замечания. В школьной математике постоянно приходится иметь дело с различными предикатами. К ним относятся, например, уравнения, неравенства, системы уравнений и неравенств, совокупности уравнений и неравенств и т. д. При этом школьная символика несколько отличается от выше приведённой. Вместо знака конъюнкции & употребляется фигурная скобка { , вместо знака дизъюнкции Ú - квадратная скобка [ , вместо знака равносильности º - знак эквиваленции Û (что в общем то понятно, подумайте – почему?). Область истинности предиката (представленного уравнением, неравенством, системой уравнений и неравенств или совокупностью уравнений и неравенств) есть ни что иное, как множество решений соответствующего уравнения, неравенства и т.д.

Пример 1. Вместо (х + 2у = 3)&(2х – у = 1) º (х = 3 – 2у)&(6 – 5у = 1) º (х = 1)&(у = 1) в школе пишут :

х +2у = 3 х = 3 – 2у х = 1 2.Вместо (х2 – 2х –3 £ 0) Ú (çхç > 4 ) º

2х – у = 1 6 – 5у = 1 у = 1. (хÎ[-1, 3] )Ú (xÎ(-¥,-4)È(4 ,+¥) ) º (хÎ[-1, 3] È (-¥,-4)È(4 ,+¥) пишут

х2 – 2х – 3 £ 0 ó х Î[-1 , 3] ó хÎ[-1, 3] È (-¥,-4)È(4 ,+¥) .

çхç > 4 xÎ(-¥,-4)È(4 ,+¥)

 

Введём кванторные операции над предикататами.

Определение. Пусть предикат Р(х) определён на множестве М.

1. Символ "х(Р(х)) обозначает высказывание, которое истинно тогда и только тогда, когда для любого элемента аÎМ Р(а) º И, т.е. ОИр = М.

Символ $х(Р(х) обозначает высказывание истинное т. и т. т. , к. хотя бы для одного элемента аÎМ Р(а) º И, т.е. , когда ОИР ¹ Æ.

Символы "и $называются квантором всеобщности и квантором существования соответственно. В первом случае говорят, что предметная переменная х связана квантором всеобщности, во втором – квантором существования.

Примеры 1."х ( х – простое число & хÎN)ºЛ, т.к. ,например, 4 – не является простым числом, однако 4ÎN.$х (х – простое число & хÎN) ºИ, т.к., например, 3 – простое число и 3ÎN.

Замечание.Для краткости выше приведённые высказывания можно записывать так: "хÎN(х – простое число) ; $хÎN(х – простое число).

2."хÎN ( х2 ³ 0 )ºИ и $хÎN2 ³ 0 )ºИ.

Связывая высказывания и предикаты операциями алгебры высказываний, будем получатьформулы логики предикатов: А Û Р(х), В & Q(x,y), $хÎN(Р(х) Û Q(x,y)) и т.д. аналогично тому, как это сделано в алгебре высказываний, можно ввести понятие равносильных формул.

Все равносильности, имеющие место в алгебре высказываний, переносятся и на логику предикатов. Кроме равносильностей алгебры высказываний, в логике предикатов есть равносильности. Связанные с кванторами.

Теорема. 1. $х(Р(х) ) Ú $х(Т(х) ) º $х ( Р(х)ÚТ(х) ); "х(Р(х)) & "х(Т(х)) º "х(Р(х) & T(x) ).

2. $х(Р(х)) º "х(Р(х) ) ; "х(Р(х) º $х ( Р(х) ).

Доказательство.Докажем, например, равносильность 2. Пусть $х(Р(х)) º И.Тогда $х(Р(х)) º Л.Следовательно, для любого хÎМ (где М – ООР) Р(х) –ложное высказывание. А поэтому ØР(х) ­– истинное высказывание. Но тогда, по определению квантора ","х(ØР(х) ) – истинно.

Пусть теперь $х(Р(х)) º Л.Тогда $х(Р(х)) º И, следовательно, существует хотя бы один элемент аÎМ такой, что Р(а)º И, а поэтому ØР(а) º Л, но тогда "х(ØР(х)) º Л. Т.о., формула 2 справедлива.

Иногда употребляется высказывание $!х(Р(х)), которое читается: «существует единственный х такой, что Р(х)» и истинное т. и т. т. , к. есть только один элемент аÎМ такой, что Р(а)ºИ.

Используя эти равносильности, легко строить отрицания условий, содержащихся, например, в определениях. Пример:("хÎN $yÎN ( x = 2y)) º $хÎN "yÎN (x ¹ 2y ).

Определение ограниченной функции: Функция f называется ограниченной на множестве Х, если выполняется условие: $аÎR+("xÎX(ïxï£ a )) . Тогда условием неограниченности функции f на множестве Х является отрицание предыдущего условия: Ø($аÎR+("xÎX(ïxï£ a )), которое согласно теореме примет вид: "аÎR+($хÎX(ïxï> а). Аналогично строятся отрицания любых других формул с кванторами.

Можно сформулировать следующее правило для построения отрицаний формул логики предикатов, состоящее из трёх пунктов:

1. В формуле, отрицание которой мы строим, исключаются операции Þ, Û, $!, используя равносильности:

А Þ В º`АÚ В ; А Û В º(`А Ú В )&(`В Ú А ) ; $!х(Р(х) º $х(Р(х) & "у( Р(у) Ú х=у).

2. Каждую из операций &, Ú, ", $ заменим на двойственные: соответственно Ú, &, $, ".

3. Применим операцию отрицания к предикату, стоящему в скобках после кванторной приставки.

Если имеется необходимость, полученную формулу преобразуем равносильным образом к удобному для чтения виду. Для многих случаев удобна следующая формулировка правила, хорошо выражающая его сущность: Чтобы получить отрицание данного утверждения, надо в его символической записи каждый квантор заменить на двойственный, а предикат заменить на противоположный.

Упражнения.

1. а) луна есть спутник Марса;

б) как много у тебя хороших книг!

в) Земля – планета;

г) ученик 11 класса;

д) DАВС ¥ DА1В1С1 ;

е) Ö4 + Ö27 – 45;

ж) а > 0.

Определить, какие из этих предложений являются высказываниями.

2. Следующие высказывания записать в виде формул, заменив простые высказывания буквами:

а) если 80 не делится на 3 и делится на 2, то 80 не делится на 6;

б) произведение трёх чисел равно 0 т. и т. т. , к. хотя бы одно из них равно 0;

в) число х0 является решением системы уравнений т. и т. т. , к. оно является решением каждого уравнения системы;

г) если в треугольнике какая-то медиана не является высотой или биссектрисой, то этот треугольник не равнобедренный и не равносторонний;

д) 3 есть простое число, а 21 является составным числом;

е) если натуральное число является простым, то оно равно 2 или нечётно;

ж) если последовательность имеет конечный предел, то она сходится.

Определить какие значения имеют эти высказывания.

3. Доказать равносильности:

а) А Þ В º`АÚ В; б) А Þ В ºА &`В; в) А Û В º (А Þ В ) & (В Þ А );

г) Ø(А Û В) º(А &`В)Ú(`А & В); д) А Þ В º`В Þ`А; е) А Û В º `В Û`А.

4. Для каждой из данных теорем сформулировать теоремы: прямую, обратную, противоположную, обратную противоположной, определить какие из теорем истинны.

а) если две прямые перпендикулярны третьей, то они параллельны;

б) сумма углов треугольника равна 1800;

в) середина диагонали параллелограмма является его центром симметрии;

г) если две противоположные стороны четырёхугольника равны и параллельны, то такой четырёхугольник – параллелограмм;

д) в прямоугольном треугольнике сумма квадратов катетов равна квадрату гипотенузы;

е) диагонали прямоугольника равны;

ж) в равнобедренном треугольнике медиана, проведённая к основанию, является биссектрисой и высотой.

5. Пользуясь теоремой Гаубера, доказать, что верны теоремы, обратные к следующим:

1) пусть а,в,сÎR.Тогда при с > 0: а) если а > в, то ас > вс; б) если а = в, то ас = вс; в) если а < в, то ас < вс;

2) пусть а,в,с – длины сторон DАВС; тогда: а) если ÐА < ÐB, to a < в; б) если ÐА = ÐB,

то а = в; в) если ÐА > ÐB, то а > в;

3) пусть а,в,с – длины сторон DАВС; тогда: а) если а2 + в2< с2 , то ÐС – тупой;

б) если а2 + в22 , то ÐС – прямой; в) если а2 + в22 , то ÐС – острый.

6. Выяснить, какие из ниже следующих предложений можно рассматривать как предикаты при определённом выборе его ОО:

а) х2 – 2х – 15 = 0; б) при х = 5 выполняется равенство х2 – 2х – 15 = 0; в) х3 + у; г) существует число х , для которого выполняется равенство х2 – 2х – 15 = 0; д) точки А и В лежат по разные стороны от прямой а е) если х > 3 , то х2 > 9; ж) целое число х при делении на у даёт остаток z; з) 5 – 3 = 2; и) Х – истинно; к) площадь фигуры Х равна у.

7. Даны предикаты на множестве N: Р(х) – (число х делится на 2); Q(x) – (x –число нечётное); R(x,y) – (х делится на у); S(x) – (число х – составное). Записать словами высказывания и выяснить, какие из них истинны, а какие ложны: Р(3); Р(6)&S(2); P(5)ÚQ(5); R(10,2); R(2,10); $x(P(x)ÚR(x,6)); "x(P(x)&$y(R(x,y)ÞP(x))); "x(Q(x)Þ"y(P(y)Þ(ØR(x,y))).

7. Даны предикаты на множестве М = {1,2,3, … ,12}: H(x) – (x делится на 3); Р(х) – (х делится на 9); записать словами следующие предикаты и найти их области истинности:

а) Р(х)&Н(х); б) Р(х)ÚН(х); в) Н(х)ÞР(х); г) Р(х)ÞН(х); д) Н(х)ÛР(х); е)Н(х) ÞР(х);

8. Изобразить на числовой прямой ОИ следующих предикатов: Р(х); Т(х); Р(х)ÚТ(х); Р(х)&Т(х); Р(х)ÞТ(х); где а) Р(х) – (ôх + 2ô< 3); Т(х) – (х2 + х – 2 < 0); б) Р(х) – (х2 – 6х ³ -9); Т(х) – (11-1/х <1).

9. Изобразить на плоскости ХОУ ОИ предикатов, определённых на R:

а) х2 + у2 ³4; б) ху ³4 ; в) х2 - у2 =4; г) у ³ х2; д)÷х÷ = -÷у÷ ; е) (х2 –4)2 + (у2 – 9)2 = 0;

х2 + у2<9

10. Изобразить на плоскости ХОУ ОИ предикатов Р(х,у); Q(x,y); Р(х,у)& Q(x,y); Р(х,у)Ú Q(x,y); Р(х,у)Þ Q(x,y); Р(х,у)Û Q(x,y); где

а) Р(х,у): (х2 - у2 = 0); Q(x,y): (х2 + у2<9); б) Р(х,у): (х2 < у); Q(x,y): (y – x = 3);

в) Р(х,у): (у³2х); Q(x,y): (y > 1/x ).

11. Записать предикат (и его отрицание), определяющий следующее понятие:

а) равенство множеств; б) окружность; в) рациональное число; г) параллелограмм; д) logab;

е) равносильность уравнений; ж) равнобочная трапеция.

12. Записать формулой логики предикатов следующие предложения (построить их отрицания):

а) существует равнобедренный прямоугольный треугольник; б) существует натуральное число которое делится на 2, 3, 5; в) имеется только одно действительное число, квадрат которого равен нулю; г) для любого действительного числа есть ему противоположное; д) для всякого рационального числа, отличного от 0 , есть ему обратное; е) если произведение двух натуральных чисел делится на простое число, то на него делится по крайней мере один из сомножителей; ж) если целое число больше 1, то оно простое или составное.

Задачи.

1. Доказать равносильности:

а) А Þ В º А&`В; б) АÚ(В&В)ºА; в) А&В º`А Þ В; г) (АÚВ)Ú`С º АÚ(ВÚ`С); д) АÞ(ВÞС)ºВÞ (АÞС)

е) А&ВÞСº АÞ(ВÞС); ж) АÞ(В&С) º (АÞВ)& (АÞС); з) А&(ВÞС)º( А&`В)Ú(А&C);

и) АÞ(ВÚС)º (АÞВ)ÚС.

2. Доказать тавтологии:

а) (АÞС)& (ВÞС)Þ (АÚВÞС);

б) (АÞВ)& (ВÞС)Þ (АÞВ&С);

в) (АÛВ)& (ВÛС)Þ (АÛС);

г) (АÞВ)Þ(( АÞ(ВÞС)) Þ(АÞС));

д) (АÞВ)Þ(( А&C) Þ(В&С));

е) (АÞВ) Ú(ВÞА);

ж) (АÚВ)&`ВÞА;

з) (АÞВ)Þ(`ВÞ`А);

и) (`АÞВ)&(`АÞ`В) ÞА;

к) (АÛВ) Þ (АÞВ).

3. Для каждой из ниже следующих теорем сформулировать теоремы: обратную, противоположную, противоположную обратной и эквиваленцию. Установить какие из теорем верны.

а) в равнобедренном треугольнике углы при основании равны;

б) если сумма цифр целого числа делится на 9, то и само число делится на 9;

в) если точка равноудалена от концов отрезка, то она лежит на серединном перпендикуляре;

г) диагонали равнобедренной трапеции равны;

д) параллелограмм имеет центр симметрии;

е) если а = с и в = d, то уравнение ах + в = сх + d имеет бесконечно много решений;

ж) если с = 0, то один из корней квадратного уравнения ах2 + вх + с равен 0;

з) в треугольник можно вписать окружность;

и) если произведение двух целых чисел есть число нечётное, то их сумма – число нечётное;

к) диагонали ромба перпендикулярны;

л) если функция f возрастает на интервале (а,в), то существует обратная к ней функция;

м) через любые три точки, не лежащие на одной прямой, можно провести окружность;

н) если две прямые параллельны третьей, то они параллельны между собой;

о) если оба числа а и в делятся на с, то и их сумма а + в делится на с;

п) если в четырёхугольник можно вписать окружность, то этот четырёхугольник – ромб;

р) если число оканчивается на0 или 5, то оно делится на 5;

с) площади подобных многоугольников относятся, как квадраты сходственных сторон;

т) в четырёхугольнике сумма углов равна 3600.

4. Предикаты Р(х) и Т(х) заданы на естественной области определения. Найти и изобразить на числовой прямой области истинности предикатов: Р(х); Т(х); ØР(х); Р(х)&Т(х); Р(х)ÚТ(х); Р(х)ÛТ(х); выяснить истинны или ложны высказывания: $х (Р(х)), "х (Т(х)), "х (Р(х)), $х (Т(х)), $х (Р(х)ÚТ(х)), "х (Р(х)ÚТ(х)), "х (Р(х)&Т(х)),$х (Р(х)&Т(х)), если:

а) Р(х): (Öх +2 > х), Т(х):Öх2 = |x|;

б) Р(х): (х4 –10х2 + 9=0), Т(х): (Öх2 < 0);

в) Р(х): (|x + 1| > 3), T(x): (х2 + 2х + 1 = (х + 1)2);

г) Р(х): (-х2 + 5х + 14 > 0), Т(х): (Öх2+1 < 0);

д) Р(х): ( |x| =x), Т(х): ( > 1).

5. Предикаты Р(х,у) и Т(х,у) заданы на естественной области их определения. Изобразить на плоскости ХОУ области истинности предикатов Р, Т, Р&Т, РÚТ, РÛТ. Выяснить: истинны или ложны высказывания: "х"у(Р(х,у)), "х$у(Р(х,у)), $х"у(Р(х,у)), $х $у(Р(х,у)), тоже с предикатом Т.

а) Р: (у = х2), Т: (у>2х+1); б) Р: (х2 – у2³0), Т: (х2 + у2 ³ 9); в) Р: (у ³ х2), Т: (х2 + у2 ³4);

г) Р: (ху ³4); Т: (|x| >2); д) Р: (у ³ х3), Т: (у<х2); е) Р: (ху £ 0), Т: (х2 + у2 £ 16).

6. Записать формулой логики предикатов следующие утверждения, построить их отрицания и выяснить истинны ли записанные высказывания:

а) ни одно простое число не является точным квадратом;

б) все простые числа больше 1;

в) некоторые действительные числа являются рациональными;

г) все простые числа, большие 2, нечётные;

д) некоторые простые числа – чётные;

е) для любого целого числа найдётся такое целое число, что их сумма равна 0;

ж) существует чётное число , не делящееся на 4 и делящееся на 3;

з) существует параллелограмм не имеющий осей симметриии;

и) все числа, делящиеся на 30 , делятся на 2, 3. и 5.

7. Применяя логическую символику, записать в виде формул следующие определения:

а) прямоугольник;

б) нечётная функция;

в) выпуклая фигура;

д) средняя линия трапеции;

е) точка минимума;

ж) ромб;

з) точка максимума;

и) корень n-ой степени из числа а;

к) периодическая функция;

л) составное число;

м) простое число.