Народна Освіта » Інформатика » Розділ 12. Елементи алгебри логіки

НАРОДНА ОСВІТА

Розділ 12. Елементи алгебри логіки

Історія виникнення математичної логіки; логічні операції й вирази; основні закони булевой алгебри; використання булевої алгебри для розв'язування логічних задач.

12.1. Предмет та історія виникнення математичної логіки

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

Логіка — (від грец. logos — слово, думка, поняття, закон) — наука про загальні закони розвитку об’єктивного світу й пізнання їх. Вона мас декілька напрямів: формальна логіка, імовірна логіка, математична логіка та інші. Математична логіка - складова формальної логіки. Формальна логіка — наука про форми й закони людського мислення. Основними формами мислення є поняття, судження й твердження.

Поняття — така форма мислення, коли відокремлюються найвагоміші ознаки предмета або класу предметів. За їх допомогою відрізняють цей предмет від інших.

Наприклад, за допомогою певних ознак відрізняються такі об’єкти: трактор, комп’ютер, літак, пароплав.

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

Твердження (умовивід) - форма мислення, яка дозволяє на основі одного або кількох тверджеиь-посилань отримати нове судження (значення або висновок). Умовивід може бути істинним, якщо істинним є посилання, інакше він може бути хибним. Наприклад, якщо є такі посилання: "на диску е 2,3 МБ вільного щзостору" і "файл bosh.doc займас 1,9 МБ", то істинним є такий умовивід: "файл bosh.doc може б$ти записаний на диск".

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

Висловлювання — окреме конкретне твердження, про яке можна однозначно сказати істинне воно чи хибне. Приклади висловлювань: 23 - просте число; пінгвіни - це птахи; 2 + 2 = 5; сума внз'трішніх кутів трикутника дорівнює 180'; Туніс розташований у Європі.

При вивченні висловлювань повністю відволікаються від їх конкретного змісту, враховуючи лише їх істинність чи хибність. Тому висловлювання можна позначати, наприклад, великими латинськими літерами, скажімо, А — "Гривня дорівнює 100 копійкам" і надалі оперувати їх позначеннями.

Предикати - це твердження, що містять змінні.

Приклади предикатів: сі — змінна дійсного типу; а > Ь\ N — видатний письменник; х — корінь рівняння 5£ = 10.

Якщо замість змінних підставити їх конкретні значення, то предикати стануть висловленнями, які входять до складу предиката. Наприклад, якщо а=2, а Ь=3, то предикат "а>6" стає хибним висловленням, а якщо N дорівнює "Іван Франко", то відповідний предикат стає істинним висловленням.

Перевіряємо себе

1. Що є предметом науки логіка?

2. Що вивчає математична логіка4.'

3. У чому полягає сутність булевої ял гобой?

4. Які є основні форми мислення?

5. Що називають висловлюванням?

6. Наведіть приклади істинних висловлювані

7. Наведіть приклади хибних висловлювань.

8. Чи може висловлювання одночасно бути істинним і хибним?

9. Що називають предикатом?

10. Який зв’язок існує між предикатом і висловлюванням'

11. Чи є висловлюванням речення "Котра зараз година?"

12.2. Логічні операції та вирази

Булева алгебра ґрунтується на кількох логічних операціях, серед яких найчастіше використовуються такі: заперечення (HI, NOT), кон’юнкція (I, AND), диз’юнкція (і\ВО, OR). Ці операції є базовими, тому що за допомогою цих операцій можна виразити будь-яку іншу.

Операція кон’юнкція, позначається символом &. Наприклад, кон’юнкція над змінними х і у записується так: х&у. Часто символ & взагалі опускається, між змігшими не вказується символ або ставиться символ крапки, наприклад, ху або х у.

Заперечення є унарною операцією, тобто вона застосовується для однієї змінної. Ця операція позначається рисочкою над змінною (наприклад, а).

 

Операція диз’юнкція позначається символом V, наприклад,

хУу.

У мові наведені операції та їх комбінації відповідають частці "ні" та сполучникам "і", "або", "якщо...то", "тоді й тільки тоді" та іншим. Висловлюванням у булевій алгебрі ставлять у відповідність логічні змінні, які можуть набувати одного з двох значеннь: істинно і хибно. Наприклад, висловлювання "швидкість автомобіля дорівнює 100 км" можна позначити змігшою А. У мовах програмування істинність і хибність можуть позначатись іменованими константами true та false, конкретні значення яких залежать від обраного способу кодування розробниками мов і трансляторів. У математиці інколи значення істинно позначають одиницею, а значення хибно — нулем.

Логічні вирази складаються з опсраидів, логічних операцій та круглих дужок. У мові Pascal означено шість операцій порівняння: > (більше), < (менше), = (дорівнює), <> (не дорівгпоє), >= (більше або дорівнює), <= (менше або дорівгпоє). Наприклад, логічний вираз т>п — це вираз, який стверджує, що значення змінної т більше за значення змігшої п. Тому, якщо т=2, а п=3, вираз т>п хибний, а вираз т*10>л — істинний. Таким чином, результатом обчислення логічного виразу може бути тільки одне з двох значень: true (істинно, або <так>) або false (хибно, або <ні>).

У розглянутих виразах використовувалася лише одна операція порівняння. Такі вирази називають простими. З простих логічних виразів за допомогою логічних операцій можуть створюватися складені.

У всіх мовах програмування реалізовано чотири логічні операції: not (<не>), and (<і>), or (<а6о>) та хог (<виключаюче або>). Ці операції ще називають відповідно операціями заперечення, кон’юнкції, диз’юнкції та строгої диз’юнкції. Результати виконання цих операцій над логічними виразами А і В, які набувають значень "істинно" та "хибно", наведені в таблиці. Така таблиця називається таблицею істинності. Ця таблиця є строгим математичним означенням зазначених логічних операцій.

З цієї таблиці бачимо, що результат операції and є істинним лише за умови, що обидва висловлювання А і В є істинними одночасно. Результат операції or буде істинним, якщо істинним буде хоча б одне з висловлювань А та В. Результат операції not е істиішим, якщо логічний вираз А е хибним, і, навпаки, хибним, якщо вираз А е істинним. Результат операції хог є істинним, лише тоді коли з двох висловлювань А та В буде істинним лише одне з них.

У складених логічних виразах установлено такий пріоритет операцій: not, and, or, хor. Першою з двох операцій одного пріоритету виконується та, яка у виразі розташована ліворуч. Операції, взяті в круглі дужки, виконуються першими. Наведемо приклад складеного логічного виразу:

 

На рисунку показано порядок виконання операцій у цьому виразі з припущенням, що змінні мають такі значення змігших:


У виразах, що містять арифметичні та логічні операції, а також операції порівняння, порядок їх виконання такий: заперечення (not); множення, ділення і кон’юнкція (and); додавання, віднімання і диз’юнкція (or) та строга диз’юнкція (хог); операції відношення (=. <>. <. <= >. >=).

Зауважимо, що вираз a>b or c>d с некоректним, оскільки згідно з правилами пріоритету першою мас бути виконана операція b or с. Правильний запис цього виразу такий: (a>b) or (c>d).

Приклад. Наведемо програму, яка дає змогу обчислювати значення представленого на рисунку логічного виразу, коли х, у, г мають різні значення.

Перетворення і спрощення логічних виразів здійснюється на основі тотожностей і законів булевої алгебри. Основні з них наведено нижче.

Усі наведені формули доводяться через визначення їх значень на основі прямого перебору всіх значень аргументів.

Перевіряємо себе

1. Які операції порівняння використовуються в логічних виразах?

2. Якого значення набуде логічний вираз х>=у, якщо х=3, у=5?

3. Які логічні операції застосовуються в логічних виразах?

4. Яким є порядок виконання операцій у виразі not а(а and b) or с ?

5. Який пріоритет мають операції порівняння, логічні та арифметичні операції?

Виконуємо

1. Нехай А і В логічні вирази. Які з наведених нижче пар складених логічних виразів рівнозначні?

