Вопрос 2-3. Основы алгебры высказываний

Алгебра высказываний — базовый раздел математической логики. Ее изучение является непременным условием успешного освоения теоретической информатики. Математическая логика изучает высказывания или утверждения, а также способы доказательств их истинности или ложности. В математической логике составные высказывания состоят из элементарных высказываний, предикатов, логических операций и кванторов существования и всеобщности. При изучении дисциплины «Информатика» будет рассмотрен только один раздел математической логики — алгебра высказываний.

Объектами обычной (школьной) алгебры являются числа, а основными операциями — сложение и умножение. Объектами алгебры высказываний являются элементарные (неразложимые) высказывания, а операциями — логические связки И, ИЛИ, НЕ.

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

Элементарные высказывания обычно обозначаются большими буквами латинского алфавита А, В, С, D,... В алгебре высказываний содержательный смысл высказываний не рассматривается; высказывания делятся на истинные и ложные.

Смысл операций И, ИЛИ и НЕ алгебры высказываний общепринят.

♦ Высказывание А И В истинно тогда и только тогда, когда одновременно истинны высказывания А и В.

♦ Высказывание А ИЛИ В ложно тогда и только тогда, когда одновременно ложны высказывания А и В.

♦ Высказывание НЕ А истинно тогда и только тогда, когда ложно высказывание А.

Операцию И называют конъюнкцией (или операцией логического умножения) и обозначают символами &, /\ или отсутствием символа.

Операцию ИЛИ называют дизъюнкцией (или операцией логического сложения) и обозначают символами \/ или +.

Операцию НЕ называют отрицанием (или инверсией) и обозначают символом — или чертой над высказыванием.

В дальнейшем для обозначения операций И, ИЛИ и НЕ будут использованы символы /\, V и черта над высказыванием.

В математической логике применяются также операции импликация и эквиваленция. Для обозначения операций импликация и эквиваленция используют символы -> и ~ соответственно.

♦ Высказывание А -> В ложно тогда и только тогда, когда высказывание А истинно, а высказывание В ложно.

♦ Высказывание А ~ В истинно тогда и только тогда, когда оба высказывания А и В истинны или когда оба высказывания А и В ложны.

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

Например: А, А v В, A /\ B v C /\ D и т.д.

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

Логическую функцию (функцию алгебры логики), как и функцию в математическом анализе, можно задать в виде формулы или в виде таблицы.

Формула алгебры высказываний определяется следующим образом.

1. Элементарное высказывание является формулой алгебры высказываний.

2.Если Ф₁ и Ф — формулы алгебры высказываний, то (Ф /\ Ф₂),(Ф v Ф) и Ф₁ являются формулами алгебры высказываний.

3. Других формул алгебры высказываний нет.

Примеры формул алгебры высказываний от трех логических переменных X , Х и Х₃:

(X₁ \/ Х ) /\ Х \/ Х ,

Х \/Х \/Х .

Отметим, что при написании формул алгебры высказываний действуют обычные правила приоритета операций при расстановке скобок.

Табличное задание функции алгебры логики называется ее таблицей истинности. В таблице истинности наборы значений логических переменных обычно располагают в порядке возрастания соответствующих этим наборам двоичных чисел (рис. 1).

 

X	Х	Х	F

Рис. 1. Пример таблицы истинности булевой функции F от трех логических переменныхХ , Х₂ и Х₃

Отметим, что таблица истинности булевой функции от п переменных состоит из 2" + 1 строк и п + 1 столбцов. Напомним, что число двоичных наборов длины п равно 2". Таким образом, формирование таблицы истинности конкретной булевой функции от п переменных сводится к

заполнению нулями и единицами 2" компонент ее последнего столбца.

Рассмотрим построение таблицы истинности булевой функции, заданной формулой алгебры высказываний.

Существуют два подхода к решению этой задачи.

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

