Примеры решения задач “Законы и правила преобразования логических выражений “

 №1.

Какое логическое выражение равносильно выражению ¬ (А \/ ¬B)?

1)A \/ B          2)A /\ B        3) ¬A \/ ¬B        4) ¬A /\ B

 

Решение (вариант 1, использование законов де Моргана):

1)      данное выражение представляет инверсию (отрицание) сложного высказывания, заданного в скобках. Раскроем скобки по закону де Моргана:

¬ (А \/ ¬B) = ¬А /\ ¬(¬B)

2)      теперь воспользуемся законом двойного отрицания, по которому  ¬(¬B) = В:

¬А /\ ¬(¬B) = ¬A /\ B

Ответ: 4

 

Решение (вариант 2, через таблицы истинности, если забыли формулы де Моргана):

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

А

В

¬А

¬B

А \/¬B

¬ (А \/ ¬B)

A\/ B

A/\B

¬A\/ ¬B

¬A/\B

0

0

1

1

1

0

0

0

1

0

0

1

1

0

0

1

1

0

1

1

1

0

0

1

1

0

1

0

1

0

1

1

0

0

1

0

1

1

0

0

 

Очевидно, что таблицы истинности исходного выражения ¬ (А \/ ¬B) и выражения ¬A/\ Bсовпадают во всех строчках.

 Ответ: 4



№2.

Упростить формулу \/ В) /\  (А \/С).

Решение:

  1. Раскроем скобки: \/ В) /\  (А \/ С) = A  /\  A \//\  C \//\  A \//\  C;
  2. По закону идемпотентности A/\A=A, следовательно,
    /\  A \//\  C \//\  A \//\  C = A \/ A /\ C \/ B /\ A \/ B /\ C;
  3. В высказываниях А и А /\ C вынесем за скобки А и используя свойство А \/  1= 1, получим
    A \/A /\ C \/B /\ A \/ B /\ C = A /\ (1 \/ C) \/ B /\ A \/ B /\ C = A \/ B /\ A \/ B /\ C;
  4. Аналогично предыдущему пункту вынесем за скобки высказывание А.
    A \/ B /\ A \/ B /\ C = A /\ (1 \/ B) \/ B /\ C = A \/ B /\ C.

Таким образом, мы доказали закон дистрибутивности.

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