Логические выражения. Порядок логических операций
С помощью логических операций из простых высказываний (логических переменных и констант) можно построить логические выражения, которые также называются булевскими функциями. Например, C=(( Ā B)B)А
Чтобы избежать большого количества скобок в булевских функциях принято следующее соглашение о старшинстве операций.
Первыми выполняются операции в скобках затем операции в следующем порядке: отрицание, конъюнкция и дизъюнкция слева на право, импликация, эквиваленция.
Зависимости между логическими операциями
Операции не являются независимыми; одни из них могут быть выражены через другие. С помощью таблиц истинности можно доказать следующие равносильности:
AB= Ā B
AB=(AB)(BA)=( Ā B)(AB)=(AB)( Ā B)
A=A закон двойного отрицания.
AB=BA коммутативный закон для конъюнкции
AB=BA коммутативный закон для дизъюнкции
(AB)C=A(BC) ассоциативный закон для конъюнкции
(AB)C=A(BC) ассоциативный закон для дизъюнкции
A(BC)=(AB)(AC) дистрибутивные законы
A (BC)=(AB)(AC)
AA=A закон идемпотенции для конъюнкции
AA=A закон идемпотенции. для дизъюнкции
(AB)=AB законы де Моргана
(AB)=AB
A1=A закон единицы для конъюнкции
A0=0 закон нуля для конъюнкции
A1=1 закон единицы для дизъюнкции
A0=A закон нуля для дизъюнкции
A(AA)=A законы поглощения
A(AA)=A
AA=1 закон исключения третьего
AA=0 закон противоречия
A(AB)=AB
A(AB)=AB
Глупости Одну и ту же зависимость между логическими переменными можно выразить различными формулами. Поэтому важно иметь возможность приводить формулы к некоторому стандартному виду. Существует несколько стандартных форм, к которым приводятся логические выражения с помощью эквивалентных преобразований (формулы 1-23).
Первая из них – дизъюнктивная нормальная форма (ДНФ), имеет вид
A1A2…An, где каждое из составляющих есть конъюнкция простых высказываний и их отрицаний, например
B=(A1A2A3)(A4A5)
Вторая – конъюнктивная нормальная форма (КНФ), имеет вид
A1A2…An, где каждое из составляющих есть дизъюнкция простых высказываний и их отрицаний, например
B=(A1A2A3)(A4A5)A6
Табличное и алгебраическое задание булевских функций
Задать булевскую функцию можно, в виде аналитического выражения или определяя ее значения для всех возможных наборов значений аргументов. Каждый аргумент может иметь два значения 0 и 1, следовательно, n аргументов могут принимать 2n различных наборов. Пусть, например булевская функция имеет три аргумента X1,X2,X3. Общее число наборов 23=8, зададим таблицу истинности функции, указав для каждого набора аргументов значение функции (в нашем случае зададим произвольное F).
-
№
X1
X2
X3
F
1
0
0
0
0
2
0
0
1
1
3
0
1
0
0
4
0
1
1
1
5
1
0
0
0
6
1
0
1
1
7
1
1
0
0
8
1
1
1
1
Для составления аналитической (алгебраической) формы F по результатам таблицы сделаем следующее:
- в
комбинациях, где функция F
= 1, единицу в аргументе заменим именем
функции, а нуль именем с отрицанием,
(т.е. комбинации аргументов 0 0 1 поставим
в соответствие выражение
это называется коституентой единицы);
- все элементы (конституенты единицы) соединим знаками дизъюнкции.
Для рассматриваемого примера, получим
(1)
Как нетрудно проверить, построенная функция (1) удовлетворяет всем строкам заданной таблицы истинности. Функция представляет дизъюнктивную нормальную форму. Кроме того, заметим, что в каждую группу дизъюнкций входят все аргументы функции. Такая ДНФ называется совершенной.
Аналогично, для комбинаций, где функция принимает значение нуля можно построить алгебраическую форму
(2),
которая также удовлетворяет заданной таблице истинности и представляет собой конъюнктивную нормальную форму, в данном случае совершенную. Каждая конъюнкция называется конституентой нуля.
Приведенный пример показывает, что любая булевская функция заданная таблично может быть представлена КНФ или ДНФ, и, обобщая, можно сказать, что вообще любая булевская функция представляется в КНФ или ДНФ.
Матрицы смежности будет состоять из пяти строк и пяти столбцов.
-
КНФ или ДНФ
Матрица инцидентности будет состоять из пяти строк и шести столбцов