Логические операции над предикатами
Отрицанием предиката Р(х), заданного на множестве Х, называется предикат 
, заданный на том же множестве и истинный при тех и только тех значениях х
Х, при которых предикат Р(х) принимает значение лжи.
2. Операция конъюнкции.
Конъюнкцией предикатов Р(х) и Q(x), заданных на множестве Х, называется предикат Р(х)
Q(x), заданный на том же множестве и обращающийся в истинное высказывание при тех и только тех значениях х
Х, при которых оба предиката принимают значения истины.
Если обозначить ТР – множество истинности предиката Р(х), ТQ – множество истинности предиката Q(х), а множество истинности их конъюнкции TPÙQ, то, по всей видимости, TPÙQ = TP Ç TQ.
Докажем это равенство.
Наглядно это можно изобразить следующим образом.
3. Операция дизъюнкции.
Дизъюнкцией предикатов Р(х) и Q(x) называется предикат Р(х)
Q(x), определенный на том же множестве Х и обращающийся в истинное высказывание при тех и только тех значениях х
Х, при которых принимает значение истины хотя бы один из предикатов Р(х) или Q(x).
Аналогично доказывается, что TPÚQ = TP È TQ.
4. Операция импликации.
Импликацией предикатов Р(х) и Q(x), заданных на множестве Х, называется предикат Р(х) 
Q(x), определенный на том же множестве Х и обращающийся в ложное высказывание при тех и только тех значениях х
Х, при которых Р(х) принимает значение истины, а Q(x) – значение лжи.
5 .Операция эквиваленции.
Эквиваленцией предикатов Р(х) и Q(x), заданных на множестве Х, называется предикат Р(х) 
Q(x), определенный на том же множестве Х и принимающий значение истины при тех и только тех значениях х
Х, при которых значения каждого из предикатов либо истинны либо ложны. Множество истинности в таком случае выглядит так:
TPÛQ = 
.
Пример. На множестве М= <1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,15, 16, 17, 18, 19, 20> заданы предикаты: А(х) – «число х не делится на 5», В(х) – «х – число четное», С(х) – «х – число простое», D(x) – «число х кратно 3». Найти множество истинности следующих предикатов:
a) А(х)
В(х); b) A(x)
; c) C(x)
A(x); d) B(x)
D(x) и изобразить их при помощи диаграмм Эйлера-Венна.
Решение: a) Найдем множество истинности предикатов.
А(х): T 
= <1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19>;
В(х): Т 
= <2, 4, 6, 8, 10, 12, 14, 16, 18, 20>.
Множество истинности конъюнкции А(х)
В(х) есть пересечение множеств истинности T 
и Т
.
b) Множествa истинности А(х): T 
= <1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19>; 
: T 
=<1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20>.
Тогда множество истинности A(x)
будет следующим:
с) Множествa истинности С(х): Т 
=<1, 2, 3, 5, 7, 11, 13, 17, 19>; А(х): T 
= <1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19>.
Множество истинности импликации есть объединение множества истинности второго предиката с множеством истинности отрицания первого.
Значит множество истинности импликации C(x)
A(x) будет следующим: Т = <1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
d) Множества истинности В(х): Т1= и D(x): T 
= <3, 6, 9, 12, 15, 18>. Тогда множество истинности дизъюнкции B(x)
D(x) есть объединение множеств истинности Т1 и T2 и будет следующим: Т = <2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20>.
Операции над предикатами. Описание математических понятий с помощью логики предикатов
Операции над предикатами. Описание математических понятий с помощью логики предикатов.
§3. Логические операции над предикатами.
Предикаты так же, как высказывания, могут принимать два значения: “истина” (1) и “ложь” (0), поэтому к ним применимы все операции логики высказываний, в результате чего из элементарных предикатов формируются сложные предикаты (как и в логике высказываний, где из элементарных высказываний формировались сложные, составные). Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов. Эти операции в логике предикатов сохраняют тот же смысл, который был им присвоен в логике высказываний.
Пусть на некотором множестве 
определены два предиката 
и 
.
Определение 7. Конъюнкцией двух предикатов и называется новый (сложный) предикат 
, который принимает значение “истина” при тех и только тех значениях 
, при которых каждый из предикатов принимает значение “истина”, и принимает значение “ложь” во всех остальных случаях.
Очевидно, что областью истинности предиката является общая часть области истинности предикатов и , т. е. пересечение 
.
Пример 8. Для предикатов : “ 
– четное число” и : “ кратно 3” конъюнкцией является предикат “ – четное число и кратно трем”, т. е. предикат “ делится на 6”.
Определение 8. Дизъюнкцией двух предикатов и называется новый предикат 
, который принимает значение “ложь” при тех и только тех значениях , при которых каждый из предикатов принимает значение “ложь”, и принимает значение “истина” во всех остальных случаях.
Ясно, что областью истинности предиката является объединение области истинности предикатов P(x) и Q(x), т. е. 
.
Определение 9. Отрицанием предиката P(x) называется новый предикат 
или
, который принимает значение “истина” при всех значениях , при которых предикат принимает значение “ложь”, и принимает значение “ложь” при тех значениях , при которых предикат принимает значение “истина”.
Очевидно, что 
, т. е. множество истинности предиката является дополнением к множеству IP.
Определение 10. Импликацией предикатов и называется новый предикат 
, который является ложным при тех и только тех значениях , при которых одновременно принимает значение “истина”, а – значение “ложь”, и принимает значение “истина” во всех остальных случаях.
Поскольку при каждом фиксированном справедлива равносильность 
, то 
.
Определение 11. Эквиваленцией предикатов и называется новый предикат 
, который обращается в “истину” при всех тех и только тех , при которых и обращаются оба в истинные или оба в ложные высказывания.
Для его множества истинности имеем: 
§4. ПРИМЕНЕНИЕ ЯЗЫКА ЛОГИКИ ПРЕДИКАТОВ ДЛЯ ЗАПИСИ МАТЕМАТИЧЕСКИХ ПРЕДЛОЖЕНИЙ, ОПРЕДЕЛЕНИЙ, ПОСТРОЕНИЯ ОТРИЦАНИЯ ПРЕДЛОЖЕНИЙ.
1. Запись математических предложений и определений в виде формул логики предикатов.
Язык логики предикатов удобен для записи математических предложений и определений. Он дает возможность выражать логические связи между понятиями, записывать определения, теоремы, доказательства. Приведем несколько примеров таких записей.
Пример 1. Определение предела числовой последовательности.
Используя трехместный предикат 
, запишем:
,
Пример 2. Определение предела функции в точке.
Определение предела “
” функции ƒ(х), определенной в области E, в точке x0:
,
где 
.
Пример 3. Определение непрерывности функции в точке.
Функция 
, определенная на множестве E, непрерывна в точке 
, если 
, где 
.
Пример 4. Определение возрастающей функции.
Функция , определенная на множестве E, возрастает на этом множестве, если
.
Здесь использован двуместный предикат 
.
2. Построение противоположный утверждений.
Пусть дано некоторое математическое утверждение А. Ему будет противоположным будет утверждение 
. Логика предикатов позволяет путем равносильных преобразований формулы придать ей хорошо обозримый вид.
Определение неограниченной функции мы получим, беря отрицание этой формулы и проводя равносильные преобразования:
.
Последняя формула дает не негативное, а положительное определение неограниченной функции.
Из приведенного определения видно, что для построения противоположного утверждения к утверждению, заданному формулой логики предикатов, содержащей все кванторы впереди, необходимо заменить все кванторы на противоположные и взять отрицание от предиката, стоящего под знаком кванторов.
Как известно, многие теоремы математики допускают формулировку в виде условных предложений. Например, рассмотрим следующую теорему: «Если точка лежит на биссектрисе угла, то она равноудалена от сторон этого угла». Условием этой теоремы является предложение «Точка лежит на биссектрисе угла», а заключением – предложение «Точка равноудалена от сторон угла». Видим, что и условие, и заключение теоремы представляют собой предикаты, заданные на множестве R2. Обозначая эти предикаты соответственно через Р(х) и Q(x), где хÎR2, теорему можем записать в виде формулы:
В связи с этим, говоря о строении теоремы, можно выделить в ней три части:
1) условие теоремы: предикат Р(х), заданный на множестве R2;
2) заключение теоремы: предикат Q(x), заданный на множестве R2;
3) разъяснительная часть: в ней описывается множество объектов, о которых идет речь в теореме.
Особый интерес представляет построение утверждения, отрицающего справедливость некоторой теоремы: 
.
Это будет утверждение: 
.
Следовательно, чтобы доказать, что теорема неверна, достаточно указать такой элемент 
, для которого 
— истина, a 
— ложь, то есть привести контрпример.
Используя данный прием докажем несправедливость утверждений:
1) «Если дифференцируемая функция имеет в точке х0 производную, равную нулю 
, то точка х0 – точка экстремума». Достаточно указать один пример, опровергающий утверждение теоремы. Функция 
в точке х=0 имеет производную 
, но эта точка не является точкой экстремума. Значит, теорема не верна.
2) «Если в четырехугольнике диагонали равны, то четырехугольник является параллелограммом» В качестве контрпримера можно привести равнобокую трапецию, у которой диагонали равны, но она не является прямоугольником.
3 Прямая, обратная и противоположная теоремы.
Рассмотрим четыре теоремы:
, (1)
, (2)
, (3)
. (4)
Определение 1: Пара теорем, у которых условие одной является заключением второй, а условие второй является заключением первой, называются взаимно обратными друг другу.
Так, теоремы (1)и (2), а также (3) и (4)- взаимно обратные теоремы. При этом, если одну из них называют прямой теоремой, то вторая называется обратной.
Определение 2: Пара теорем, у которых условие и заключение одной являются отрицанием соответственно условия и заключения другой, называются взаимно противоположными.
Так, теоремы (1) и (3), а также (2) и (4) являются взаимно противоположными теоремами.
Например, для теоремы
“Если в четырехугольнике диагонали равны, то четырехугольник является прямоугольником ” (1) обратной является теорема
“Если четырехугольник является прямоугольником, то его диагонали равны” (2).
Для теоремы (1) противоположной является теорема
“Если в четырехугольнике диагонали не равны, то четырехугольник не является прямоугольником” (3),
а для теоремы (2) противоположной является теорема
“Если четырехугольник не является прямоугольником, то его диагонали не равны ” (4).
В рассмотренном примере теоремы (1) и (4) являются одновременно ложными, а теоремы (2) и (3) одновременно истинными. Контрпримером к теореме (1) является равнобочная трапеция.
Ясно, что прямая и обратная теоремы, вообще говоря, не равносильны, т. е. одна из них может быть истинной, а другая – ложной. Однако легко показать, что теоремы (1) и (4), а также (2) и (3) всегда равносильны.
.
Из этих равносильностей следует, что, если доказана теорема (1), то доказана и теорема (4), а если доказана теорема (2), то доказана и теорема (3).
4. Необходимые и достаточные условия.
(1)
Как отмечалось, множество истинности предиката 
есть множество 
. Но тогда множеством ложности этого предиката будет 
. Последнее множество будет пустым лишь в случае, когда 
(см. рисунок).
Итак, предикат является истинным для всех 
том и в только в том случае, когда множество истинности предиката Р(х) содержится в множестве истинности предиката Q(x). При этом говорят, что предикат Q(x) логически следует из предиката Р(х), и предикат Q(x) называют необходимым условием для предиката Р(х), а предикат Р(х) – достаточным условием для Q(x).
Часто встречается ситуация, при которой истинны взаимно обратные теоремы
(1)
.(2)
Это, очевидно, возможно при условии, что 
.
В таком случае из теоремы (1) следует, что условия Р(х)являются достаточными для Q(x), а из теоремы (2) следует, что условие Р(х)является необходимым для Q(x).
Таким образом, если истинны теоремы (1) и (2), то условие Р(х) является и необходимым, и достаточным для Q(x). Аналогично в этом случае условие Q(х) является необходимым и достаточным для Р(x).
Иногда вместо логической связки “необходимо и достаточно ” употребляют логическую связку “тогда и только тогда”.
Так как здесь истинны высказывания (1) и (2), то истинно высказывание
.
1) Теорема «Если число l делится на 12, то оно делится на 3» истинна. Поэтому здесь делимость числа l на 12 является достаточным условием для делимости числа l на 3, а делимость числа l на 3 является необходимым условием для делимости числа l на 12. В то же время обратная теорема «Если число l делится на 3, то оно делится на 12» не верна. Поэтому делимость числа l на 3 не является достаточным условием делимости числа l на 12, а делимость числа l на 12 не является необходимым условием делимости числа l на 3.
2) Теоремы «В описанном четырехугольнике суммы длин противоположных сторон равны между собой» и «Если в четырехугольнике суммы длин противоположных сторон равны между собой, то в этот четырехугольник можно вписать окружность» взаимно обратны. Обе они истинны, и, следовательно, здесь можно употребить логическую связку «необходимо и достаточно»:
«Для того, чтобы в четырехугольник можно было вписать окружность, необходимо и достаточно, чтобы суммы длин его противоположных сторон были равны между собой».
3) Для каждого из условий выясните, является ли оно необходимым и является ли оно достаточным, чтобы выполнялось неравенство 
:
а) х=0, б) 
, в) 
, г) 
, д) 
, е) 
.
Неравенство перепишем в виде 
, его решением являются 
.
а) 
– достаточное условие для выполнения неравенства, т. к. 0Î[-2, 4].
б) [-1, 3]Ì [-2, 4]. Значит – достаточное условие.
в) [-3, +¥)É[-2, 4], следовательно, является необходимым условием.
г) (-2, +¥)Ë[-2, 4] и [-2, 4]Ë(2, +¥), значит, не является ни необходимым, ни достаточным условием.
д) [-1, 10] Ë[-2, 4] и [-2, 4]Ë [-1, 10], значит, не является ни необходимым, ни достаточным условием.
5. Доказательство теорем методом от противного.
Доказательство теорем методом от противного обычно проводится по следующей схеме: предполагается, что теорема
(1)
Покажем, что такой подход дает доказательство истинности теоремы (1).
Действительно, предположение о том, что теорема (1) не справедлива, означает истинность ее отрицания, т. е. формулы 
. Можно показать, что противоречивое утверждение, которое получается из допущенного предположения, как мы видели из ранее рассмотренных примеров, может быть записано как конъюнкция 
, где С – некоторое высказывание.
Задачи для самостоятельного решения
1. Доказать несправедливость утверждений:
а) «Если дифференцируемая функция 
имеет в точке х0 вторую производную, равную нулю, то точка х0 – точка перегиба графика функции».
б) «Если числовая последовательность ограничена, то она имеет предел».
в) «Если функция непрерывна в точке х0, то она имеет производную в этой точке».
2. Для каждого из условий выясните, является ли оно необходимым и является ли оно достаточным, чтобы выполнялось неравенство 
:
а) х=1, б) 
, в) , г) 
, д) , е) 
.
4. В предложениях вместо многоточия поставьте слова «необходимо, но не достаточно», «достаточно, но не необходимо», «не необходимо и недостаточно», «необходимо и достаточно»:
а) Для того, чтобы четырехугольник был прямоугольным…, чтобы длины его диагоналей были равны;
б) Для того, чтобы 
…, чтобы х=3;
в) Для того, чтобы сумма четного числа натуральных чисел была четным числом…, чтобы каждое слагаемое было четным;
г) Для того, чтобы окружность можно было вписать в четырехугольник…, чтобы сумма длин суммы длин его противоположных сторон были равны;
д) Для того, чтобы множество было счетным…, чтобы его элементы можно было записать в виде занумерованной последовательности;
е) Для того, чтобы числовая последовательность имела предел…, чтобы она была ограниченной.
а) Необходимый, но недостаточный признак параллелограмма;
б) Необходимый и достаточный признак параллелограмма;
в) Достаточное, но не необходимое условие, чтобы уравнение sinx = a имело решение.
г) Необходимое, но не достаточное условие, чтобы уравнение sinx = a имело решение.