а) not (A and В) A or В

б) not (A and В) (not A) or (not В)

в) not (A or В) A and В

г) not (A or В) (not A) and (not В)

д) (A and В) or ((not A) and (not В)) А=В

е) АоВ ((not A) and В) or (A and (not В))

е) A=B=true A and В

ж) A=B=true А=В

з) A=false false

и) (not (A or В)) and A (A or B) and (not B) and (not A)

i) (A or B) and (not B) A

Складіть програму для обчислення логічного виразу: ((not а) and b) or (a and(not b)).

12.3. Використання булевої алгебри для розв’язування логічних задач

Змістові логічні задачі можуть роз’язуватися різними способами, у тому числі засобами алгебри логіки. За цим способом вони розв’язуються в такій послідовності:

- детально вивчається умова задачі;

- логічні висловлювання позначаються логічними змінними;

- розробляється буловий вираз, у якому між усіма висловлюваннями встановлюються логічні зв’язки;

- визначається значения істинності булсвого виразу;

- робиться висновок про результат розв’язання задачі.

Приклад. У фінальному забігу учнів школи на 100 м взяли участь Антонов, Васько, Соломко і Дахов. Три вболівальниці, які спостерігали за змаганнями, дали такі прогнози:

— Ксеня: першим буде Дахов, другим - Васько;

— Марічка: першим буде Соломко, четвертим - Антонов;

— Світлана: другим буде Дахов, третім — Васько.

Після змагань з’ясувалося, що тільки одне із тверджень у кожному прогнозі було правильним. Які місця посіли учасники змагань?

Позначимо кожне із тверджень учасників прогнозу такими змінними:

Перший Дахов — В1;

Перший Соломко — СІ;

Другий Васько - В2;

Другий Дахов - Б2;

Третій Васько - ВЗ;

Четвертий Антонов — А4.

Оскільки одне із тверджень у кожному прогнозі правильне (істинне), можна записати:

Б1 V В2=1; СІ V А4=1; Б2 V В3=1.

Очевидно, що (Б1 V В2)(С1 V А4)(Б2 V В3)=1

Перетворимо цей вираз на такий: (БІСІ V Б1А4 V В2С1 V В2А4)(Б2 V Ь3)=1. Значення виразу БІСІ хибне, тому що за умовами змагань перше місце не можна присуджувати двом різним учасникам. Тому вираз можна записати так: (Б1А4 V В2С1 V В2А4)(Б2 V В3)=1. Перетворимо останній вираз на такий:

Б1А4Б2 V Б1А4ВЗ V В2С1Б2 V В2С1ВЗ V В2А4Б2 V В2А4ВЗ = 1.

Усі виокремлені жирним шрифтом вирази хибні. Наприклад, вираз Б1А4Б2 хибні тому, що Дахов не може одночасно посісти перше й друге місце, а вираз В2С1В2 - тому, що Васько і Дахов не можуть разом бути на другому місці. Таким чином, істинним е вираз Б1А4ВЗ, тобто першим був Дахов, другим — Соломко, третім - Васько, четвертим - Антонов.

Перевіряємо себе

1. У якій послідовності розв’язуються логічні задачі засобами алгебри логіки?

2. На основі яких даних робиться висновок про результат розв’язання задачі?

Виконуємо

1. Сім’я, збираючись на прогулянку, ввечері обговорює почутий прогноз погоди на завтра.

Батько. Якщо не буде вітру, то буде хмарно і без дощу.

Мати. Якщо буде дощ, то буде хмарно і без вітру.

Син. Якщо буде хмарно, то буде дощ і не буде вітру.

То ж якою за прогнозом завтра б}'де погода?

2. Троє завзятих уболівальників футболу перед початком сезону сперечалися про перспективи команд.

— "Ось побачите, "Шахтар" не стане першим, — сказала Наталя. -Першим буде "Динамо".

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

Петро, до якого звсрщ'вся Микола, обурився:

-"Динамо не бачити першого місця, а ось у "Металіста" найпотужніша команда".

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

