Предикаты и операции над ними

Отношение порядка. Упорядоченные множества

Определение. Отношение R на множестве Х называется отношением порядка, если оно транзитивно и асимметрично или антисимметрично.

Определение. Отношение R на множестве Х называется отношением строгого порядка, если оно транзитивно и асимметрично.

Примеры отношений строгого порядка: «больше» на множестве натуральных чисел, «выше» на множестве людей и др.

Определение. Отношение R на множестве Х называется отношением нестрогого порядка, если оно транзитивно и антисимметрично.

Примеры отношений нестрогого порядка: «не больше» на множестве действительных чисел, «быть делителем» на множестве натуральных чисел и др.

Определение. Множество Х называют упорядоченным, если на нем задано отношение порядка.

Пример. На множестве Х = {1; 2; 3; 4; 5} заданы два отношения: «х £ у» и «х – делитель у».

Оба эти отношения обладают свойствами рефлексивности, антисимметричности и транзитивности (постройте графы и проверьте свойства самостоятельно), т.е. являются отношением нестрогого порядка. Но первое отношение обладает свойством связности, а второе – нет.

Определение. Отношение порядка R на множестве Х называется отношением линейного порядка, если оно обладает свойством связности.

В начальной школе изучаются многие отношения порядка. Уже в первом классе водятся отношение «меньше», «больше» на множестве натуральных чисел, «короче», «длиннее» на множестве отрезков и др.

Контрольные вопросы

1. Дайте определение бинарного отношения на множестве Х.

2. Как записать утверждение о том, что элементы х и у находятся в отношении R?

3. Перечислите способы задания отношений.

4. Сформулируйте свойства, которыми могут обладать отношения. Как данные свойства отражаются на графе?

5. Какими свойствами должно обладать отношение, чтобы оно являлось отношением эквивалентности?

6. Как отношение эквивалентности связано с разбиением множества на классы?

7. Какими свойствами должно обладать отношение, чтобы оно являлось отношением порядка?

Глава 5. Предикаты и теоремы

В математике часто встречаются предложения, содержащие одну или несколько переменных, например: «х + 2 = 7», «город стоит на Волге». Эти предложения не являются высказываниями, т.к. о них нельзя сказать, истинны они или ложны. Однако при подстановке конкретных значений переменной х они обращаются в истинные или ложные высказывания. Так, в первом примере при х = 5 получаем истинное высказывание, а при х = 3 – ложное высказывание.

Определение. Предложение с переменными, которое при конкретных значениях переменных обращается в высказывание, называется высказывательной формой или предикатом.

По числу входящих в предикат переменных различают одноместные, двухместные и т.д. предикаты и обозначают А (х), В (х;у)…

Пример: А (х): «х делится на 2» – одноместный предикат, В (х; у): «прямая х перпендикулярна прямой у» – двухместный предикат.

Следует иметь в виду, что в предикате переменные могут содержаться неявно: «число делится на 2», «студент получил отличную оценку на экзамене по математике».

Задание предиката, как правило, предполагает и задание множества, из которого выбираются значения переменных, входящих в предикат.

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

Так, предикат «х > 2» можно рассматривать на множестве натуральных чисел или действительных чисел.

Каждый предикат А (х), х Î Х определяет множество Т Ì Х, состоящее из элементов, при подстановке которых в предикат А (х) вместо х получается истинное высказывание.

Определение. Множество, состоящее из всех тех значений, при подстановке которых в предикат получается истинное высказывание, называется множеством истинности предиката (обозначается Т).

Пример. Рассмотрим предикат А (х): «х < 5», заданный на множестве натуральных чисел. Т = {1; 2; 3; 4}.

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

Пусть Т_А – область истинности предиката А (х), Т_В – область истинности предиката В (х).

Определение. Конъюнкцией предикатов А (х) и В (х) называется предикат А (х) Ù В (х), который истинен для тех и только тех значениях х Î Х, для которых оба предиката истинны.

Покажем, что Т_{А Ù В} = Т_А Ç Т_В.

Доказательство. 1) Пусть а Î Т_{А Ù В} Þ А (а) Ù В (а) – истинное высказывание. По определению конъюнкции имеем: А (а) – истинно, В (а) – истинно Þ а Î Т_А Ù а Î Т_В Þ а Î Т_А Ç Т_В Þ Т_{А Ù В} Ì Т_А Ç Т_В.

2) Пусть b Î Т_А Ç Т_В Þ b Î Т_А Ù b Î Т_В Þ А (b) – истинно, В (b) – истинно Þ по определению конъюнкции А (b) Ù В (b) – истинное высказывание Þ b Î Т_{А Ù В} Þ Т_А Ç Т_В Ì Т_{А Ù В} .

Т.к. Т_{А Ù В} Ì Т_А Ç Т_В и Т_А Ç Т_В Ì Т_{А Ù В} , то по свойству равенства множеств Т_{А Ù В} = Т_А Ç Т_В, что и требовалось доказать.

Заметим, что полученное правило справедливо и для предикатов, содержащих более одной переменной.

Пример. Рассмотрим предикаты А (х): «х < 10», В (х): «х делится на 3», заданные на множестве натуральных чисел. Найдем область истинности предиката А (х) Ù В (х): «х < 10 и делится на 3».

Т_А = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10}, Т_В = {3; 6; 9; 12; 15; …}, тогда Т_{А Ù В} = {3; 6; 9}.

Определение. Дизъюнкцией предикатов А (х) и В (х) называется предикат А (х) Ú В (х), который истинен для тех и только тех значениях х Î Х, для которых истинен хотя бы один из предикатов.

Можно доказать (самостоятельно), что Т_{А Ú В} = Т_А È Т_В.

Пример. Рассмотрим предикаты А (х): «х делится на 2», В (х): «х делится на 3», заданные на множестве натуральных чисел. Найдем область истинности предиката А (х) Ú В (х): «х делится на 2 или на 3».

Т_А = {2; 4; 6; 8; 10;…}, Т_В = {3; 6; 9; 12; 15; …}, Т_{А Ú В} = {2; 3; 4; 6; 8; 9; …}.

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

Заметим, что = .

Определение. Импликацией предикатов А (х) и В (х) называется предикат А (х) Þ В (х) (читают: «Если А (х), то В (х)»). Он обращается в ложное высказывание при тех значениях х Î Х, для которых предикат А (х) истинен, а предикат В (х) ложен.

Из определения имеем, что предикат А (х) Þ В (х) ложен на множестве Т_А Ç , а следовательно истинен на дополнении к этому множеству. Воспользовавшись законами операций над множествами, имеем: .

Контрольные вопросы

1. Что называется высказывательной формой или предикатом?

2. Какие различают предикаты по числу входящих в них переменных? Приведите примеры.

3. Какое множество называют областью определения предиката?

4. Какое множество называют множеством истинности предиката?

5. Что называют конъюнкцией предикатов? Докажите равенство, связывающее область истинности конъюнкции предикатов с областями истинности этих предикатов.

6. Дайте определения дизъюнкции, отрицания, импликации предикатов. Запишите равенства, связывающие области истинности конъюнкции предикатов с областями истинности этих предикатов.

Дата добавления: 2014-01-04