Например, значение формулы ( Х \/ Х ) /\ Х \/ Х при Х₁= 0, Х = 1 и Х = 0 (на наборе (0,1,0)) равно

(0 \/ 1)/\0\/0 = (1v1)/\0 v1=(1v1)/\0 v1 =

= 1/\0 v1 = 0v1 = 1.

При использовании второго подхода формулу последовательно раскладывают на более простые подформулы и последовательно (в обратном порядке) строят таблицы истинности этих подформул.

Например, при построении таблицы истинности булевой функции, заданной формулой F(Х , X₂, Х₃ =Х₂ V Х V Х_1, рассматривают подформулы X₂ V Х₃, Х₂ V Х₃, Х₁ и Х₂ V X₃ V Х₁ (рис. 2).

 

X	Хг	Х	Х2 v Х3	X2vX		Х2 v Хъ v Х,	F

Рис. 2. Таблица истинности булевой функции, заданной формулой F(X₁ , Х_г , Х₃)

Рассмотрим теперь обратную задачу: по таблице истинности булевой функции следует написать формулу алгебры высказываний.

Введем определение некоторых формул специального вида.

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

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций. Число элементарных конъюнкций в ДНФ может быть равно единице.

Совершенной дизъюнктивной нормальной формой (СДНФ) называется ДНФ, в которой все элементарные конъюнкции имеют длину, равную числу переменных.

Примеры:

1. Формула X /\X₂ /\ X₃vX₂vX₂/\ Х₃ является ДНФ.

2. Формула (Х /\Х v Х )/\Х₂ не является СДНФ.

3. Формулы Х₁/\Х₂ и Х₁/\Х₂VХ/\Х являются СДНФ булевых функций от переменных Х₁ и Х .

Отметим свойство элементарной конъюнкции, имеющей длину, равную числу переменных. Она обращается в 1 ровно на одном наборе значений переменных. Таким образом, каждому набору значений переменных соответствует ровно одна такая элементарная конъюнкция.

Например, набору (0,1,0) соответствует конъюнкция X /\X₂ /\ X₃ .На этом свойстве основан следующий алгоритм нахождения формулы алгебры высказываний булевой функции, заданной таблицей истинности.

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

Булева функция, равная 0 (равная 1) на всех наборах значений ее переменных, называется тождественно ложной (тождественно истинной). Тождественно ложную (тождественно истинную) булеву функцию будем обозначать через 0 (через 1).

Отметим, что описанный выше алгоритм не дает результата в случае тождественно ложных булевых функций. Но для таких функций формулой алгебры высказываний является, например, формула Х /\ Х .

Если подформулу Ф формулы алгебры высказываний Ф заменить равносильной Ф₁ формулой, то полученная формула Ф будет равносильна формуле Ф. Говорят, что формула Ф получена из Ф равносильным преобразованием. Такой подход используется для нахождения равносильной исходной формуле формулы, оптимальной в некотором смысле (например, имеющей наименьшее число вхождений переменных). Для реализации этого подхода разработан набор пар равносильных формул. Приведем примеры таких пар.

A v В и В v A; A v А и A; Av1и1;AvO и A — свойства дизъюнкции;

А/\В и В/\А;А/\А и А; А/\1 и А; А/\О и 0 — свойства конъюнкции;

A и A — закон отрицания отрицания;

A v А /\ В и А — закон поглощения;

A v В и А /\ В ; А/\В и A v В — законы де Моргана.

Проверку равносильности формул Ф и Ф (от одних и тех же переменных) наиболее просто осуществить следующим образом. Для этих формул построить таблицы истинности Т, и Т,. Формулы Ф₁ и Ф, равносильны тогда и только тогда, когда таблицы истинности T и Т₂ одинаковы. В качестве примера следует проверить равносильность формул А - В и

A v В.

Из формулы A/\BvC /\ D, применяя законы де Моргана и закон отрицания отрицания, можно получить равносильную ей формулу A/\BvCvD.

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

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