Аксиомы и основные свойства алгебры логики

 

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

АКСИОМЫ алгебры логики:

 

0 * 0 = 0 0 + 0 = 0

0 * 1 = 0 0 + 1 = 1

1 * 0 = 0 1 + 0 = 1

1 * 1 = 1 1 + 1 = 1

 

ЗАКОНЫ алгебры логики:

1. Закон одинарных элементов

1 * X = X 0 * X = 0

1 + X = 1 0 + X = X

2. Законы отрицания

а) Закон дополнительных элементов.

б) Двойное отрицание

поэтому отрицание можно переносить из одной части равенства в другую.

в) Закон двойственности (правилоМоргана).

Отрицание дизъюнкции есть конъюнкция отрицаний и наоборот - отрицание конъюнкции есть дизъюнкция отрицаний:

Правило справедливо для любого числа переменных.

3. Комбинационные законы.

Они во многом соответствуют обычной алгебре, но есть и отличия.

а) тавтологии( многократное повторение)

б) переместительности

A+B+C+D=A+C+B+D

в) сочетательности

A+B+C+D=A+(B+C)+D=A+B+(C+D)

г) распределительности

X1(X2+X3)= X1X2 + X1X3

X1+X2X3=(X1+X2)(X1+X3)=/ докажем это путём раскрытия скобок/=

= X1X1+ X1X3+ X1X2+ X2X3= X1(1+X3+X2)+ X2X3= X1+X2X3

д) правило поглощения (одна переменная поглощает другие)

X1+X1X2 X3 =X1(1+X2 X3 )=X1

е) правило склеивания (выполняется только по одной переменной)

Также как в обычной математике имеется старшинство операций:

1) Действие в скобках

2) Операция с одним операндом (одноместная операция) –НЕ

3) Конъюнкция - И

4) Дизъюнкция - ИЛИ

5) Сумма по модулю два.

Операции одного ранга выполняются слева направо в порядке написания.

 

Понятие базиса

 

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

Базисов может быть много:

1. И, ИЛИ, НЕ 2. И, НЕ

3. И – НЕ 4. НЕ – И

5. ИЛИ, НЕ 6. ИЛИ – НЕ

7. НЕ – ИЛИ 8. “0”, ”1”, НЕ, n и другие.

 

Рисунок 1.15 – Некоторые базисы

 

Мажоритарный элемент ( n) имеет нечетное число входов и вырабатывает 1, если число единиц на входе больше чем нулей (правило голосования).

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

Используя законы алгебры логики, можно переходить от одного базиса к другому.

Например, пусть имеется элемент 3И-НЕ, а необходимо реализовать следующие операции:

1. НЕ

2. И (для 2-x переменных)

3. ИЛИ (для 2-x переменных)

Реализуем эти операции.

1. Операция НЕ получается на основании закона тавтологии (рис.1.16)

Рисунок 1.16 – Инвертор на элементе Шеффера

 

2. Операция И получается на основании законов тавтологии и двойного отрицания (рис. 1.17)

Рисунок 1.17 – Конъюнктор на элементах Шеффера

 

3. Операция ИЛИ получается на основании правила двойственности . Тогда получаем следующую реализацию (рис. 1.18):

Рисунок 1.18 –Дизъюнктор на элементах Шеффера

 








Дата добавления: 2016-01-18; просмотров: 2918;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.