ЗАКОНИ МОРГАНА

Л очі Моргана правила виведення , що використовуються в логіці висловлювань, які встановлюють , що в результаті відмови в диз'юнкцію і кон'юнкцію пропозицій або пропозіціональних змінних. Ці закони були визначені математиком Августом Де Морганом.

Закони Моргана є дуже корисним інструментом для демонстрації обгрунтованості математичних міркувань. Пізніше вони були узагальнені в рамках концепції множин математиком Джорджем Булом.

Це узагальнення, зроблене Булом, повністю еквівалентне початковим законам Моргана, але воно розроблене спеціально для множин, а не для пропозицій. Це узагальнення також відоме як закони Моргана.

Огляд логіки пропозицій

Перш ніж розглянути, що конкретно є законами Моргана, і як вони використовуються, корисно згадати деякі основні поняття логіки пропозицій. (Детальніше див. Статтю про логіку пропозицій).

У царині математичної (або пропозиційної) логіки висновок - це висновок, який видається із сукупності передумов або гіпотез. Цей висновок разом із вищезгаданими передумовами породжує те, що відомо як математичне міркування.

Такі міркування повинні бути доказовими або спростованими; тобто не всі умовиводи або висновки в математичному міркуванні є справедливими.

Помилковість

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

Логіка пропозицій точно відповідає за розробку та надання методів, за допомогою яких без будь-якої неоднозначності математичні міркування можуть бути перевірені або спростовані; тобто зробити висновок дійсним з приміщень. Ці методи відомі як правила висновку, до яких належать закони Моргана.

Пропозиції

Істотними елементами логіки пропозицій є пропозиції. Пропозиції - це твердження, які можна стверджувати, що вони дійсні чи ні, але водночас не можуть бути правдивими чи хибними. У цьому питанні не повинно бути ніякої неоднозначності.

Так само, як числа можна поєднувати за допомогою операцій додавання, віднімання, множення і ділення, пропозиціями можна керувати за допомогою відомих логічних сполучників (або сполучників): заперечення (¬, «не»), диз'юнкції (V , "Або"), сполучники (Ʌ, "і"), умовні (→, "якщо…, то …") і двозначні (↔, "якщо і тільки якщо").

Для більш загальної роботи замість розгляду конкретних пропозицій розглядаються змінні пропозиції, які представляють будь-які пропозиції, і їх зазвичай позначають малими літерами p, q, r, s тощо.

Формула пропозицій - це комбінація змінних пропозицій за допомогою деяких логічних сполучників. Іншими словами, це склад змінних пропозицій. Зазвичай вони позначаються грецькими літерами.

Кажуть, що формула пропозицій логічно передбачає іншу, коли остання істинна кожен раз, коли перша правда. Це позначається:

Коли логічне значення між двома пропозиційними формулами є зворотним - тобто коли попереднє значення також є дійсним у протилежному сенсі - формули, як кажуть, є логічно еквівалентними, і вони позначаються через

Логічна еквівалентність є різновидом рівності між формулами пропозицій і дозволяє замінити одну, коли це необхідно.

Закони Моргана складаються з двох логічних відповідностей між двома пропозиційними формами, а саме:

Ці закони дозволяють відокремлювати заперечення диз'юнкції чи кон'юнкції, як заперечення змінних.

Перший можна прочитати так: заперечення диз'юнкції дорівнює сполучнику негативів. А друге читається так: заперечення кон'юнкції - це диз'юнкція негативів.

Іншими словами, заперечення диз'юнкції двох пропозиційних змінних рівносильно поєднанню заперечень обох змінних. Так само заперечення сполучення двох змінних пропозицій рівносильно диз'юнкції заперечень обох змінних.

Як було сказано раніше, заміна цієї логічної еквівалентності допомагає довести важливі результати разом з іншими існуючими правилами висновку. За допомогою них ви можете спростити безліч формул пропозицій, щоб вони були більш корисними для роботи.

Далі наведено приклад математичного доказу з використанням правил умовиводу, включаючи закони Моргана. Зокрема, показано, що формула:

Він еквівалентний:

Останнє простіше зрозуміти і розвинути.

Демонстрація

Варто зазначити, що обгрунтованість законів Моргана може бути продемонстрована математично. Один із способів - порівняння таблиць істинності.

Набори

Ті ж правила умовиводу і поняття логіки, що застосовуються до пропозицій, також можуть бути розроблені, розглядаючи множини. Це те, що відоме як булева алгебра, після математика Джорджа Була.

Для розмежування випадків необхідно змінити позначення і перенести на множини, усі вже бачені поняття логіки пропозицій.

Набір - це сукупність предметів. Набори позначаються великими літерами A, B, C, X,…, а елементи набору позначаються малими літерами a, b, c, x тощо. Коли елемент a належить множині X, він позначається:

Коли він не належить до X, позначення:

Спосіб представлення наборів - розміщення їх елементів всередині брекетів. Наприклад, набір натуральних чисел представлений:

Набори можна також представити без написання явного переліку їх елементів. Вони можуть бути виражені у вигляді {:}. Товста кишка читається "така, що". Зліва від двох точок розміщується змінна, що представляє елементи множини, а праворуч розміщується властивість або умова, яким вони задовольняються. Це:

Наприклад, безліч цілих чисел, що перевищують -4, можна виразити як:

Або рівнозначно і скорочено:

Аналогічно, наступні вирази представляють набори непарних і парних чисел відповідно:

Союз, перехрестя та доповнення множин

Далі ми побачимо аналоги логічних сполучників у випадку множин, які є частиною основних операцій між множинами.

Союз та перехрестя

Об'єднання та перетин множин визначаються відповідно таким чином:

Наприклад, розглянемо набори:

Отже, ви повинні:

Доповнення

Доповнення набору формується елементами, які не належать до зазначеного набору (того ж типу, який представляє оригінал). Доповнення множини A позначається:

Наприклад, у межах натуральних чисел доповненням набору парних чисел є непарні числа, і навпаки.

Щоб визначити доповнення набору, універсальний або основний набір розглянутих елементів повинен бути зрозумілий з самого початку. Наприклад, неоднаково розглядати доповнення множини над натуральними числами, як над раціональними числами.

Наступна таблиця показує взаємозв’язок або аналогію, що існує між операціями над раніше визначеними множинами та сполучниками логіки пропозицій: