Імплікація та логічне слідування

Ще одна важлива зв'язка \(A\to B\), називається імплікацією. Вона хибна тільки для комбінації \(\T\to \F\), що інтерпретується як "з істини не можна отримати брехню". В інших випадках вона істинна:

З істини "слід" істина, тому \(\T \to \T\) це \(\T\). З брехні можна вивести будь-що, тому \(\F \to \F\) і \(\F \to \T\) вважаються істинними. Аргументи імплікації називаються посилкою і наслідком.

Для висловлювань інтерпретація імплікації як логічного слідування виглядає дивною.
Так ((2 \ cdot 2 = 4) ~ \ to ~ ~ \) "Сонце це зірка" - справжня формула, хоча посилка і слідство між собою ні як не пов'язані.

Найкраща ситуація для предикатів. Наприклад, в арифметиці за будь-якого \(x\) істинно твердження: "якщо \(x 2) \to (x

Логічне слідування

Нехай \(P=P(A,B(x). )\) і \(Q=Q(A,C(x,y). )\) формули, що залежать від висловлювань та предикатів. Ці формули рівні \(\T\) або \(\F\) при певних значеннях, що входять до них елементарних тверджень.

Наприклад: \[ A ~\Rightarrow~ A\vee B,~~~~~~~~~~~~~~~~A\,\&\,B ~\Rightarrow~ A. \] Так, перше слідування означає, що якщо \(A\) істинно, то для будь-якого \(B\), диз'юнкція \(A\vee B\) буде істинною. Справедлива теорема:

Наприклад, формула \(A \to (A\vee B)\) - загальнозначуща. Імплікація \(P\to Q\) (бінарна функція), на відміну від слідування \(P\Rightarrow Q\), визначена і коли \(P\) хибно. При логічному ж прямуванні мається на увазі істинність посилки. Зокрема, справедливо правило modus ponens:

означає, що якщо обидві посилки \(P\) і \(P\to Q\) істинні, то істинна формула \(Q\). Якщо \(P\equiv\F\), то \(Q\) - це \(\T\) або \(\F\).Варто перевірити загальнозначимість формули \(P\,\&\,(P\to Q) \to Q\).

Слідство має транзитивністю: \[якщо~P\Rightarrow X~ і~X\Rightarrow Q,~то~P\Rightarrow Q.\]

