Алгоритм розв'язання логічних задач
з прикладами різних видів
Для розв'язування логічної задачі можна використати наступну схему:
Метод міркувань здебільшого використовують при розв'язуванні простих задач.
Метод полягає в послідовних міркуваннях з використанням всіх відомих умов. Частина умови в задачі може бути хибною. Тому потрібно переглянути всі твердження й викреслити ті з них, недоречність яких очевидна, порівняти ті, що залишилися, між собою і визначити зв'язки та протиріччя.
Розв’язування задачі доцільно супроводжувати записами і нотатками. Можна ввести певні позначення (наприклад, 1 – істинне висловлювання, 0 – хибне).
Задача 1.
Троє свідків так розповіли про автомобіль, який вони бачили:
1) Це була Хонда чорного кольору.
2) Це був Форд синього кольору.
3) Це Мерседес, але не синій.
Кожен з них мав рацію лише в одному зі своїх тверджень. Який це був автомобіль?
Спочатку припустимо, що автомобіль - Хонда, тоді твердження свідків можна записати у вигляді:
1) 1 0 - одне істинне, інше помилкове: автомобіль Хонда, не чорна;
2) 0 1 - не Форд, синій;
3) 0 0 - не Мерседес (припущення - Хонда), що не синій – не вірно, тому що в 2) - синій.
Два висловлювання 3-го свідка - помилкові - суперечить умові.
Тепер припустимо, що це Форд.
1) 0 1 - автомобіль не Хонда, чорна;
2) 1 0 - якщо Форд, то не синій;
3) 0 1 - не Мерседес і не синій.
Отже - це чорний Форд.
Перевіримо ще одне припущення: автомобіль - Мерседес.
1) 0 1 - автомобіль не Хонда, чорна;
2) 0 0 - якщо не Форд, то синій - протиріччя.
Відповідь: чорний Форд [1-3].
Суть методу таблиць полягає в фіксації умов задачі і отриманих результатів міркувань в таблиці, складені під умову конкретної задачі, які складаються з n x n клітинок (кількість n і кількість таблиць залежить від умови задачі). Дані задачі вносяться до відповідних клітинок таблиці знаком «+» і «-» або «1» і «0», залежно від того є висловлювання істинним чи хибним. Після використання всіх умов завдання клітинки, що залишилися порожніми, заповнюють знаком «+» або «-», які встановлюють шляхом логічних міркувань.
Задача 2.
Зустрілися троє друзів - Біленко, Сіренко і Черненко. Черненко сказав одному, одягненому в сірий костюм: «Цікаво, що на одному з нас білий костюм, на іншому - сірий і на третьому - чорний, але на кожному костюм кольору, який не відповідає прізвищу». Який колір костюма у кожного з друзів?
Розв’язання. У лівому стовпчику таблиці 3x3 (табл. 1) запишемо прізвища друзів, у верхньому рядку - кольори їх костюмів. За умовою у Біленка - не білий костюм, у Сіренка - не сірий і у Черненка - не чорний. Поставимо три мінуси на перетині відповідних рядків і стовпців таблиці.
У Черненка - не сірий костюм, так як за умовою в сірий костюм одягнений один з його друзів, ставимо мінус у відповідній клітинці. Отже, на ньому може бути тільки костюм білого кольору, поставимо у відповідній клітинці таблиці плюс.
Тоді у Сіренко - не білий костюм, значить, на ньому може бути лише чорний костюм, а на Біленко - сірий костюм.
Цю задачу неважко було б розв’язати і без допомоги таблиці - безпосереднім перебором. Але якщо в подібній задачі потрібно встановити відповідність між двома множинами, кожна з яких містить не по три, а по чотири, п'ять або шість (і більше!) елементів, то розв’язання за допомогою таблиці набагато простіше.
Таблиця в задачах на відповідність між двома множинами, (але лише в тих випадках, коли ці множини містять елементів порівну) має таку властивість: в кожному рядку таблиці є тільки один плюс, в кожному стовпці також є тільки один плюс. Отже, якщо в якій-небудь клітинці таблиці стоїть плюс то в інших клітинках, що стоять в тому ж рядку або в тому ж стовпці, може бути тільки мінус [4,6].
Розв’язання вище наведених задач може бути реалізоване з використанням графів. Графом називається кінцева множина точок, що є вершинами графа, деякі з яких з'єднані лініями, які називають ребрами. Кількість ребер, що виходять з вершини графа, називається степенем цієї вершини.
Схема методу графів наступна: у двох або більше множин, які беруть участь в умові задачі, елементи, між якими встановлено взаємно однозначну відповідність, з'єднуються суцільною лінією і пунктирною лінією, якщо така відповідність відсутня.
В окремих випадках цей спосіб є більш наочним і ефективним, ніж побудова таблиць.
Задача 2.
Три подруги були в білій, червоній і блакитній сукнях. Їх туфлі були таких самих трьох кольорів. Тільки у Тамари колір сукні і туфель збігався. Валя була в білих туфлях. Ні сукня, ні туфлі Ліди не були червоними. Визначте колір сукні та туфель кожної з подруг.
Розв’язання. Зобразимо на малюнку три множини: множину подруг {Т, В, Л}, множину їх суконь {Б, Ч, Г} і множину їх туфель {б, ч, г} (рис. 1).
Проведемо на малюнку суцільні і пунктирні лінії, що відповідають умові задачі.
Для отримання відповіді потрібно розшифрувати літери, які стоять в вершинах трьох трикутників із суцільними сторонами.
У Валі білі туфлі, тоді зрозуміло, що у Ліди - голубі, у Тамари – червоні туфлі і, отже, червоне плаття. Далі, у Ліди – біле плаття, у Валі - блакитне.
Відповідь: Тамара - в червоній сукні і червоних туфлях, Валя - в блакитній сукні і білих туфлях, Ліда - в білій сукні і блакитних туфлях [4].
Початок алгебри логіки, покладено працями англійського математика Дж. Буля, її також називають булевою алгеброю або алгеброю висловлень.
Під висловленням розуміється будь-яке твердження, яке може бути істинним або хибним.
Істинному висловленню приписується 1, хибному – 0.
Висловлення можуть бути простими і складними. Складні висловлення складаються з простих.
Для об’єднання простих висловлень в складні використовуються логічні зв’язки, що відповідають логічним функціям, аргументами яких є прості висловлення.
Алгоритм методу алгебри логіки може бути наступний :
·вивчити умову задачі;
·ввести систему позначень для логічних висловлювань;
·записати умову задачі мовою алгебри логіки;
·сконструювати логічну формулу, яка описує логічні зв’язки між всіма висловлюваннями умови задачі, для цього об’єднати логічним множенням формули кожного твердження;
·прирівнняти добуток до одиниці, спростити формулу;
·проаналізувати отриманий результат, або скласти таблицю істинності;
·визначити значення істинності логічної формули;
·з отриманих значень істинності формули визначаються значення істинності введених логічних висловлень, на основі яких робиться висновок про розв’язок.
Задача 4. «Олексій, Борис і Григорій знайшли в землі посудину. Кожен з них висловив по два припущення.
Олексій – Ця посудина грецька, V століття.
Борис – Ця посудина фінікійська, III століття.
Григорій – Це не грецька посудина, IV століття.
Вчитель історії сказав друзям, що кожен з них правий лише в одному з двох своїх припущень. Де і в якому столітті була виготовлена посудина?»
Отже,
Список використаних літературних джерел
Давайте практикуватись!