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

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

(1) B = A; (2) AB = B; (3) A = B; (4) A  ય; (5) AB  .

Пусть 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) AB  

Множество, которое включается в пустое множество, само является пустым, т.е. AB = . Заметим, что AB = (A\B)(B\A). Множество A\B состоит из области 3, множество B\A состоит из области 0, тогда множество AB состоит из областей 3 и 0. Поскольку AB = , то области 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) (AB  ) равносильно тому, что 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. A, B  некоторые множества. Постройте граф логической зависимости для утверждений (1)(6):

(1) B¢ Ç A¢ Í A; (2) A D B¢ = B; (3) A = B; (4) A È B¢ Í B D A¢;

(5) A Ç B¢ Í Æ; (6) A¢ Ê B.

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

Граф логической зависимости для утверждений (1)(6):

Задача 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):