Слідство у випадку не симетрично. Так, \(A ~\Rightarrow~ A\vee B\) ( справедливо тільки в один бік і з \(A\vee B\) не слід \(A\) (тому \(A\vee B \to A\) ) не тавтологія. Тим не менш, існують і прямування в обидві сторони: \(\Leftrightarrow\). або двостороннє правило: \[ A\,\&\, B ~\Leftrightarrow A,~~ B. \] Вправо, це \(A\,\&\, B\Rightarrow A\), вліво воно означає: коли обидві посилки (A) і (B) істинні, істинна та їх кон'юнкція.

Двосторонній висновок \(P\Leftrightarrow Q\) аналогічний функції еквівалентності \(P\equiv Q\). Твердження: "якщо \(P\), то \(Q\) і навпаки", "\(P\) тоді і тільки тодіколи \(Q\)" означають \(P\Leftrightarrow Q\).

Якщо \(P\Rightarrow X\Rightarrow Q\), то \(P\) називають достатнім умовою, а (Q) - необхідним умовою для (X). Коли необхідне і достатнє умови збігаються, то вони збігаються і з (X): (Pequiv Qequiv X).

Прямий логічний висновок

Більшість міркувань у математиці можна поділити на прямі та зворотні. Отримання по ((\bf MP)) з двох формул (P) і (P\to Q) третьої формули (Q) є прикладом прямого логічного дотримання. Ще одне, потужніше, правило прямого слідування називається резолюцією: \[ ()~~~~~~~~~~~~~~~P\vee S ,~~~ \neg P \vee Q ~~~~~\Rightarrow~~~~~S\vee Q . \] Дійсно: оскільки \(P\) і \(\neg P\) не можуть бути одночасно істинними, а посилки \(P \vee\, S\) та \(\neg P\vee Q \) істинні за визначенням, то істинно \(S\) або \(Q\).Якщо \(S\) - хибно, виходить окремий випадок \(()\). Варто також перевірити, що \((P\vee S) \,\&\,(\neg P \vee Q) ~\to~S\vee Q\) - це тавтологія.

Варіантом резолюції є метод ланцюжків імплікацій: \[ P\to S,~~~S\to Q ~~~~~\Rightarrow~~~~~ P\to Q. \] Якщо в кожній формулі висловити імплікацію через диз'юнкцію (замінити \(P\to S \) на \(\neg P\vee S\)), то вийде слідування, що збігається з резолюцією точністю до перепозначень: \[\neg P \vee \underline,~~\neg \underline \vee Q~~\overset< \Rightarrow>~~ \neg P\vee Q\].

Метод розбору випадків - Ще один приклад прямих міркувань. Нехай із (P) необхідно вивести (Q). Розглянемо кілька тверджень, наприклад, \(P_1\) і \(P_2\), об'єднання яких дорівнює \(P\). Кажуть, що (P_1) і (P_2) покривають всі можливі випадки. Якщо з кожного затвердження \(P_i\) випливає \(Q\), то воно випливає і з \(P=P_1\vee P_2\): \[ P_1\vee P_2,~~~P_1\to Q,~~~ P_2\to Q ~~~~~\Rightarrow~~~~Q. \] \(\lhd\) Доведемо це правило за допомогою резолюції: \[ \underline\vee P_2,~~~\neg \underline\vee Q,~~~\neg P_2\vee Q ~~~~~\overset <\Rightarrow>~~~~~~ \underline<\underline>\vee Q,~~~\neg \underline<\underline>\vee Q~~~~~\overset<\Rightarrow>~~~~Q. \] Формула та її заперечення підкреслені. У першому висновку це \(P_1\) і з формул \(P_1\vee P_2\) і \(\neg P_1\vee Q\) випливає \(P_2\vee Q\). У другому висновку формула та її заперечення — це \(P_2\), а резолюція призводить до \(Q\vee Q~\Leftrightarrow~ Q\). \(\square\)

Наведемо як неформальний приклад просту теорему:

\(\lhd\) Розглянемо два випадки: \(P_1: \mathrm(x)\,\&\,\mathrm(y)\) та \(P_2: \mathrm(x)\,\&\,\mathrm (y) \). За умовою теореми \(P_1\vee P_2\) є посилкою.
За визначенням \(\mathrm(x)\) і \(P_1\), існують такі \(n,m\in \mathbb N\), що \(x=2n\) і \(y=2m\). Тоді \(x+y=2(n+m)\) - парно (\(Q\)).
У другому випадку \(P_2:\) \(x=2n+1\), \(y=2m+1\) та \(x+y=2(n+m+1)\) також парно (знов \ (Q \)). Тому теорема істинна. \(\square\)

Доказ протилежного

Доказ протилежного - Винятково важливий зворотний метод. У ньому, замість прямого укладання \(P ~\Rightarrow~ Q\), показують, що \(P\) і заперечення \ (Q \) суперечливі, тобто. з них випливає завжди хибне твердження, подібне \(A\,\&\,\neg Aequiv \F\):

\[ P~\&~\neg Q ~\to~~\F~~~~~~~~~\Leftrightarrow~~~~~~~~~~P ~\to~ Q. \] На малюнку область істинності формули \(P\) є підмножиною області істинності \(Q\), тому заперечення \(Q\) (сірий колір) і \(P\) не перетинаються (\(P\,\&\,\neg Q\) equiv \F\)). Нескладно бачити, що \(\neg (P\, \&\, \neg Q) ~ equiv ~ P to Q). Дамо також формальний доказ методу від протилежного.

