Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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


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

 

Определение. Отношение 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; Просмотров: 3545; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.006 сек.