какие предикаты обычно используются для представления бинарных отношений между объектами

Свойства, отношения и предикаты

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

В традиционной логике свойство отображается в суждениипредикатом, а вещь, которой принадлежит это свойство, –субъектом. Следует, однако, различать субъект и предикат в грамматике и логике, подобнотомукак мы различаем предложение и суждение (высказывание) Суждения, имеющие субъектно-предикатную структуру, отображают часто встречающиеся в действительном мири связи между вещами, событиями и явлениями, соднойстороны, и их свойствами и признаками, с другой.Именно эти связи и стали предметом изучения традиционной логики. Хотя различные виды отношений, такие,как»больше», «меньше», «выше», «ниже», «дальше», «ближе» и т.п., не говоря уже об отношениях родства встречаются часто, но традиционная логика либо совершенно не интересовалась логическим анализом отношений, либо пыталась свести их к субъектно-предикатной структуре.

Впервые изучением логики отношений занялись математики, и ее основоположником считается английский математик и логик О. де Морган. Интерес к данной логике со стороны математиков вовсе не случаен, поскольку именно в этой науке встречаются самые разнообразные отношения (равенства, неравенства, подобия, между, включения, конгруэнтности, параллельности и т.д.). Такие отношения представлены в формулировке аксиом различных математических дисциплин, и поэтому для доказательства теорем необходимы точные определения тех логических операций, которые можно производить над отношениями.

С логической точки зрения отношения можно рассматривать как обобщение обычного предиката традиционной логики, выражающего свойства предметов. Если этот предикат характеризует один-единственный предмет или, как мы будем говорить в дальнейшем, объект, то в логике отношений он определяет отношение между разными объектами. Так, когда мы говорим, что число 5 больше, чем 3, то тем самым устанавливаем между ними отношение «больше» по величине.

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

Символически это представляется так:

где Р обозначает предикат, a x1, х2. хn – соответствующие объекты. Если п = 0, тогда предикат будет нерасчлененным высказыванием, которое рассматривалось в предыдущей главе, при п = 1 предикат представляет свойство, при n = 2 – бинарное отношение, при п = 3 – тернарное отношение и т.д.

С логико-математической точки зрения предикат можно рассматривать как пропозициональную функцию. В отличие от математических функций, где аргументами служат числа и другие математические объекты, в пропозициональной функции аргументами являются только высказывания. Если такой предикат выражает свойство, например «быть студентом», то, подставив вместо аргумента х фамилии разных лиц, мы получим различные высказывания, истинные и ложные, т.е., если Иванов действительно студент, то он будет удовлетворять функции Р(х), где Р обозначает свойство «быть студентом». Аналогично, если Ч(х) обозначает свойство «быть четным числом», то число 4 удовлетворяет этой функции, а число 5 – нет. Обратите внимание, что в этом случае вместо обычных чисел аргументами служат высказывания о числах.

Предикат Р(х,у) является пропозициональной функцией от двух аргументов и выражает бинарное отношение между двумя объектами, например «Москва южнее, чем С.-Петербург». В данном случае предикат Р обозначает отношение «быть южнее». Если вместо «Москвы» взять «Мурманск», то получится ложное высказывание. Отсюда становится ясно, что предикат или пропозициональная функция сами по себе не являются высказываниями, и потому не могут считаться ни истинными _ни ложными. Они становятся истинными или ложными высказываниями после того, как вместо их аргументов подставляются конкретные высказывания. Такой функциональный подход к предикатам дает возможность обращаться с ними как со специальными видами функций, аргументами которых являются не математические, а логические объекты, а именно высказывания.

Объектами же рассуждений могут быть самые разнообразные предметы как реального, так и идеального мира, события, явления, процессы. Предикаты, которые их характеризуют, в принципе позволяют выделить класс (или множество) этих объектов. Такой класс в логике называютуниверсумом рассуждения. Например, универсумом рассуждений в арифметике является множество чисел, в химии– различные химические элементы, простые и сложные вещества, в которые они входят, в биологии – живые организмы, в социальных науках– группы, коллективы, классы людей и соответствующие общественные структуры. Логика не изучает и не определяет универсумы конкретных видов рассуждений. Это составляет задачу конкретных наук. Поэтому в логическом анализе такие универсумы предполагаются заданными.