\(\lhd\) Нехай \(P\,\&\,\neg Q~\to~\F\) істинно. Тоді за визначенням імплікації \(P\,\&\,\neg Q\) хибно. Для \(\) можливо 3 варіанти \(\<\F,\,\F\>\), \(\<\F,\,\T\>\) і \(\<\T,\, \T>>). Для них \(P\to Q\) істинно. Аналогічно для логічного прямування у зворотний бік. \(\square\)

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

Непрямий доказ - Це окремий випадок методу від протилежного. У ньому, замість \(P \to Q\), з'ясовується, що \(\neg Q \to \neg P\). Якщо це так, то означає справедливо і \(P \to Q\): \[ \neg Q ~\to~ \neg P ~~~~~~~~~\Leftrightarrow~~~~~~~~~~~ P ~\to~ Q. \] Фактично \(\neg Q\to \neg P\) дорівнює \(Q\vee \neg P\), що еквівалентно \(P\to Q\).

Подібний метод виведення може здатися тривіальною тавтологією. Однак, це не так. Насправді беруть заперечення \(\neg Q\). З цієї формули логічно виводять (іноді досить складним чином) формулу (neg P). Якщо побудований висновок \(\neg Q~\Rightarrow~\neg P\), то, як ми бачили вище, формула \(\neg Q\to \neg P\) виявляється тавтологією. Саме цьому етапі, з допомогою непрямого докази, виводиться \(P\to Q\). Нарешті, якщо посилка \(P\) вважається істинною, то за правилом \(()\) з \(P\) і \(P\to Q\) виводиться \(Q\).

Класичний приклад міркування від протилежного, доказ, що

\(\lhd\) В якості \(P\) виступають стандартні аксіоми арифметики.
Необхідно довести \(Q:~\sqrt\neq n/m\), де \(n/m\) нескоротна дріб.
Нехай \(\neg Q: ~ sqrt = n / m). Тоді \(n^2=2m^2\) і отже \(n\) - парно, тобто. \ (n = 2k \).
Але тоді \((2k)^2 = 2m^2\) чи \(m^2 = 2k^2\), тобто. \(m\) - також парно, а це суперечить нескоротності дробу \(n/m\).
Тому (Q) істинно. \(\square\)

Формули та закони логіки

На вступному уроці, присвяченому основ математичної логікиМи познайомилися з базовими поняттями цього розділу математики, і зараз тема отримує закономірне продовження. Крім нового теоретичного, а точніше навіть не теоретичного – а загальноосвітнього матеріалу на нас чекають практичні завдання, і тому якщо ви зайшли на дану сторінку з пошуковика та/або погано орієнтуєтесь у матеріалі, то, будь ласка, пройдіть за вищезгаданим посиланням і почніть з попередньої статті. Крім того, для практики нам знадобиться 5 таблиць істинності логічних операційякі я наполегливо рекомендую переписати від руки.

НЕ запам'ятати, НЕ роздрукувати, а саме ще раз осмислити та власноруч переписати на папір – щоб вони були перед очима:

- Таблиця НЕ;
- Таблиця І;
- Таблиця АБО;
- Імплікаційна таблиця;
- Таблиця еквіваленції.

Це дуже важливо. В принципі, їх було б зручно занумерувати "Таблиця 1", "Таблиця 2" і т.д., але я неодноразово підкреслював вада такого підходу – як кажуть, в одному джерелі таблиця виявиться першою, а в іншому – сто першою. Тому використовуватимемо «натуральні» назви. Продовжуємо:

Насправді, з поняттям логічної формули ви вже знайомі. Наведу стандартне, але досить дотепне визначення: формулами алгебри висловлювань називаються:

1) будь-які елементарні (прості) висловлювання;

2) якщо і – формули, то формулами також є вирази виду
.

Жодних інших формул немає.

Зокрема формулою є будь-яка логічна операція, наприклад, логічне множення . Зверніть увагу на другий пункт – він дозволяє рекурсивним чином «створити» скільки завгодно довгу формулу. Оскільки – формули, то – також формула; оскільки і – формули, то – теж формула тощо. буд. Будь-яке елементарне висловлювання (Знову ж згідно з визначенням) може входити до формули неодноразово.

Формулою не є, наприклад, запис - і тут простежується очевидна аналогія з «сміттям алгебри» , з якого не зрозуміло - чи потрібно числа складати або множити.

Логічну формулу можна розглядати як логічну функцію. Запишемо у функціональному вигляді ту саму кон'юнкцію:

Елементарні висловлювання й у разі грають роль аргументів (незалежних змінних), які у класичної логіці можуть набувати 2 значення: істина або брехня. Далі для зручності я іноді називатиму прості висловлювання змінними.

Таблиця, що описує логічну формулу (функцію) називається, як було озвучено, таблицею істинності. Будь ласка – знайома картинка:

Принцип формування таблиці істинності такий: «на вході» слід перерахувати усі можливі комбінації істини та брехні, які можуть приймати елементарні висловлювання (аргументи). В даному випадку до формули входять два висловлювання, і неважко з'ясувати, що таких комбінацій чотири. «На виході» отримуємо відповідні логічні значення всієї формули (функції).

Треба сказати, що «вихід» тут вийшов «одного кроку», але у випадку логічна формула є складнішою. І в таких «непростих випадках» потрібно дотримуватися порядок виконання логічних операцій:

- Насамперед виконується заперечення;
– у другу чергу – кон'юнкція;
- Потім - диз'юнкція;
- Потім імплікація;
- І, нарешті, нижчий пріоритет має еквівалентність.

Приміром, запис передбачає, що треба здійснити логічне множення , та був – логічне складання: . Прямо як у «звичайній» алгебрі – «спочатку множимо, та був складаємо».

Порядок дій можна змінити звичним способом – дужками:
– тут насамперед виконується диз'юнкція і лише потім «сильніша» операція.

Напевно, всі розуміють, але на всякого пожежника: і – це дві різні формули! (як у формальному, так і змістовному плані)

Складемо таблицю істинності для формули. До цієї формули входять два елементарні висловлювання і «на вході» нам потрібно перерахувати всі можливі комбінації одиниць та нулів. Щоб уникнути плутанини та різночитань, домовимося перераховувати комбінації. суворо у такому порядку (який я, власне, де-факто використовую із самого початку):

У формулу входять дві логічні операції, і відповідно до їхнього пріоритету, в першу чергу потрібно виконати заперечення висловлювання . Ну що ж, заперечуємо стовпець «пе» - одиниці перетворюємо на нулі, а нулі - на одиниці:

На другому кроці дивимося на стовпці та й застосовуємо до них операцію АБО.Трохи забігаючи вперед, скажу, що диз'юнкція перестановна (і – це одне й те саме), І тому стовпці можна аналізувати в звичному порядку - зліва направо. «Якщо два нулі – ставимо нуль, якщо хоча б одна одиниця – одиницю»:

Таблиця істинності побудована. А тепер згадаємо стару-добру імплікацію:

…Уважно-уважно дивимося на підсумкові колонки…. рівносильними або тотожними:

(три горизонтальні рисочки – це значок тотожності)

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

Сформулюємо загальне визначення: дві формули називаються рівносильними (тотожними)якщо вони приймають однакові значення при будь-якому наборі значень, що входять до цих формул змінних (Елементарних висловлювань). Також кажуть, що «Формули рівносильні, якщо збігаються їх таблиці істинності»але мені не дуже подобається ця фраза.

Скласти таблицю істинності для формули і переконатися у справедливості знайомого вам тотожності.

Ще раз повторимо порядок розв'язання задачі:

