Головна |
Логічні вирази називаються рівносильними, Якщо їх істінностние значення збігаються при будь-яких значеннях, що входять в них логічних змінних.
В алгебрі логіки є ряд законів, що дозволяють виробляти рівносильні перетворення логічних виразів. Наведемо співвідношення, що відображають ці закони.
1. Закон подвійного заперечення:
А = .
Подвійне заперечення виключає заперечення.
2. Переместітельний (комутативними) закон:
- Для логічного додавання:
А U B = B U A;
- Для логічного множення:
A&B = B&A.
Результат операції над висловлюваннями не залежить від того, в якому порядку беруться ці висловлювання.
У звичайній алгебрі a + b = b + a, a 'b = b' a.
3. Сполучний (асоціативний) закон:
- Для логічного додавання:
(A U B) U C = A U (B U C);
- Для логічного множення:
(A&B) &C = A& (B&C).
При однакових знаках дужки можна ставити довільно або взагалі опускати.
У звичайній алгебрі:
(A + b) + c = a + (b + c) = a + b + c,
а '(b' c) = a '(b' c) = a 'b' c.
4. Розподільчий (дистрибутивний) закон:
- Для логічного додавання:
(A U B) & C = (A & C) U (B & C);
- Для логічного множення:
(A&B) U C = (A U C) & (B U C).
Визначає правило виносу загального висловлювання за дужку.
У звичайній алгебрі:
(A + b) 'c = a' c + b 'c.
5. Закон загальної інверсії (закони де Моргана):
- Для логічного додавання
= & ;
- Для логічного множення:
= U
6. закон ідемпотентності (Від латинських слів idem - той же самий і potens -сильний; дослівно - рівносильний):
- Для логічного додавання:
A U A = A;
- Для логічного множення:
A&A = A.
Закон означає відсутність показників ступеня.
7. Закони виключення констант:
- Для логічного додавання:
A U 1 = 1, A U 0 = A;
- Для логічного множення:
A& 1 = A, A& 0 = 0.
8. Закон суперечності:
A& = 0.
Неможливо, щоб суперечать висловлювання були одночасно істинними.
9. Закон виключення третього:
A U = 1.
З двох суперечливих висловлювань про одне й тому самому предметі одне завжди істинно, а друге - хибне, третього не дано.
10. закон поглинання:
- Для логічного додавання:
A U (A&B) = A;
- Для логічного множення:
A& (A U B) = A.
11. Закон виключення (склеювання):
- Для логічного додавання:
(A&B) U ( &B) = B;
- Для логічного множення:
(A U B) & ( U B) = B.
12. Контрапозиція (правило перевертання):
(A U B) = (BU A).
Справедливість наведених законів можна довести табличним способом: виписати всі набори значень А і В, обчислити на них значення лівої і правої частин доказуваного вираження і переконатися, що результуючі стовпці співпадуть.
Приклад 3.11. Знайдіть X, якщо U = В.
Для перетворення лівій частині рівності послідовно скористаємося законом де Моргана для логічного додавання і законом подвійного заперечення:
( & ) U ( &A)
Згідно з розподільчим законом для логічного додавання:
& ( U A)
Відповідно до закону виключення третього і закону виключення констант:
& 1 =
Отриману ліву частину прирівняємо правої:
= В
Остаточно отримаємо, що X = .
Приклад 3.12. Зробіть логічний вираз (A U B U C) &
Правильність спрощення перевірте за допомогою таблиць істинності для початкового і одержаного логічного виразу.
Відповідно до закону загальної інверсії для логічного додавання (до першого закону Моргана) і закону подвійного заперечення:
(A U B U C) & = (A U B U C) & ( & B & )
Згідно з розподільчим (дистрибутивному) закону для логічного додавання:
(A U B U C) & ( &B& ) = (A& ) U (B& ) U (C& ) U (A&B) U (B&B) U (C&B) U (A& ) U (B& ) U (C& )
Згідно закону протиріччя:
(A& ) = 0; (C& ) = 0
Згідно закону ідемпотентності
(B&B) = B
Підставляємо значення і, використовуючи переместітельний (комутативними) закон і групуючи доданки, отримуємо:
0 U (A&B) U ( &B) U B U (C&B) U ( &B) U (C& ) U (A& ) U 0
Згідно закону виключення (склеювання)
(A&B) U ( &B) = B
(C&B) U ( &B) = B
Підставляємо значення і отримуємо:
0 U B U B U B U (C& ) U (A& ) U 0
Згідно закону виключення констант для логічного додавання і закону ідемпотентності:
0 U B U 0 U B U B = B
Підставляємо значення і отримуємо:
B U (C& ) U (A& )
Згідно з розподільчим (дистрибутивному) закону для логічного множення:
(C& ) U (A& ) = (C U A) & (C U ) & ( U A) & ( U )
Згідно закону виключення третього:
(C U ) = 1
( U A) = 1
Підставляємо значення і остаточно отримуємо:
B& & .
Методи (різновиди) МКР. | Завдання для самостійного виконання