Припустимо, що є дві формули, X і Y. Ці формули будуть відомі як еквівалентність, якщо X ↔ Y є тавтологією. Якщо дві формули X ↔ Y є тавтологією, то ми також можемо записати це як X ⇔ Y, і ми можемо читати це відношення як X є еквівалентністю Y.
Примітка: є деякі моменти, які ми повинні мати на увазі під час лінійної еквівалентності формули, які описані таким чином:
- ⇔ використовується лише для позначення символу, але не є сполучним.
- Значення істинності X і Y завжди буде рівним, якщо X ↔ Y є тавтологією.
- Відношення еквівалентності містить дві властивості, тобто симетричність і транзитивність.
Метод 1: Метод таблиці істинності:
У цьому методі ми побудуємо таблиці істинності будь-якої формули з двома висловлюваннями, а потім перевіримо, чи є ці висловлювання еквівалентними.
приклад 1: У цьому прикладі ми маємо довести X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
рішення: Таблиця істинності X ∨ Y ⇔ ¬(¬X ∧ ¬Y) описана таким чином:
| X | І | X ∨ Y | ¬X | ¬І | ¬X ∧ ¬Y | ¬(¬X ∧ ¬Y) | X ∨ Y ⇔ ¬(¬X ∧ ¬Y) |
|---|---|---|---|---|---|---|---|
| Т | Т | Т | Ф | Ф | Ф | Т | Т |
| Т | Ф | Т | Ф | Т | Ф | Т | Т |
| Ф | Т | Т | Т | Ф | Ф | Т | Т |
| Ф | Ф | Ф | Т | Т | Т | Ф | Т |
Як бачимо, X ∨ Y і ¬(¬X ∧ ¬Y) є тавтологією. Отже, X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
приклад 2: У цьому прикладі ми маємо довести (X → Y) ⇔ (¬X ∨ Y).
рішення: Таблиця істинності (X → Y) ⇔ (¬X ∨ Y) описана таким чином:
| X | І | X → Y | ¬X | ¬X ∨ Y | (X → Y) ⇔ (¬X ∨ Y) |
|---|---|---|---|---|---|
| Т | Т | Т | Ф | Т | Т |
| Т | Ф | Ф | Ф | Ф | Т |
| Ф | Т | Т | Т | Т | Т |
| Ф | Ф | Т | Т | Т | Т |
Як бачимо, X → Y і (¬X ∨ Y) є тавтологією. Отже (X → Y) ⇔ (¬X ∨ Y)
Формула еквівалентності:
Існують різні закони, які використовуються для підтвердження формули еквівалентності, яка описана таким чином:
Ідемпотентний закон: Якщо є одна формула оператора, то вона матиме такі властивості:
X ∨ X ⇔ X X ∧ X ⇔ X
Асоціативний закон: Якщо існує три формули оператора, то вона матиме такі властивості:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Комутативний закон: Якщо існує дві формули оператора, то вона матиме такі властивості:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Закон розподілу: Якщо існує три формули оператора, то вона матиме такі властивості:
як відкрити файл json
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Закон про тотожність: Якщо є одна формула оператора, то вона матиме такі властивості:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Закон доповнення: Якщо є одна формула оператора, то вона матиме такі властивості:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Закон поглинання: Якщо існує дві формули оператора, то вона матиме такі властивості:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
Із закону Моргана: Якщо існує дві формули оператора, то вона матиме такі властивості:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
Спосіб 2: Процес заміни
У цьому методі ми припустимо формулу A : X → (Y → Z). Формула Y → Z може бути відома як частина формули. Якщо замінити цю частину формули, тобто Y → Z, на формулу еквівалентності ¬Y ∨ Z в A, то ми отримаємо іншу формулу, тобто B : X → (¬Y ∨ Z). Перевірити, чи еквівалентні наведені формули A і B одна одній, легко. За допомогою процесу заміни ми можемо отримати B з A.
приклад 1: У цьому прикладі ми маємо довести, що {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.
рішення: Тут ми візьмемо ліву частину і спробуємо отримати праву частину.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Тепер ми будемо використовувати асоціативний закон так:
⇔ (¬X ∨ ¬Y) ∨ Z
Тепер ми використаємо закон Де Моргана таким чином:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Звідси доведено
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z приклад 2: У цьому прикладі ми маємо довести, що {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y.
рішення: Тут ми візьмемо ліву частину і спробуємо отримати праву частину.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Звідси доведено
{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y
приклад 3: У цьому прикладі ми маємо довести, що X → (Y → X) ⇔ ¬X → (X → Y).
рішення: Тут ми візьмемо ліву частину і спробуємо отримати праву частину.
X → (Y → X) ⇔ ¬X ∨ (Y → X) ⇔ ¬X ∨ (¬Y ∨ X) ⇔ (¬X ∨ X) ∨ ¬Y ⇔ T ∨ ¬Y ⇔ T and ¬X → (X → Y) ⇔ ¬(¬X) ∨ (X → Y) ⇔ X ∨ (¬X ∨ Y) ⇔ (X ∨ ¬X) ∨ Y ⇔ T ∨ Y ⇔ T
Звідси доведено
X → (Y → X) ⇔ ¬X → (X → Y)
Приклад 4: У цьому прикладі ми маємо довести, що (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.
рішення: Тут ми візьмемо ліву частину і спробуємо отримати праву частину.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Тепер ми будемо використовувати асоціативний і розподільний закони таким чином:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Тепер ми використаємо закон Де Моргана таким чином:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Тепер ми будемо використовувати закон розподілу таким чином:
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Звідси доведено
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
Приклад 5: У цьому прикладі ми маємо показати, що ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) є тавтологією.
рішення: Тут ми візьмемо маленькі частини та розв’яжемо їх.
Спочатку ми використаємо закон Де Моргана та отримаємо наступне:
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
тому
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
Також
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Отже
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Таким чином
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Отже, можна сказати, що наведена формула є тавтологією.
Приклад 6: У цьому прикладі ми маємо показати, що (X ∧ Y) → (X ∨ Y) є тавтологією.
рішення: (X ∧ Y) → (X ∨ Y)
перехід непрозорості css
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Тепер ми використаємо закон Де Моргана таким чином:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Тепер ми будемо використовувати асоціативний закон і комутативний закон таким чином:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Тепер ми використаємо закон заперечення таким чином:
⇔ (T ∨ T) ⇔ T
Отже, можна сказати, що наведена формула є тавтологією.
Приклад 7: У цьому прикладі ми повинні написати заперечення деяких тверджень, які описані наступним чином:
- Мері завершить освіту або прийме лист про приєднання до компанії XYZ.
- Завтра Гаррі піде покататися або побігати.
- Якщо я отримаю хороші оцінки, мій двоюрідний брат заздрить.
рішення: Спочатку ми розв’яжемо перше твердження так:
1. Припустимо, що X: Marry закінчить свою освіту.
Y: Прийміть лист про приєднання компанії XYZ.
Ми можемо використати наступну символічну форму, щоб висловити це твердження:
X ∨ Y
Заперечення X ∨ Y описується таким чином:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
У підсумку, заперечення даного твердження буде:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Припустимо, Х: Гаррі піде покататися
Y: Гаррі побіжить завтра
Ми можемо використати наступну символічну форму, щоб висловити це твердження:
X ∨ Y
Заперечення X ∨ Y описується таким чином:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
У підсумку, заперечення даного твердження буде:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Припустимо X: якщо я отримаю хороші оцінки.
Y: Мій двоюрідний брат буде ревнувати.
Ми можемо використати наступну символічну форму, щоб висловити це твердження:
X → Y
Заперечення X → Y описується таким чином:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
У підсумку, заперечення даного твердження буде:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
Приклад 8: У цьому прикладі ми повинні записати заперечення деяких тверджень за допомогою закону Де Моргана. Ці заяви описані таким чином:
- Мені потрібен набір з діамантами і ціна золотого персня.
- Ви отримаєте хорошу роботу або не знайдете хорошого партнера.
- Я беру багато роботи і не можу з нею впоратися.
- Моя собака їде в подорож або влаштовує безлад у домі.
рішення: Заперечення всіх тверджень за допомогою закону Де Моргана описується одне за одним так:
- Мені не потрібен діамантовий набір, або я не вартий золотого персня.
- Ви не можете отримати хорошу роботу, але ви отримаєте хорошого партнера.
- Я не беру багато роботи або можу впоратися.
- Мій пес не їздить у подорожі і не влаштовує безладу в домі.
Приклад 9: У цьому прикладі у нас є кілька тверджень, і ми повинні написати заперечення цих тверджень. Заяви описуються таким чином:
- Якщо йде дощ, то план походу на пляж скасовується.
- Якщо я буду старанно вчитися, то отримаю хороші оцінки на іспиті.
- Якщо я піду на нічну вечірку, то мене покарає батько.
- Якщо ви не хочете зі мною розмовляти, то вам доведеться заблокувати мій номер.
рішення: Заперечення всіх тверджень описується одне за іншим так:
- Якщо план походу на пляж скасовується, значить йде дощ.
- Якщо я отримую хороші оцінки на іспиті, то я старанно вчуся.
- Якщо я отримаю покарання від батька, то я йду на вечірку.
- Якщо вам доведеться заблокувати мій номер, то ви не хочете зі мною розмовляти.
Приклад 10: У цьому прикладі ми повинні перевірити, чи (X → Y) → Z і X → (Y → Z) логічно еквівалентні чи ні. Ми повинні обґрунтувати нашу відповідь за допомогою таблиць істинності та за допомогою правил логіки, щоб спростити обидва вирази.
рішення: Спочатку ми використаємо метод 1, щоб перевірити, чи є (X → Y) → Z і X → (Y → Z) логічно еквівалентними, що описується наступним чином:
зробити сценарій виконуваним
Спосіб 1: Тут ми припустимо наступне:
(X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z)
І
X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z)
Спосіб 2: Тепер ми скористаємося другим способом. У цьому методі ми будемо використовувати таблицю істинності.
| X | І | З | X → Y | (X → Y) → Z | Y → Z | X → (Y → Z) |
|---|---|---|---|---|---|---|
| Т | Т | Т | Т | Т | Т | Т |
| Т | Т | Ф | Т | Ф | Ф | Ф |
| Т | Ф | Т | Ф | Т | Т | Т |
| Т | Ф | Ф | Ф | Т | Т | Т |
| Ф | Т | Т | Т | Т | Т | Т |
| Ф | Т | Ф | Т | Ф | Ф | Т |
| Ф | Ф | Т | Т | Т | Т | Т |
| Ф | Ф | Ф | Т | Ф | Т | Т |
У цій таблиці істинності ми бачимо, що стовпці (X → Y) → Z і X → (Y → Z) не містять ідентичних значень.