Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Навчальний посібник
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
«ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Я.П. Романчук
ДИСКРЕТНА МАТЕМАТИКА
Конспект лекцій
Розглянутий на засіданні кафедри АСУ
як навчальний посібник для студентів
базового напрямку 050101 «Комп’ютерні науки»
денної та заочної форм навчання (протокол № 1-10/11 від 31 серпня 2010 р.)
Львів − 2010
УДК 519.1+519.6
Я.П. Романчук. Дискретна математика: Конспект лекцій для студентів напряму комп’ютерні науки спеціальності Інформаційні управляючі системи та технології. – Львів: НУЛП, 2010. – 210 с.
У конспекті викладено теорію множин і відношень; алгебру логіки і алгебру логіки висловлень і предикатів, теорію графів, моделі алгоритмів і програм, формальні граматики й мови, основи теорії кодування та шифрування.
Кожен розділ складається з основних визначень, властивостей, операцій і теорем; має значну кількість розв’язаних і ілюстрованих прикладів з об’єктами дискретної природи; містить вправи для аудиторної та самостійної роботи студентів.
Конспект лекцій може бути корисним для студентів інших спеціальностей, які бажають вивчати методи дискретної математики для використання їх у природничих і гуманітарних науках із залученням інформаційних технологій.
Рецензент:
І.М. Дронюк, кандидат фізико-математичних наук, доцент кафедри АСУ.
Відповідальна за випуск:
З.Я. Шпак, кандидат технічних наук, доцент кафедри АСУ.
Лекція 2
3. ЛОГІКА ВИСЛОВЛЕНЬ
Логіка, як наука про закони людського мислення бере початок від грецького філософа Аристотеля. Ідеї побудови логіки на математичній основі вперше були запропоновані німецьким математиком Г. Лейбніцом. Пізніше англієць Д. Буль створив алгебру висловлень, у якій висловлення позначені буквами.
3.1. Основні означення.
Означення 3.1. Висловлення – це розповідне речення, про яке можна сказати, що воно істинне або хибне. Істинність або хибність, приписувані висловленню, називаються його істиннісним значенням.
Наприклад, речення «Сонце – це зірка», «Балаклава – обласний центр України», «Карась – не риба» є висловленнями, причому перше – істинне, а друге й третє – хибні. А речення «котра година?», «вивчіть вірш» не є висловленнями.
У математичних міркуваннях і повсякденній мові часто зустрічаються речення, що утворені видозміною деякого речення з використанням слова не, або складені із простих речень з використанням сполучників: і, або, якщо … то, тоді і тільки тоді, коли. Ці сполучники називаються сентенційними сполучниками. На відміну від повсякденної мови, у математичній логіці зміст таких висловлень може бути визначений однозначно.
Означення 3.2. Висловлення, що не містить сполучників, називається простим (елементарним); висловлення, що містить сполучники, називається складним.
Висловлення будемо позначати буквами латинського алфавіту , , , , , … . Розглянемо наступні прості висловлення:
«я прокидаюся рано»;
«я йду на роботу».
З використанням п’яти сентенційних сполучників можна утворити наступні складні висловлення:
заперечення – це речення, видозмінене з використанням слова не; воно позначається як , . Наприклад,
«я не прокидаюся рано»;
кон’юнкція – це речення, котре утворюється з’єднанням двох простих речень із використанням слова і; позначається як . Наприклад,
«я прокидаюся рано і йду на роботу»;
диз’юнкція це речення, що утворене з’єднанням двох простих речень з використанням слова або; вона позначається як . Наприклад,
«я прокидаюся рано або не йду на роботу»;
імплікація це речення, яке утворене з’єднанням двох простих речень з використанням слів якщо … то; позначається як . Наприклад, »
«якщо я прокидаюся рано, то йду на роботу»;
еквівалентність це речення, утворене з’єднанням двох простих речень з використанням слів тоді і тільки тоді, коли; позначається як . Наприклад,
«я прокидаюся рано тоді і тільки тоді, коли йду на роботу».
Означення 3.3. Символи називаються бінарними з’єднаннями, тому що вони з’єднують два висловлення, а символ ~ унарним з’єднанням, тому що застосовується тільки до одного висловлення.
Є ще одне бінарне з’єднання – що виключає або (нерівнозначність, додавання за модулем 2). Позначається як , читається як «або або ». Висловлення істинне тоді, коли істиннісні значення і не збігаються, і хибне – у протилежному випадку.
Приклад 3.1. Представити логічними формулами наступні висловлення:
«Сьогодні не світить сонце»;
«Я піду гуляти або залишуся вдома»;
«Спортсмен здобув перемогу і одержав заслужену нагороду»;
«Якщо цех перевиконає план, то робітники одержать премії»;
«Сім’ю варто створювати тоді і тільки тоді, коли між молодими людьми є почуття любові та поваги»;
«На вулиці ясно або похмуро»;
«Якщо парубок зневажає фізичними вправами або годинами сидить за комп’ютером, то це спричиняє погіршення його самопочуття та формує погану поставу».
Розв’язок:
1) Висловлення «Сьогодні не світить сонце» утворене запереченням висловленню «Сьогодні світить сонце». Останнє позначимо через , тоді початкове висловлення є складним, його представимо логічною формулою: .
2) Складне висловлення «Я піду гуляти або залишуся вдома» утворене із двох простих, з’єднаних сполучником «або»:
«Я піду гуляти»;
«Я залишуся вдома». Отже, маємо логічну формулу .
3) Складне висловлення «Спортсмен здобув перемогу і одержав заслужену нагороду» утворене із двох простих, з’єднаних сполучником «і»:
«Спортсмен здобув перемогу»;
«Спортсмен одержав заслужену нагороду». Отже, маємо логічну формулу .
4) Складне висловлення «Якщо цех перевиконає план, то робітники одержать премії», утворене із двох простих, з’єднаних логічним сполучником «якщо … то»:
«Цех перевиконає план»;
«Робітники одержать премії». Отже, маємо логічну формулу .
5) Складне висловлення «Сім’ю варто створювати тоді і тільки тоді, коли між молодими людьми є почуття любові й поваги» утворене із трьох простих, які з’єднані логічним сполучником «тоді і тільки тоді» і сполучником «і»:
«Сім’ю варто створювати»;
«Між молодими людьми є почуття любові»;
«Між молодими людьми є почуття любові й поваги». Отже, маємо логічну формулу .
6) Складене висловлення «На вулиці ясно або похмуро» утворене із двох простих:
«На вулиці ясно»;
«На вулиці похмуро», з’єднаних сполучником «або», очевидно в розділовому змісті, тобто «що виключає або» , тому що одночасно на вулиці не може бути і ясно, і похмуро. Отже, маємо логічну формулу: .
7) Складне висловлення «Якщо парубок зневажає фізичними вправами або годинами сидить за комп’ютером, то це спричиняє погіршення його самопочуття і викликає погану поставу» розіб’ємо на прості:
«Парубок зневажає фізичними вправами»;
«Парубок годинами сидить за комп’ютером»;
«Виникає погіршення самопочуття»;
«Виникає погана постава».
Логічна формула, що описує таке висловлення, буде мати вигляд:
.
Прості висловлення можуть бути істинними або хибними незалежно одне від другого, але вони визначають значення складного висловлення.
Таблиці істинності для розглянутих вище логічних формул дозволяють легко визначити значення складного висловлення.
Заперечення
Кон’юнкція
Диз’юнкція
Імплікація
Еквівалентність
1
0
1
1
1
1
1
1
0
1
1
0
0
1
0
0
0
1
0
1
1
0
0
0
0
0
1
1
Висловлення істинне, коли висловлення хибне, і хибне – у протилежному випадку. Наприклад, якщо «сьогодні холодно», то «сьогодні не холодно».
Висловлення істинне, коли обидва висловлення істинні, і хибне – у всіх інших випадках. Прикладом кон’юнкції може бути відповідь на питання: «За яких умов учень, що закінчує школу, може бути студентом?». Якщо прийняти за «одержати атестат зрілості», а за «пройти конкурсний відбір до ВНЗ», то учень буде студентом тоді, коли одержить атестат зрілості і пройде конкурсний відбір
Висловлення хибне в тому випадку, коли обидва з простих висловлень хибні, і істинне в усіх інших випадках. Як приклад, розглянемо наступні висловлення: «на вулиці йде дощ», «хтось забув виключити душ». Тоді «я чую шум води». Це можливе, якщо на вулиці йде дощ, або якщо хтось забув виключити душ, або при виконанні цих двох умов.
Висловлення хибне, якщо істинне, а хибне; і істинне у всіх інших випадках. Висловлення «якщо … то» має пояснюючий характер. Пояснюючий характер імплікації пов’язаний із причинно-наслідковим відношенням, при якому виступає в ролі (по)дії (посилки імплікації), а наслідку (висновку). Якщо «на вулиці йде дощ», а «над моєю головою розкрита парасолька», тоді «я залишуся сухим» буде помилковим тільки в тому випадку, якщо на вулиці йде дощ, а парасолька не розкрита .
Висловлення істинне, коли значення і збігаються, і хибне – у протилежному випадку. Оскільки еквівалентність виражається через кон’юнкцію двох імплікацій , то це відношення виникає при одночасному виконанні двох умов: «із випливає » і «із випливає ».
Приклад. Присвоїмо висловленням і значення 1, якщо і означають «дочка», і 0, якщо і означають «син». Тоді складне висловлення «у сім’ї одностатеві діти» істинне тоді і тільки тоді, коли або , або .
Для запису складних висловлень у символічній формі часто виникає необхідність у використанні великої кількості дужок. Щоб усунути цю незручність вводять деякі домовленості. Домовимося, що є найсильніше сполучення (тобто тотожність має найбільшу область дії), а за нею йде . Далі – рівносильні і , а потім ~ найслабше сполучення. Необхідно пам’ятати, що спочатку виконуються слабші сполучення, а потім більш сильні.
Якщо істиннісні значення простих компонентів відомі, то істиннісне значення складного висловлення може бути визначене з використанням таблиць істинності.
Приклад 3.2. Визначити істиннісне значення висловлення
,
якщо і істинні , а хибне .
Розв’язок: Істиннісне значення висловлення можна швидко знайти, якщо написати під кожним простим висловленням його істиннісне значення, а істиннісне значення кожного складного висловлення – під відповідним сполученням. Для зручності читання послідовні кроки можуть бути записані один під іншим:
А
В
С
А
В
С
1
1
0
1
1
0
0
1
0
0
1
0
Звідси можемо зробити висновок: дане висловлення хибне.
Складне висловлення може приймати як істинне, так і хибне значення, залежно від значень, приписуваним простим компонентам. Для того, щоб однозначно вказати ті ситуації, коли складне висловлення є істинним, необхідно врахувати всі можливі ситуації. З цією метою ми будемо будувати таблиці істинності складних висловлень, використовуючи таблиці істинності простих компонентів. Наведемо два еквівалентних способи побудови таблиці істинності складного висловлення. Перший полягає в тому, що складне висловлення ми розбиваємо на прості, і встановлюємо істинне значення кожного сполучення. А при другому способі ми записуємо істиннісні значення під кожним сполученням. Проілюструємо обидва підходи на прикладі.
Приклад 3.3. Побудувати таблицю істинності висловлення .
Розв’язок: Побудуємо таблицю істинності двома способами:
1
1
1
0
1
1
1
1
1
0 1 1
1
1
0
0
1
0
1
1
0
0 1 0
1
0
1
0
1
1
1
0
1
0 1 1
1
0
0
0
1
0
1
0
0
0 1 0
0
1
1
1
1
1
0
1
1
1 1 1
0
1
0
1
1
0
0
1
0
1 1 0
0
0
1
1
0
0
0
0
1
1 1 0
0
0
0
1
0
0
0
0
0
1 1 0
Необхідно відзначити важливість розходження між мовою і метамовою, між об’єктними і суб’єктними висловленнями. Якщо знехтувати цими розходженнями, то можна прийти до протиріччя, так званого логічного парадоксу. Наведемо приклад відомого парадоксу. Англійський логік Бертран Рассел розглянув таку притчу: «В одному селі жив перукар. Він голив усіх тих жителів села, хто не голився сам». Рассел задався питанням: чи може перукар поголити самого себе? Його міркування наступні: якщо перукар захоче поголитися сам, то як житель цього села, що голиться сам, він не повинен це робити; але якщо перукар не стане голитися, то вже як житель села, що не голиться сам, він буде зобов’язаний себе поголити.
Викладемо зміст цього протиріччя формальною мовою. Позначимо перукаря, а жителя села. Нехай висловлення означає « голить ». Тоді ситуація в селищі може бути описана двома метависловлюваннями:
якщо , то ;
якщо , то .
Коли перукар розглядається як рядовий житель села , то обидва метависловлювання стають внутрішньо суперечливими:
якщо , то ;
якщо , то .
Звідси ми можемо зробити висновок, що незважаючи на те, що , як і , є об’єктною змінною, її не можна ставити на один рівень із , оскільки саме відносно були сформульовані всі метависловлювання. Як висловлення можна розглядати будь-які з відомих нам ситуацій: « вчить »; « співає для »; …, при цьому під розуміємо вчителя, артиста, і т.п.
Вправи:
1. Які з наступних пропозицій є висловленнями? Вкажіть їх істиннісне значення:
а) Сьогодні − вівторок. б) На вулиці мороз.
в) Як пройти до бібліотеки? г) Все наше життя − гра!
д) У тайзі субтропічний клімат. е) Гамлет − принц датський.
ж) Як поживаєш? з) А чи не піти нам до лісу?
і) На городі бузина, а в Києві дядько.
2. Нехай , і позначають наступні висловлення:
«Я поїду влітку до Криму»;
«Я хочу поїхати до Криму»;
«У мене є гроші».
Записати в символьній формі наступні висловлення:
а) «Я хочу поїхати до Криму і я поїду влітку до Криму»;
б) «У мене немає грошей, тому я не поїду влітку до Криму»;
в) «У мене є гроші, але я не хочу їхати до Криму, і я не поїду влітку до Криму»;
г) «Я поїду влітку до Криму тоді і тільки тоді, коли у мене є гроші і я хочу поїхати до Криму».
3. Нехай , і означають наступні висловлення:
«Я вчуся за контрактом»;
«Я здам сесію вчасно»;
«Я одержу стипендію».
Записати в символьній формі наступні висловлення:
а) «Я не здам сесію вчасно»;
б) «Якщо я вчуся за контрактом, то не одержую стипендію»;
в) «Якщо я не вчуся за контрактом і здам сесію вчасно, то одержу стипендію»;
г) «Якщо я не вчуся за контрактом і не одержую стипендії, то сесію я здав невчасно»;
д) «Я одержу стипендію тоді і тільки тоді, коли я вчасно здам сесію і я не вчусь за контрактом».
4. Нехай , , , і позначають наступні висловлення:
«Я живу в маленькому місті»;
«У нашому місті є театр»;
«Я люблю театр»;
«У мене є вільний час»,
«Я можу ходити до театру щодня».
Записати в символьній формі наступні висловлення:
а) «У мене немає вільного часу і я не можу ходити до театру щодня»;
б) «Я живу в маленькому місті, і в ньому немає театру, тому я не можу ходити до театру щодня»;
в) «Я не люблю театр або в мене немає вільного часу, тому я не можу ходити до театру щодня»;
г) «У нас у місті є театр, я люблю театр і можу ходити до театру щодня»;
д) «Я можу ходити до театру щодня тоді і тільки тоді, коли в нашому місті є театр, я люблю театр і у мене є вільний час».
5. Нехай , і позначають наступні висловлення:
«Я працюю в солідній фірмі»;
«Я одержую високу зарплату»;
«Я займаю високу посаду».
Інтерпретуйте наступні висловлення як звичайні пропозиції:
а) ; б) ;
в) ; г) .
6. Нехай , і позначають наступні висловлення:
«Я люблю грати в комп’ютерні ігри»;
«У мене є комп’ютер»;
«У мене є час для ігор».
Інтерпретуйте наступні висловлення як звичайні пропозиції:
а) ; б) ;
в) ; г) .
7. Побудуйте таблиці істинності для висловлень у вправах 2 6.
8. Запишіть у символьній формі наступні складні висловлення:
а) «Якщо конкуренція серед виробників товарів народного споживання висока, то для залучення потенційних покупців фірмі-виробникові необхідно: підвищувати якість товару; грамотно вирішувати питання цінової політики; проводити акції;
б) «Для того щоб стати заможним, парубок може виграти велику суму коштів в казино або одержати роботу з високим заробітком. Якщо парубок задумає розбагатіти, граючи в казино, він ризикує програти все і стати жебраком. Якщо парубок вирішив зробити кар’єру, то йому необхідно одержати гарну освіту, багато працювати над собою, добре зарекомендувати себе. Робота з високою заробітною платнею − шлях до заможного життя»;
в) «Я хочу зробити подарунок Антону: комп’ютерні диски або квитки в кіно. Якщо я подарую Антону диски з новими комп’ютерними іграми, то Антон буде грати на комп’ютері всю ніч. Якщо Антон буде грати на комп’ютері всю ніч, він дуже втомиться, і я не зможу його побачити завтра. Я зможу завтра побачити Антона тільки тоді, коли подарую йому квитки в кіно.»
9. Знайти істиннісне значення кожного з наступних висловлень:
а) , якщо , , ;
б) , якщо , , ;
в) , якщо , , ;
г) , якщо , , ;
д) , якщо , , .
10. Скласти істиннісну таблицю для кожного з наступних висловлень:
а) ;
б) ;
в) ;
г) ;
д) .
3.2. Істиннісна функція
Обчислення висловлень призначене для аналізу логічних зв’язків між реченнями, які залежать тільки від побудови нових речень із вихідних з використанням уже відомих нам сентенційних сполучників. Для такого аналізу необхідна наявність вихідної непорожної множини простих речень і виконання наступних допущень:
а) кожне просте речення є висловленням, тобто кожному простому реченню можна поставити у відповідність його істиннісне значення;
б) кожне з висловлень, які аналізуємо, складається із простих висловлень багаторазовим використанням сентенційних сполучників і приймає істиннісне значення, випливаючи з наведених раніше таблиць істинності для сентенційних сполучень, відповідно до істиннісних значень простих речень-висловлень.
Отже, нехай нам дана непорожна множина простих висловлень , ,… Розширимо цю множину, приєднавши до неї всі ті висловлення, які можна утворити із простих, багаторазово і усілякими способами використовуючи різні сентенційні сполучники. Тобто, елементами розширеної множини будуть: ; ; ; ;… Елементи цієї множини називають формулами, причому елементи вихідної множини – простими формулами (або компонентами), а інші – складними формулами.
Кожній простій формулі ставиться у відповідність один елемент із множини . Істиннісне значення складної формули визначається у відповідності із таблицями істинності для заперечення, диз’юнкції, кон’юнкції, імплікації і еквівалентності.
Якщо простими компонентами формули служать , , …, , то для Означення істиннісного значення формули по істиннісним значенням простих компонентів , , …, , необхідно побудувати таблицю істинності, що складає з рядків.
Означення 3.4. Істиннісна функція – це функцій від аргументів, кожний із яких може приймати значення 1 або 0, і сама функція може приймати значення 1 або 0.
Позначати істиннісні функції будемо як , і т.д.
Під істиннісними функціями будемо розуміти елементи множини , що має наступні властивості:
а) кожна з функцій , , , , елемент множини ;
б) якщо функція елемент множини , то елементом множини буде і функція, отримана підстановкою в якості змінної в кожну з функцій, перерахованих вище.
Як приклади, можна навести наступні істиннісні функції: , , …
3.3. Еквівалентні висловлення. Тавтології.
Особливу увагу при обчисленні висловлень треба звертати на складні висловлення, що мають різну побудову, але приймають істинне значення в однакових випадках, тобто вони мають однакові таблиці істинності. Такі висловлення називають логічно еквівалентними. Наприклад, нехай «на вулиці холодно», «я легко одягнений». Розглянемо висловлення «невірно, що на вулиці холодно і я легко одягнений» і висловлення «на вулиці не холодно або я не легко одягнений» . Побудуємо таблиці істинності:
1
1
0
0
1
0
1
1
0
1
1
1
0
0
1
1
Як видно, в усіх чотирьох рядках істиннісні значення складних формул збігаються, отже, два розглянутих висловлення – логічно еквівалентні.
Логічно еквівалентні висловлення і позначають як eq .
З умовним висловленням – імплікацією зв’язані ще три типи висловлень: конверсія, інверсія і контрапозиція. Вони визначаються таким чином:
імплікація; конверсія висловлення ;
інверсія висловлення ;
контрапозиція висловлення .
Приклад 3.4. Нехай задане таке висловлення-імплікація «Якщо він їсть вітаміни, то він здоровий», тоді:
«Якщо він здоровий, то він їсть вітаміни» конверсія;
«Якщо він не їсть вітаміни, то він не здоровий» інверсія;
«Якщо він не здоровий, то він не їсть вітаміни» контрапозиція.
При побудові висловлення-імплікації і пов’язаних із ним конверсії, інверсії і контрапозиції важливий не порядок слів у висловленні, а те, яка частина висловлення є частиною «якщо», а яка − частиною «то».
Закон контрапозиції твердить, що імплікація і його контрапозиція логічно еквівалентні, у чому можна легко переконатися, порівнявши їхні таблиці істинності. Еквівалентність і контрапозиція умовних висловлень мають у математиці велике значення, оскільки часто набагато простіше довести теорему від оберненого, ніж дати її пряме доведення. Неважко також показати, що конверсія і інверсії імплікації також мають однакові таблиці істинності, а, отже, − еквівалентні. У той же час імплікація (або її контрапозиція) і конверсія (або інверсія) мають різні таблиці істинності. Нерозуміння цього факту приводить до побудови помилкових логічних міркувань.
Означення 3.5. Висловлення, істинне при всіх розподілах простих компонентів, називається логічно істинним, загальнозначущим або тавтологією. Висловлення, хибне при всіх розподілах простих компонентів, називається логічно хибним або протиріччям.
Добре відомим нам прикладом тавтології є аксіоми і теореми в математиці, оскільки вони істинні завжди.
Маючи логічно істинне висловлення – тавтологію, легко побудувати логічно хибне висловлення – протиріччя. Для цього досить взяти заперечення тавтології. Якщо тавтологія, то протиріччя.
Для того щоб вирішити питання про те, що дана формула є тавтологією чи ні, треба розглянути її таблицю істинності. Дійсно, формула є тавтологією тоді і лише тоді, коли її істиннісне значення дорівнює 1 при кожному із приписаних простим компонентам формули значенням 1 або 0.
Приклад 3.5. Чи є висловлення тавтологією?
Розв’язок: Розглянемо таблицю істинності даного висловлення:
1
1
1
1
1
1
0
0
0
1
0
1
0
1
1
0
0
0
1
1
Як випливає з таблиці істинності, при кожному з розподілі значень простих компонентів, формула, що описує це висловлення, приймає значення 1. Отже, розглядуване висловлення є тавтологією.
Незважаючи на те, що метод установлення загальної значимості формул з використанням дослідження їхніх таблиць істинності громіздкий і стомливий, він завжди дає відповідь на поставлене питання.
Нижче представимо список деяких тавтологій. Їх запам’ятовувати немає необхідності, оскільки цей список буде використовуватися нами як довідковий матеріал. Для самостійної роботи студентам може бути запропоновано перевірити представлені тавтології шляхом побудови їхніх таблиць істинності.
Тавтологічні імплікації:
1. ; 8. ;
2. ; 9. ;
3. ; 10. ;
4. ; 11. ;
5. ; 12. ;
6. ; 13. ;
7. ; 14. .
Тавтологічні еквіваленції:
15. ; 17. ;
16. ; 18. ;
19. ; 20. ;
21. ; 21а. ;
22. ; 22а. ;
23. ; 23а. ;
24. ; 24а. ;
25. ; 25а. ;
Тавтологїі для виключення зв’язувань:
26. ; 30. ;
27. ; 31. ;
28. ; 32. .
29. ;
Замість того, щоб для обчислення істиннісного значення формули, користуватися таблицями істинності, можна вдатися до арифметичних процедур. Для цього приймають деякі угоди, а саме:
1. Формула інтерпретується як істиннісна функція, де кожен простий компонент розглядається як змінна, котрій можна приписати значення 1 або 0.
2. Суми і добутки доданків і співмножників 1 і 0, що входять у формули, обчислюються як у звичайній арифметиці, за винятком 1+1=0.
Легко перевірити (з використанням таблиць істинності), що основні істиннісні функції задаються наступними формулами:
; ; ;
; .
У цих термінах тавтологіями є ті істиннісні функції, які тотожно рівні нулю.
Приклад 3.6. Довести, що формула є тавтологією, не використовуючи таблицю істинності.
Розв’язок: Виконаємо ряд перетворень:
;
. Але , то другий і третій доданки дорівнюють нулю, отже, . Далі, , оскільки . Отже, задана формула є тавтологією.
Зауважимо, що в даній алгебрі і тотожно дорівнюють нулю, що істотно полегшує спрощення довгих виразів.
Вправи:
1. Для заданого висловлення сформулюйте конверсію, інверсію і контрапозицію:
а) «Якщо мені вдасться укласти вигідну угоду, то фірма виплатить мені премію»;
б) «Якщо парубок одержав паспорт, то він повнолітній»;
в) «Якщо я не буду працювати, то я не буду мати що їсти»;
г) «Якщо я не здам сесію, то мене відрахують із інституту»;
д) «Якщо ти маєш гарну освіту, то в тебе великі шанси зробити блискучу кар’єру».
2. Перевірити, чи є наступні висловлення еквівалентними:
а) і ; б) і ;
в) і ; г) і ;
д) і ?
3. Перевірити тавтологічні імплікації:
а) використовуючи таблиці істинності;
б) не використовуючи таблиці істинності.
4. Перевірити тавтологічні еквіваленції:
а) використовуючи таблиці істинності;
б) не використовуючи таблиці істинності.
5. Перевірити тавтології для виключення сполучень:
а) використовуючи таблиці істинності;
б) не використовуючи таблиці істинності.
3.4. Основні схеми побудови логічно правильних міркувань.
Логічний наслідок.
Вивчаючи математику, ми найчастіше стикаємося з теоремами та їхніми доведеннями. При цьому теореми є істинними твердженнями. У математичних системах вся необхідна інформація повинна утримуватися в аксіомах і раніше доведених теоремах. Розвиваючи конкретний розділ знань, можна не включати в його розгляд всі аксіоми і раніше доведені теореми. Замість цього доведені теореми можна прийняти за аксіоми. Важливим є те, щоб логічні правила, які використають для виведення нових теорем із аксіом і раніше доведених теорем, не породжували як теореми хибні висловлення. Ці логічні правила називаються правилами висновку або схемами логічно правильних міркувань.
Означення 3.6. Одержання нових знань із уже наявних, виражених у формі висловлення, називається умовиводом або міркуванням. При цьому вихідні висловлення, твердження називаються гіпотезами або засновками, а одержувані – висновком або логічним наслідком.
Означення 3.7. Правильним умовиводом називається таке міркування, висновок (логічний наслідок) якого є істинний щораз, коли істинні його гіпотези.
Умовивід звичайно представляють у вигляді
.
Тут: гіпотези, висновок, а символ «» означає «отже».
Правильність (або істинність) побудованого умовиводу можна перевірити двома способами, а саме:
з використанням таблиці істинності можна показати, що висновок істинний щоразу, коли істинні гіпотези;
з використанням логічних правил можна довести істинність висновку.
При перевірці правильності міркувань з використанням таблиць істинності, варто звернути увагу на те, що міркування з посилками висновком істинне тоді й тільки тоді, коли висловлення
є тавтологія, при цьому порядок проходження посилок не важливий.
Існує й інший підхід до перевірки логічності складного міркування на основі використання таблиці істинності. Необхідно пам’ятати, що умовивід є істинним, якщо одиниці наслідку накривають усі одиниці узагальненої посилки , що є кон’юнкцією всіх гіпотез .
Перелічимо деякі, найпоширеніші правила висновку (схеми логічно правильних міркувань):
1. Правило відділення (Modus Ponens):
«Якщо з висловлення випливає висловлення і висловлення істинне, то істинне і ».
2. Правило заперечення (Modus Tollens):
«Якщо із випливає , але висловлення хибне, то хибне й ».
3. Правила ствердження-заперечення (Modus Ponendo-Tollens):
«Якщо істинне або висловлення , або висловлення (у розділовому змісті) і істинне одне з них, то інше хибне».
4. Правила заперечення-ствердження (Modus Tollen-Ponens):
а)
«Якщо істинне або висловлення , або висловлення (у розділовому змісті) і хибне одне з них, те істинне інше»;
б)
«Якщо істинне висловлення , або висловлення (у нерозділовому змісті) і хибне одне з них, то істинне інше».
5. Правило силогізму (правило транзитивності):
«Якщо із випливає , а із випливає
19.02.2013 18:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора