Основные тождества (равносильные формулы) алгебры логики.

 

1. xÙy=yÙx; xÚy=yÚx – коммутативность
2. xÙ(yÙz)= (xÙy)Ùz; xÚ(yÚz)= (xÚy) Úz; - ассоциативность
3. xÙ(yÚz)=(xÙy)Ú(xÙz); xÚ(yÙz)=(xÚy)Ù(xÚz) – дистрибутивность
4. xÙx=x; xÚx=x - идемпотентность;
5. xÙ1=x; xÚ1=1; xÙ0=0; xÚ0=x – законы операций с константами
6. xÙ(yÚx)=x; xÚ(yÙx)=x – законы поглощения;
7. xÙØx=0 - закон противоречия;
8. xÚØx=1 - закон исключения третьего
9. ØØx=x – закон двойного отрицания
10. x®y = Øy®Øx – закон контрапозиции;
11. Ø(xÙy)= ØxÚØy; Ø(xÚy)=ØxÙØy – законы де Моргана;
12. (xÙy)Ú(xÙØy)=x; (xÚy)Ù(xÚØy)=x - формулы расщепления (или склеивания)

 

Все тождества можно доказать, составив таблицы истинности.

Если в тождестве заменить знак = на <-> то получится тавтология.

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

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