Алгебра высказываний — базовый раздел математической логики. Ее изучение является непременным условием успешного освоения теоретической информатики. Математическая логика изучает высказывания или утверждения, а также способы доказательств их истинности или ложности. В математической логике составные высказывания состоят из элементарных высказываний, предикатов, логических операций и кванторов существования и всеобщности. При изучении дисциплины «Информатика» будет рассмотрен только один раздел математической логики — алгебра высказываний.
Объектами обычной (школьной) алгебры являются числа, а основными операциями — сложение и умножение. Объектами алгебры высказываний являются элементарные (неразложимые) высказывания, а операциями — логические связки И, ИЛИ, НЕ.
Важность изучения алгебры высказываний в курсе «Информатика» не вызывает сомнения. Например, поиск информации в наиболее распространенных в экономике реляционных базах данных в основном производится формированием запроса в виде составных высказываний, элементами которых являются характеристики полей записей. Кроме того, высказывания используются при построении алгоритмов, содержащих ветвящиеся процессы.
|
|
Элементарные высказывания обычно обозначаются большими буквами латинского алфавита А, В, С, D,... В алгебре высказываний содержательный смысл высказываний не рассматривается; высказывания делятся на истинные и ложные.
Смысл операций И, ИЛИ и НЕ алгебры высказываний общепринят.
♦ Высказывание А И В истинно тогда и только тогда, когда одновременно истинны высказывания А и В.
♦ Высказывание А ИЛИ В ложно тогда и только тогда, когда одновременно ложны высказывания А и В.
♦ Высказывание НЕ А истинно тогда и только тогда, когда ложно высказывание А.
Операцию И называют конъюнкцией (или операцией логического умножения) и обозначают символами &, /\ или отсутствием символа.
Операцию ИЛИ называют дизъюнкцией (или операцией логического сложения) и обозначают символами \/ или +.
Операцию НЕ называют отрицанием (или инверсией) и обозначают символом — или чертой над высказыванием.
В дальнейшем для обозначения операций И, ИЛИ и НЕ будут использованы символы /\, V и черта над высказыванием.
В математической логике применяются также операции импликация и эквиваленция. Для обозначения операций импликация и эквиваленция используют символы -> и ~ соответственно.
♦ Высказывание А -> В ложно тогда и только тогда, когда высказывание А истинно, а высказывание В ложно.
♦ Высказывание А ~ В истинно тогда и только тогда, когда оба высказывания А и В истинны или когда оба высказывания А и В ложны.
|
|
Из элементарных высказываний, применяя операции булевой алгебры, можно получать составные высказывания любой сложности.
Например: А, А v В, A /\ B v C /\ D и т.д.
Истинность или ложность конкретного составного высказывания зависит от истинности или ложности входящих в него элементарных высказываний. Так возникает понятие логической функции. При рассмотрении логических функций вводят понятие логической переменной — элементарного высказывания, которое может быть истинным или ложным. Логическая переменная, соответствующая истинному (ложному) высказыванию, равна 1 (равна 0).
Логическую функцию (функцию алгебры логики), как и функцию в математическом анализе, можно задать в виде формулы или в виде таблицы.
Формула алгебры высказываний определяется следующим образом.
1. Элементарное высказывание является формулой алгебры высказываний.
2.Если Ф1 и Ф — формулы алгебры высказываний, то (Ф /\ Ф2),(Ф v Ф) и Ф1 являются формулами алгебры высказываний.
3. Других формул алгебры высказываний нет.
Примеры формул алгебры высказываний от трех логических переменных X, Х и Х3:
(X1 \/ Х) /\ Х \/ Х,
Х \/Х \/Х.
Отметим, что при написании формул алгебры высказываний действуют обычные правила приоритета операций при расстановке скобок.
Табличное задание функции алгебры логики называется ее таблицей истинности. В таблице истинности наборы значений логических переменных обычно располагают в порядке возрастания соответствующих этим наборам двоичных чисел (рис. 1).
X | Х | Х | F |
Рис. 1. Пример таблицы истинности булевой функции F от трех логических переменных Х, Х2 и Х 3
Отметим, что таблица истинности булевой функции от п переменных состоит из 2" + 1 строк и п + 1 столбцов. Напомним, что число двоичных наборов длины п равно 2". Таким образом, формирование таблицы истинности конкретной булевой функции от п переменных сводится к
заполнению нулями и единицами 2" компонент ее последнего столбца.
Рассмотрим построение таблицы истинности булевой функции, заданной формулой алгебры высказываний.
Существуют два подхода к решению этой задачи.
В первом подходе при вычислении значения функции на наборе значений переменных эти значения подставляют в формулу и, используя определение логических операций, находят значение формулы на этом наборе.
Например, значение формулы (Х \/ Х) /\ Х \/ Х при Х1= 0, Х = 1 и Х = 0 (на наборе (0,1,0)) равно
(0 \/ 1)/\0\/0 = (1v1)/\0 v1=(1v1)/\0 v1 =
= 1/\0 v1 = 0v1 = 1.
При использовании второго подхода формулу последовательно раскладывают на более простые подформулы и последовательно (в обратном порядке) строят таблицы истинности этих подформул.
Например, при построении таблицы истинности булевой функции, заданной формулой F(Х, X2, Х3 = Х2 V Х V Х1 , рассматривают подформулы X2 V Х3, Х2 V Х3, Х1 и Х2 V X3 V Х1 (рис. 2).
X | Хг | Х | Х2 v Х 3 | X2 v X | Х2 v Хъ v Х, | F | |
Рис. 2. Таблица истинности булевой функции, заданной формулой F(X1 , Хг, Х3)
Рассмотрим теперь обратную задачу: по таблице истинности булевой функции следует написать формулу алгебры высказываний.
Введем определение некоторых формул специального вида.
Элементарной конъюнкцией называется логическое произведение переменных или их отрицаний, в котором переменная может входить не более одного раза. Число переменных или их отрицаний в элементарной конъюнкции называют ее длиной. Отметим, что длина элементарной конъюнкции может быть равна единице.
|
|
Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций. Число элементарных конъюнкций в ДНФ может быть равно единице.
Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, в которой все элементарные конъюнкции имеют длину, равную числу переменных.
Примеры:
1. Формула X /\X2 / \ X3vX2vX2/\ Х3 является ДНФ.
2. Формула (Х /\Х v Х)/\ Х 2 не является СДНФ.
3. Формулы Х1/\Х2 и Х1/\Х2VХ/\Х являются СДНФ булевых функций от переменных Х1 и Х.
Отметим свойство элементарной конъюнкции, имеющей длину, равную числу переменных. Она обращается в 1 ровно на одном наборе значений переменных. Таким образом, каждому набору значений переменных соответствует ровно одна такая элементарная конъюнкция.
Например, набору (0,1,0) соответствует конъюнкция X /\X2 / \ X3. На этом свойстве основан следующий алгоритм нахождения формулы алгебры высказываний булевой функции, заданной таблицей истинности.
Для каждого набора, на котором булева функция F равна 1, находим элементарную конъюнкцию, равную числу переменных длины, которая обращается в 1 на этом наборе. Дизъюнкция этих конъюнкций является формулой алгебры высказываний булевой функции F.
Булева функция, равная 0 (равная 1) на всех наборах значений ее переменных, называется тождественно ложной (тождественно истинной). Тождественно ложную (тождественно истинную) булеву функцию будем обозначать через 0 (через 1).
Отметим, что описанный выше алгоритм не дает результата в случае тождественно ложных булевых функций. Но для таких функций формулой алгебры высказываний является, например, формула Х /\ Х.
Если подформулу Ф формулы алгебры высказываний Ф заменить равносильной Ф1 формулой, то полученная формула Ф будет равносильна формуле Ф. Говорят, что формула Ф получена из Ф равносильным преобразованием. Такой подход используется для нахождения равносильной исходной формуле формулы, оптимальной в некотором смысле (например, имеющей наименьшее число вхождений переменных). Для реализации этого подхода разработан набор пар равносильных формул. Приведем примеры таких пар.
|
|
A v В и В v A; A v А и A; Av1и1;AvO и A — свойства дизъюнкции;
А/\В и В/\А;А/\А и А; А/\1 и А; А/\О и 0 — свойства конъюнкции;
A и A — закон отрицания отрицания;
A v А /\ В и А — закон поглощения;
A v В и А /\ В; А/\В и A v В — законы де Моргана.
Проверку равносильности формул Ф и Ф (от одних и тех же переменных) наиболее просто осуществить следующим образом. Для этих формул построить таблицы истинности Т, и Т,. Формулы Ф1 и Ф, равносильны тогда и только тогда, когда таблицы истинности T и Т2 одинаковы. В качестве примера следует проверить равносильность формул А - В и
A v В.
Из формулы A/\BvC /\ D, применяя законы де Моргана и закон отрицания отрицания, можно получить равносильную ей формулу A/\BvCvD.
Отметим, что для любой формулы алгебры высказываний существует равносильная ей формула, в которой операция отрицания применяется только к переменным.
В качестве примера использования алгебры высказываний можно продемонстрировать равносильность высказываний «Неверно, что Иванов не сдал зачет по информатике и не защитил курсовую работу» и «Иванов сдал зачет по информатике или защитил курсовую работу».