1) Так як у формулу входять дві змінні, то всього буде 4 можливі набори нулів та одиниць. Записуємо їх в обумовленому порядку.

2) Імплікації «слабші» за кон'юнкцію, але вони розташовуються в дужках. Заповнюємо стовпець, при цьому зручно використовувати таке прикладне міркування: «якщо з одиниці слідує нуль, то ставимо нуль, у всіх інших випадках – одиницю». Далі заповнюємо стовпець для імплікації, і при цьому, увага! - Стовпці і слід аналізувати «праворуч наліво»!

3) І на завершальному етапі заповнюємо підсумковий стовпець. А тут зручно міркувати так: "якщо в стовпцях і дві одиниці, то ставимо одиницю, у всіх інших випадках - нуль".

І, нарешті, звіряємось із таблицею істинності еквівалентності .

Основні рівносильності алгебри висловлювань

З двома з них ми тільки-но познайомилися, але ними справа, зрозуміло, не обмежується. Тотожностей досить багато і я перерахую найважливіші та найвідоміші з них:

Комутативність кон'юнкції та комутативність диз'юнкції

Комутативність - Це перестановочність:

Знайомі з 1-го класу правила: «Від перестановки множників (доданків) твір (сума) не змінюється». Але при всій здається елементарності цієї властивості, справедливо воно далеко не завжди, зокрема, некомутативним є множення матриць (У загальному випадку їх переставляти не можна), а векторний добуток векторів - Антикоммутативно (перестановка векторів спричиняє зміну знака).

І, крім того, тут знову хочу підкреслити формалізм математичної логіки. Так, наприклад, фрази «Студент склав іспит і випив» і «Студент випив і склав іспит» різні з змістовної точки зору, але невиразні з позицій формальної істинності.…Таких студентів знає кожен із нас, але з етичних міркувань ми не озвучуватимемо конкретних імен =)

Асоціативність логічного множення та додавання

Або якщо «по-шкільному» – поєднана властивість:

Дистрибутивні властивості

Зверніть увагу, що в 2-му випадку некоректно говорити про «розкриття дужок», у відомому сенсі тут «фікція» - адже їх можна прибрати взагалі: т. к. множення - це сильніша операція.

І знову ж таки – ці, здавалося б, «банальні» властивості виконуються далеко не у всіх алгебраїчних системах, і, більше того, вимагають доказів (про які ми дуже скоро поговоримо). До речі, другий дистрибутивний закон несправедливий навіть у нашій «звичайній» алгебрі. І справді:

Закон ідемопотентності

Прямо якийсь принцип здорової психіки: "я і я - це я", "я чи я - це теж я" =)

І відразу кілька схожих тотожностей:

...Мда, щось я навіть підзавіс ..., так і доктором філософії завтра можна прокинутися =)

Закон подвійного заперечення

Ну а тут уже напрошується приклад із російською мовою – всі чудово знають, що дві частки «не» означають «так». А для того, щоб посилити емоційне забарвлення заперечення нерідко використовують три «не»:
– навіть із крихітним доказом вийшло!

Закони поглинання

У правому тотожності дужки можна опустити.

Закони де Моргана