3. Джону, Марго та О ліверу оголошено підозру в співучасті в пограбуванні банку. Викрадачі втекли на автомобілі, що чекав на них. На слідстві Джон дав свідчення, що злочинці зникли па синьому "Запорожці", Марго сказала, що це були чорні "Жигулі", а Олівср стверджував, що це була "Нива" і не синя. Щоб заплутати слідство, кожен із них вказав правильно або марку машини, або тільки її колір. Якого кольору і якої марки була машина?

4.  Петрик, Василько і Марійка залишились удома самі. Хтось із них змінив пароль на комп’ютері. Коли мама запитала, хто це зробив, вони сказали:

Петрик: "Я не змінював. Марійка теж не змінювала".

Василько: "Марійка справді не змінювала. Це зробив Петрик".

Марійка: "Василько обманює. Це він змінив".

Після додаткових запитань з’ясувалося, що двоє дітей двічі сказали правду, а третя дитина — один раз обманула, а один раз сказала правд}'.

Хто змінив пароль?

Хтось із трьох — Ледачий, Байдужий чи Безвідповідальний — забув вимкнути світло в офісі, внаслідок чого фірмі нарахували штраф.

У ході службового розслідування кожен із них зробив дві заяви. Безвідповідальний: "Я цього не робив. Це зробив Байдужий". Ледачий: "Байдужий не винен. Це зробив Безвідповідальний".

Байдужий: "Я цього не робив. Ледачий цього не робив". У результаті службового розслідування з’ясувалося, що один із них двічі збрехав, другий двічі сказав правду, а третій — один раз збрехав, а другий раз

сказав правду. Хто повинен компенсувати фірмі збитки?

Завдання

1. Скласти таблицю істинності для логічних виразів:

а) не А або В; б) або не В і С

2. Побудувати логічний вираз для розв’язування задачі. Розв’язати задачу.

За підсумками першості школи з шахів кращими стали Нестор, Михайло, Люба та Руслан. Перед початком змагань палкі прихильники шахів висловили припущення, щодо розподілу місць. Перший сказав, що переможе Нестор, а Михайло стане другим. Дрз'гий прихильник друге місце віддав Любі, а Русланові - четверте. Третій не погодився з двома попередніми. Він спрогиозував, що Руслан посяде третє місце, а Нестор буде четвертим. Після завершення змагань з’ясувалось, що кожен із прихильників був правий лише в одному зі своїх прогнозів. Як розподілились місця між чотирма учасниками?

Для допитливих

Корені математичної логіки сягають глибокої давнини. Першим до створення її наукових основ наблизився німецький учений Г.В. Лейбніц (1646-1716), який указав шлях для перетворення логіки "зі словесного царства, повного иевизпаченостей, на царство математики, де відношення між об’єктами або висловлюванями визначаються абсолютно точно".

Значного успіху в перетворенні логіки на математичну науку досяг у 1847 році англійський математик Джордж Будь, який розробив

алгебру логіки, пізніше названу на його честь булевою алгеброю. Дж. Буль розробив систему позначень і правил, яку можна застосовувати до ВСІХ об’єктів, у тому ЧИСЛІ буКВ, цифр і речень. За допомогою цієї системи можна кодувати висловлювання символами мови, до яких можна застосовзшати введені ним операції: кон’юнкції (І — AND), диз’юнкції (АБО - OR), заперечення (НІ - NOT).

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

 

Словничок

 

Логіка

— наука про загальні закони розвитку об’єктивного світу й пізнання їх.

Поняття

— форма висловлювання, яким виокремлюються і означуються найвагоміші ознаки предмета або класу предметів.

Твердження

— форма мислення, яка дає змогу на основі одного або кількох твсрджень-посилаиь отримати нове судження (значення або висновок).

Предикати

— твердження, що містять змінні.

 

Це матеріал з підручника Інформатика 8 клас (поглиблений рівень) Гуржій

 

Категорія: Інформатика

Автор: admin от 15-12-2016, 12:02, Переглядів: 3873