Числення висловлень і алгебра висловлень. Основні проблеми числення висловлень - реферат українською
Довільну формулу F числення висловлень можна змістовно інтерпретувати як складене висловлення, істинність або хибність якого залежить від істинності елементарних висловлень, що до нього входять. Таким чином, кожній формулі F числення висловлень можна аналогічно тому, як це було зроблено в алгебрі висловлень, поставити у відповідність функцію істинності f.
Виникає питання, як пов’язано таке змістовне «істинносне» тлумачення (інтерпретація) формул числення висловлень з їхньою формальною вивідністю.
Теорема 5.5. Будь-яка теорема числення висловлень ЧВ є тотожно істинним висловленням (тавтологією).
Доведення. Тотожна істинність усіх аксіом легко перевіряється безпосередньо побудовою відповідних таблиць істинності для кожної з них (рекомендуємо це зробити самостійно).
Відтак, доведемо, що обидва правила виведення числення висловлень перетворюють тотожно істинні формули у тотожно істинні.
Якщо A(p1,p2,...,pn) - тотожно істинна формула, то для довільного набору значень a1,a2,...,an її пропозиційних змінних A(a1,a2,...,an) є істинною. Отже, тотожно істинною буде і будь-яка формула A, що отримується з формули A шляхом підстановки замість пропозиційних змінних p1,p2,...,pn довільних формул B1,B2,.....,Bn, оскільки останні можуть набувати лише значень 0 або 1.
Доведемо, що коли формули A і AB є тотожно істинними, тоді формула B, яку ми дістаємо з них за правилом висновку, також є тотожно істинною. Припустімо супротивне: нехай B не є тотожно істинною формулою, тобто існує набір значень її змінних, на якому вона набуває значення 0. Тоді підставимо цей набір у формулу AB, оскільки A є тавтологією, то дістанемо вираз 10, значенням якого є 0. Останнє суперечить припущенню про тотожну істинність формули AB.
Таким чином, ми переконалися в тому, що всі аксіоми числення висловлень ЧВ є тотожно істинними формулами алгебри висловлень, а застосування обох правил виведення (підстановки і висновку) до тотожно істинних формул знову приводить до тотожно істинних формул. Отже, всі вивідні формули (теореми) числення висловлень є тотожно істинними формулами алгебри висловлень.
Справедливою є й обернена теорема, яку подамо без доведення.
Теорема 5.6. Будь-яка тотожно істинна формула алгебри висловлень є теоремою числення висловлень ЧВ.
Дві останні теореми дозволяють вирішити три важливі проблеми числення висловлень: проблему несуперечності, проблему повноти і проблему розв’язності. Розглянемо їх послідовно.
1. Проблема несуперечності.
Для кожної формальної теорії кардинальним є питання несуперечності. Справді, така теорія будується послідовним приєднанням нових теорем, які формально виводять з аксіом за допомогою правил виведення. Отже, немає жодної гарантії, що в цьому процесі ми не дійдемо до суперечності. Iнакше кажучи, виникає питання, чи при поступовому нагромадженні теорем формальної теорії (числення) не трапиться так, що одна з теорем суперечитиме іншим. Саме так виникає проблема несуперечності числення.
Числення є несуперечним, якщо неможливо одночасно вивести з аксіом числення як формулу A, так і її заперечення A.
Наслідок 5.1. Числення висловлень ЧВ є несуперечною формальною теорією.
Справді, якщо формула A вивідна у численні висловлень, то формула A не може бути вивідною, бо за теоремою 5.5 формула A є тотожно істинною в алгебрі висловлень, а формула A - тотожно хибною. Отже, A не може бути теоремою числення висловлень ЧВ.
2. Проблема повноти.
Iнша проблема, що виникає при дослідженні різних числень висловлень: чи будь-яка тотожно істинна формула алгебри висловлень буде вивідною в заданому численні? Це питання й являє собою проблему повноти для числення висловлень.
Смисл такої постановки питання полягає в тому, що при побудові числення потрібно знати, чи достатньо аксіом і правил виведення даного числення для того, щоб можна було вивести будь-яку формулу, яка в змістовному розумінні є тотожно істинною.
Наслідок 5.2. Числення висловлень ЧВ є повним.
Справедливість цього твердження безпосередньо випливає з теореми 5.6.
У математичній логіці існує й інше поняття повноти системи аксіом (або числення), що грунтується на неможливості доповнення системи аксіом будь-якою формулою, яку не можна вивести з даних аксіом.
3. Проблема розв’язності.
Розв’язувальним методом для формальної теорії T називають метод, за допомогою якого для довільної формули A з T можна за скінченне число кроків визначити, чи буде A теоремою, чи ні.
Числення T називають розв’язним, якщо для T існує розв’язувальний метод, у противному разі - формальна теорія T є нерозв’яною.
Наслідок 5.3. Числення висловлень ЧВ є розв’язною теорією.
Виникає питання, як пов’язано таке змістовне «істинносне» тлумачення (інтерпретація) формул числення висловлень з їхньою формальною вивідністю.
Теорема 5.5. Будь-яка теорема числення висловлень ЧВ є тотожно істинним висловленням (тавтологією).
Доведення. Тотожна істинність усіх аксіом легко перевіряється безпосередньо побудовою відповідних таблиць істинності для кожної з них (рекомендуємо це зробити самостійно).
Відтак, доведемо, що обидва правила виведення числення висловлень перетворюють тотожно істинні формули у тотожно істинні.
Якщо A(p1,p2,...,pn) - тотожно істинна формула, то для довільного набору значень a1,a2,...,an її пропозиційних змінних A(a1,a2,...,an) є істинною. Отже, тотожно істинною буде і будь-яка формула A, що отримується з формули A шляхом підстановки замість пропозиційних змінних p1,p2,...,pn довільних формул B1,B2,.....,Bn, оскільки останні можуть набувати лише значень 0 або 1.
Доведемо, що коли формули A і AB є тотожно істинними, тоді формула B, яку ми дістаємо з них за правилом висновку, також є тотожно істинною. Припустімо супротивне: нехай B не є тотожно істинною формулою, тобто існує набір значень її змінних, на якому вона набуває значення 0. Тоді підставимо цей набір у формулу AB, оскільки A є тавтологією, то дістанемо вираз 10, значенням якого є 0. Останнє суперечить припущенню про тотожну істинність формули AB.
Таким чином, ми переконалися в тому, що всі аксіоми числення висловлень ЧВ є тотожно істинними формулами алгебри висловлень, а застосування обох правил виведення (підстановки і висновку) до тотожно істинних формул знову приводить до тотожно істинних формул. Отже, всі вивідні формули (теореми) числення висловлень є тотожно істинними формулами алгебри висловлень.
Справедливою є й обернена теорема, яку подамо без доведення.
Теорема 5.6. Будь-яка тотожно істинна формула алгебри висловлень є теоремою числення висловлень ЧВ.
Дві останні теореми дозволяють вирішити три важливі проблеми числення висловлень: проблему несуперечності, проблему повноти і проблему розв’язності. Розглянемо їх послідовно.
1. Проблема несуперечності.
Для кожної формальної теорії кардинальним є питання несуперечності. Справді, така теорія будується послідовним приєднанням нових теорем, які формально виводять з аксіом за допомогою правил виведення. Отже, немає жодної гарантії, що в цьому процесі ми не дійдемо до суперечності. Iнакше кажучи, виникає питання, чи при поступовому нагромадженні теорем формальної теорії (числення) не трапиться так, що одна з теорем суперечитиме іншим. Саме так виникає проблема несуперечності числення.
Числення є несуперечним, якщо неможливо одночасно вивести з аксіом числення як формулу A, так і її заперечення A.
Наслідок 5.1. Числення висловлень ЧВ є несуперечною формальною теорією.
Справді, якщо формула A вивідна у численні висловлень, то формула A не може бути вивідною, бо за теоремою 5.5 формула A є тотожно істинною в алгебрі висловлень, а формула A - тотожно хибною. Отже, A не може бути теоремою числення висловлень ЧВ.
2. Проблема повноти.
Iнша проблема, що виникає при дослідженні різних числень висловлень: чи будь-яка тотожно істинна формула алгебри висловлень буде вивідною в заданому численні? Це питання й являє собою проблему повноти для числення висловлень.
Смисл такої постановки питання полягає в тому, що при побудові числення потрібно знати, чи достатньо аксіом і правил виведення даного числення для того, щоб можна було вивести будь-яку формулу, яка в змістовному розумінні є тотожно істинною.
Наслідок 5.2. Числення висловлень ЧВ є повним.
Справедливість цього твердження безпосередньо випливає з теореми 5.6.
У математичній логіці існує й інше поняття повноти системи аксіом (або числення), що грунтується на неможливості доповнення системи аксіом будь-якою формулою, яку не можна вивести з даних аксіом.
3. Проблема розв’язності.
Розв’язувальним методом для формальної теорії T називають метод, за допомогою якого для довільної формули A з T можна за скінченне число кроків визначити, чи буде A теоремою, чи ні.
Числення T називають розв’язним, якщо для T існує розв’язувальний метод, у противному разі - формальна теорія T є нерозв’яною.
Наслідок 5.3. Числення висловлень ЧВ є розв’язною теорією.
Скачати реферат Числення висловлень і алгебра висловлень. Основні проблеми числення висловлень
Схожі українські реферати
|
1. Реферат: Чинники і умови ґрунтоутворення, гумус ґрунту, якісна оцінка земель Характеристика основних чинників і умов ґрунтоутворення ҐРУНТОТВОРНИЙ ПРОЦЕС І ЧИННИКИ ҐРУНТОУТВОРЕННЯ ЗАГАЛЬНА СХЕМА ҐРУНТОТВОРНОГО ПРОЦЕСУ Ґрунтотворний процес відноситься до категорії біофізико-хімічних. Агентами ґрунтоутворення є живі... 2. Реферат: Чинники котрі сприяли великому церковному розколу Вступ Актуальність теми. Християнство з самого початку було єдиним. Є всі підстави стверджувати, що християнство виникло у середині першого століття серед євреїв і в початковій своїй стадії було сектою в іудаїзмі. Згідно чотирьох Євангелій і книги... 3. Реферат: Чинники підвищення ефективності використання капітальних вкладень і фінансових інвестицій На рівень ефективності використання капітальних вкладень, їхню результативність (віддачу) впливає велика сукупність різноманітних організаційно-економічних чинників. Без ретельного врахування таких у практиці сучасного господарювання неможливо до... 4. Реферат: Чинники формування ідентичності в юності З усіх проблем, з якими зустрічались люди в ході розвитку людства, ймовірно, найбільш загадковою є сама людська природа. В яких тільки напрямках не велись пошуки, яких тільки концепцій не було висунуто,- ясної і чіткої відповіді до цього часу людств... 5. Реферат: Чинники формування психологічних проблем дитини Сім’я є одним із основних факторів, які впливають на формування особистості дитини. Багатьма психологічними дослідженнями показано, що особистісні проблеми дітей – неврози, страхи, девіантна та делінквентна поведінка тощо – значною мірою зумовлені н... 6. Реферат: Чинники, що визначають інвестиційні якості фінансових інструментів Оцінювання інвестиційних якостей окремих фінансових інструментів, що обертаються на ринку, є одним з найважливіших завдань процесу здійснення фінансових інвестицій. Воно являє собою інтегральну характеристику окремих їх видів, здійснену інвестором з ... 7. Реферат: Чинники,що визначають параметри попиту на гроші Чинники,що визначають параметри попиту на гроші Монетарна теорія розглядає багатство як один із визначальних чинників попиту на гроші. В працях Дж.Кейнса розроблена методологія оцінки попиту на різні форми багатства. Гроші ( це тільки одна із розма... 8. Реферат: ЧИСЕЛЬНІСТЬ НАСЕЛЕННЯ СВІТУ ТА ЙОГО РОЗМІЩЕННЯ До числа найбільш актуальних проблем сучасного людства відноситься проблема народонаселення, пов'язана насамперед із прискореними темпами зростання населення. Так, на початку нашої ери на Землі нараховувалося близько 200 млн. осіб, у 1000 р. - 275 мл... 9. Реферат: Чисельність населення України. Природний рух Населення є самовідтворювальною множиною людей, що перебуває постійно у динаміці. Зміни кількості населення, його структури на певній території за певний часовий відрізок характеризують демографічний процес. Залежно від тенденцій кількісних і якісних... 10. Реферат: Числення висловлень Числення висловлень (ЧВ) згідно з поданою у розділі 1 схемою означається таким чином. 1. Алфавіт числення висловлень складається з елементарних і змінних висловлень (пропозиційних змінних): a,b,c,d,...,x,y,z (можливо з індексами), знаків логічних ...
11. Реферат: Числення висловлень і алгебра висловлень. Основні проблеми числення висловлень
Довільну формулу F числення висловлень можна змістовно інтерпретувати як складене висловлення, істинність або хибність якого залежить від істинності елементарних висловлень, що до нього входять. Таким чином, кожній формулі F числення висловлень можна... 12. Реферат: Числення предикатiв. Теорiя першого порядку Числення предикатiв, тобто формальна теорiя предикатiв будується за вищенаведеною класичною схемою побудови формальних (математичних) теорiй. 1. Алфавiт числення предикатiв, тобто множина вихiдних символiв складається з предметних (iндивiдних) змiнн... 13. Реферат: Числівники в діловому мовленні Числівники в діловому мовленні Здебільшого в ділових паперах не обходяться без цифрових даних. Вони вимагають спеціального оформлення. Так, однозначні числа, що не мають посилань на одиниці виміру, в ділових паперах записуються словами. Наприклад:... 14. Реферат: Числові послідовності. Границя, основні властивості границь. Нескінченно малі і нескінченно великі величини, їх властивості Числові послідовності. Границя, основні властивості границь. Нескінченно малі і нескінченно великі величини, їх властивості План Числова послідовність. Означення границі числової послідовності. Основні теореми про границі. Обчислення д... 15. Реферат: Числові послідовності. Границя, основні властивості границь. Нескінченно малі і нескінченно великі величини, їх властивості. Формулювання теореми про існування границі монотонної послідовності і функції. Порівняння величин. Еквівалентні нескінченно малі в План • Числові послідовності. • Границя, основні властивості. • Границя монотонної послідовності і функції. • Нескінченно малі і нескінченно великі величини, їх властивості. • Порівняння величин. • Еквівалентні нескінченно малі вели... 16. Реферат: Числові ряди. Збіжність і розбіжність. Сума ряду. Дії над збіжними рядами. Необхідна ознака збіжності Числові ряди. Збіжність і розбіжність. Сума ряду. Дії над збіжними рядами. Необхідна ознака збіжності План Числові ряди. Збіжність і розбіжність Сума ряду Дії над збіжними рядами Необхідна ознака збіжності Гармонічний ряд ЧИСЛОВІ... 17. Реферат: Числові ряди. Збіжність і розбіжність. Сума ряду. Дії над збіжними рядами. Необхідна ознака збіжності. Гармонічний ряд План • Числові ряди. Збіжність і розбіжність • Сума ряду • Дії над збіжними рядами • Необхідна ознака збіжності • Гармонічний ряд ЧИСЛОВІ РЯДИ 1 Ряд. Сума ряду Означення 1. Нехай задана нескінченна послідовність чисел Вираз... 18. Реферат: Числові ряди. Збіжність і розбіжність. Сума ряду. Дії над збіжними рядами. Необхідна ознака збіжності. Гармонічний ряд. План • Числові ряди. Збіжність і розбіжність • Сума ряду • Дії над збіжними рядами • Необхідна ознака збіжності • Гармонічний ряд ЧИСЛОВІ РЯДИ 1 Ряд. Сума ряду Означення 1. Нехай задана нескінченна послідовність чисел..... 19. Реферат: Числові ряди. поняття збіжності ряду. Необхідна умова збіжності Основні поняття — деяка нескінченна послідовність чисел. Побудований із цих чисел за допомогою знака «+» символ (9.1) — членами ряду; n-ий член un — називається загальним членом ряду. Побудуємо частинні суми ряду: (9.2) . Означення. Ч... 20. Реферат: Числові та степеневі ряди ПЛАН 1. Числові ряди. 2. Степеневі ряди. 1. Числові ряди У деяких задачах розглядають суми, що складаються із нескінченної кількості доданків. Властивості таких нескінченних сум часто суттєво відрізняються від властивостей сум скінченної ... 21. Реферат: Числові характеристики випадкових величин та їх властивості Закон розподілу ймовірностей як для дискретних, так і для неперервних випадкових величин дає повну інформацію про них. Проте на практиці немає потреби так докладно описувати ці величини, а достатньо знати лише певні параметри, що характеризують їх і... |
|