Алгебра высказываний (булева алгебра)

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

Основное понятие булевой алгебры — выказывание. Под простым высказыванием понимается предложение, о котором можно сказать, истинно оно или ложно (третьего не дано). Высказывания обознача­ются латинскими буквами и могут принимать одно из двух значений: ЛОЖЬ (обозначим 0 ) или ИСТИНА (обозначим 3). Например, со­держание высказывания А: «дважды два равно четырем» истинно А = 1, а высказывание В: «три больше пяти» всегда есть ЛОЖЬ. В дальнейшем нас не будет интересовать содержательная часть выска­зываний, а только их истинность. Два высказывания А и В называ­ются равносильными, если они имеют одинаковые значения истин­ности, записывается А = В.

Логические операции

Сложное высказывание можно построить из простых с помощью логических операций: отрицания, конъюнкции, дизъюнкции, импликации и логических выражений, представляющих собой комбинации логи­ческих операций. Рассмотрим их подробней.

Операцией отрицания А называют высказывание Алгебра высказываний (булева алгебра) - student2.ru (или Алгебра высказываний (булева алгебра) - student2.ru , го­ворят не А), которое истинно тогда, когда А ложно, и ложно тогда, когда А истинно. Например, если событие А состоит в том, что «зав­тра будет снег», то Алгебра высказываний (булева алгебра) - student2.ru «завтра НЕ будет снега», истинность одного утверждения автоматически означает ложность второго. Отрица­ние — унарная (т.е. для одного операнда) логическая операция. Ей соответствует языковая конструкция, использующая частицу НЕ,

Это правило можно записать в виде следующей таблицы:

Алгебра высказываний (булева алгебра) - student2.ru

Такая таблица называется таблицей истинности.

Конъюнкцией (логическим умножением) двух высказываний А и В является новое высказывание С, которое истинно только тогда, ког­да истинны оба высказывания, записывается Алгебра высказываний (булева алгебра) - student2.ru (при этом говорят С равно А и В). Примером такой операции может быть следующая: пусть высказывание А состоит в том, что «высота шкафа меньше высоты двери», событие В «ширина шкафа меньше ширины двери», событие С «шкаф можно внести в дверь, если ши­рина шкафа меньше ширины двери И высота шкафа меньше высо­ты двери», т.е. данная операция применяется, если два высказыва­ния связываются союзом И.

Таблица истинности этой операции, как следует из определения, имеет вид

Алгебра высказываний (булева алгебра) - student2.ru

Дизъюнкцией (логическим сложением) двух высказываний А и В является новое высказывание С, которое истинно, если истинно хотя бы одно высказывание. Записывается Алгебра высказываний (булева алгебра) - student2.ru (при этом говорят:

С равно А ИЛИ В). Пример такой операции следующий: пусть выс­казывание А состоит в том, что «студент может добираться домой на автобусе», событие В «студент может добираться домой на троллей­бусе», событие С «студент добрался домой на автобусе ИЛИ троллей­бусе», т.е. данная операция применяется, если два высказывания свя­зываются союзом ИЛИ.

Таблица истинности такой операции следующая:

Алгебра высказываний (булева алгебра) - student2.ru

Импликацией двух высказываний А (А называется посылкой) и В (В называется заключением) является новое высказывание С, кото­рое ложно только тогда, когда посылка истинна, а заключение лож­но, записывается Алгебра высказываний (булева алгебра) - student2.ru (при этом говорят, из А следует В). Примером такой операции может быть любое рассуждение типа: если произошло событие А, то произойдет событие В, «если идет дождь, то на небе тучи». Очевидно, операция не симметрична, т.е. из Алгебра высказываний (булева алгебра) - student2.ru не всегда истинно, в нашем примере «если на небе тучи, то идет дождь» не всегда истинно.

Таблица истинности импликации следующая:

Алгебра высказываний (булева алгебра) - student2.ru

Алгебра высказываний (булева алгебра) - student2.ru

Алгебра высказываний (булева алгебра) - student2.ru

Эквиваленцией двух высказываний А и В является новое выска­зывание С, которое .истинно только тогда, когда оба высказывания имеют одинаковые значения истинности, записывается Алгебра высказываний (булева алгебра) - student2.ru

Алгебра высказываний (булева алгебра) - student2.ru Примером такой операции может быть любое выска­зывание типа: событие А равносильно событию В.

Алгебра высказываний (булева алгебра) - student2.ru

Алгебра высказываний (булева алгебра) - student2.ru

Таблица истинности:

Логические Выражения. Порядок логических операций

С помощью логических операций из простых высказываний (ло­гических переменных и констант) можно построить логические вы­ражения, которые также называются булевскими функциями. Напри­мер. Алгебра высказываний (булева алгебра) - student2.ru

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

Первыми выполняются операции в скобках, затем операции в следующем порядке: отрицание, конъюнкция и дизъюнкция слева направо, импликация, эквиваленция.

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

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

Алгебра высказываний (булева алгебра) - student2.ru

Алгебра высказываний (булева алгебра) - student2.ru

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

Первая из них - дизъюнктивная нормальная форма (ДНФ), имеет вид Алгебра высказываний (булева алгебра) - student2.ru , где каждое из составляющих есть конъюнкция простых высказываний и их отрицаний, например:

