Упражнение. Как объяснить, что на рис. 16.1 некоторые стрелки заострены с двух сторон, а некоторые – только с одной?
Определение 1. С кажем, что отношение Р (заданное на некотором множестве М) асимметрично, если ни для какой пары элементов a,b из множества М не может одновременно быть aPb
и bPa.
На графе асимметричного отношения, очевидно, никакие стрелки не могут быть заострены с двух сторон.
Определение 2. Скажем, что отношение Р, заданное на множестве М, транзитивно, если для любых трех элементов a,b,c
из М одновременная справедливость aPb и bPc влечет за собой справедливость аPc.
На графе транзитивного отношения, таким образом, одновременно с составным путем (вдоль стрелок), идущим из a в c через b, cуществует стрелка, непосредственно идущая из a в c.
Определение 3. Отношение Р, заданное на множестве М, называется связным, если для любых двух элементов a, b из М справедливо хотя бы одно из двух соотношений: aPb, bPa.
Определение 4. Отношение Р задает на множестве М линейный порядок, если оно асимметрично, транзитивно и связно.
Пример. Пусть множество М состоит из n человек. Очевидно, что линейно упорядочить множество М – это поставить людей, составляющих данное множество, в очередь друг за другом. Заметим, что в силу правила произведения из n людей можно образовать n! различных очередей.
Преподавая тему «Отношения на множестве», авторы столкнулись с некоторым дефицитом интересных, но несложных задач. Предлагаемая ниже задача представляет собой попытку компенсировать упомянутый дефицит.
Задача 1. В стране Карабасии N городов, причем каждый город соединен с каждым дорогой с односторонним движением (направление движения показано стрелкой на специальных дорожных указателях). Однажды ночью в Карабасию прилетел Змей Горыныч и переставил указатели так, что на следующее утро ни один из жителей Карабасии, выехавший из своего города, не смог потом вернуться домой. Требуется выяснить:
а) Как это удалось сделать Змею Горынычу?
б) Сколькими различными способами мог осуществить Змей Горыныч свою затею?
Решение. а) На первый взгляд, задача кажется трудной. Однако решение ее очнь простое. Нужно перенумеровать числами от 1 до N все города Карабасии и установить дорожные указатели так, чтобы каждая стрелка указывала направление от города с меньшим номером к городу с большим номером. Тогда, выехав из произвольно взятого города, в него будет невозможно вернуться. (При этом из города с номером N невозможно будет выехать.)
б) Ответ: N!
Задача 2. Верно ли, что если из каждого города в Карабасии можно выехать, то найдется хотя бы один город, в который можно будет вернуться? (Движение по всем дорогам Карабасии одностороннее.)
– квантор общности (х – «для всех х»);
– квантор существования (х – «найдется х»);
– дизъюнкция высказываний (АВ – «А или В», в смысле «хотя бы одно из двух»);
– конъюнкция высказываний (АВ – «А и В»);
¬ – отрицание высказывания (¬А – «не А», «неверно, что А»);
– импликация высказываний (АВ – «если А, то В»);
– эквиваленция высказываний (АВ – «А тогда и только тогда, когда В»);