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

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

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

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

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

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

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

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

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

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

х² – 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 (х² ³ 0) º И и $хÎ N (х² ³ 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А₁В₁С₁ ;

е) Ö4 + Ö27 – 45;

ж) а > 0.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

а) х² – 2х – 15 = 0; б) при х = 5 выполняется равенство х² – 2х – 15 = 0; в) х³ + у; г) существует число х, для которого выполняется равенство х² – 2х – 15 = 0; д) точки А и В лежат по разные стороны от прямой а е) если х > 3, то х² > 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 < 0); б) Р(х) – (х² – 6х ³ -9); Т(х) – (11-1/х <1).

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

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

х² + у²<9

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

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

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

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

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

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

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

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

Задачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ж) ромб;

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

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

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

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

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