Алгебра высказываний (булева алгебра) - student2.ru

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

Алгебра высказываний (булева алгебра) - student2.ru где каждое из составляющих есть дизъюнк­ция простых высказываний и их отрицаний, например:

Алгебра высказываний (булева алгебра) - student2.ru

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

Задать булевскую функцию можно, определяя ее значения для всех наборов значений аргументов. Каждый аргумент может иметь два значения: 0 и 1, следовательно, n аргументов могут принимать 2n раз­личных наборов. Пусть, например, булевская функция имеет три ар­гумента: X,, Х2, Х3 Общее число наборов 23 = 8; зададим таблицу ис­тинности функции, указав для каждого набора значение функции.

Х1 Х2 Х3 Р
I

Для составления алгебраической формы по результатам табли­цы сделаем следующее. В комбинациях, где функция принимает зна­чение 1, единицу заменим именем функции, а нуль — именем с от­рицанием (т.е. комбинации 0 0 1 поставим в соответствие выражение Алгебра высказываний (булева алгебра) - student2.ru ), все элементы соединим знаками дизъюнкции, для рассматриваемого примера получим

Алгебра высказываний (булева алгебра) - student2.ru Алгебра высказываний (булева алгебра) - student2.ru

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

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

Алгебра высказываний (булева алгебра) - student2.ru Алгебра высказываний (булева алгебра) - student2.ru ,

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

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

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

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

Задать множество можно перечислением его элементов. Напри­мер, множество образованное из п элементов ар а2, ..., ап, обознача­ется А = {а,, а2, ..., ап}; пишется а е А (говорится «элемент а при надлежит множеству А»), если а является элементом множества А, в противном случае Алгебра высказываний (булева алгебра) - student2.ru

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

Алгебра высказываний (булева алгебра) - student2.ru Два множества считаются равными, если состоят из одних и тех же элементов; записывается этот факт А = В.

Множество А1 называется подмножеством А (записываете ),

если все элементы множества А, являются элементами А,

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

Объединением множеств А и В (записывается Алгебра высказываний (булева алгебра) - student2.ru ) называется

множество, состоящее из элементов как одного, так и второго мно­жества. Например, А и В — множества точек, принадлежащих неко­торым двум кругам, имеющим общие точки, тогда объединением Алгебра высказываний (булева алгебра) - student2.ru будет фигура, состоящая из общих точек.

Пересечением множеств А и В (записывается Алгебра высказываний (булева алгебра) - student2.ru ) называется

множество, состоящее из элементов, принадлежащих как одному, так и второму множеству одновременно.

Алгебра высказываний (булева алгебра) - student2.ru

Дополнением множества А до В называется множество, состоящее из элементов множества В, не принадлежащих А. Дополнение обо­значается Алгебра высказываний (булева алгебра) - student2.ru (рис. 1.7).

Алгебра высказываний (булева алгебра) - student2.ru

Рис. 1.7. Операции надмножествами

16.3, Элементы теории графов

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

Граф задается парой множеств: множества Е, называемого мно­жеством вершин, и множества II, называемого множеством ребер. Ребро Алгебра высказываний (булева алгебра) - student2.ru есть пара, где Алгебра высказываний (булева алгебра) - student2.ru ,

Алгебра высказываний (булева алгебра) - student2.ru

указывающая, между какими двумя вершинами проведено ребро. Говорят, что ребро Алгебра высказываний (булева алгебра) - student2.ru инцидентно вершинам е., е. Если порядок ребер не имеет значения, т.е. Алгебра высказываний (булева алгебра) - student2.ru , то ребро называется неориентированным или просто ребром, если же порядок имеет значение, то ребро Алгебра высказываний (булева алгебра) - student2.ru называется ориентированным ребром или дугой. Вершина еi. — назы­вается началом дуги, еj. - конец дуги. Граф, содержащий хотя бы одну дугу, называется ориентированным графом или орграфом

Граф Алгебра высказываний (булева алгебра) - student2.ru называется конечным, если множество Е вершин

конечно.

Граф Алгебра высказываний (булева алгебра) - student2.ru •, у которого любые две вершины соединены ребром,

Алгебра высказываний (булева алгебра) - student2.ru называется полным. Если хотя бы две вершины соединены несколь­кими ребрами, то такой граф называется мультиграфом. Две верши­ны Алгебра высказываний (булева алгебра) - student2.ru называются смежными, если они соединены ребром. Чис­ло ребер, инцидентных данной вершине е., называется локальной степенью этой вершины p(ei) Число ребер r графа G(Е,U) определя­ется выражением

Алгебра высказываний (булева алгебра) - student2.ru , где n — количество вершин в графе. Рассмотрим граф,

изображенный на рис. 1.8.

Алгебра высказываний (булева алгебра) - student2.ru

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

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

Алгебра высказываний (булева алгебра) - student2.ru

Важным в теории графов является понятие части графа G(Е,U), который обозначается Алгебра высказываний (булева алгебра) - student2.ru

Множества вершин и ребер части графа являются подмножества­ми вершин и ребер исходного графа Алгебра высказываний (булева алгебра) - student2.ru

Наши рекомендации