2.3: Логічні еквіваленти
- Page ID
- 64937
Деякі логічні твердження «однакові». Наприклад, в останньому розділі ми обговорювали той факт, що умовний і його контрапозитив мають однаковий логічний зміст. Чи не були б ми виправдані в написанні щось на зразок наступного?
\(A \implies B = ¬B \implies ¬A\)
Ну, одне досить серйозне заперечення на те, що знак\((=)\) рівності вже отримав роботу; він використовується для позначення, що дві числові величини однакові. Те, що ми робимо тут, дійсно щось інше! Проте, між певними складовими висловлюваннями існує поняття «однаковість», і нам потрібен символічний спосіб його вираження. Є два позначення в загальному вживанні. Позначення, яке, здається, віддають перевагу логікам, є біумовним\((\iff)\). Позначення, яке ми будемо використовувати в іншій частині цієї книги, є знаком рівності з трохи додаткових прикрас на ньому\((\cong)\).
Таким чином, ми можемо або написати
\((A \implies B) \iff (¬B \implies ¬A)\)
або
\(A \implies B \cong ¬B \implies ¬A.\)
Мені подобається останнє, але використовуйте будь-яку форму, яка вам подобається - ніхто не матиме жодних проблем з розумінням.
Формальне визначення логічної еквівалентності, яке ми описували, полягає в наступному: два складних речення логічно еквівалентні, якщо в таблиці істинності (яка містить всі можливі комбінації істинних значень змінних предикатів у своїх рядках) значення істинності двох речень рівні в кожному ряду.
Розглянемо два складних речення\(A ∨ B\) і\(A ∨ (¬A ∧ B)\). Між ними є загальна кількість змінних\(2\) предикатів, тому таблиці істинності з\(4\) рядками буде достатньо. Заповніть відсутні записи в таблиці істинності і визначте, чи є твердження рівнозначними.
| \(A\) | \(B\) | \(A ∨ B\) | \(A ∨ (¬A ∧ B)\) |
|---|---|---|---|
| \ (A\) ">\(T\) | \ (B\) ">\(T\) | \ (A ∨ B\) "> | \ (A ∨ (¬A B)\) "> |
| \ (A\) ">\(T\) | \ (B\) ">\(\phi\) | \ (A ∨ B\) "> | \ (A ∨ (¬A B)\) "> |
| \ (A\) ">\(\phi\) | \ (B\) ">\(T\) | \ (A ∨ B\) "> | \ (A ∨ (¬A B)\) "> |
| \ (A\) ">\(\phi\) | \ (B\) ">\(\phi\) | \ (A ∨ B\) "> | \ (A ∨ (¬A B)\) "> |
Можна, в принципі, перевірити всі логічні еквівалентності, заповнивши таблиці істинності. Дійсно, у вправах для цього розділу ми попросимо вас розробити певний об'єкт при цьому завданні. Хоча ця діяльність може бути дещо цікавою, і багато хто з моїх студентів хочуть заповнення таблиць істини, щоб бути значною частиною їх середньострокового іспиту, ви, ймовірно, врешті-решт прийшли, щоб знайти його дещо стомлюючим. Трохи більш зрілий підхід до логічних еквівалентів полягає в наступному: використовуйте набір основних еквівалентів - які самі можуть бути перевірені за допомогою таблиць істинності - як основні правила або закони логічної еквівалентності, і розробити стратегію перетворення одного речення в інше, використовуючи ці правила. Цей процес буде відчувати себе дуже звичним, це як «робити» алгебру, але правила, які дозволяється використовувати, тонко відрізняються.
По-перше, у нас є комутативні закони, по одному для кон'юнкції та диз'юнкції. Варто зазначити, що не існує комутативного закону для імплікації.
Комутативна властивість кон'юнкції говорить про це\(A∧B \cong B ∧A\). Це цілком очевидне твердження з точки зору лінгвістики. Звичайно, це те ж саме, щоб сказати «погода холодна і сніжна», як це сказати «погода сніжна і холодна». Ця комутативна властивість також зрозуміла з точки зору цифрових логічних схем.
Комутативна властивість диз'юнкцій однаково прозора з точки зору принципової схеми.
Асоціативні закони також мають щось спільне з тим, які операції замовлення виконуються. Можна подумати про різницю в наступних термінях: Комутативні властивості включають просторовий або фізичний порядок, а асоціативні властивості включають часовий порядок. Асоціативний закон додавання може бути використаний, щоб сказати, що ми отримаємо той самий результат, якщо ми додамо\(2\) і\(3\) спочатку\(4\), потім додаємо, або якщо ми додамо\(2\) до суми\(3\) і\(4\) (тобто\((2+3)+4\) це те саме, що і\(2+ (3+4)\).) Зверніть увагу, що фізично цифри знаходяться в тому ж порядку (\(2\)\(3\)потім\(4\)) в обох виразах, але дужки вказують пріоритет при оцінці знаків плюса.
Асоціативний закон кон'юнкції стверджує, що\(A∧(B ∧C) \cong (A∧B)∧C\). У візуальному плані це означає, що наступні дві схеми рівнозначні.
Про це говорить асоціативний закон диз'юнкції\(A∨(B ∨ C) \cong (A∨B)∨ C\). Візуально це виглядає так:
У ситуації, коли асоціативність і комунітативність стосуються символи, що беруть участь, можуть з'являтися в будь-якому порядку і з будь-якими розумними дужками. Скільки різних способів можна\(2 + 3 + 4\) виражати суму? Враховуйте лише вираз, які повністю укладені в дужки.
Наступним типом основних логічних еквівалентів, які ми розглянемо, є так звані розподільні закони. Розподільні закони передбачають взаємодію двох операцій, коли ми розподіляємо множення на суму, ми фактично замінюємо один екземпляр операнда і асоційованого оператора двома екземплярами, як показано нижче.
Логічні оператори і ∨ кожен розподіляють по іншому. Таким чином, ми маємо розподільний закон кон'юнкції над диз'юнкцією, який виражається в еквівалентності\(A ∧ (B ∨ C) \cong (A ∧ B) ∨ (A ∧ C)\) і в наступній цифровій логічній схемі.
Ми також маємо розподільний закон диз'юнкції над кон'юнкцією, який задається еквівалентністю\(A ∨ (B ∧ C) \cong (A ∨ B) ∧ (A ∨ C)\) та на схемі принципу:
Традиційно закони, які ми щойно заявили, називатимуться ліво-розподільними законами, і ми також повинні констатувати, що існують закони, що застосовуються праворозподільні закони. Оскільки в нинішніх умовах ми вже говорили, що комутативний закон діє, це насправді не потрібно.
Викладіть правильні варіанти розподільних законів.
Наступний набір законів, які ми розглянемо, походять від спроби з'ясувати, що розподіл знака мінус над сумою\((−(x + y) = −x + −y)\) має відповідати в булевій алгебрі. Спочатку рум'яна, можна припустити, що аналогічна річ в булевій алгебрі буде щось на зразок\(¬(A∧B) \cong ¬A∧¬B\), але ми можемо легко відхилити це, дивлячись на таблицю істинності.
| \(A\) | \(B\) | \(¬(A ∧ B)\) | \(¬A ∧ ¬B\) |
|---|---|---|---|
| \ (A\) ">\(T\) | \ (B\) ">\(T\) | \ (¬ (A B)\) ">\(\phi\) | \ (¬А ¬Б\) ">\(\phi\) |
| \ (A\) ">\(T\) | \ (B\) ">\(\phi\) | \ (¬ (A B)\) ">\(T\) | \ (¬А ¬Б\) ">\(\phi\) |
| \ (A\) ">\(\phi\) | \ (B\) ">\(T\) | \ (¬ (A B)\) ">\(T\) | \ (¬А ¬Б\) ">\(\phi\) |
| \ (A\) ">\(\phi\) | \ (B\) ">\(\phi\) | \ (¬ (A B)\) ">\(T\) | \ (¬А ¬Б\) ">\(T\) |
Те, що насправді працює, - це набір правил, відомих як закони DeMorgan, які в основному говорять про те, що ви розподіляєте негативний знак, але ви також повинні змінити оператора. Як логічні еквіваленти, закони ДеМоргана є
\(¬(A ∧ B) \cong ¬A ∨ ¬B\)
і
\ (¬ (A سB)\ конг ¬А ¬Б.)
У звичайній арифметиці існує два поняття «зворотне». Негативне число відоме як його адитивне обернене, а зворотне число - його мультиплікативний зворотний. Ці поняття призводять до пари рівнянь,
\(x + −x = 0\)
і
\(x · \dfrac{1}{x} = 1.\)
Булева алгебра має лише одне «обернене» поняття, заперечення присудка (тобто логічне заперечення), але рівняння вище мають аналоги, як\(0\) і символи і\(1\) які з'являються в них. Спочатку розглянемо булеве вираз\(A ∨ ¬A\). Це логічне або твердження і його повна протилежність; коли одне істинне, інше є помилковим і навпаки. Але,\(A ∨ ¬A\) диз'юнкція, завжди вірна! Ми використовуємо символ\(t\) (який розшифровується як тавтологія) для представлення складного речення, значення істинності якого завжди вірно. А тавтологія (\(t\)) - це
Булева алгебра щось на зразок нуля (\(0\)) - це арифметика. Подібне мислення про булеве вираження\(A ∧ ¬A\) призводить до визначення символу\(c\) (що означає протиріччя), щоб представляти речення, яке завжди є помилковим. Правила, які ми обговорювали, відомі як закони комплементарності:
\(A ∨ ¬A \cong t\)і\(A ∧ ¬A \cong c\)
Тепер, коли у нас є спеціальні логічні речення, представлені\(t\) і\(c\) ми можемо представити так звані закони ідентичності,\(A ∧ t \cong A\) і\(A ∨ c \cong A\). Якщо ви «і» твердження з чимось, що завжди вірно, ця нова сполука має точно такі ж значення істини, що і оригінал. Якщо ви «або» твердження з чимось, що завжди є помилковим, нове складне твердження також не змінюється від оригіналу. Таким чином, виконання з'єднання з тавтологією не має ніякого ефекту - ніби як множення на\(1\). Виконання диз'юнкції з протиріччям також не має ефекту — це дещо схоже на додавання\(0\).
Число\(0\) має особливу властивість:\(0 · x = 0\) являє собою рівняння, яке тримається незалежно від того, що\(x\) є. Це відоме як властивість домінування. Зверніть увагу, що не існує правила домінування, яке передбачає\(1\). На логічній стороні, обидва символи\(t\) і\(c\) мають відповідні правила домінування.
\(A ∨ t \cong t\)і\(A ∧ c \cong c\)
У математиці слово ідемпотент використовується для опису ситуацій, коли сили речі рівні з цією річчю. Наприклад, тому що кожна сила\(1\) є\(1\), ми говоримо, що\(1\) це ідемпотент. Обидві логічні операції мають відносини ідемпотенції, які просто завжди працюють (незалежно від операнда). У звичайній алгебрі ідемпотенти дуже рідкісні (\(0\)і\(1\) єдині, які спадають на думку), але в булевій алгебрі кожен твердження еквівалентний його квадрату - де квадрат\(A\) може бути інтерпретований як\(A ∧ A\) або як\(A ∨ A\).
\(A ∨ A \cong A\)і\(A ∧ A \cong A\)
Є кілька властивостей логічного оператора заперечення, які слід вказати, хоча, ймовірно, вони здаються самоочевидними. Якщо ви формуєте заперечення заперечення, ви повертаєтеся до того ж самого, що і оригінал; також символи\(c\) і\(t\) є запереченням один одного.
\(¬(¬A) \cong A\)і\(¬t \cong c\)
Нарешті, слід згадати дійсно дивну властивість, звану поглинанням, яка стверджує, що вирази\(A∧(A∨B)\) і насправді\(A∨(A∧B)\) не мають нічого спільного з\(B\) взагалі! Обидва попередні твердження еквівалентні\(A\).
\(A ∧ (A ∨ B) \cong A\)і\(A ∨ (A ∧ B) \cong A\)
У таблиці 2.3.1 ми зібрали всі ці основні логічні еквіваленти в одному місці.
| Таблиця 2.3.1: Основні логічні еквіваленти. | |||
|---|---|---|---|
| Кон'юнктивна версія | диз'юнктивна версія | Алгебраїчний аналоговий | |
| Комутативні закони | \(A∧B≅B∧A\) | \(A∨B≅B∨A\) | \(2+3=3+2\) |
| Асоціативні закони | \(A∧(B∧C)A∧(B∧C) ≅(A∧B)∧C\) | \(A∨(B∨C)A∨(B∨C) ≅(A∨B)∨C\) | \(2+(3+4)2+(3+4) =(2+3)+4\) |
| Закони про розподіл | \(A∧(B∨C)≅A∧(B∨C)≅ \\(A∧B)∨(A∧C)\) | \(A∨(B∧C) ≅ \\ (A∨B)∧(A∨C)\) | \(2⋅(3+4)2⋅(3+4) =(2⋅3+2⋅4)\) |
| Закони ДеМорган | \(¬(A∧B)¬(A∧B) ≅¬A∨¬B\) | \(¬(A∨B)¬(A∨B) ≅¬A∧¬B\) | \(\text{none}\) |
| Подвійне заперечення | \(¬(¬A)≅A\) | \(\text{same}\) | \(−(−2)=2\) |
| взаємодоповнюваність | \(A∧¬A≅c\) | \(A∨¬A≅t\) | \(2+(−2)=0\) |
| Закони ідентичності | \(A∧t≅A\) | \(A∨c≅A\) | \(7+0=7\) |
| Домінування | \(A∧c≅c\) | \(A∨t≅t\) | \(7⋅0=0\) |
| Ідемпотенція | \(A∧A≅A\) | \(A∨A≅A\) | \(1⋅1=1\) |
| Поглинання | \(A∧(A∨B)≅A\) | \(A∨(A∧B)≅A\) | \(\text{none}\) |
Вправи:
Існують\(3\) операції, що використовуються в базовій алгебрі (додавання, множення та зведення в ступінь), і, таким чином, існують потенційно\(6\) різні закони розподілу. Викладіть всі\(6\) «закони» і визначте\(2\), які насправді дійсні. (Як приклад, розподільний закон додавання над множенням буде виглядати так\(x + (y · z) = (x + y) · (x + z)\), що це не один з істинних.)
Використовуйте таблиці істинності для перевірки або спростування наступних логічних еквівалентів.
- \((A ∧ B) ∨ B \cong (A ∨ B) ∧ B\)
- \(A ∧ (B ∨ ¬A) \cong A ∧ B\)
- \((A ∧ ¬B) ∨ (¬A ∧ ¬B) \cong (A ∨ ¬B) ∧ (¬A ∨ ¬B)\)
- Закони поглинання.
Намалюйте пари пов'язаних цифрових логічних схем, які ілюструють закони DeMorgan.
Знайдіть заперечення кожного з наступних і максимально спростіть.
\((A ∨ B) \iff C\)
\((A ∨ B) \implies (A ∧ B)\)
Оскільки умовне речення еквівалентно певній диз'юнкції, а оскільки закон ДеМорган говорить нам, що заперечення диз'юнкції є сполучником, випливає, що заперечення умовного є сполучником. Знайдіть заперечення (заперечення речення часто називають його «запереченням») для кожного з наступних умов.
- «Якщо ви курите, ви отримаєте рак легенів».
- «Якщо речовина блищить, це не обов'язково золото».
- «Якщо є дим, також повинен бути вогонь».
- «Якщо число у квадраті, результат позитивний».
- «Якщо матриця квадратна, вона обертається».
Так звана «етика взаємності» - це ідея, яка виникла в багатьох світових релігіях і філософіях. Нижче наведені твердження етики з декількох джерел. Обговоріть їх логічні значення і визначте, які (якщо такі є) логічно еквівалентні.
- «Не слід поводитися по відношенню до інших таким чином, який є несприятливим для себе». Менцій Vii.A.4 (Індуїзм)
- «Ніхто з вас [по-справжньому] не вірить, поки він не побажає своєму братові те, що він бажає для себе». Номер 13 імама «Сорок хадисів Аль-Нававі». (Іслам)
- «І як ви хочете, щоб люди робили вам, так само робіть і їм». Лука 6:31, Переклад І. Огієнка. (Християнство)
- «Те, що ненависне вам, не робіть своєму ближньому. Це закон: все інше - коментар». Талмуд, Шабат 31а. (Іудаїзм)
- «І це нікому не шкодить, роби те, що хочеш» (Wicca)
- «Те, що ви б уникнути страждань себе, прагнете не нав'язувати іншим». (грецький філософ Епіктет — перше століття н.е.)
- «Не робіть іншим так, як ви очікуєте, що вони повинні зробити з вами. Їх смаки можуть бути не однаковими». (ірландський драматург Джордж Бернард Шоу —\(20^{\text{th}}\) століття н.е.)
Ви зіткнетеся з двома вихідцями з землі лицарів і валів. Заповніть пояснення для кожного рядка доказів своєї особистості.
- Наташа каже: «Борис - валет». Борис каже: «Ми з Наташею лицарі».
Претензія: Наташа - лицар, а Борис - валет.
Доказ: Якщо Наташа - валет, то Борис - лицар.
Якщо Борис - лицар, то Наташа - лицар.
Тому якщо Наташа - валет, то Наташа - лицар.
Звідси Наташа - лицар.
Тому Борис - валет.
Q.E.D.
- Бонапарт каже: «Я лицар, а Веллінгтон - валет». Веллінгтон каже: «Я б сказав вам, що Б - це лицар».
Претензія: Бонапарт - лицар, а Веллінгтон - валет.
Доказ: Або Веллінгтон - валет, або Веллінгтон - лицар.
Якщо Веллінгтон - лицар, то випливає, що Бонапарт - лицар.
Якщо Бонапарт - лицар, то Веллінгтон - валет.
Отже, якщо Веллінгтон - лицар, то Веллінгтон - валет (що неможливо!)
Таким чином, Веллінгтон - валет.
Оскільки Веллінгтон - валет, його твердження «Я б сказав вам, що Бонапарт - лицар» є помилковим.
Тож Веллінгтон насправді сказав би нам, що Бонапарт - це валет.
Оскільки Веллінгтон - валет, ми робимо висновок, що Бонапарт - лицар.
Таким чином, Бонапарт - лицар, а Веллінгтон - валет (як стверджується).
Q.E.D.