Головна

Логічні закони і правила перетворення логічних виразів

  1. B яких випадках допускається зміна державного контракту на виконання НДР, ДКР і технологічних робіт для державних потреб?
  2. II. Правила орфографії, пов'язані з фонемно-графемно
  3. II. Неопіоідние анальгетики (ЛВ з інших фармакологічних груп, що володіють болезаспокійливу дію)
  4. IV етап: психологія як наука про психічні процеси, психічні стани, індивідуально-психологічні особливості особистості (з початку ХХ ст. По теперішній час).
  5. IV. ЗАКОНИ ХП таблиць
  6. PRINT спісок_вираженій
  7. А) Логічні відносини між простими судженнями

Логічні вирази називаються рівносильними, Якщо їх істінностние значення збігаються при будь-яких значеннях, що входять в них логічних змінних.

В алгебрі логіки є ряд законів, що дозволяють виробляти рівносильні перетворення логічних виразів. Наведемо співвідношення, що відображають ці закони.

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& & .

Методи (різновиди) МКР. | Завдання для самостійного виконання

© 2016-2022  um.co.ua - учбові матеріали та реферати