ТЕОРЕТИЧНІ ВІДОМОСТІ, ПРИКЛАДИ РОЗВ’ЯЗАННЯ ПРАКТИЧНИХ ЗАДАЧ
1. Ознайомлення з основними функціями алгебри логіки, освоєння навичок розв'язання логічних задач.
Короткі теоретичні відомості
Для розв'язання логічних задач застосовується алгебра логіки або Булева алгебра.
У її основу покладене елементарне логічне висловлення, яке може бути тільки істинним або хибним.
Для спрощення дій елементарні висловлення позначаються буквами, а істина й «неправда» логічними одиницями й нулем відповідно. Тоді прості елементарні висловлення можна зв'язати між собою за допомогою логічних функцій і, знаючи, як вони працюють, розраховувати їх.
Основні функції (логічні операції) алгебри логіки наступні:
Кон’юнкція (логічне множення): у природній мові відповідає союзу «і», позначається &.
Кон’юнкція – це логічна операція, що ставить у відповідність кожним двом простим висловленням складене висловлення, що є істинним тоді й тільки тоді, коли обоє вихідні висловлення істині.
Диз'юнкція – (логічне додавання): у природній мові відповідає союзу «або», позначається V.
Диз'юнкція – це логічна операція, яка кожним двом простим висловленням ставить у відповідність складене висловлення, що є істинним, коли хоча б одне із двох утворюючих його висловлень істинно, і хибним у всіх інших випадках.
Інверсія (заперечення): у природній мові відповідає словам «невірно, що…» і частці не, позначається Ā.
Інверсія – це логічна операція, яка кожному простому висловленню ставить у відповідність складене висловлення, що полягає в тому, що вихідне висловлення заперечується.
КонтрольнІ прикладИ
1.1 «П'ять офіцерів».
В одній з гарячих точок служили 5 офіцерів: генерал, полковник, майор, капітан і лейтенант. Один з них сапер, другий – піхотинець, третій – танкіст, четвертий – зв'язковий, п'ятий – артилерист. У кожного з них є сестра. І кожний з них одружений на сестрі свого однополчанина. От що ще відомо про цих офіцерів:
· Принаймні один з родичів зв’язкового старший за нього званням.
· Капітан ніколи не ніс службу у Хабаровську.
· Обидва родича піхотинця і обидва родича танкіста несли службу в Мурманську. Ні один родич генерала у Мурманську не був.
· Танкіст служив в Твері разом з обама своїми родичами, а лейтенант там не служив.
· Полковник служив у Махачкалі разом зі своїми родичами.
· Танкіст не служив у Махачкалі. Там служив тільки один з його родичів.
· Генерал служив з обома своїми родичами у Хабаровську, а в Махачкалі він не був.
· Артилерист не служив ні в Хабаровську, ні в Твері.
Визначте, хто з офіцерів яке звання має?
Розв'язок задачі
Ясно, що кожний офіцер має двох родичів. Один з них – брат дружини, а другий – чоловік сестри. Позначимо для зручності кожного офіцера буквою й розташуємо їх так, щоб сусідом кожного були його родичі (рис. 1.1).
Рис. 1.1. Розташування один за одним
Нехай піхотинець буде позначений буквою А. Оскільки троє з офіцерів служили в Мурманську, а двоє там не були, то танкістові повинна відповідати або буква В, або Г. Допустимо, що танкіст – В. Звідси випливає (з урахуванням умови задачі), що А і В не служили в Мурманську й що Б – генерал. Продовжуючи міркувати, доходимо висновку, що Б, В і Г служили у Твері. Тому лейтенантом повинен бути А або Д і букві Д повинен відповідати артилерист. Далі, або В й Г, або В й Б не служили в Махачкалі. Отже, А, Д і Б або А, Д і Г служили в Махачкалі. А оскільки ми знаємо, що Б не служив у Махачкалі, це значить, що там служили А, Д й Г і що Д – полковник. Таким чином, А – лейтенант.
Переходимо до наступного етапу розв'язку. A, Б і В служили в Хабаровську, а Д там не служив. Нам відомо, що капітан у Хабаровську не служив. Оскільки капітал не може бути Д, отже, йому відповідає буква Г. Далі доходимо висновку, що В – майор. Відомо, що щонайменше один офіцер повинен бути старший за званням, чим зв'язковий. Отже, зв'язковий не може бути Б и повинен бути Г, а саперові відповідає буква Б.
Таким чином, у підсумку виходить, що лейтенант – піхотинець, генерал – сапер, майор – танкіст, капітан – зв'язковий, полковник – артилерист.
1.2. «Фінальний забіг»
Кожний другий пасажир в автобусі із захопленням читав спортивний розділ газети, а інші жваво обговорювали останні спортивні новини. Іван Михайлович не встигнув купити газету, і йому не залишалося нічого іншого, як заглядати в газети, розгорнуті іншими пасажирами, і ловити обривки розмов, що доносилися до нього.
Головною новиною дня був фінал, що відбувся напередодні, естафети 4´100 м для чоловіків. У фінал після напруженої боротьби вийшли команди шести країн: європейські команди А и B, африканські команди C і D і 2 команди-представниці американського континенту E і F.
Іван Михайлович охоче довідався б, як розподілилися місця серед учасників фіналу, але зробити це виявилося непросто. У той день Іван Михайловичу особливо не везло: стоїло йому прилаштуватися до кого-небудь, щоб заглянути через плече, як щасливий власник спортивної газети негайно перевертав сторінку, а репліки знавців і цінителів попиту, що доносилися з усіх боків, були малозрозумілими.
Вийшовши з автобуса, Іван Михайлович зміг відновити в пам'яті лише наступні крихти інформації:
1. Команда А здобула перемогу над командою В.
2. Африканська команда одержала золоті медалі.
3. Команда В здобула перемогу над командою D.
4. По всьому було видно, що перше й друге місця дістануться американським командам, і раптом в останній момент між ними вклинилася європейська команда.
5. Африканська команда відстала від усіх інших учасників фіналу.
6. Першими фінішували 3 африканських бігуна.
7. Команда F здобула перемогу над командою В.
8. Команда Е здобула перемогу над командою F.
9. У складі європейських команд не було африканських спортсменів.
Користуючись цими уривчастими відомостями, Іван Михайлович спробував відновити, як розподілилися місця між шістьома командами, що приймали участь у фіналі естафетного бігу, але марно.
Нарешті, після ретельного аналізу Іван Михайлович зрозумів, що одна з дев'яти перерахованих вище посилок неправильна. Він що-небудь не так зрозумів, або погано розглядів, або неправильно згадав.
Усі інші посилки дійсні.
Як розподілилися місця між шістьома командами, що прийняли участь у фінальному забігу?
Розв'язок задачі
Для того щоб розв'язати завдання, необхідно, насамперед, з'ясувати, яке з дев'яти наведених тверджень неправильне.
Отже, проаналізуємо дані твердження. Якщо твердження (9) свідомо вірне (за умовою задачі), то неважко встановити, що твердження (4), (5), і (6) не можуть бути дійсними одночасно.
Дійсно, якщо дійсне твердження (6), то 3 перші місця розділили між собою 2 африканські й 1 американська команди або 1 африканська й 2 американські команди. Але за твердженням (5) 2 африканські команди не могли бути серед тих, хто вийшов на перші три місця, а за твердженням (4) 2 американські команди могли зайняти лише перше й третє місця. Крім того, із цього ж твердження (4) випливає, що на друге місце вийшла європейська команда й, отже, серед власників трьох перших місць не було ні однієї африканської команди.
Таким чином, неправдиві відомість повинні втримуватися в якімсь із тверджень (4), (5) і (6), а інші твердження дійсні, тому що за умовою задачі неправильним є тільки одне твердження. Скористаємося спочатку свідомо дійсними твердженнями.
Об'єднаємо твердження (1), (3) і (7) в одне, тому що вони взаємозалежні між собою. Прочитавши їх у послідовності (1)-(7)-(3), приходимо до наступного висновку: якщо виключити команди С і Е, то представники інших команд могли прийти до фінішу лише в послідовності A, F, В, D. Отже, серед команд, що зайняли 3 перші місця, свідомо повинна бути європейська команда А. У найгіршому разі, вона могла вийти на третє місце, але виявилася серед призерів. Це означає, що твердження (6) неправильно. Щоб визначити, яке місце зайняла кожна із шести команд, розташуємо дійсні твердження в наступному порядку: (2), (4), (5), (8), (1)-(7)-(3), (9).
Як видно із тверджень (2) і (1)-(7)-(3), перше місце могла зайняти лише команда С, оскільки команда D свідомо не вийшла на перше місце. За твердженням (5), команда D могла зайняти лише останнє, шосте, місце.
Твердження (8) і (1)-(7)-(3) дозволяють схематично зобразити розподіл місць між чотирма іншими командами так, як показано на рис. 1.2 (вістря стрілки спрямоване до команди, що показала кращий час, кінець – до команди, що зайняла останнє місце).
Рис. 1.2.
Розподіл місць між чотирма явно не лідируючими командами
Залишається нез'ясованим, яка з команд – Е або А – показала кращий результат. Цю невизначеність допомагає вирішити твердження (4). Згідно зі схемою, між двома американськими командами Е и F могла "вклинитися" тільки європейська команда А.
Отже, представники чотирьох команд, про яких мова йде, могли перетнути лінію фінішу лише в наступній послідовності: Е, А, F, В. Це означає, що команда С посіла перше місце, Е – друге, А – третє, F – четверте, В – п'яте й команда D – шосте місце.