Головна

I. Рішення логічних задач засобами алгебри логіки

  1.  Cтатистика - предмет, метод, завдання
  2.  FH 06 Е ЗАВДАННЯ
  3.  FR 02 Е МЕТА ТА ЗАВДАННЯ
  4.  FW 15 10 Завдання.
  5.  I. До чого прагне педагогіка, якою вона має бути і в чому її завдання?
  6.  I. Основні завдання ЗОВНІШНЬОЇ ПОЛІТИКИ
  7.  I. Постановка завдання

Зазвичай використовується наступна схема рішення:

  1. вивчається умову задачі;
  2. вводиться система позначень для логічних висловлювань;
  3. конструюється логічна формула, що описує логічні зв'язки між усіма висловлюваннями умови задачі;
  4. визначаються значення істинності цієї логічної формули;
  5. з отриманих значень істинності формули визначаються значення істинності введених логічних висловлювань, на підставі яких робиться висновок про рішення.

Приклад 1. Троє друзів, уболівальників автогонок "Формула-1", сперечалися про результати майбутнього етапу гонок.

- Ось побачиш, Шумахер не прийде першим, - сказав Джон. Першим буде Хілл.

- Та ні ж, переможцем буде, як завжди, Шумахер, - вигукнув Нік. - А про Алезі і говорити нема чого, йому не бути першим.

Пітер, до якого звернувся Нік, обурився:

- Хіллу не бачити першого місця, а ось Алезі пілотує найпотужнішу машину.

По завершенні етапу гонок виявилося, що кожне з двох припущень двох друзів підтвердилося, а обидва припущення третього з друзів були невірними. Хто виграв етап гонки?

Рішення. Введемо позначення для логічних висловлювань:

Ш - Переможе Шумахер; Х - Переможе Хілл; А - Переможе Алезі.

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

Зафіксуємо висловлювання кожного з друзів:

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

висловлювання  істинно тільки при Ш = 1, А = 0, Х = 0.

Відповідь. Переможцем етапу гонок став Шумахер.

Приклад 2. Якийсь любитель пригод відправився в кругосвітню подорож на яхті, оснащеної бортовим комп'ютером. Його попередили, що найчастіше виходять з ладу три вузла комп'ютера - a, b, c, І дали необхідні деталі для заміни. З'ясувати, який саме вузол треба замінити, він може по сигнальним лампочкам на контрольній панелі. Лампочок теж рівно три: x, y и z.

Інструкція щодо виявлення несправних вузлів така:

  1. якщо несправний хоча б один з вузлів комп'ютера, то горить принаймні одна з лампочок x, y, z;
  2. якщо несправний вузол a, Але справний вузол с, То загоряється лампочка y;
  3. якщо несправний вузол с, Але справний вузол b, Загоряється лампочка y, Але не загоряється лампочка x;
  4. якщо несправний вузол b, Але справний вузол c, То спалахують лампочки x и y або не світиться лампочка x;
  5. якщо горить лампочка х і при цьому або несправний вузол а, Або всі три вузла a, b, c справні, то горить і лампочка y.

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

Які вузли замінив мандрівник? Які вади він виявив в інструкції?

Рішення. Введемо позначення для логічних висловлювань:

a - Несправний вузол а; x - Горить лампочка х;

b - Несправний вузол b; y - Горить лампочка y;

с - Несправний вузол с; z - Горить лампочка z.

Правила 1-5 виражаються наступними формулами:

Формули 1-5 істинні за умовою, отже, їх кон'юнкція теж істинна:

Висловлюючи імплікації через диз'юнкцію і заперечення (нагадаємо, що  ), Отримуємо:

Підставляючи в це тотожність конкретні значення істинності x= 1, y= 0, z= 0, отримуємо:

Звідси слідує що a = 0, b = 1, c = 1.

Відповідь на перше питання задачі: потрібно замінити блоки b и c; блок а не вимагає заміни. Відповідь на друге запитання задачі отримаєте самостійно.




 Додавання і віднімання |  вправи |  Глава 5. Логічні основи комп'ютерів |  З х е м а АБО |  З х е м а НЕ |  З х е м а І-НЕ |  З х е м а АБО-НЕ |  ОСНОВНІ ЗАКОНИ АЛГЕБРИ ЛОГІКИ |  Приклади. |  III. Рішення логічних задач за допомогою міркувань |

© um.co.ua - учбові матеріали та реферати