Примеры решения индивидуалных заданий второго уровня

Задача 1. A, B - некоторые множества. Постройте граф логической зависимости для высказываний 1-5:

1) B = A; 2) A¢ÇB = B; 3) A¢ = B¢; 4) A Í ય; 5) ADB¢ Í Æ.

Пусть M - множество рассмотренных выше пяти высказываний. R - бинарное отношение, заданное на M следующим образом: "x,yÎM ( x R y Û y - логическое следствие x ). Проверьте свойства (рефлексивность, симметричность, транзитивность, антирефлексивность, антисимметричность, линейность) отношения R.

Теперь посмотрите на отношение R как на соответствие из M в M и проверьте свойства (однозначность, всюду определенность, разнозначность, соответствие ”на”) этого соответствия.

Решение: Рассмотрим диаграмму Эйлера для множеств A и B (рисунок 4).

Исследуем, какие области на диаграмме должны отсутствовать, чтобы выполнялось каждое из высказываний 1-5.

1) B = A

Очевидное условие: области 2 и 1 должны быть пустыми.

2) A¢ÇB = B

Множество A¢ состоит из областей 0 и 2, а множество B - из областей 2 и 3, тогда A¢ÇB состоит из области 2. С другой стороны, множество B состоит из областей 2 и 3. Чтобы выполнилось условие A¢ÇB = B, область 3 должна быть пустой, т.е. множества A и B не пересекаются.

3) A¢ = B¢

Очевидно, что A¢ = B¢ тогда и только тогда, когда A = B, т.е. высказывание 3 равносильно высказыванию 1.

4) A Í ય

Это высказывание истинно, так как универсальное множество включает в себя все рассматриваемые множества.

5) ADB¢ Í Æ

Множество, которое включается в пустое множество, само является пустым, т.е. ADB¢ = Æ.

Заметим, что ADB¢ = (A\B¢)È(B¢\A). Множество A\B¢ состоит из области 3, множество B¢\A состоит из области 0, тогда множество ADB¢ состоит из областей 3 и 0. Поскольку ADB¢ = Æ, то области 3 и 0 должны быть пустыми. В этом случае A = B¢.

Теперь построим граф логической зависимости для высказываний 1-5.

а) Очевидно, что каждое высказывание равносильно себе, т.е. X « X.

б) Истинное высказывание 4 логически следует из любого высказывания, т.е. 1 ® 4, 2 ® 4, 3 ® 4, 4 ® 4, 5 ® 4.

в) Высказывания 1 и 3 равносильны, т.е. 1 « 3.

г) Между высказываниями 1 и 2 нет никакой логической зависимости, следовательно, между высказываниями 3 и 2 тоже нет логической зависимости.

д) Аналогично, нет логической зависимости между высказываниями 1 и 5, 3 и 5.

е) Рассмотрим высказывания 2 и 5. Высказывание 2 (A¢ÇB = B) равносильно тому, что A и B не пересекаются. Высказывание 5 (ADB¢ Í Æ) равносильно тому, что A = B¢. Если A и B не пересекаются, то не обязательно A = B¢, т.е. 5 не следует из 2. Если A = B¢, то A и B не пересекаются, т.е. 5 ® 2.

Итак, изобразим граф логической зависимости для высказываний 1-5:

Продолжим решение задачи 1. Пусть M - множество рассмотренных выше пяти высказываний. R - бинарное отношение, заданное на M следующим образом: "x,yÎM ( x R y Û y - логическое следствие x ). Проверим свойства отношения R.

а) Рефлексивность: "xÎM (x R x)

Поскольку каждое высказывание равносильно себе, то рефлексивность выполняется.

б) Симметричность: "x,yÎM (x R y Þ y R x)

Отношение R не симметрично, т.к., например, 1 ® 4, но 1 не следует из 4.

в) Транзитивность: "x,y,zÎM (x R y & y R z Þ x R z)

Отношение R транзитивно, т.к. если x ® y и y ® z, то x ® z.

г) Антирефлексивность не выполняется, т.к. выполняется рефлексивность.

д) Антисимметричность: "x,yÎM (x R y & y R x Þ x=y)

Отношение R не антисимметрично, т.к., например, 1 ® 3 и 3 ® 1, но 1¹3.

е) Линейность: "x,yÎM (x R y Ú y R x Ú x=y)

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

Итак, отношение R рефлексивно, не симметрично, транзитивно, не антирефлексивно, не антисимметрично, не линейно.

Продолжим решение задачи 1.

Посмотрим на отношение R как на соответствие из M в M и проверим свойства этого соответствия.

а) Однозначность не выполняется, т.к., например, 1 ® 3 и 1 ® 4, т.е. элемент 1 имеет более одного образа.

б) Всюду определенность выполняется, т.к. каждое высказывание следует из себя.

в) Разнозначность не выполняется, т.к., например элемент 4 имеет более одного прообраза (4 следует из всех высказываний).

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

Задача 2 аналогична задаче 1, но по условию требуется построить только граф логической зависимости (не нужно проверять свойств бинарного отношения и свойств соответствия).

Задача 3. Постройте граф логической зависимости для высказываний 1-3 о натуральных числах a, b:

1) a>b; 2) a+b³=3; 3) a=7 Þ b=9.

Решение:

а) Очевидно, что из первого высказывания не следует второе. Например, «10>3» - истинное высказывание, но «10+3³=3» - ложное, т.е. импликация «a>b Þ a+b³=3» ложна.

б) Проверим, будет ли из второго высказывания следовать первое. Высказывание «a+b³=3» истинно лишь при a=2, b=1, следовательно «a>b». Итак, из второго высказывания следует первое.

в) Проверим, будет ли из первого высказывания следовать третье. Пусть высказывание «a>b» истинно, а «a=7 Þ b=9» - ложно, т.е. a=7 и b¹9. Выберем, например, a=7 и b=2. Высказывание «7>2» истинно, но высказывание «a=7 Þ b=9» ложно, следовательно, импликация «a>b Þ (a=7 Þ b=9)» ложна, т.е. из первого высказывания не следует третье.

г) Очевидно, что из третьего высказывания не следует первое. Например, при a=10, b=23 высказывание «a=7 Þ b=9» истинно (посылка импликации ложна), а высказывание «a>b» - ложно.

д) Проверим, будет ли из второго высказывания следовать третье. Как мы вясняли ранее, высказывание «a+b³=3» истинно лишь при a=2, b=1, но при этом наборе значений a и b высказывание «a=7 Þ b=9» истинно (посылка импликации ложна). Итак, из второго высказывания следует третье.

е) Очевидно, что из третьего высказывания не следует второе. Например, при a=5, b=2 высказывание «a=7 Þ b=9» истинно (посылка импликации ложна), а высказывание «a+b³=3» - ложно.

Итак, изобразим граф логической зависимости для высказываний 1-3: