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

или ребро),

      Qn = K2 × Qn-1.

      Каждый n-куб имеет 2n вершин и n × 2n ребер.

      Найдем граф Q2, представляющий собой декартово произведение К2 × К2.

      Образуем все пары декартова произведения U×V:

      (u1v1) (u1v2) (u2v1) (u2v2).

      Пары (u1v1) и (u1v2) образуют ребро, поскольку первая вершина каждой пары одна и та же u1, а вторые вершины v1 и v2 смежны. Пары (u1v1) и (u2v2) не образуют ребра, потому что нет совпадения вершин ни для первой, ни для второй пары. Граф Q2 показан на рис. 1.16.

      Рис. 1.16

      Кубы Q3 и Q4 показаны на рис. 1.17.

      Рис. 1.17

      Связь между фундаментальными произведениями и вершинами графа – это фактически связь между областями на диаграмме Венна. Если связать таким образом все области диаграммы Венна при двух переменных, то образуется граф, изоморфный графу Q2, при трех – графу Q3, при n – Qn. Граф Q3 для диаграммы Венна при трех переменных показан на рис. 1.18.

      Рис. 1.18

      Теорема 1.5

      Каждое покрытие вершин графа, соответствующего формуле для n переменных, наименьшим числом кубов Qp, наибольшей размерности p (p = 0, 1, 2, …, n – 1), определяет все эквивалентные ей минимальные формулы.

      Минимальная форма представляет собой объединение импликант покрытия. Каждый куб Qp задает один импликант минимальной формы.

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

      Куб Q0 – это одна вершина, и поэтому импликант для него соответствует фундаментальному произведению.

      Куб размерности 1 – это ребро, и его импликант имеет на один литерал меньше, чем фундаментальное произведение вершины, например если куб задается фундаментальными произведениями AС ∩ BС ∩ C и AС ∩ B ∩ C, то здесь не изменяются литералы AС и С. Поэтому импликант состоит из их пересечения АС ∩ С.

      Куб размерности 2 состоит из четырех вершин, и если размерность задачи больше 2, то импликант имеет на две переменные меньше, чем фундаментальное произведение вершины. Например, если куб задается фундаментальными произведениями

      A ∩ B ∩ C, A ∩ B ∩ CС, A ∩ BС ∩ C, A ∩ BС ∩ CС, то здесь только литерал А не изменяется во всех четырех фундаментальных произведениях, поэтому А и будет импликантом для этого куба.

      Куб размерности 3 (при числе переменных больше 3) порождает импликант, у которого на три переменные меньше, чем в фундаментальном произведении, и т. д.

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

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

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

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

      Разобьем вершины на четыре группы и получим следующий граф (рис. 1.19):