Припустимо, що суворий викладач (ім'я якого вам також відомо:)) ставить іспит, якщо – Студент відповів на 1-е запитання і – Студент відповів на друге запитання. Тоді висловлювання про те, що Студент не склав іспит, буде рівносильно твердженню – Студент не відповів на 1-е запитання або на 2-е питання.

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

Доведемо тотожність. Оскільки в нього входить єдине висловлювання, то «на вході» можливо лише два варіанти: одиниця або нуль. Далі приписуємо одиничний стовпець і застосовуємо до них правило І:

В результаті «на виході» отримано формулу, істинність якої збігається з істинністю висловлювання. Рівносильність доведена.

Так, цей доказ є примітивним (а хтось скаже, що й тупим), але типовий Викладач з матології витрясе за нього душу. Тому навіть до таких простих речей не варто ставитися зневажливо.

Тепер переконаємось, наприклад, у справедливості закону де Моргана.

Спочатку складемо таблицю істинності для лівої частини. Оскільки диз'юнкція знаходиться в дужках, то в першу чергу виконуємо саме її, після чого заперечуємо стовпець:

Далі складемо таблицю істинності для правої частини. Тут теж все прозоро – насамперед проводимо «сильніші» заперечення, потім застосовуємо до стовпців правило І:

Результати збіглися, таким чином, тотожність доведена.

Будь-яку рівносильність можна подати у вигляді тотожно істинної формули . Це означає, що ПРИ БУДЬ-ЯКОМУ вихідному наборі нулів і одиниць "на виході" виходить строго одиниця. І цьому дуже просте пояснення: оскільки таблиці істинності і збігаються, то, зрозуміло, вони еквівалентні. Поєднаємо, наприклад, еквіваленцією ліву та праву частину щойно доведеного тотожності де Моргана:

Довести такі рівносильності:

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

Продовжуємо знайомитись із законами логіки!

Так, абсолютно правильно - ми з ними вже працюємо:

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

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

Формула, яка набуває значення Брехня при будь-якому наборі значень змінних, що входять до неї, називається тотожно хибною формулою або протиріччям.

Фірмовий приклад протиріччя від давніх греків:
– жодне висловлювання може бути істинним і хибним одночасно.

«На виході» отримані виключно нулі, отже формула дійсно тотожна хибна.

Однак і будь-яка суперечність – це також закон логіки, зокрема:

Не можна охопити таку велику тему в одній-єдиній статті, і тому я обмежуся лише кількома законами:

Закон виключеного третього

- У класичній логіці будь-яке висловлювання істинно чи хибно і третього не дано. «Бути чи не бути» – ось у чому питання.

Самостійно складіть табличку істинності і переконайтеся, що це тотожно істинна формула.

Закон контрапозиції

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

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

Якщо істинна зворотна теорема , то з закону контрапозиції , справедлива і теорема, протилежна зворотній:

І знову повернемося до наших змістовних прикладів: для висловлювань - Число ділиться на 4, - Число ділиться на 2 справедливі пряма і протилежна теореми, але помилкові зворотна і протилежна зворотній теореми. Для «дорослої» формулювання теореми Піфагора істинні всі 4 «напрямки».

Закон силогізму

Теж класика жанру: «Усі дуби – дерева, всі дерева – рослини, отже, всі дуби – рослини».

Ну і тут знову хочеться відзначити формалізм математичної логіки: якщо наш суворий Викладач думає, що якийсь Студент є дубом, то з формального погляду даний Студент, безумовно, рослина =). Хоча, якщо замислитись, то може бути і з неформальною теж =)

Давайте на цій веселій ноті проведемо доказ. У цю формулу входять вже елементарні висловлювання, а отже, всього буде: різних комбінацій нулів та одиниць (Див. три лівих стовпця таблиці). Заодно, до речі, записав вам загальну формулу; з погляду комбінаторики, тут розміщення з повтореннями.

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

1) виконуємо імплікації та . Взагалі кажучи, можна одразу виконати і 3-ю імплікацію, але з нею зручніше (і припустимо!) розібратися трохи згодом;

2) до стовпців застосовуємо правило І;

3) ось тепер виконуємо;

4) і на завершальному кроці застосовуємо імплікацію до стовпців та .

Не соромтеся контролювати процес вказівним та середнім пальцем :))

З останнього стовпця, гадаю, все зрозуміло без коментарів:
, Що й потрібно було довести.

З'ясувати, чи буде законом логіки наступна формула:

Коротке рішення наприкінці уроку. Так, і мало не забув - давайте умовимося перераховувати вихідні набори нулів і одиниць у такому самому порядку, що й за доказу закону силогізму. Рядки звичайно, можна і переставити, але це дуже ускладнить звірку з моїм рішенням.

