Основные понятия алгебры логики. Элементарные логические операции

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

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

Два высказывания А и В называются равносильными, если они имеют одинаковые значения истинности, записывается А = В.

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

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

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

А

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

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

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

А	В	А & В

Дизъюнкцией (логическим сложением) двух высказываний А и В является новое высказывание С, которое истинно, если истинно хотя бы одно высказывание. Записывается С = A Ú В (при этом говорят: «С равно А ИЛИ В). Пример такой операции следующий: пусть высказывание А состоит в том, что «студент может добираться домой на автобусе», событие В «студент может добираться домой на троллейбусе», событие С «студент добрался домой на автобусе ИЛИ троллейбусе», т.е. данная операция применятся, если два высказывания связываются союзом ИЛИ.

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

А	В	A Ú В

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

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

А	В	А ® В

Импликация имеет следующие свойства:

А ® В ≠ В ® А

А ® А = 1

0 ® А = 1

1 ® А = А

А ® 1 = 1

А ® 0 =

Эквиваленцией двух высказываний А и В является новое высказывание С, которое истинно только тогда, когда оба высказывания имеют одинаковые значения истинности, записывается С = А «В (.С = А º В). Примером такой операции может быть любое высказывание типа: событие А равносильно событию В.

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

А	В	А «В

Эквиваленция имеет следующие свойства:

А «В = В «А

А «В = «

А «1 = А

А «0 =

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

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

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

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

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

A1 Ú А2 Ú … Ú Аn,

где каждое из составляющих высказываний есть конъюнкция простых высказываний и их отрицаний, например: В = (& А2 & A3) Ú (А4 & А5).

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

A1 Ù А2 Ù … Ù Аn,

где каждое из составляющих есть дизъюнкция Гфостых высказываний и их отрицаний, например: В = (Ú А2 Ú ) & (А4 Ú А5) & А6.

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

В комбинациях, где функция принимает значение 1, единица заменяется именем функции, а нуль — именем с отрицанием (т.е. комбинации 0 0 1 ставиться в соответствие выражение &&X3), все элементы соединяются знаками дизъюнкции.

Для рассматриваемого примера получим

F(X1, Х2, X3) = (&&X3)Ú(& Х2 & X3)Ú(Х1 &&X3) Ú(Х1&Х2&X3).

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

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

F(X1, Х2, X3) = (Х1ÚХ2ÚX3) & (Х1ÚÚX3) & (ÚХ2ÚX3) & (ÚÚX3),

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

Дата добавления: 2014-01-06