Логіка та вирішення проблем

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

Розділи

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

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

У системах Знаємо це основні завдання з логіки належать до розділу математики: логіка на Znaiemo matematyku. Там ви знайдете математичні значення логічних операцій, модифікації логічних виразів, квантори, докази та інші теми.

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

• Логічні сполучники та таблиці істинності – основні логічні сполучники (and = і також, or = або) та їх використання.
  • Логічні твердження – написані словами твердження та їх оцінка.
  • Логічна дедукція – висновки з кількох тверджень, розв’язування логічних задач з текстами.
  • Логічні задачі на ґратці – логічні задачі з символами та цифрами (Судоку, Паркани).

Судження – це речення або твердження, яке є істинним або хибним.

Приклади тверджень

• „Сьогодні я встав о восьмій ранку.“
• „Я одягнений у червону футболку.“
• „Мій брат старший за мене.“

Приклади речень, які не є судженнями

• „Завтра буде дощ?“
• „Іди спати!“
• „Чому трава зелена?“

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

Приклади

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

Особливості та каверзні ситуації

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

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

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

Ланцюжок наслідків

Щоразу, коли перший факт веде до другого, а другий веде до третього, тоді перший факт також веде до третього.

Імплікація з правивою передумовою

Якщо ми маємо імплікацію, яка має дійсну передумову, то її висновок також має бути дійсним.

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

У цій темі ми працюємо з логічними виразами з формальним позначенням (наприклад, A або B), при цьому деякі логічні сполучення позначаються англійськими словами (and, or, not). Ця нотація поширена в інформатиці і використовується, наприклад, у багатьох мовах програмування. Розбиваємо тему на наступні підтеми:

• Логічні сполучники та таблиці істинності –значення окремих логічних сполучників, перепис із загальномовної на інформаційну нотацію (and, or, not, xor, ⇒, ⇔)
• Оцінювання логічних виразів – оцінка складених виразів, що поєднують декілька логічних сполучників
• Редагування логічних виразів – переписування до еквівалентного виразу (який виглядає інакше, але завжди має однакове значення істинності)

Ви також можете практикувати роботу з логічними твердженнями в різних нотаціях:

• Логічні твердження словами – висловлювання звичайною мовою
• Логіка на Знаємо математику – робота з висловлюваннями у математичній нотації (∧,∨,¬)
• Логічні вирази в Python – робота з логічними виразами в контексті програмування

Значення істинності

В інформатиці ми використовуємо як взаємозамінне таке:

• 1 = true = правда
• 0 = false = неправда

Логічні сполучники

Таблиця істинності логічних операцій

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

Наприклад, сполучник and має значення істини (true, 1), якщо і тільки якщо обидва твердження є істинними.

Отже, 1 and 1 = 1, але, наприклад, 1 and 0 = 0.

Таблиця істинності логічних операцій

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

Транскрипція основних логічних сполучників

Перепис імплікації, еквівалентності та операції xor

Аналогічні закони, як і при обчисленні з числами

До логічних операцій and тa or також застосовуються комутативний (1-й і 2-й рядки наступної таблиці), асоціативний (3-й і 4-й рядки) і розподільний закони (5-й і 6-й рядки) :

Ви також можете знайти інші вправи з дещо іншими позначеннями на сторінці знаємо математику.

Логічнf послідовність за допомогою логічних виразів є формальним варіантом виведення логічних наслідків за допомогою слів.

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

Ми кажемо, що вираз виводиться (тобто випливає) із даних виразів тоді і тільки тоді, коли він справедливий у всіх випадках, у яких справедливі всі дані вирази.

Приклади

• З виразу X \text{ and } Y ми можемо зробити висновок X, тому що завжди, коли є дійсним X \text{ and } Y, має бути дійсним і X i Y, а через це є дійсним і саме X.
• З виразу X \text{ or } Y та \text{not } X ми можемо зробити висновок Y. Для того, щоб здійснювалось X \text{ or } Y, має бути дійсним X або Y, але X не може бути дійсним. Тому дійсне Y.
• З виразу X \Leftrightarrow Y та X ми можемо зробити висновок Y. Вираз X \Leftrightarrow Y стверджує, що Y завжде має те ж значення, що і X. З правдивості X ми тоді можемо виводити і правдивість Y.

У цьому розділі ви можете потренуватися у своєму вмінні розв’язувати логічні задачі. Тут ви знайдете різні типи завдань:

• Лабіринт – різні стилі лабіринту, включаючи стрибки та просування крізь стіни.
• Логічні задачі з пересуваннями – розв’язування задач рухом об’єктів.
• Логічні завдання на сітці – заповнення клітинок або країв сітки.

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

Лабіринти складаються з переплетення коридорів і доріжок, в яких ми зазвичай шукаємо шлях від старту до мети. Людей захоплювали лабіринти з давніх часів. Історично відомі лабіринти включають, наприклад, легендарний лабіринт Мінотавра з грецької міфології або лабіринти в замкових садах (наприклад, знаменитий лабіринт у Хемптон-Корт в Англії).

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

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

Непрохідний лабіринт	Лабіринт без можливості повороту ліворуч
рішення	рішення

У цих завданнях ви відпрацюєте вміння знаходити послідовність кроків для досягнення потрібного стану.