Предикаты заданы на множестве докажите что

Логические операции над предикатами

Отрицанием предиката Р(х), заданного на множестве Х, называется предикат , заданный на том же множестве и истинный при тех и только тех значениях хХ, при которых предикат Р(х) принимает значение лжи.

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 имело решение.

Источник