Логіка широко застосовується при вирішенні логічних завдань. Різноманітність логічних задач дуже велике. Способів їх вирішення теж чимало. Але найбільшого поширення набули наступні три способи вирішення логічних завдань:
# 61485; засобами алгебри логіки;
# 61485; за допомогою міркувань.
Познайомимося з ними по черзі.
I. Рішення логічних задач засобами алгебри логіки
Зазвичай використовується наступна схема рішення:
1. вивчається умову задачі;
2. вводиться система позначень для логічних висловлювань;
3. конструюється логічна формула, що описує логічні зв'язки між усіма висловлюваннями умови задачі;
4. визначаються значення істинності цієї логічної формули;
5. з отриманих значень істинності формули визначаються значення істинності введених логічних висловлювань, на підставі яких робиться висновок про рішення.
Завдання 1 Троє друзів, уболівальників автогонок "Формула-1", сперечалися про результати майбутнього етапу гонок.
- Ось побачиш, Шумахер не прийде першим, - сказав Джон. Першим буде Хілл.
- Та ні ж, переможцем буде, як завжди, Шумахер, - вигукнув Нік. - А про Алезі і говорити нема чого, йому не бути першим.
Пітер, до якого звернувся Нік, обурився:
- Хіллу не бачити першого місця, а ось Алезі пілотує найпотужнішу машину.
По завершенні етапу гонок виявилося, що кожне з двох припущень двох друзів підтвердилося, а обидва припущення третього з друзів були невірними. Хто виграв етап гонки?
Введемо позначення для логічних висловлювань: Ш - переможе Шумахер; Х - переможе Хілл; А - переможе Алезі.
Репліка Ніка "Алезі пілотує найпотужнішу машину" не містить ніякого твердження про місці, яке займе цей гонщик, тому в подальших міркуваннях не враховується.
Зафіксуємо висловлювання кожного з друзів:
З огляду на те, що припущення двох друзів підтвердилися, а припущення третього невірні, запишемо і спростимо справжнє висловлювання
Висловлення істинно тільки при Ш = 1, А = 0, Х = 0.
Відповідь. Переможцем етапу гонок став Шумахер.
II. Рішення логічних задач табличним способом
При використанні цього способу умови, які містить завдання, і результати міркувань фіксуються за допомогою спеціально складених таблиць.
Завдання 2. У симфонічний оркестр взяли на роботу трьох музикантів: Брауна, Сміта і Вессона, які вміють грати на скрипці, флейті, альті, кларнеті, гобої і трубі.
1. Сміт найвищий;
2. грає на скрипці менше зростанням грає на флейті;
3. грають на скрипці і флейті і Браун люблять піцу;
4. коли між альтистом і трубачем виникає сварка, Сміт мирить їх;
5. Браун не вміє грати ні на трубі, ні на гобої.
На яких інструментах грає кожен з музикантів, якщо кожен володіє двома інструментами?
Складемо таблицю і відобразимо в ній умови задачі, заповнивши відповідні клітини цифрами 0 і 1 в залежності від того, помилково або істинно відповідне висловлювання. Так як музикантів троє, інструментів шість і кожен володіє тільки двома інструментами, виходить, що кожен музикант грає на інструментах, якими інші не володіють. З умови 4 випливає, що Сміт не грає ні на альті, ні на трубі, а з умов 3 і 5, що Браун не вміє грати на скрипці, флейті, трубі і гобої. Отже, інструменти Брауна - альт і кларнет. Занесемо це у таблицю 5.10, а що залишилися клітини стовпців "альт" і "кларнет" заповнимо нулями.
Відповідь: Браун грає на альті і кларнеті, Сміт - на флейті і гобої, Вессон - на скрипці і трубі.
III. Рішення логічних задач за допомогою міркувань
Цим способом зазвичай вирішують нескладні логічні завдання.
Завдання 3. Вадим, Сергій і Михайло вивчають різні іноземні мови: китайський, японський і арабська. На питання, яку мову вивчає кожен з них, один відповів: "Вадим вивчає китайську, Сергій не вивчає китайську, а Михайло не вивчає арабську". Згодом з'ясувалося, що в цій відповіді тільки одне твердження вірне, а два інших помилкові. Яку мову вивчає кожен з молодих людей?
Є три твердження:
1. Вадим вивчає китайську;
2. Сергій не вивчає китайську;
3. Михайло не вивчає арабську.
Якщо вірно перше твердження, то вірно і друге, так як юнаки вивчають різні мови. Це суперечить умові завдання, тому перше твердження помилкове. Якщо вірно друге твердження, то перше і третє повинні бути помилкові. При цьому виходить, що ніхто не вивчає китайську. Це суперечить умові, тому друге твердження теж помилково. Залишається вважати це остання причина твердження, а перше і друге - хибними. Отже, Вадим не вивчає китайський, китайський вивчає Сергій.
Відповідь: Сергій вивчає китайську мову, Михайло - японський, Вадим - арабська.
Вирішіть завдання: 1. Коля, Боря, Вова і Юра зайняли перші 4 місця в спортивних змаганнях. На питання, які вони місця зайняли, вони відповіли: a) Коля не зайняв, ні перше, ні четверте місце b) Боря посів друге місце c) Вова не був останнім. 2. У кафе зустрілися троє друзів Бєлов, Чернов і Рижов. «Чудово, що у всіх нас різний колір волосся, але в жодного він не відповідає прізвища», - зауважив чорнявий. «Ти маєш рацію», - сказав Бєлов. Якого кольору волосся у Рижова? 3. Відомо, що одне з двох висловлювань «Король Пік і дама Пік несповна розуму» і «Дама Пік несповна розуму» - істинно, а друге ложно. З'ясувати, хто в своєму розумі. 4. На вокзалі на табло першого перону був напис «Вологда», на табло другого - «Псков або Новгород», на табло третього - «Псков». Від пасажирів надійшли скарги, що поїзди їдуть не туди, куди вказували написи. На якому пероні який потяг стояв. 5. Хто зі студентів A, B, C, D грає, а хто не грає в шахи, якщо відомо, що a) якщо A або B грають, то C не грає; b) якщо B не грає, то грають C і D; c) C грає.
Тема 6.1 Поняття алгоритму. Властивості алгоритму. Способи запису алгоритмів.
Основні поняття: алгоритм, властивості алгоритму, блок-схема, код, псевдокод, мова програмування.
Послідовність виконання дій.
У псевдокоді не застосовуються суворі синтаксичні правила для запису команд, які притаманні формальним мовам, що полегшує запис алгоритму на стадії його проектування і дає можливість використовувати більш широкий набір команд, розрахований на абстрактного виконавця. Однак в псевдокоді найчастіше є деякі конструкції, властиві формальним мовам, що полегшує перехід від запису на псевдокоді до запису алгоритму на формальному мові. Наприклад, в псевдокоді, також каки в формальних мовах, існують службові слова, зміст яких визначено раз і назавжди.
Наприклад, алгоритми на алгоритмічній мові записуються за допомогою службових слів, представлених в таб-особі 1.7.
Таблиця 1.7. Службові слова алгоритмічної мови.
Загальний вигляд алгоритму:
алг назва алгоритму (аргументи і результати)
дано умови застосовності алгоритму
треба мета виконання алгоритму
нач опис проміжних величин
послідовність команд (тіло алгоритму)
Частина алгоритму від слова алг до слова поч називається заголовком, а частина, укладена між словами поч і кін - тілом алгоритму.
Єдиний або формальний підхід до визначення псевдокоду не існує, тому використовуються різні псевдокоду, що відрізняються набором службових слів і основних (базових) конструкцій.
Програмна форма подання алгоритмів передбачає, що а лгорітм, призначений для виконання на комп'ютері, повинен бути записаний на зрозумілій йому мові. У цьому випадку мова для запису ал-горітмов повинен бути формалізований. Така мова прийнято називати язи-ком програмування, а запис алгоритму на цій мові - програм-мій.
Стадії створення алгоритму:
1. Алгоритм повинен бути представлений у формі, зрозумілою людині, який його розробляє.
2. Алгоритм повинен бути представлений у формі, зрозумілій тому об'єкту (в тому числі і людини), який буде виконувати описані в алгоритмі дії.
Виконавець алгоритму - об'єкт, який виконує алгоритм.
Ідеальними виконавцями є машини, роботи, комп'ютери.
Виконавець здатний виконати тільки обмежена кількість команд. Тому алгоритм розробляється і деталізується так, щоб в ньому були присутні тільки ті команди і конструкції, які може виконати виконавець.
Виконавець, як і будь-який об'єкт, знаходиться в певному середовищі і може виконувати тільки допустимі в ньому дії. Якщо виконавець зустріне в алгоритмі невідому йому команду, то виконання алгоритму припиниться.
Комп'ютер - автоматизований виконавець алгоритмів.
Алгоритм, записаний на «зрозумілою» комп'ютера мовою програмування, називається програмою.
Програмування - процес складання програми для комп'ютера. Для перших ЕОМ програми записувалися у вигляді послідовності елементарних операцій. Це була дуже трудомістка і неефективна робота. Тому в подальшому були розроблені спеціальні мови програмування. В даний час існує безліч штучних мов для складання програм. Однак так і не вдалося створити ідеальний мову, який би влаштував би всіх.
Тема 6.2 Основні алгоритмічні конструкції.
Основні поняття: лінійний алгоритм, розгалуження, повне і неповне розгалуження, циклічний алгоритм, цикл з передумовою, цикл з умовою поста, цикл з параметром ..
- завдання до читання тексту
Приклад 2. Складіть блок-схему алгоритму обчислення периметра прямокутного трикутника по його катетам а й в.
2. Структура розгалуження. Залежно від результату перевірки умо-вія ( «так» або «ні») здійснює вибір одного з альтернативних шляхів роботи алгоритму. Кожен із шляхів веде до загального виходу, тому ра-бота алгоритму триватиме незалежно від того, який шлях буде обраний. Структура «розгалуження» буває чотирьох видів: «якщо-то»; «Якщо-то-інакше»; «Вибір»; «Вибір-інакше».
есліусловіе то дії все
Приклад 1. Визначити значення змінної a після виконання фрагмента алгоритму при a = 5 і a = 10.
Виконайте завдання: 1. Дано довжини сторін трикутника A, B, C. Знайти площу трикутника S. Складіть блок-схему алгоритму вирішення поставленого завдання. 2. Дано координати вершин трикутника АВС. Знайти його площу. Складіть блок-схему алгоритму вирішення поставленого завдання. 3. У квадратній кімнаті шириною A і висотою B є вікно і двері з розмірами C на D і M на N відповідно. Обчисліть площу стін для обклеювання їх шпалерами. Складіть блок-схему алгоритму вирішення поставленого завдання. 4. Обчислити шлях, пройдений човном, якщо її швидкість в стоячій воді v км / год, швидкість течії річки v1 км / ч, час руху по озеру t1 ч, а проти течії річки - t2 ч. Складіть блок-схему алгоритму вирішення поставленого завдання . 5. Дана блок-схема алгоритму: Визначити результат виконання алгоритму при певних значеннях вихідних даних, наприклад, при x = 16 і y = 2. 6. Що обчислюється по даному алгоритму: а) Ao + Bo = a + b; б) Ao + Bo = a - b; в) Ao + Bo = - a + b; г) Ao + Bo = - a - b. 7. Дана блок-схема алгоритму:
Спірін Тетяна Венедиктівна, ТРОЇЦЬКА Олена Анатоліївна
МАТЕМАТИКА І ІНФОРМАТИКА
Навчальний посібник в 2 частинах
[1] Даймонд складається з семи рядків:
перша і сьома рядки - іменники-антоніми;
другий рядок - прикметник, що описує першу іменник;
третій рядок - три дієслова, що відносяться до першого іменника;
четвертий рядок - чотири іменників, два з них відносяться до першого іменника, два інших - до другого іменника;
п'ятий рядок - три дієслова, що відносяться до другого іменника;
шостий рядок - два прикметників, що описують другий іменник.
приклад:
день;
Яскравий, радісний;
Сяє, обігріває, обнадіює;
Світанок, сонце, тіні, закон;
Охолоджує, насторожує, наближається;
Загадкова, темна;
Ніч.