Зависимости между логическими операциями

Операции не являются независимыми; одни из них могут быть выражены через другие. Можно доказать с помощью таблиц истинности следующие равносильности:

1. A®B=ØAÚB

2. A«B=(A®B)Ù(B®A)=(ØAÚB)Ù(AÚØB)=(AÙB)Ú(ØAÙØB)

3. ØØA=Aзакон двойного отрицания.

4. AÙB=BÙAкоммутативный закон для конъюнкции

5. AÚB=BÚAкоммутативный закон для дизъюнкции

6. (AÙB)ÙC=AÙ(BÙC)ассоциативный закон для конъюнкции

7. (AÚB)ÚC=AÚ(BÚC)ассоциативный закон для дизъюнкции

8. AÙ(BÚC)=(AÙB)Ú(AÙC)дистрибутивные законы

9. AÚ (BÙC)=(AÚB)Ù(AÚC)

10. AÙA=Aзакон идемпотенции для конъюнкции

11. AÚA=Aзакон идемпотенции. для дизъюнкции

12. Ø(AÙB)=ØAÚØBзаконы де Моргана

13. Ø(AÚB)=ØAÙØB

14. AÙ1=Aзакон единицы для конъюнкции

15. AÙ0=0закон нуля для конъюнкции

16. AÚ1=1закон единицы для дизъюнкции

17. AÚ0=Aзакон нуля для дизъюнкции

18. AÚ(AÙA)=Aзаконы поглощения

19. AÙ(AÚA)=A

20. AÚØA=1закон исключения третьего

21. AÙØA=0закон противоречия

22. AÙ(ØAÚB)=AÙB

23. AÚ(ØAÙB)=AÚB

Одну и ту же зависимость между логическими переменными можно выразить различными формулами. Поэтому важно иметь возможность приводить формулы к некоторому стандартному виду. Существует несколько стандартных форм, к которым приводятся логические выражения с помощью эквивалентных преобразований (формулы 1-23).

Первая из них – дизъюнктивная нормальная форма (ДНФ), имеет вид

A1ÚA2Ú…ÚAn, где каждое из составляющих есть конъюнкция простых высказываний и их отрицаний, например

B=(ØA1ÙA2ÙA3)Ú(A4ÙA5)

Вторая – конъюнктивная нормальная форма (КНФ), имеет вид

A1ÙA2Ù…ÙAn, где каждое из составляющих есть дизъюнкция простых высказываний и их отрицаний, например

B=(ØA1ÚA2ÚØA3)Ù(A4ÙA5)ÙA6

Табличное и алгебраическое задание булевских функций

Задать булевскую функцию можно, определяя ее значения для всех наборов значений аргументов. Каждый аргумент может иметь два значения 0 и 1, следовательно, n аргументов могут принимать 2ⁿ различных наборов. Пусть, например булевская функция имеет три аргумента X₁,X₂,X₃. Общее число наборов 2³=8, зададим таблицу истинности функции, указав для каждого набора значение функции.

№	X1	X2	X3	F

Для составления алгебраической формы по результатам таблицы сделаем следующее. В комбинациях, где функция принимает значение 1, единицу заменим именем функции, а нуль именем с отрицанием, (т.е. комбинации 0 0 1 поставим в соответствие выражение ØX₁ÙØX₂ÙX₃), все элементы соединим знаками дизъюнкции, для рассматриваемого примера, получим

F(X₁,X₂,X₃) = (ØX₁ÙØX₂ÙX₃)Ú(ØX₁ÙX₂ÙX₃)Ú(X₁ÙØX₂ÙX₃) Ú(X₁ÙX₂ÙX₃)

Как нетрудно заметить, построенная функция удовлетворяет заданной таблице истинности. Функция представляет дизъюнктивную нормальную форму. Кроме того, заметим, что в каждую группу дизъюнкций входят все аргументы функции. Такая ДНФ называется совершенной, а каждая группа дизъюнкций называется коституентой единицы.

Аналогично, для комбинаций, где функция принимает значение нуля можно построить алгебраическую форму

F(X₁,X₂,X₃) = (X₁ÚX₂ÚX₃)Ù( X₁ÚØX₂ÚX₃)Ù(ØX₁ÚX₂ÚX₃) Ù(ØX₁ÚØX₂ÚX₃) (2)

