C помощью диаграмм Эйлера-Венна

ОСМЕЛИВАЙСЯ БЫТЬ УМНЫМ

ДОКАЗАТЕЛЬСТВО ЛОГИЧЕСКИХ ЗАКОНОВ

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

• построив таблицу истинности для правой и левой части закона;
• выполнив эквивалентные преобразования над правой и левой частью формулы для приведения их к одному виду;
• с помощью диаграмм Эйлера-Венна;
• путем правильных логических рассуждений.

В качестве примера приведем различные способы доказательства законов де Моргана.

1. По таблице истинности:

C помощью диаграмм Эйлера-Венна

Ø(A V B) Ø (A L B)

ØA L ØB ØA V ØB

Упрощение сложных высказываний - это замена их на равносильные им на основе законов алгебры высказываний.

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

• по свойству констант X = Х L 1, Х = X V 0
• по закону исключенного третьего 1 = A V ØA
• по закону противоречия Z L ØZ = 0
• по закону идемпотентности В = В V В = B V B V B V B, C = C L C = C L C L C L C
• по закону двойного отрицания Е = Ø ØЕ

Рассмотрим, как можно применять перечисленные приёмы на следующих примерах.

Пример 1. Упростить: А LВ V А LØВ

По закону дистрибутивности вынесем А за скобки:

А LВ V А LØВ = A L(B V ØB) = А L1 = А

Пример 2. Упростить: (А V В) L(А V ØВ)

1 способ. Раскроем скобки по закону дистрибутивности:

(А V В) L(А V ØВ) = A V (B LØB) = A V 0 = A

2 способ. Перемножим скобки (как в обычной алгебре) на основании того же закона дистрибутивности:

(A V B) L(A V ØB) = A LA V A LØB V B LA V ØB LB = A V A L(B V ØB) V 0 = A V A L1 = A

Пример 3. Упростить: X V ØX LY

На первый взгляд, пример не позволяет его упростить, так как в этом выражении ничего нельзя вынести за скобки. Заметим, что “хочется”, чтобы у переменной Х “появился” Y. Для этого представим Х как Х L1, а 1 распишем по закону исключенного третьего как (Y V ØY). Далее раскроем скобки.

X V ØX LY = X L1 V ØX LY = X L(Y V ØY) V ØX LY = X LY V ØX LØY V X LY =

Далее “хочется” сгруппировать слагаемые. Нам не хватает для этого одного слагаемого. Учитывая, что законы идемпотентности позволяют нам добавлять в выражение любой из имеющихся уже в нём слагаемых (сомножителей), добавим к полученному выражению X LY. Получим:

= X LY V X LØY V ØX LYVX LY=(X LY V X LØY) V (ØX LY V X LY) =

= X L(Y V Y) V Y L(X V X) = X L1 V Y L1 = X V Y

Пример 4. Упростить A LC V B LØC V A LB

Один из возможных вариантов упрощения состоит в том, чтобы добавить к последнему слагаемому переменную С. Это делается стандартным способом: умножить А LB на 1, а 1 расписать как (С V ØC).

A LC V B LØC V A LB = A LC V B LØC V A LB L1 =

= A LC V B LØC V A LB L(C V ØC) = A LC V B LØC V A LB LC V A LB LØC =

= A LCVA LB LC V B LØC V A LB LØC=A LC L(1 V B)VBLØCL(1 V A) =

= A LC V B LC

Пример 5. Упростить: Ø(ØX V ØY)

Применим закон де Моргана:

Ø(ØX V ØY) = ØØ(X L Y) = X LY

Пример 6. Упростить: ØX LY V X LØY V X LØZ

В данном случае воспользуемся законом двойного отрицания.

ØX LY V X LØY V X LØZ = ØØ (ØX LY V X LØY V X LØZ) = (раскроем одно отрицание) = Ø ((X LY) L(X LY) L (X LZ) = (XVY) L (XVY) L (XVZ))=

(перемножим первую и вторую скобки, упростим, а третью пока оставим без изменения)

= (X LX V X LY V X LY V Y LY) L (X V Z) = (X LY V X LY) L (XVZ) =

(перемножим скобки и упростим)

= X LX LY V X LY LZ V X LY V X LY LZ = X LY LZ V X LY =

(раскроем по закону де Моргана)

= X LY LZ L (X V Y) = (X V Y V Z) L (X V Y)