1. Дизъюнкция двух переменных равна 1, если хотя бы одна из них равна 1 и равна 0, если обе переменные равны 0:
0+0=0;
0+1=1;
1+0=1;
1+1=1.
2. Конъюнкция двух переменных равна 0, если хотя бы одна переменная равна 0 и равна 1, если обе переменные равны 1:
0∙0=0;
0∙1=0;
1∙0=0;
1∙1=1.
3.Инверсия одного значения переменной совпадает с ее другим значением:
1= 0;
0 = 1.
Элементарные булевые функции
Булевой функцией f(x1, x2,..., xn) называется функция, которая принимает два значения 0 или 1 в зависимости от переменных х1, каждая из которых может также принимать только два значения 0 или 1.
Одной из важнейших интерпретаций теории булевых функций является теория переключательных функций. Первоначально математический аппарат теории булевых функций был применен для анализа и синтеза релейно-контактных схем с операциями последовательного и параллельного соединения контактов.
Любая булевая функция может быть представлена таблицей, в левой части которой перечислены все наборы переменных, а в правой части - значения функции. Пример такого задания для трех переменных представлен в таблице.
Представление булевой функции
x1 | x2 | x3 | f(х1,х2,х3) |
Для формирования столбца значений переменных удобен лексикографический порядок, в соответствии с которым каждый последующий набор значений получается из предыдущего прибавлением 1 в двоичной системе счисления, например, 100=011+1.
Булевая функция п переменных может иметь 2n наборов. Поскольку функция принимает только два значения, общее число булевых функций и переменных равно 22n. Таким образом, функция одной переменной может иметь четыре значения: у = х; у = -x (отрицание х); у = 0 (константа 0); у = 1 (константа 1).
Из них выделим функцию "отрицание x" (обозначается -x ). Эта функция представлена в таблице
Функция отрицания
x | -x |
Булевых функций двух переменных - 16. Те из них, которые имеют специальные названия, представлены в таблице.
Булевы функции двух переменных
x 1 x 2 | x 1 Ú x 2 | x 1 & x 2 | x 1 É x 2 | x 1 ~ x 2 | x 1 Å x 2 | x 1 ¯ x 2 | x 1 ½ x 2 |
0 0 | |||||||
0 1 | |||||||
1 0 | |||||||
1 1 |
В таблице представлены следующие функции двух переменных:
x 1 Ú x 2– дизъюнкция;
x 1 & x 2– конъюнкция;
x 1 É x 2– импликация;
x 1 ~ x 2– эквивалентность;
x 1 Å x 2– сложение по модулю 2;
x 1 ¯ x 2– стрелка Пирса;
x 1 ½ x 2 – штрих Шеффера
Остальные функции специальных названий не имеют и могут быть выражены через перечисленные выше функции.
Формулы логики булевых функций
Формула логики булевых функций определяется индуктивно следующим образом:
1. Любая переменная, а также константы 0 и 1 есть формула.
2. Если A и B - формулы, то A, A Ú B, A & B, A É B, A ~ B есть формулы.
3. Ничто, кроме указанного в пунктах 1-2, не есть формула.
Пример 2.1.
Выражение (- x Ú y)&((y É z)~ x) является формулой
Выражение (– x&y É z ~ x) не является формулой
Часть формулы, которая сама является формулой, называется подформулой.
Пример 2.2.
x& (y É z) – формула; y É z – ее подформула.
Функция f есть суперпозиция функций f1,f2,...,fn, если f получается с помощью подстановок этих формул друг в друга и переименованием переменных.
Пример 2.3.
f1 = х1&х2 (конъюнкция); f2 =-x (отрицание).
Возможны две суперпозиции:
1)f=f1(f2) = (—х1)&(—х2) - конъюнкция отрицаний;
2)f=f2(f1) = -(x1&х2) - отрицание конъюнкции.
Порядок подстановки задается формулой.
Всякая формула задает способ вычисления функции, если известны значения переменных.
Пример 2.4.
Построим таблицу значений функции
f (x1,х2,х3)=(х2 É х3)~(x1 Ú х2).
Вычисление функции f(x1 х2, х3)
x 1 | x 2 | x 3 | x 3 | x 2É x 3 | (x 2É x 3) | x 1 | x 1 Ú x 2 | f (x1,х2,х3) |
Таким образом, формула каждому набору аргументов ставит в соответствие значение функции. Следовательно, формула так же, как и таблица, может служить способом задания функции. В дальнейшем формулу будем отождествлять с функцией, которую она реализует. Последовательность вычислений функции задается скобками. Принято соглашение об опускании скобок в соответствии со следующей приоритетностью операций:, &, Ú, É и ~.
Графы и деревья
Такая структура, как граф (в качестве синонима используется также термин «сеть»), имеет самые различные применения в информатике и в смежных прикладных областях, поэтому познакомимся с основными понятиями теории графов.
Граф G = (V, Е) задается парой конечных множеств V и Е. Элементы первого множества v1, v2,..., vM называются вершинами графа (при графическом представлении им соответствуют точки). Элементы второго множества e1, e2,..., eN называют ребрами. Каждое ребро определяется парой вершин (при графическом представлении ребро соединяет две вершины графа). Если ребра графа определяются упорядоченными парами вершин, то такой граф называют ориентированным – орграфом (на чертеже при изображении ориентированного графа на каждом ребре ставят стрелку, указывающую его направление). Ориентированный граф с пятью вершинами и семью ребрами изображен на рис. 3.2.
Рис. 3.2. Пример ориентированного графа
Если порядок ребер не имеет значения, то граф называется неориентированным.
Если две вершины соединены двумя или более ребрами, то эти ребра называют параллельными (например, ребра е 4 и е5). Если начало и конец ребра совпадают, то такое ребро называется петлей (например, ребро e7).
Граф без петель и параллельных ребер называется простым.
Если ребро ек определяется вершинами vi и vj (будем обозначать этот факт следующим образом: еk = (vi, vj), то говорят, что ребро ек инцидентно вершинам vi и vj.
Граф G(E,U) называется конечным, если множество Е вершин конечно. Граф G(E,U), у которого любые две вершины соединены ребром, называется полным. Если хотя бы две вершины соединены несколькими ребрами, то такой граф называется мультиграфом. Две вершины еi, еj ÎЕ называются смежными, если они соединены ребром. Число ребер, инцидентных данной вершине еi, называется локальной степенью этой вершины р(еi). Число ребер r графа G(E,U) определяется выражением
где n — количество вершин в графе.
Рассмотрим граф, изображенный на рис. 3.3.
Рис. 3.3. Ориентированный граф
Множество вершин графа состоит из пяти элементов: Е = {1, 2, 3, 4, 5}, а множество ребер U = {(1, 2), (1, 4), (1, 5), (2, 3), (3, 4), (5, 3)}. Ребро (5, 3) — является ориентированным ребром или дугой. Число ребер в графе определяется по значению локальных степеней для каждой вершины:
р(1) = 3; р(2) = 2; р(3) = 3; р(4) = 2; р(5) = 2; р = (3+2+3+2+2)/2=6.
Важным в теории графов является понятие части графа G(E,U), который обозначается G'(E',U') Í G(E,U).
Множества вершин и ребер части графа являются подмножествами вершин и ребер исходного графа Е'ÍЕ, U' ÍU. Многие задачи на графах состоят в определении частей графа с заданными свойствами. Часть графа G'(E',U')ÍG(E,U) называется подграфом графа G(E,U), если Е'ÍЕ, а подмножество U'ÍU образовано только ребрами, инцидентными вершинам множества Е'.
Полным графом называется граф G(E,U), у которого каждая вершина соединена ребрами с остальными вершинами (рис. 3.4).
Рис. 3.4. Полный граф
Обязанность графов
Маршрутом графа G называется последовательность ребер S=(u1,u2,... un), в которой каждые два соседних ребра имеют общую вершину, т.е. u1= (e1, e2); u2= (e2, е3);... un= (en, еn+1). Не исключено, что одно и то же ребро может встречаться несколько раз на одном маршруте.
Две вершины еi и еj называются связанными, если существует маршрут из еi в еj.
Компонентой связности графа называется подмножество его вершин с инцидентными им ребрами, такое, что любая вершина связана с любой другой вершиной маршрута. Например, из графа на рис. 3.5 можно выделить следующие две компоненты связанности, показанные сплошной линией.
Рис. 3.5. Компоненты связанности графа
Простой цепью, или простым путем, называется маршрут, в котором ни одно ребро не повторяется дважды. Элементарной цепью или элементарным путем называется маршрут, в котором ни одна вершина не повторяется дважды. Циклом в графе называется маршрут, у которого начальная вершина совпадает с конечной. Например, следующий граф имеет цикл S = (1, 2, 3, 5, 4, 1) (рис. 3.6).
Рис. 3.6. Цикл в графе
Цикл, проходящий по всем ребрам графа только один раз, называется эйлеровым циклом. В теории графов доказывается теорема, определяющая, содержит ли граф эйлеров цикл. Оказывается, конечный граф содержит эйлеров цикл тогда и только тогда, когда он связан, и все его локальные степени вершин четные. Важной прикладной задачей теории графов является задача поиска в графе цикла, проходящего через каждую вершину только один раз. Такие циклы называются гамильтоновыми циклами.
Задание графа
Граф может задаваться в виде рисунка, аналитически, в виде матрицы. Выше приводилось задание графа в виде рисунка. Аналитическое задание состоит в задании элементов множества вершин Е={е1, е2,... еn} и множества ребер U = {u1, u2,... um}.
Для выполнения различного рода формальных преобразований над графами удобно использовать их матричные задания. Матрица А размерностью n ´ n называется матрицей смежности графа G(E,U), если ее элементы образованы по правилу: элемент матрицы аij= m, если вершины еi и еj соединены m ребрами, и аij=0, если эти вершины не связаны ребрами. Матрица смежности имеет число строк и столбцов, равное количеству вершин графа.
Матрица А размерностью n ´ m называется матрицей инцидентности графа G(E,U), если ее элементы образованы по правилу: элемент матрицы bij=1, если вершина еi инцидентна ребру uj и bij=0 в противном случае. Так как каждое ребро инцидентно двум вершинам, то в каждой строке этой матрицы ровно два ненулевых элемента.
Построим матрицы смежности и инцидентности для графа, изображенного на рис. 3.7.
Рис. 3.7. Пример графа.
Матрица смежности будет состоять из пяти строк и пяти столбцов.
Матрица инцидентности будет состоять из пяти строк и шести столбцов.
а | b | с | d | е | f | |
Анализ приведенных здесь понятий и определений показывает, что в качестве моделей графы удобно использовать в тех случаях, когда рассматривается система каких-либо объектов, между которыми существуют определенные связи, отношения, когда изучается структура системы, возможности ее функционирования. В информатике графы используются в разделах: операционные системы, алгоритмизация, структуры данных, информационное моделирование и др.
Весьма важным является связанный граф, не имеющий циклов, он называется деревом. В дереве любые две вершины связаны единственным путем. Вершина называется концевой, если ей инцидентно не более одного ребра; одна из концевых вершин может быть выбрана в качестве корня.
Лес - это любой граф без циклов. На рис. 3.8 показаны возможные деревья с пятью вершинами.
Рис. 3.8. Примеры деревьев
Деревья бывают также ориентированные и неориентирование.
Нижеследующие определения неориентированного дерева, как легко показать, эквивалентны друг другу. Неориентированное дерево есть связный граф, содержащий п вершин и n-1 ребер, либо связный граф, не имеющий циклов, либо граф, в котором каждая пара вершин соединена одной и только одной простой цепью.
Если G = (X, А) - неориентированный граф с n вершинами, то остовным деревом (или, короче, остовом) графа G называется всякий остовный подграф графа G, являющийся деревом (в смысле приведенного выше определения). Например, если G - граф, показанный на рисунке (а), то граф на рисунке (б) является остовом графа G, как и граф, изображенный на рисунке (в). Из сформулированных выше определений вытекает, что остов графа G можно также рассматривать как минимальный связный остовный подграф графа G, где «минимальность» понимается в том смысле, что никакое собственное подмножество ребер этого остова не образует связный остовный подграф графа G.