Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Основные законы булевой алгебры

К основным законам (тождествам, правилам) булевой алгебры относятся:

1. Коммутативные (переместительные) законы:

2. Ассоциативные (сочетательные) законы:

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

4. Закон двойного отрицания:

5. Законы тавтологии (идемпотентности):

6. Законы нулевого элемента:

7. Законы единичного элемента:

8. Законы дополнительного элемента. В булевой алгебре дополнительным элементом по отношению к а является отрицание

9. Законы двойственности (де Моргана):

Следствия:

10. Законы поглощения:

11. Правила сокращения:

Следствия:

12. Правила склеивания:

Комментарии к законам булевой алгебры

1. Для доказательства законов можно использовать:

а) метод совершенной индукции,

б) одни законы для доказательства других законов.

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

2. Большинство законов задается парой соотношений (дуальность законов булевой алгебры). При этом одно соотношение можно получить из другого, заменив операции конъюнкции на дизъюнкцию или дизъюнкцию на конъюнкцию. В законах, в которых участвуют логические константы (0 и 1), они заменяются на противоположные значения.

3. Некоторые законы можно распространять на произвольное число элементов.

4. В любом законе любую букву можно заменить на произвольное логическое выражение.

5. Законы применяются для упрощения булевых функций.

 

Разнообразие булевых функций

Булевы функции от одной переменной приведены в табл.2.1.

 

Обозначение аргумента и функции Значения аргумента и функции Наименование функции
x  
Логический ноль
Повторение x
Инверсия x
Логическая единица

 

Таблица 2.1. Булевы функции от одной переменной

Булева функция от n аргументов f n(Х) называется вырожденной по аргументу xi, если ее значение не зависит от этого аргумента, то есть для всех наборов аргументов имеет место равенство:

f(x1, x2, ... , xi-1, 0, xi+1, ... , xn) = f(x1, x2, xi-1, 1, xi+1, ... , xn).

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

Среди функций от одной переменной содержатся две вырожденные: логический ноль и логическая единица.

Булевы функций от двух переменных приведены в табл.2.2.

Среди функций от двух переменных шесть вырожденных функций, к которым относятся:

· логический ноль;

· логическая единица;

· функция повторения аргументов x1 и x2;

· отрицание аргументов x1 и x2.

 

Некоторые функции от трех переменных представлены в табл. 2.3.

 

Замечание. Функции сумма по модулю 2 и исключающее ИЛИ для трех аргументов являются неэквивалентными.

 

Утверждение. Общее число разнообразных булевых функций, в том числе и вырожденных, от n аргументов равно .


Аргументы и функции (в символической форме) Значения аргументов и функций Обозначение функций Наименование Вырожденность Представление функции в булевом базисе
x1
x2
Логический ноль + -
x1 & x2 Конъюнкция -
x1 D x2 Запрет x1 по x2 -
x1 Повторение x1 + -
x2 D x1 Запрет x2 по x1 -
x2 Повторение x2 + -
x1Å x2 Сумма по модулю 2, неравнозначность, исключительное ИЛИ -
x1Ú x2 Дизъюнкция -
x1¯ x2 Функция Вебба, стрелка Пирса -
x1~ x2 (x1º x2) Равнозначность, эквивалентность -
Отрицание x2 +
x2® x1 Импликация от x2 к x1 -
Отрицание x1 +
x1® x2 Импликация от x1 к x2 -
x1ï x2 Штрих Шеффера -
Логическая единица + -

Таблица 2.2. Булевы функции от двух переменных


Значение аргументов Значение функций
Сумма по модулю 2 Исключающее ИЛИ Функция мажоритарности
x1 x2 x3 x1Å x2Å x3 XOR (x1,x2,x3) x1#x2#x3

 

Таблица 2.3. Некоторые функции от трех переменных

Последнее изменение этой страницы: 2016-06-09

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...