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

Элементы математической логики

Цифровых устройств

Алгебра логики и теоретические основы синтеза

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

Базой алгебры логики являются понятия о высказывании, истинности и лож­ности высказывания, связях между высказываниями. Высказывание или логический аргумент в зависимости от значения бывают истинными или ложными. Значение высказывания может изменяться с изменением обстоя­тельств, и таким образом высказывание меняет оценку своей истинности. С точки зрения логики, высказывания можно разделить на:

□ высказывание истинно постоянно (математически их принимают равны­ми 1); □ высказывание ложно постоянно (математически их принимают равными 0);

□ высказывание, которое может быть истинным или ложным в зависимости от определенных условий, т. е. принимать значение 1 или 0 попеременно.

По смыслу высказывания бывают простые и сложные. Простое высказывание — логический аргумент (переменная) — входит в состав сложного высказыва­ния логической функции, которая зависит от истинности или ложности аргу­мента. Обычно простое высказывание обозначается малыми буквами латин­ского или русского алфавита: х, е, z, т, р, а, b. Сложные высказывания или логические функции, обозначают большими буквами латинского или русско­го алфавита: А, F, Р, X, Y, S, Q). Связи между высказываниями-аргументами по своей логике разные, и из-за этого значение сложного высказывания непо­стоянное.

В алгебре логики введена следующая система аксиом, которая опре­деляет свойства и отношения основных операций:

а+b=b+а

а(b + с) = аb + ас

а + bс = (а + b)(а + с)

а + =1

а+=b+

а = b

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

1. Законы нулевого множества

0 = 0

0 + а = а

0=0,

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

2. Законы универсального множества

1 = а

1 + а = 1

1 + а + b +... + = 1,

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

3. Законы идемпотентности (повторения, тавтологии)

аа...а = а

а + а +.... + а = а.

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

= а,

т. е. двойную инверсию можно снять.

5. Законы дополнительности:

а) логическое противоречие

а = 0,

т. е. конъюнкция любой переменной и ее инверсии есть 0.

б) закон исключенного третьего а + =1,

т. е. дизъюнкция любой переменной и ее инверсии есть 1.

6. Коммутативный (закон перемещения) закон

аb = bа

a+b=b+a,

т. е. результаты выполнения операций конъюнкции и дизъюнкции не за­висят от того, в каком порядке следуют переменные.

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

а(bс) = (аb)с = аbс

а + (b+ с) = (а + b) + с = а + с + b,

т. е. для записи конъюнкции или дизъюнкции скобки можно опустить.

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

а) конъюнкции относительно дизъюнкции

а(b+ с) = аb + ас;

б) дизъюнкции относительно конъюнкции

а + bс = (а + b)(а + с).

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

а(а + b) = а

а(а + b)(а + с)...(а + w) = а

а + аb = а

a+аb+ ас+...+ аw = а

а(+ b) = аb

а + b = а + b.

10. Законы склеивания (распространения)

аb + а = а

(а + b)(а +) = а.

11. Законы обобщенного склеивания

аb + а + bс = аb + а

(а + b)(+ с)(b+ с) = (а + b)( + с)

(а + b)(+с) = ас + b.

12. Законы де Моргана (законы инверсии):

а) для двух переменных

= +,

т. е. инверсия конъюнкции есть дизъюнкция инверсий;

=,

т. е. инверсия дизъюнкции есть конъюнкция инверсий;

б) для n переменных

13. Теорема разложения

.

Дата добавления: 2014-01-11