Которая также удовлетворяет заданной таблице истинности и представляет собой конъюнктивную нормальную форму, в данном случае совершенную. Каждая конъюнкция называется конституентой нуля.

В следующей главе будет показано, как основываясь на булевой алгебре, создаются цифровые устройства.

1.6.2. Элементы теории множеств

Множеством называется любое объединение определенных вполне различимых объектов; их может и не быть вообще. Можно говорить о множестве точек на отрезке [0,1], множестве студентов в группе, множестве снежных дней в июле на экваторе, т.е. множество образуют любые объекты, объединенные по любому признаку. Объекты, составляющие множество, называются элементами множества. Множество, не имеющее ни одного элемента, называется пустым, оно обозначается Æ. Множество, состоящее из конечного числа элементов, называется конечным, в противном случае – бесконечным.

Задать множество можно перечислением его элементов. Например, множество образованное из n элементов a1,a2,…,an , обозначается A={ a1,a2,…,an }; пишется aÎA (говорится «элемент a принадлежит множеству A»), если a является элементом множества А, в противном случае aÏA.

Задать множество можно также, указав общее свойство для всех его и только его элементов. Например, множество точек равноудаленных от концов отрезка.

Два множества считаются равными, если состоят из одних и тех же элементов; записывается этот факт A=B.

Множество А₁ называется подмножеством А (записывается А₁ÌА), если все элементы множества А₁ являются элементами А.

Для множеств определены следующие операции: объединения, пересечения, дополнения.

Объединениеммножеств А и В(записывается AÈB) называется множество состоящее из элементов как одного так и второго множества. Например, Aи B– множества точек принадлежащих некоторым двум кругам, имеющим общие точки, тогда объединением AÈBбудет фигура, состоящая из общих точек.

Пересечениеммножеств А и В(записывается AÇB) называется множество, состоящее из элементов, принадлежащих как одному так и второму множеству одновременно.

ДополнениеммножестваА до Вназывается множество, состоящее из элементов множества В, не принадлежащих А. Дополнение обозначается Ā=В-А.

1.6.3. Элементы теории графов

Основные понятия

.

Граф задается парой множеств: множестваEназываемого множеством вершин и множества U, называемого множеством ребер. Ребро uÎUесть пара (e_i,e_j), где e_i,e_jÎE , указывающая, между какими двумя вершинами проведено ребро. Говорят, что ребро uÎU инцидентно вершинам e_i,e_j. Если порядок ребер не имеет значения, т.е.

u= (e_i,e_j)= (e_j,e_i), то ребро называется неориентированным или просто ребром, если же порядок имеет значение, то ребро u= (e_i,e_j) называется ориентированным ребром или дугой. Вершина e_i- называется началом дуги, e_j – конец дуги. Граф, содержащий хотя бы одну дугу, называется ориентированным графом или орграфом.

Граф G(E,U) называется конечным, если множествоE вершин конечно.

Граф G(E,U),у которого любые две вершины соединены ребром, называется полным. Если хотя бы две вершины соединены несколькими ребрами, то такой граф называется мультиграфом. Две вершины e_i,e_jÎE называются смежными, если они соединены ребром. Число ребер, инцидентных данной вершине e_i, называется локальной степенью этой вершины r(e_i). Число ребер rграфа G(E,U)определяется выражением

,где n– количество вершин в графе.

Рассмотрим граф, изображенный на рисунке 1.8.

Ориентированный граф рис. 1.8.

Множество вершин графа состоит из пяти элементов E={1,2,3,4,5}, а множество ребер U={(1,2),(1,4),(1,5),(2,3),(3,4),(5,3)}. Ребро (5,3) – является ориентированным ребром или дугой. Число ребер в графе определяется по значению локальных степеней для каждой вершины:

r(1)=3; r(2)=2; r(3)=3; r(4)=2; r(5)=2; r=(3+2+3+2+2)/2=6

Важным в теории графов является понятие части графа G(E,U), который обозначается G¢(E¢,U¢)ÍG(E,U)

Множества вершин и ребер части графа являются подмножествами вершин и ребер исходного графа

