Принцип двойственности в алгебре Буля

Заключается в возможности замены операции И на операцию ИЛИ и наоборот, если значение 1 поменять на 0, значение 0 на 1, а знаки логического сложения « » на знаки логического умножения «Λ» и наоборот.

Этот принцип вытекает из только что рассмотренных таблиц истинности, то есть

Если , то

Если , то

Правила для сочетаний переменной с константами 0,1 с самой переменной Х и её инверсией.

Для операций дизъюнкции:

X + 0 = X

X + 1 = 1

X + X = X

X + = 1

Для операций конъюнкции:

X · 0 = 0

X · 1 = X

X · X = X

X · = 0

Для инверсии:

X =

Законы булевой алгебры

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

1. Переместительный закон – порядок записи переменных не влияет на результат (переменные можно менять местами). Имеет аналог в обычной алгебре.

+

2.Сочетательный закон (ассоциативный). Можно производить объединение переменных в скобки.

3.Распределительный закон (дистрибутивный)

не имеет аналога в обычной алгебре, поэтому докажем путем почленного перемножения скобочных выражений правой части:

(Х₁ + Х₂)(Х₁ + Х₃) = Х₁Х₁ + Х₁Х₃ + Х₁Х₂ + Х₂Х₃ =Х₁ + Х₁Х₃ + Х₁Х₂ + Х₂Х₃ = Х₁(1 + Х₃ + Х₂) + Х₂Х₃ = Х₁ + Х₂Х₃, что и требовалось доказать.

4.Закон поглощения

Докажем первое выражение:

=

Докажем второе выражение:

5.Закон склеивания

=

Докажем первое выражение:

Докажем второе выражение:

=

6.Закон инверсии или правило де Моргана. (Огастес де Морган – 1806-1871 шотландский математик и логик, независимо от Джорджа Буля пришел к основным идеям математической логики).

; Инверсия дизъюнкции переменных есть конъюнкция инверсий этих же переменных.

Соответственно: Инверсия конъюнкции переменных есть дизъюнкция инверсий этих же переменных

или

; Дизъюнкция переменных есть инверсия конъюнкции инверсий этих же переменных.

7.Закон повторений или тавтологии:

8.Закон двойной инверсии

; Четное количество инверсий может быть отброшено.

Логические функции л.Ф.

Л.Ф. называется функция двоичных переменных

Y = (

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

Если число аргументов равно , то число возможных комбинаций значений аргументов равно .

Конкретную комбинацию переменных называют набором.

Пример:

Л.Ф. называется определенной, если известно ее логическое значение для каждого возможного набора переменных

Л.Ф. называется частично определенной, если для некоторых наборов переменных функция Y = ( недоопределена (не задана).

Способы представления логических функций

1 способ – словами. Например – правило выполнения операции дизъюнкции: значение функции Y истинно, если хотя бы один из ее аргументов принимает единичное значение.

2 способ – табличный с помощью таблиц истинности.

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

4 способ – графический, использующий геометрическое представление логической функции в виде n-мерных кубов или матриц Карно (в данном материале не излагается).

Рассмотрим пример изложения некоторой логической функции:

словами: Значение функции трех аргументов считается истинным, если хотя бы два аргумента приняли единичные значения. В остальных случаях функция Y ложна, то есть равна 0.

От словесного описания функции перейдем к её формальному выражению в виде таблицы истинности (табл. 1.4):

число строк таблицы равно , где n = 3 – число независимых аргументов, т.е.

Таблица 1.4

Таблица истинности функции трех

переменных Х₁, Х₂ и Х₃

			Y
0	0	0	0
0	0	1	0
0	1	0	0
0 1 1 1 1	1 0 0 1 1	1 0 1 0 1	1 0 1 1 1

Это мажоритарный элемент (франц. – большой, большинство), т.е. необходимо наличие min 2 аргументов (большинство из трех) чтобы Y = 1.

аналитически: Анализируя вышеприведенную таблицу истинности, видим, что значение Y = 1 если:

а) т.е. сочетание

или

б) т.е. сочетание

или

в) т.е. сочетание

или

г) т.е. сочетание

Каждое из произведений аргументов, содержащее все переменные в прямом или инверсном виде, для которых значение Y истинно или ложно называют минтермом или конституентом 1 или 0 соответственно.

Тогда логическую функцию Y = ( можно представить в виде суммы четырех минтермов (конституентов 1).

Y = +

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

Точно так же можно выделить и ложные (нулевые) значения функции (из табл.), т.е.

Значение Y = 0 если:

а) т.е. сочетание

или

б) т.е. сочетание

или

в) т.е. сочетание

или

г) т.е. сочетание

Следовательно:

= +

Поставив инверсии над левой и правой частями выражения и используя правило Де Моргана, получим:

Y =(

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