Существует два принципиально отличных способа задания универсума рассуждения, первый из которых состоит в систематическом перечислении всех тех объектов, которые составляют класс объектов, характеризуемых данным свойством или отношением. Очевидно, что такой универсум должен быть конечным множеством. Однако в научном познании приходится иметь дело не только с конечными, но и бесконечными множествами объектов. Например, в математике уже натуральный ряд чисел является бесконечным множеством, поскольку к любому, сколь угодно большому натуральному числу можно прибавить единицу и тем самым неограниченно продолжать этот процесс. При формулировании научных законов также часто приходится обращаться к бесконечному множеству объектов. Так, в законе всемирного тяготения Ньютона утверждается, что два любых тела притягиваются друг к другу с гравитационной силой, прямо пропорциональной произведению их масс и обратно пропорциональной квадрату расстояния между ними. При этом предполагается, что количество таких тел во Вселенной бесконечно много. Очевидно, что поскольку бесконечное множество нельзя задать с помощью конечного списка его элементов, то приходится для этого обращаться к некоторому общему правилу или закону образования его элементов. Например, зная, что четными называются числа, делящиеся на 2, всегда можно определить, является ли рассматриваемое число четным или нечетным.

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

Хотя в принципе, если свойство или отношение сформулированы достаточно ясно и четко, установить универсум можно, но на практике сделать это бывает трудно из-за неопределенности критериев разграничения множеств объектов. Порой бывает, например, нелегко ответить на вопрос, принадлежит ли данный объект к множеству растений или животных, металлов или металлоидов, устойчивых или неустойчивых систем, когда заходит речь о переходных, промежуточных явлениях.

Но в большинстве случаев при наличии предиката, выражающего свойство или отношение, можно всегда установить его универсум, или, как предпочитают говорить математики, область значений переменных пропозициональной функции, которую называютобластью определения функции. Если эта область точно не установлена, то пропозициональная функция при подстановке на место аргументов конкретных объектов превращается в бессмысленную фразу, а не осмысленное высказывание – истинное или ложное. Нередко бывает так, что функция оказывается неопределенной в некоторой области значений. Например, в математике говорят, что уравнение х 2 + 1=0 не определено в области действительных чисел, ибо имеет мнимый корень. Чтобы гарантировать точность рассуждений, в математике и логике ясно и однозначно определяют ту предметную область, к которой относятся переменные пропозициональных функций или предикатов.

В простейшем исчислении предикатов, которое называют также узким или исчислением предикатов первой ступени, в качестве значения переменных будут рассматриваться индивиды или объекты. Но можно в качестве значений переменных брать также предикаты, связанные кванторами. Такое исчисление называют исчислением предикатов второй ступени. Дальнейшие обобщения приводят к исчислениями предикатов высших ступеней.

Так же, как и в исчислении высказываний, мы будет предполагать, что высказывание Р(х,у), получаемое при любой паре значений из области ее значений, может быть либо истинным, либо ложным. Другими словами, в исчислении предикатов, как и в исчислении высказываний, выполняется закон исключенного третьего. Но при этом, как мы увидим в дальнейшем, сама процедура получения значения истинности сложного высказывания, состоящего из элементарных высказываний, значительно усложняется: ведь в таком случае с ним приходится соотносить не один, а пару, тройку или вообще п-ку объектов из области значений переменных.

Источник

Лекция 3. Отношения на множествах. Свойства бинарных отношений

п.3. Отношения на множествах. Свойства бинарных отношений.

Когда говорят о родстве двух людей, например, Сергей и Анна, то подразумевают, что есть некая семья, к членам которой они относятся. Упорядоченная пара (Сергей, Анна) отличается от других упорядоченных пар людей тем, что между Сергеем и Анной есть некое родство (кузина, отец и т. д.).

В математике среди всех упорядоченных пар прямого произведения двух множеств A и B (A´B) тоже выделяются «особые» пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В качестве примера рассмотрим множество S студентов какого-нибудь университета и множество K читаемых там курсов. В прямом произведении S´K можно выделить большое подмножество упорядоченных пар (s, k), обладающих свойством: студент s слушает курс k. Построенное подмножество отражает отношение «… слушает …», естественно возникающее между множествами студентов и курсов.

Для строгого математического описания любых связей между элементами двух множеств введем понятие бинарного отношения.

Определение 3.1. Бинарным (или двухместным) отношением r между множествами A и B называется произвольное подмножество A´B, т. е.

.

В частности, если A=B (то есть rÍA2), то говорят, что r есть отношение на множестве A.

Элементы a и b называются компонентами (или координатами) отношения r.

Замечание. Договоримся, что для обозначения отношений между элементами множеств использовать греческий алфавит: r, t, j, s, w и т. д.

Пример 3.1. Пусть даны два множества A= <1; 3; 5; 7>и B=<2; 4; 6>. Отношение зададим следующим образом t=<(x; y)ÎA´B | x+y=9>. Это отношение будет состоять из следующих пар (3; 6), (5; 4) и (7; 2), которые можно записать в виде t=<(3; 6), (5; 4), (7;2)>. В данном примере Dt= <3; 5; 7>и Rt= B=<2; 4; 6>.

