Дискретная математика. Краткий курс. Учебное пособие. Александр Анатольевич Казанский

двумя импликантами, что и доказывает минимальное покрытие на рис. 1.21.

      Пример 1.14. Найти минимальную форму для следующей формулы

      Е = (A ∩ B ∩ CС) ∪ (A ∩ B ∩ C) ∪ (ВС ∩ C) ∪ (AС ∩ B ∩ C).

      Определим все пять фундаментальных произведений для формулы Е и получим

      Е = (А ∩ B ∩ C) ∪ (A ∩ B ∩ CС) ∪ (A ∩ BС ∩ C) ∪ (AС ∩ BС ∩ C) ∪ ∪ (AС ∩ B ∩ C).

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

      Рис. 1.22

      Рис. 1.23

      Е1 = А ∩ B ∪ А ∩ С ∪ AС ∩ B;

      Е2 = А ∩ B ∪ ВС ∩ С ∪ AС ∩ B и при этом

      А ∩ B ∪ А ∩ С ∪ AС ∩ B = А ∩ B ∪ ВС ∩ С ∪ AС ∩ B.

      1.17. Решенные задачи

      Множества и подмножества

      1.1. Определить, какие из следующих множеств правильно определены:

      А = {1, 2, 3, 4 },

      B = { a, d, c, d, f },

      C = {x: x ∈ N и

      =2},

      D = { A, B, C },

      Все множества определены правильно.

      Множество А состоит из чисел. Строго говоря, числа – выдуманные объекты, их не существует. Они придуманы для того, чтобы записывать результаты счета. Поэтому более точно следовало бы говорить о множестве символов чисел, или множестве их имен. Однако очень часто, когда необходимо представить множество каких-то объектов, обычно представляют их имена.

      Множество В задано списком букв, однако буква d повторяется дважды. С точки зрения определения это множество эквивалентно следующему: { a, d, c, f }, а такие разные списки могут приводить к недоразумениям. Поскольку во втором списке буква d выброшена из множества, то получается, что d ∉ B, в то же время очевидно, что d ∈ B. Чтобы избежать подобных недоразумений, более рационально задавать множества перечислением элементов без повторения одинаковых.

      Множество С не содержит ни одного элемента, т. е. является пустым (C = Ø). В данном случае x должно быть равным нулю или – 8 и тогда

      = 2, или

      = 2, но ни 0, ни – 8 не является натуральными числами. Возникает вопрос – почему же тогда задаются пустые множества, если они не существуют? Причина в том, что это не всегда заранее известно. Например, если множество задано формулой и производится преобразование этой формулы, то может оказаться, что какая-то часть этой формулы не имеет элементов. Но наличие пустых множеств и наличие правил действий с ними позволяет выполнять преобразования и таких формул. С другой стороны, в настоящее время имеется множество улиц Москвы, на которых в течение дня бывают пробки. Однако никто не может дать гарантии, что не наступит время, когда это множество станет пустым.

      Множество D также правильно определено, но его элементами являются множества, т. е. это множество множеств.

      1.2. Найти список элементов для каждого из множеств:

      (а) А = {x: x ∈ N, x – нечетно и x < 10},

      (b) B = {x: x ∈ N,

      ∈N и x < 50},

      (c) C = {x: x ∈ N и

       <