Дискретная математика. Краткий курс. Учебное пособие. Александр Анатольевич Казанский
Читать онлайн книгу.
граф следующим образом. Вершины графа сопоставим фундаментальным произведениям, а две вершины соединены ребром, если соответствующие им фундаментальные произведения имеют различие точно в одном литерале (т. е. являются смежными).
Для единообразного изображения графов на диаграммах разобьем множество вершин на группы, которые разместим на диаграмме слева направо. В самую левую группу поместим вершину, которой соответствует фундаментальное произведение, не содержащее переменных с дополнениями. Далее поместим вершины, которым соответствуют фундаментальные произведения с одним дополнением, затем с двумя, с тремя и т. д. Последняя, правая, группа должна содержать вершину, соответствующую фундаментальному произведению, в котором все переменные имеют дополнения. Диаграмма может содержать не все группы, и каждая группа может содержать не все вершины, поскольку это определяется конкретным многочленом. Такое размещение вершин удобно еще и потому, что ребра в графе будут появляться только между вершинами, находящимися в соседних группах, поскольку только они могут быть смежными.
Пример 1.12. Построить граф для множества, задаваемого многочленом, представляющим собой полную нормальную форму объединения пересечений:
Е = (А ∩ В ∩ С) ∪ (А ∩ В ∩ СС) ∪ (А ∩ ВС ∩ СС) ∪ (АС ∩ В ∩ СС) ∪ ∪ (АС ∩ ВС ∩ СС).
Многочлен содержит 5 фундаментальных произведений, поэтому в графе будет 5 вершин. Поскольку многочлен содержит n = 3 переменных, то при разбиении вершин возможны n + 1 = 4 группы. В левой группе будет вершина соответствующая фундаментальному произведению А ∩ В ∩ С. В следующей за ней группой с одним дополнением возможны три вершины, однако в данном многочлене имеется только одна такая вершина, соответствующая фундаментальному произведению А ∩ В ∩ СС. Фундаментальных произведений с двумя дополнениями в данном многочлене два: А ∩ ВС ∩ СС и АС ∩ В ∩ СС, поэтому группа состоит из двух вершин. Последняя правая группа состоит из одной вершины. Граф выглядит следующим образом (рис. 1.13):
Рис. 1.13
Пример 1.13. Для множества, задаваемого многочленом Е из предыдущего примера, найти полную нормальную форму пересечения объединений и построить для нее граф.
Чтобы найти для Е эквивалентную ему полную нормальную форму пересечения объединений, необходимо, как известно из параграфа 1.13, либо раскрыть скобки в выражении для Е, либо использовать диаграмму Венна. Любой из этих способов дает
Е = (A ∪ B ∪ CC) ∩ (A ∪ BC ∪ CC) ∩ (AC ∪ B ∪ CC).
Многочлен содержит три фундаментальных объединения, поэтому граф будет иметь три вершины. Группы, которая должна состоять из фундаментального объединения, не имеющего дополнений, здесь нет. Группа с одним дополнением имеет одно фундаментальное объединение A ∪ B ∪ CC, а группа с двумя дополнениями имеет два фундаментальных объединения: A ∪ BC ∪ CC и AC ∪ B ∪ CC, поэтому граф имеет вид (рис. 1.14):
Рис. 1.14
Следует