Пример 3.2. Отношение равенства на множестве действительных чисел есть множество r=<(x; y) | x и y – действительные числа и x равно y>. Для этого отношения существует специальное обозначение «=». Область определения совпадает с областью значений и является множеством действительных чисел, Dr= Rr.

Пример 3.3. Пусть A – множество товаров в магазине, а B – множество действительных чисел. Тогда j=<(x; y)ÎA´B | y – цена x> – отношение множеств A и B.

Если обратить внимание на пример 3.1., то можно заметить, что данное отношение было задано сначала в виде t=<(x; y)ÎA´B | x+y=9>, а потом записано в виде t=<(3; 6), (5;4), (7;2)>. Это говорит о том, что отношения на множествах (или одном множестве) можно задавать различными способами. Рассмотрим способы задания бинарных отношений.

Способы задания отношений:

1) с помощью подходящего предиката;

2) множество упорядоченных пар;

3) в графической форме: пусть A и B – два конечных множества и r – бинарное отношение между ними. Элементы этих множеств изображаем точками на плоскости. Для каждой упорядоченной пары отношения r рисуют стрелку, соединяющую точки, представляющие компоненты пары. Такой объект называется ориентированным графом или орграфом, точки же, изображающие элементы множеств, принято называть вершинами графа.

4) в виде матрицы: пусть A=<a1, a2, …, an> и B=<b1, b2, …, bm>, r – отношение на A´B. Матричным представлением r называется матрица M=[mij] размера n´m, определенная соотношениями

.

Кстати, матричное представление является представлением отношения в компьютере.

Пример 3.4. Пусть даны два множества A=<1; 3; 5; 7>и B=<2; 4; 6>. Отношение задано следующим образом t=<(x; y) | x+y=9>. Задать данное отношение как множество упорядоченных пар, орграфом, в виде матрицы.

Решение. 1) t= <(3; 6), (5; 4), (7; 2)>— есть задание отношения как множества упорядоченных пар;

2) соответствующий ориентированный граф показан на рисунке.

3) в матричном представлении это отношение имеет вид

Пример 3.5. Еще в качестве примера можно рассмотреть предложенную Дж. фон Нейманом (1903 – 1957) блок-схему ЭВМ последовательного действия, которая состоит из множества устройств M:

,

где a – устройство ввода, b – арифметическое устройство (процессор), c – устройство управления, d – запоминающее устройство, e – устройство вывода.

Рассмотрим информационный обмен между устройствами mi и mj, которые находятся в отношении r, если из устройства mi поступает информация в устройство mj.

Это бинарное отношение можно задать перечислением всех его 14 упорядоченных пар элементов:

Соответствующий орграф, задающий это бинарное отношение, представлен на рисунке:

Матричное представление этого бинарного отношения имеет вид:

Для бинарных отношений обычным образом определены теоретико-множественные операции: объединение, пересечение и т. д.

Введем обобщенное понятие отношения.

Определение 3.3. n-местное (n—арное) отношение r – это подмножество прямого произведения n множеств, то есть множество упорядоченных наборов (кортежей)

Многоместные отношения удобно задавать с помощью реляционных таблиц. Такое задание соответствует перечислению множества n-к отношения r. Реляционные таблицы широко используются в компьютерной практике в реляционных базах данных. Заметим, что реляционные таблицы нашли применение в повседневной практике. Всевозможные производственные, финансовые, научные и другие отчеты часто имеют форму реляционных таблиц.

Слово «реляционная» происходит от латинского слова relation, которое в переводе на русский язык означает «отношение». Поэтому в литературе для обозначения отношения используют букву R (латинскую) или r (греческую).

Далее мы будем рассматривать только двухместные (бинарные) отношения, при этом опуская слово «бинарные».

Определение 3.4. Пусть rÍA´B есть отношение на A´B. Тогда отношение r-1 называется обратным отношением к данному отношению r на A´B, которое определяется следующим образом:

Определение 3.5. Пусть r ÍA´B есть отношение на A´B, а s ÍB´C – отношение на B´C. Композицией отношений s и r называется отношение t ÍA´C,которое определяется следующим образом:

2) Используя определение композиции двух отношений, получаем

из (1, y)Îr и (y, d)Îs следует (1, d)Îs◦r;

Теорема 3.1. Для любых бинарных отношений выполняются следующие свойства:

1) ;

2) ;

3) — ассоциативность композиции.

Доказательство. Свойство 1 очевидно.

Свойство 3 доказать самостоятельно.

3.2. Свойства бинарных отношений.