Перетворення логічних формул

Крім свого «логічного» призначення, рівносильності широко використовуються для перетворення та спрощення формул. Грубо кажучи, одну частину тотожності можна міняти іншу. Так, наприклад, якщо в логічній формулі вам зустрівся фрагмент, то за законом ідемпотентності замість нього можна (і потрібно) просто записати. Якщо ви бачите, то за законом поглинання спрощуйте запис до. І так далі.

Крім того, є ще одна важлива річ: тотожність справедлива не тільки для елементарних висловлювань, але й для довільних формул. Так, наприклад:

, де - будь-які (скільки завгодно складні) формули

Перетворимо, наприклад, складну імплікацію (1-е тотожність):

Далі застосуємо до дужки "складний" закон де Моргана, при цьому, в силу пріоритету операцій, саме закон, де :

Дужки можна прибрати, тому що всередині знаходиться «сильніша» кон'юнкція:

Далі напрошується використати «простий» закон де Моргана тощо.

Ну, а з комутативністю взагалі все просто – навіть позначати нічого не потрібно… Щось запал мені в душу закон силогізму:))

Таким чином, закон можна переписати і в більш вигадливому вигляді:

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

Як тренування спростимо формулу.

З чого розпочати? Насамперед, розібратися з порядком дій: тут заперечення застосоване до цілої дужки, яка «скріплена» з висловлюванням «трохи слабшою» кон'юнкцією. Фактично, маємо логічний твір двох множників: . З двох операцій, що залишилися, нижчим пріоритетом має імплікація, і тому вся формула має наступну структуру: .

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

(1) Використовуємо тотожність. А нашому випадку.

Потім зазвичай слідують «розбирання» з дужками. Спочатку все рішення, потім коментарі. Щоб не вийшло «олія масляна», використовуватиму значки «звичайної» рівності:

(2) До зовнішніх дужок застосовуємо закон де Моргана, де.

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

(4) В силу комутативності диз'юнкції міняємо місцями та . Дужки, що залишилися, теж прибираємо з озвученої вище причини.

(5) З огляду на комутативності диз'юнкції змінюємо місцями і , і навіть .

(6) Використовуємо закон ідемпотентності та закон виключеного третього

(7) Двічі використовуємо тотожність

Ось воно як… виявилося, що наша формула – теж істинна:

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

Напевно, всі звернули увагу на формалізм останніх перетворень, але краще вирішувати саме так! » На зразок небажано.

Пара завдань для закріплення матеріалу:

Виразити еквівалентність через заперечення, кон'юнкцію, диз'юнкцію та розкрити дужки

Акуратно проводимо перетворення відповідно до рівносильностей. Після цього буде не зайвим повернутися до параграфа про еквівалентності і знайти там фразу, яка відповідає отриманому результату ;-)

Спростити логічну формулу

Рішення з докладними коментарями дуже близько.

І на закінчення уроку невелике напуття для читачів, яким належить занурення в матлогіку. Даний предмет у мене був на 1-му курсі інституту, і в ході вивчення обчислення висловлювань, предикатів та інших «машин тюринга» я припускався принципової помилки – а саме, намагався. «підігнати» під математичну логіку неформальну основу. розуміння всієї стрункості формальної теорії, важливості «очевидних» доказів і т. д. Прийшло далеко не одразу. вищій алгебрі та деяким іншим предметам.

…Але щоб ви прочитали ці рядки, я таки підніс матеріал, скоріше у «шкільному» стилі – з численними змістовними прикладами!

Завдання 1. Рішення: Складемо таблицю істинності для формули :

(Докладні інструкції щодо заповнення таблиці знаходяться після умови завдання)
Отриманий результат збігається з еквіваленцією висловлювань і таким чином:

Завдання 2. Рішення: докази проведемо за допомогою таблиць істинності:

