Определение
Наглядное представление: двудольный граф — это граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.
Определение: неориентированный
граф G = (W,E) называется
двудольным, если множество его вершин
можно разбить на две части
,
| U | > 0, | V | > 0, так, что ни одна
вершина в U не соединена с вершинами
в U и ни одна вершина в V не
соединена с вершинами в V.
Пример: решётка, вершины которой раскрашены в 2 цвета в шахматном порядке.
Двудольный граф называется полным,
если для каждой пары вершин
существует
ребро
.
Для | U | = i, | V | = j такой
граф называется Ki,j
Упражнение 1. Приведите пример двудольного графа с 6 вершинами. Упражнение 2. Докажите признаки двудольных графов:
1) Граф является двудольным тогда и только тогда, когда он не содержит цикла нечётной длины.
2) Граф является двудольным тогда и только тогда, когда он 2-раскрашиваем (то есть его хроматическое число равняется двум). Хроматическое число – минимальное количество цветов, требуемое для раскраски вершин графа, при которой любые вершины, соединенные ребром, раскрашены в разные цвета.
Двудольные графы применяются, когда изучаемые объекты разделяются на две группы так, что внутри групп интересующие нас взаимодействия отсутствуют. Например, в экономике — производители и потребители.
На рисунках вершины двудольного графа часто располагают на параллельных прямых.
С двудольными графами связана задача
о назначениях. Пусть
—
множество претендентов на рабочие
места,
—
множество рабочих мест. Необходимо
каждого из претендентов обеспечить
работой в соответствии с его профессиональной
подготовкой.
Булевы функции
Определение. Функцию от одной или нескольких переменных, аргументы и значение которой могут принимать только значения 0 или 1, называют булевой функцией (в честь английского математика Джорджа Буля (1815 - 1864), одного из основателей математической логики).
Примеры.
Конъюнкция:
=
1 тогда и только тогда, когда x
и y оба равны 1.
Дизъюнкция:
=
1 тогда и только тогда, когда x
и y оба равны 1.
Для того, чтобы каждый раз не описывать значения словами, булеву функцию обычно задают таблицей истинности, то есть таблицей, в которой указаны значения для всех наборов переменных.
При этом значения наборов переменных располагают в лексикографическом порядке. Сначала набор из одних нулей, затем правый ноль заменяют 1, и так далее, до набора из одних единиц. Например:
|
x |
y |
|
|
0 |
0 |
0 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
|
x |
y |
|
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
1 |
Эквивалентность:
(Значение
выражения равно 1, если значения x
и y совпадают)
|
x |
y |
|
|
0 |
0 |
1 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
Симметрическая разность:
(Значение
выражения равно 1, если значения x
и y не совпадают)
|
x |
y |
|
|
0 |
0 |
1 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
Импликация:
(Мнемоническое
правило: из нуля следует что угодно –
и ноль, и единица)
|
x |
y |
|
|
0 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
Отрицание:
|
x |
|
|
0 |
1 |
|
1 |
0 |
Приоритет булевых функций
Высший приоритет у отрицания. За ним идёт конъюнкция. Далее – дизъюнкция, симметрическая разность, эквивалентность, импликация. Иногда, впрочем, для дополнительного уточнения конъюнкцию заключают в скобки.
Некоторые равенства о булевых функциях двух переменных
В дальнейшем нам понадобятся следующие три равенства. Их можно обосновать логическими рассуждениями, а можно и с помощью сравнения таблиц истинности.
1.
2.
3.
Пример построения таблицы истинности для булевой функции трёх переменных
Для функции трёх переменных таблица истинности содержит 8 строк.
Например:
Для вычисления такой функции имеет смысл составить дополнительные столбцы, для промежуточных вычислений.
|
x |
y |
z |
|
|
f |
|
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
0 |
|
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
Примечание. В дальнейшем мы будем
рассматривать действия с булевыми
функциями прежде всего на примере
функции
.
Но если студенты быстро понимают
материал, можно рассматривать
дополнительные примеры для не очень
сложных функций – например,
или
.
Совершенная дизъюнктная нормальная форма (СДНФ)
и совершенная конъюнктная нормальная форма (СКНФ)
В некоторых случаях бывает удобно выразить булеву функцию только через конъюнкцию, дизъюнкцию и отрицание.
Например, это удобно из-за того, что выражения с этими операциями удобно подставлять одно в другое.
Для вычисления СКНФ и СДНФ нам пригодится только что построенная таблица.
|
x |
y |
z |
|
|
f |
СДНФ |
СКНФ |
|
0 |
0 |
0 |
1 |
0 |
0 |
|
|
|
0 |
0 |
1 |
1 |
1 |
1 |
|
|
|
0 |
1 |
0 |
0 |
1 |
0 |
|
|
|
0 |
1 |
1 |
0 |
1 |
0 |
|
|
|
1 |
0 |
0 |
1 |
0 |
0 |
|
|
|
1 |
0 |
1 |
1 |
1 |
1 |
|
|
|
1 |
1 |
0 |
1 |
1 |
1 |
|
|
|
1 |
1 |
1 |
1 |
1 |
1 |
|
|
Правило построения СДНФ: выбрать те и только те строки, в которых значение функции равно 1, затем в этих строках записать конъюнкцию x, y, z по следующему правилу:
Если соответствующая переменная равна 0, то пишем её с отрицанием, если она равна 1, то пишем без отрицания.
Например, во второй строке мы пишем
,
поскольку в соответствующей строке
были значения x = 0, y
= 0, z = 1.
СДНФ записывают как дизъюнкцию этих выражений. При этом иногда операцию конъюнкции не пишут, подобно тому как для умножения не пишут операцию умножения.
В итоге получаем: СДНФ =
.
Построение СКНФ в некотором смысле двойственно к построению СКНФ.
Вместо строк со значением 1 берём строки со значением 0, вместо дизъюнкции – конъюнкция, а вместо конъюнкции дизъюнкцию.
И одно принципиальное отличие – там,
где значение переменной равно 0, мы берём
её без отрицания, а там, где это значение
равно 1, берём с отрицанием. Сравните
первую и третью строки, выражения в
которых равны соответственно
и
.
Выражение для СКНФ можно получить, перемножив все эти дизъюнкции.
СКНФ =
.
Следующее важное действие – упростить СДНФ.
Это можно сделать с помощью действий, аналогичных вынесению множителя за скобку.
Итак, упрощённая форма СДНФ в данном
случае равна
.
Показать логическую схему, причём написать, что для первоначальной записи потребовалось бы очень много элементов: импликация, эквивалентность, и так далее. А для СКНФ достаточно трёх элементов: И, ИЛИ и НЕ.
Привести пример составления схемы для СДНФ и для упрощённой ДНФ.
Но, как во многих задачах на упрощение, возникает вопрос: можно ли упростить выражение дальше? Точнее сказать – можно ли получить выражение, содержащее ещё меньше букв и равное данному?
Ответ даёт метод минимизирующих карт.
Для его применения составьте таблицу такого вида.
|
f |
Значения переменных |
x |
y |
z |
xy |
xz |
yz |
xyz |
|
0 |
000 |
|
|
|
|
|
|
|
|
1 |
001 |
|
|
z |
|
|
|
|
|
0 |
010 |
|
y |
|
|
|
|
|
|
0 |
011 |
|
y |
z |
|
|
yz |
|
|
0 |
100 |
x |
|
|
|
|
|
|
|
1 |
101 |
x |
|
z |
|
xz |
|
|
|
1 |
110 |
x |
y |
|
xy |
|
|
|
|
1 |
111 |
x |
y |
z |
xy |
xz |
yz |
xyz |
Каждую переменную, x, y и z, мы снабжаем или не снабжаем отрицанием в соответствии со значениями переменных.
Например, если во втором столбце 001, то x и y с отрицаниями, а z – без отрицания.
А в остальных столбцах переменные сопровождаются отрицаниями в соответствии с третьим, четвёртым и пятым столбцами.
Теперь производим вычёркивание по следующему принципу.
Сначала вычёркиваем все строки, в которых значение функции равно нулю. В данном примере вычёркиваются строки с номерами 1, 3, 4 и 5.
Затем в каждом столбце, если элемент
был один раз вычеркнут, он вычёркивается
во всех оставшихся клетках столбца.
Например, если во второй сверху клетке
шестого столбца элемент
был вычеркнут, то в третьей сверху клетке
его также вычеркнем.
Теперь из оставшихся элементов, взяв по одному элементу из строки, составим самое короткое выражение.
В данном примере из второй и шестой
строк имеет смысл взять два одинаковых
выражения
,
а из седьмой и восьмой строк – два
одинаковых выражения xy,
поскольку при вычислении дизъюнкции
получим:
.
Рекомендуется сначала найти упрощённое выражение методом минимизирующих карт, а затем производить упрощение СДНФ алгебраическими преобразованиями.
Если преобразования дали такой же ответ, что и метод минимизирующих карт, это добавляет уверенности в ответе.
Если они дали ответ длиннее, то, возможно, вы не до конца использовали возможности упрощения.
А если преобразования дали ответ короче, чем метод минимизирующих карт, то такая ситуация теоретически противоречива: метод минимизирующих карт даёт самую короткую форму записи.
В качестве упражнения на булевы функции
можно рассматривать вычисление функции
,
где f – функция от
трёх переменных.
Задачу можно решать двумя способами.
Первый способ: найти значения выражений
для
всех значений пары x,
y. Затем подставить
полученные значения в функцию от трёх
переменных.
Например: если x = y
= 0, то
(по таблице истинности для функции f).
Дополнительное условие для этой задачи: по таблице истинности необходимо определить формулу для полученной функции от двух переменных. Например, xy или x XOR y.
Второй способ: подставить в исходную
формулу для функции (например,
)
вместо переменной y
выражение
,
а вместо переменной z
выражение
,
затем упростить выражение.