E¢ÍE U¢ÍU

Многие задачи на графах состоят в определении частей графа с заданными свойствами.

Часть графаG¢(E¢,U¢)ÍG(E,U)называется подграфом графа G(E,U), если E¢ÍE , а подмножество U¢ÍU образовано только ребрами инцидентными вершинам множества E¢.

Часть графаG¢(E¢,U¢)ÍG(E,U)называется суграфом графа G(E,U), если E¢ÍE , а подмножество U¢ÍU образовано ребрами инцидентными вершинам множества E¢. В графе, изображенном выше, можно выделить подграф G¢(E¢,U¢), где E¢={1,2,3}, множество ребер U¢={(1,2),(2,3)} и суграф G¢(E¢,U¢),у которого E¢={1,2}, U¢={(1,2),(1,4),(1,5),(2,3)}.

Полным графом называется граф G(E,U), у которого каждая вершина e_iÎEсоединена ребрами с остальными вершинами. Например,

Рис. 1.9. Полный граф

Связанность графов

Маршрутом графа Gназывается последовательность ребер S=(u₁,u₂,…u_n), в которой каждые два соседних ребра имеют общую вершину, т.е. u₁=(e₁,e₂); u₂=(e₂,e₃); …u_n=(e_n,e_n+1); Не исключено, что одно и то же ребро может встречаться несколько раз на одном маршруте.

Две вершины e_i и e_j называются связанными, если существует маршрут из e_i в e_j.

Компонентой связности графа называется подмножество его вершин с инцидентными им ребрами, такое, что любая вершина связана с любой другой вершиной маршрута. Например, из графа на рисунке 1.10. можно выделить следующие две компоненты связанности, показанные сплошной линией.

Рис 1.10. Компоненты связанности графа

Простой цепью или простым путем называется маршрут, в котором ни одно ребро не повторяется дважды. Элементарной цепью или элементарным путем называется маршрут, в котором ни одна вершина не повторяется дважды. Циклом в графе называется маршрут, у которого начальная вершина совпадает с конечной. Например, следующий граф имеет цикл S=(1,2,3,5,4,1). Рис.1.11.

Рис 1.11. Цикл в графе

Цикл, проходящий по всем ребрам графа только один раз, называется Эйлеровым циклом. В теории графов доказывается теорема, определяющая, содержит ли граф эйлеров цикл. Оказывается, конечный граф содержит эйлеров цикл тогда и только тогда, когда он связан, и все его локальные степени вершин четные. Важной прикладной задачей теории графов является задача поиска в графе цикла, проходящего через каждую вершину только один раз. Такие циклы называются гамильтоновыми циклами.

Весьма важным является связанный граф, не имеющий циклов, он называется деревом. В дереве любые две вершины связаны единственным путем. Вершина называется концевой, если ей инцидентно не более одного ребра; одна из концевых вершин может быть выбрана в качестве корня.

Задание графа

Граф может задаваться в виде рисунка, аналитически, в виде матрицы. Выше приводилось задание графа в виде рисунка. Аналитическое задание состоит в задании элементов множества вершин и E={e₁,e₂,…e_n} и множества ребер U={u₁,u₂,…u_m}.

Для выполнения различного рода формальных преобразований над графами удобно использовать их матричные задания. Матрица A размерностью n´n, называется матрицей смежности графа G(E,U), если ее элементы образованы по правилу: элемент матрицы a_ij=m, если вершины e_i и e_jсоединены m ребрами, и a_ij=0, если эти вершины не связаны ребрами. Матрица смежности имеет число строк и столбцов равное количеству вершин графа.

Матрица A размерностью n´m, называется матрицей инциндентности графа G(E,U), если ее элементы образованы по правилу: элемент матрицы b_ij=1, если вершина e_i инцидентна ребру u_j, и b_ij=0 в противном случае. Так как каждое ребро инцидентно двум вершинам, то в каждой строке этой матрицы ровно два ненулевых элемента.

Построим матрицы смежности и инцидентности для графа, изображенного на рисунке 1.12.

Рис 1.12.

Матрицы смежности будет состоять из пяти строк и пяти столбцов.

Матрица инцидентности будет состоять из пяти строк и шести столбцов

	a	b	c	d	e	f