а) Двічі записуємо всі варіанти істини та брехні висловлювання та застосовуємо до стовпців операцію АБО:

Результат збігається із . Тотожність доведено

б) складемо таблицю істинності для лівої частини тотожності
. Спочатку до стовпців і застосовуємо операцію АБО, потім до стовпців і - операцію І:

Через війну істинність формули збіглася з істинністю висловлювання , в такий спосіб, тотожність доведено.

Завдання 3. Рішення: складемо таблицю істинності:

Висновок: дана формула не є тотожною істинною (законом логіки)

Завдання 4. Рішення:

(1) Використовуємо тотожність.
(2) Двічі застосовуємо тотожність.
(3) Використовуємо дистрибутивний закон, в даному випадку:
(квадратні дужки можна було не ставити - вони не змінюють порядок дій, але допомагають краще бачити ситуацію).
(4) У квадратних дужках використовуємо комутативність кон'юнкції.
(5) Двічі використовуємо той самий дистрибутивний закон.
(6) У другій ліворуч дужці використовуємо комутативність кон'юнкції.
(7) Відповідно до закону протиріччя: .
(8) До формули двічі застосовуємо тежство.
(9) А це вже для краси :)) Дужки, до речі, можна було прибрати набагато раніше (я їх не опускав з метою покращити сприйняття перетворень).

Примітка: на 3-му кроці можна було розкрити дужки за «правилом множення багаточленів» і відразу перейти до кроку № 7, але, строго кажучи, цю дію ще потрібно обґрунтувати. А раптом в алгебрі логіки це правило несправедливе?

Завдання 5. Рішення:

(1) Для лівої дужки використовуємо закон де Моргана. У другій дужці - "розкладаємо" імплікацію.
(2) У першій дужці двічі застосовуємо закон подвійного заперечення. З огляду на комутативність кон'юнкції змінюємо місця і .
(3) До «ікса» та правої дужки застосовуємо дистрибутивний закон.
(4) Відповідно до закону протиріччя висловлювання, середня дужка тотожно хибна.
(5) До лівої дужки застосовуємо тотожність. Забираємо всі дужки, оскільки це не змінює порядок дій.
(6) Використовуємо комутативність множення та закон поглинання.

Автор: Ємелін Олександр

(Перехід на головну сторінку)

знижка 15% на перший замовлення, при оформленні введіть промокод: 5530-hihi5

Що таке логіка - Введення в математичну логіку

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

Щоб дізнатися, як логіка працює в математиці, візьмемо для прикладу два факти:

Площу кола можна обчислити за формулою

Можна скласти ці твердження і зробити висновок, що площа кола

. У цьому полягає основна мета математики — виводити нову інформацію. Тому логіка відіграє у ній важливу роль: допомагає об'єднувати відомі факти та отримувати на їх основі нові дані.

Розглянемо ще раз знайомий приклад із колом:

Факт 1: Існує коло

Факт 2: Площа кола обчислюється за формулою.

- це радіус
Висновок: Площа кола

А тепер уявімо, що ми отримали неправильну інформацію. Насправді, радіус дорівнює 10:

Факт 1 (хибний): Існує коло

Факт 2 (Істинний): Площа кола обчислюється за формулою

- це радіус
Висновок (хибний): Площа кола

Перший факт не відповідає дійсності, тому ми дійшли невірного висновку. Ми вірно поєднали факти — логіка у наших діях правильна. Але ми мали неправильну інформацію, і тому помилилися у висновку.

На цьому прикладі видно, що логіка – це правильний висновок інформації, а не висновок правильної інформації. Важливо розрізняти ці поняття, щоб глибше розуміти математику.

Візьмемо ще один приклад – доказ твердження:

«Будь-які дві точки визначають рівно одну пряму»

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

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

З іншого боку, правила логіки визначають сенс математичних тверджень. Наприклад, твердження «Існує ціле число, яке не є сумою двох квадратів» можна передати мовою математики у такому вигляді: