Практична робота №1 «Вирішення логічних завдань»

Мета роботи: ознайомитися з основними функціями алгебри логіки, освоїти навички вирішення логічних завдань.

 

Короткі теоретичні відомості

Для вирішення логічних завдань застосовується алгебра логіки або буллева алгебра.

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

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

Основні функції (логічні операції) алгебри логіки наступні:

Кон'юнкція (логічне множення): в природній мові відповідає поняттю «і», позначається &.

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

Диз'юнкція - (логічне додавання): в природній мові відповідає поняттю «або», позначається V.

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

Інверсія - (заперечення): в природній мові відповідає словами «невірно, що ...» і частці «не», позначається Ā.

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

 

Приклади виконання завдання

Завдання 1 «П'ять офіцерів»

В одній з гарячих точок служили 5 офіцерів: генерал, полковник, майор, капітан і лейтенант. Один з них сапер, інший - піхотинець, третій - танкіст, четвертий - зв'язківець, п'ятий - артилерист. У кожного з них є сестра. І кожен з них одружений на сестрі свого однополчанина. Ось що ще відомо про цих офіцери:

• Щонайменше, один з родичів зв'язківця старше його за званням.

• Капітан ніколи не служив в Хабаровську.

• Обидва родича-піхотинця і обидва родича-танкіста служили раніше в Мурманську. Жоден родич генерала в Мурманську не був.

• Танкіст служив в Твері разом з обома своїми родичами, а лейтенант там не служив.

• Полковник служив в Махачкалі разом зі своїми родичами.

• Танкіст не служив в Махачкалі. Там служив тільки один з його родичів.

• Генерал служив з обома своїми родичами в Хабаровську, а в Махачкалі він не бував.

• Артилерист не служив ні в Хабаровську, ні в Твері.

Визначте, хто з офіцерів яке звання має?

 

Розв’язок  завдання

Ясно, що кожен офіцер має двох родичів. Один з них - брат дружини, а інший - чоловік сестри. Позначимо для зручності кожного офіцера буквою і розташуємо їх так, щоб сусідом кожного були його родичі (рис. 1.1).

 

Рис. 1.1. Розташування по порядку

 

Нехай піхотинець буде позначений буквою А. Оскільки троє з офіцерів служили в Мурманську, а двоє там не були, то танкісту повинна відповідати або літера В, або Г. Припустимо, що танкіст - В. Звідси випливає (з урахуванням умови задачі), що А і В не служили в Мурманську і що Б - генерал. Продовжуючи міркувати, приходимо до висновку, що Б, В і Г служили в Твері. Тому лейтенантом повинен бути А чи Д і букві Д повинен відповідати артилерист. Далі, або В і Г, або В і Б не служили в Свердловську. Отже, А, Д і Б або А, Д і Г служили в Свердловську. А оскільки ми знаємо, що Б не служив в Свердловську, це означає, що там служили А, Д і Г і що Д - полковник. Таким чином, А - лейтенант.

Переходимо до наступного етапу розв'язання. A, Б і В служили в Хабаровську, а Д там не служив. Нам відомо, що капітан в Хабаровську не служив. Оскільки капітан не може бути Д, отже, йому присвоєно літеру Г. Далі приходимо до висновку, що В - майор. Відомо, що щонайменше один офіцер повинен бути старше за званням, ніж зв'язківець. Отже, зв'язківець не може бути Б і повинен бути Г, а саперу відповідає буква Б.

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

 

Завдання 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 - шосте місце.

 

Індивідуальні завдання

Вирішіть завдання, відповідно до вашого варіанту. Опишіть хід розв'язання задачі, логічні міркування.

Варіант 1

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

Чи був слуга з племені правдивих або ж брехуном.

Варіант 2

Чотири юних філателіста - Діма, Толя, Сашко та Петя - купили поштові марки. Кожен з них купував марки тільки однієї країни, причому двоє з них купили російські марки, один - болгарські, а один - словацькі. Відомо, що Діма і Толя купили марки двох різних країн. Марки різних країн купили Діма з Сашею, Петя з Сашею, Петя з Дімою і Толя з Сашею. Крім того, відомо, що Діма купив не болгарські марки.

Які марки купив кожний з хлопчиків?

Варіант 3

Чотири людини взялися виконувати роботу маляра, слюсаря, коваля і штукатура - кожен буде робити щось одне. З'ясувалося, що Антон не буде маляром і не буде слюсарем, Олексій не буде ковалем і не буде маляром, Євген не буде слюсарем і не буде маляром, Дмитро не буде ковалем і не буде слюсарем. Відомо також, що якщо Антон не буде ковалем, то Дмитро не буде маляром.

Хто і яку роботу буде виконувати?

Варіант 4

П'ятеро дівчат поїхали у відпустку кожна на своїй машині. Всі машини були різного кольору. Першою їхала на білій машині американка. За нею на «Тойоті» росіянка. За француженкою на синій машині їхав жовтий «Сітроен». Замикала колону англійка на фіолетовому «Форді». «Плімут» був новіше «Б'юік», але менш потужний, тому він їхав в середині колони, а полька чудово виглядала у своєму брючному костюмі. Одна з машин була зеленого кольору.

Хто і на якій машині їхав - вказати колір і марку.

Варіант 5

Повернувшись додому, Мегре подзвонив на набережну Орфевр.

Мегре: Є новини?

Полісмен: Так, шеф. Надійшли повідомлення від інспекторів. Торранс встановив, що якщо Франсуа був п'яний, то або Етьєн вбивця, або Франсуа бреше. Жульєн вважає, що або Етьєн вбивця, або Франсуа не був п'яний, і вбивство сталося після півночі. Інспектор Люка просив передати вам, що якщо вбивство сталося після півночі, то або Етьєн вбивця, або Франсуа бреше. Потім подзвонила …

Мегре: Все. Спасибі. Цього достатньо.

Комісар поклав трубку. Він знав, що тверезий Франсуа ніколи не бреше. Тепер він знав все.

Опишіть, що знає Мегре?

Варіант 6

Сім'я складається з п'яти осіб: Олексія, Віри, Даші, Гліба і Євгенії. Коли сім'я дивиться телевізор, то виконуються наступні умови:

• Дивляться або Даша, або Євгенія, або обидві разом.

• Дивляться або Гліб, або Віра, але не разом.

• Даша і Гліб або дивляться разом, або разом не дивляться.

• Якщо телевізор дивиться Олексій, то дивиться і Віра.

• Якщо телевізор дивиться Євгенія, то дивляться Олексій і Даша.

Хто дивиться телевізор?

Варіант 7

Брауну, Джонсу і Сміту пред'явлено звинувачення в пограбуванні банку. Викрадачі втекли на автомобілі, який їх чекав. На слідстві Браун показав, що злочинці зникли на синьому «Бьюїк», Джонс сказав, що це був «Форд-мустанг» і ні в якому разі не синій. Сміт заявив, що це була не синя «Тойота».

Стало відомо, що бажаючи заплутати слідство, кожен з них вказав правильно або тільки марку машини, або її колір.

Якого кольору і якої марки був автомобіль?

Варіант 8

Микола хотів запросити в гості Андрія, Віктора, Сергія, Дмитра, Євгена, Федора, Георгія та Олега. При цьому він зіткнувся з наступними труднощами:

• Андрій ніколи не прийде, якщо запросити Віктора чи Сергія, або якщо одночасно прийдуть Дмитро і Євгеній.

• Дмитро прийде тільки в тому випадку, якщо буде запрошений і Євген.

• Євген не прийме запрошення, якщо прийде Віктор.

• Федір наносить візити тільки в супроводі Георгія.

• Олег не буде заперечувати проти присутності Федора тільки в тому випадку, якщо буде запрошений і Андрій.

• Якщо не буде запрошений Федір, то Олег буде проти запрошення Євгена.

• Щоб прийшов Георгій, необхідно запросити Дмитра чи Олега.

• Георгій відмовиться від запрошення, якщо запросять Євгена без Андрія, а також у разі запрошення Віктора чи Сергія.

Кого міг запросити Микола?

Варіант 9

У складі експедиції має бути шість фахівців: біолог, лікар, синоптик, гідролог, механік і радист. Є вісім кандидатів, з яких потрібно вибрати шість учасників експедиції. Імена претендентів: Андрій, Віктор, Сергій, Дмитро, Євген, Федір, Григорій, Микола.

Обов'язки біолога можуть виконувати Євген і Григорій, лікаря - Андрій та Дмитро, синоптика - Федір і Григорій, гідролога - Віктор та Федір, радиста - Сергій і Дмитро, механіка - Сергій та Микола. Передбачено, що в експедиції кожен виконує тільки один обов'язок.

Кого і на якій посаді слід включити в експедицію, якщо Федір не може їхати без Віктора, Дмитро - без Миколи і без Сергія, Сергій не може їхати разом з Григорієм, Андрій разом з Віктором?

Варіант 10

П'ятеро друзів - Андрій, Борис, Віктор, Григорій і Дмитро вирішили записатися в гурток любителів логічних задач. Керівник гуртка дав їм завдання. Вони повинні були приходити на заняття по можливості частіше, але в різних поєднаннях, дотримуючись наступні умови:

• Якщо Андрій приходить разом Дмитром, то Борис повинен бути присутнім.

• Якщо Дмитро відсутній, то Борис повинен бути, а Віктор повинен бути відсутнім.

• Якщо приходить Дмитро, то Григорій нехай не приходить.

• Андрій і Віктор не можуть одночасно ні присутнім, ні відсутніми.

• Якщо Борис відсутня, то Дмитро повинен бути присутнім, але в тому випадку, якщо не присутній Віктор.

• Якщо Віктор присутній, але відсутній Борис, то Григорій повинен бути, а Дмитро повинен бути відсутнім.

В яких поєднаннях друзі могли відвідувати заняття?

Варіант 11

Семеро друзів - Антонов, Борисов, Васильєв, Глєбов, Дмитрієв, Єгоров і Іванов - за дивним збігом обставин мають співпадаючі імена, причому жоден з них не є «тезкою» свого прізвища.

Крім того, про них відомо наступне:

• Всі крім Антонова і Глєбова вже одружені.

• Нареченій Єгора дуже не подобатися прізвище нареченого.

• Прізвище Глеба збігається з ім'ям Іванова.

• Дружини Дмитрієва та Івана - рідні сестри.

• Той, чиє ім'я співпадає з прізвищем Бориса, одружений, і його прізвище збігається з ім'ям Єгорова.

• Іван, Єгор, Василь - брюнети.

• Решта четверо, в числі яких Іванов, Єгоров і Васильєв, - блондини.

Яке прізвище у Василя?

Варіант 12

У родині п'ятеро осіб: чоловік, дружина, їх син, сестра чоловіка і батько дружини. Їх фах - інженер, юрист, слюсар, учитель і економіст. Відомо, що юрист і вчитель - не кровні родичі. Слюсар молодше економіста, і обидва грають у футбол за збірну свого заводу. Інженер молодше вчителя, але старший за дружину свого брата.

Назвіть професії кожного.

 

Запитання для самоперевірки

1.  Для чого використовується алгебра логіки?

2.  Дайте визначення поняттю «кон'юнкція»

3.  Дайте визначення поняттю «диз'юнкція»

4.  Дайте визначення поняттю «інверсія»