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

Читать онлайн книгу.

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


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

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

      Е = (ABCС) ∪ (ABC) ∪ (ВС ∩ C) ∪ (AС ∩ BC).

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

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

      Разобьем вершины на четыре группы, построим граф и найдем два его минимальных покрытия (рис. 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: xN и

      =2},

      D = { A, B, C },

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

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

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

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

      = 2, или

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

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

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

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

      (b) B = {x: xN,

      ∈N и x < 50},

      (c) C = {x: xN и

       <


Скачать книгу