Рассмотрим специальные свойства бинарных отношений на множестве A.

Свойства бинарных отношений.

1. Отношение r на A´A называется рефлексивным, если (a,a) принадлежит r для всех a из A.

2. Отношение r называется антирефлексивным, если из (a,b)Îr следует a¹b.

3. Отношение r симметрично, если для a и b, принадлежащих A, из (a,b)Îr следует, что (b,a)Îr.

4. Отношение r называется антисимметричным, если для a и b из A, из принадлежности (a,b) и (b,a) отношению r следует, что a=b.

5. Отношение r транзитивно, если для a, b и c из A из того, что (a,b)Îr и (b,c)Îr, следует, что (a,c)Îr.

Решение. 1) Это отношение рефлексивно, так как для каждого aÎA, (a; a)Îr.

2) Отношение не является антирефлексивным, так как не выполняется условие этого свойства. Например, (2, 2)Îr, но отсюда не следует, что 2¹2.

3) Рассмотрим все возможные случаи, показав, что отношение r является симметричным:

4) Данное отношение не является антисимметричным, поскольку (1, 2)Îr и (2,1)Îr, но отсюда не следует, что 1=2.

5) Можно показать, что отношение r транзитивно, используя метод прямого перебора.

Как по матрице представления

определить свойства бинарного отношения

1. Рефлексивность: на главной диагонали стоят все единицы, звездочками обозначены нули или единицы.

.

2. Антирефлексивность: на главной диагонали все нули.

3. Симметричность: если .

4. Антисимметричность: все элементы вне главной диагонали равны нулю; на главной диагонали тоже могут быть нули.

.

Операция «*» выполняется по следующему правилу: , где , .

5. Транзитивность: если . Операция «◦» выполняется по обычному правилу умножения, при этом надо учитывать: .

3.3 Отношение эквивалентности. Отношение частичного порядка.

Отношение эквивалентности является формализацией такой ситуации, когда говорят о сходстве (одинаковости) двух элементов множества.

Определение 3.6. Отношение r на A есть отношение эквивалентности, если оно рефлексивно, симметрично и транзитивно. Отношение эквивалентности arb часто обозначается: a

Пример 3.8. Отношение равенства на множестве целых чисел есть отношение эквивалентности.

Пример 3.9. Отношение «одного роста» есть отношение эквивалентности на множестве людей X.

Отношение «сравнимых по модулю m целых чисел» есть отношение эквивалентности на множестве целых числе ¢. В самом деле:

это отношение рефлексивно, т. к. для «x΢ имеем x—x=0, и, следовательно, оно делится на m;

это отношение симметрично, т. к. если (x—y) делится на m, то и (y—x) тоже делится на m;

это отношение транзитивно, т. к. если (x—y) делится на m, то для некоторого целого t1 имеем , а если (y—z) делится на m, то для некоторого целого t2 имеем , отсюда , т. е. (x—z) делится на m.

Определение 3.7. Отношение r на A есть отношение частичного порядка, если оно рефлексивно, антисимметрично и транзитивно и обозначается символом °.

Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить при каких условиях считать, что один элемент множества превосходит другой.

Пример 3.12. Во множестве подмножеств некоторого универсального множества U отношение AÍB есть отношение частичного порядка.

Пример 3.13. Схема организации подчинения в учреждении есть отношение частичного порядка на множестве должностей.

Прообразом отношения частичного порядка является интуитивное понятие отношения предпочтения (предшествования). Отношение предпочтения выделяет класс задач, которые можно объединить, как задача о проблеме выбора наилучшего объекта.

Формулировка задачи: пусть имеется совокупность объектов A и требуется сравнить их по предпочтительности, т. е. задать отношение предпочтения на множестве A и определить наилучшие объекты.

Отношение предпочтения P, которое можно определить как «aPb, a, bÎA Û объект a не менее предпочтителен, чем объект b» является по смыслу рефлексивным и антисимметричным (каждый объект не хуже самого себя, и, если объект a не хуже b и b не хуже a, то они одинаковы по предпочтительности). Естественно считать, что отношение P транзитивно (хотя в случае, когда, например, предпочтения обсуждаются группой лиц с противоположными интересами, это свойство может быть нарушено), т. е. P – отношение частичного порядка.

Один из возможных способов решения задачи сравнения объектов по предпочтительности – ранжирование, т. е. упорядочение объектов в соответствии с убыванием их предпочтительности или равноценности. В результате ранжирования мы выделяем «наилучшие» или «наихудшие» с точки зрения отношения предпочтения объекты.

Области применения задачи о проблеме выбора наилучшего объекта: теория принятия решений, прикладная математика, техника, экономика, социология, психология.

Источник