Referat.me

Название: Числення висловлень і алгебра висловлень Основні проблеми числення висловлень

Вид работы: реферат

Рубрика: Астрономия

Размер файла: 17.59 Kb

Скачать файл: referat.me-1930.docx

Краткое описание работы: Реферат на тему: Числення висловлень і алгебра висловлень. Основні проблеми числення висловлень. Довільну формулу F числення висловлень можна змістовно інтерпретувати як складене висловлення, істинність або хибність якого залежить від істинності елементарних висловлень, що до нього входять.

Числення висловлень і алгебра висловлень Основні проблеми числення висловлень

Реферат на тему:

Числення висловлень і алгебра висловлень. Основні проблеми числення висловлень.


Довільну формулу F числення висловлень можна змістовно інтерпретувати як складене висловлення, істинність або хибність якого залежить від істинності елементарних висловлень, що до нього входять. Таким чином, кожній формулі F числення висловлень можна аналогічно тому, як це було зроблено в алгебрі висловлень, поставити у відповідність функцію істинності f .

Виникає питання, як пов’язано таке змістовне «істинносне» тлумачення (інтерпретація) формул числення висловлень з їхньою формальною вивідністю.

Теорема 5.5. Будь-яка теорема числення висловлень ЧВ є тотожно істинним висловленням (тавтологією).

Доведення . Тотожна істинність усіх аксіом легко перевіряється безпосередньо побудовою відповідних таблиць істинності для кожної з них (рекомендуємо це зробити самостійно).

Відтак, доведемо, що обидва правила виведення числення висловлень перетворюють тотожно істинні формули у тотожно істинні.

Якщо A (p 1 ,p 2 ,...,pn ) - тотожно істинна формула, то для довільного набору значень a 1 ,a 2 ,...,an її пропозиційних змінних A (a 1 ,a 2 ,...,an ) є істинною. Отже, тотожно істинною буде і будь-яка формула A , що отримується з формули A шляхом підстановки замість пропозиційних змінних p 1 ,p 2 ,...,pn довільних формул B 1 ,B 2 ,.....,Bn , оскільки останні можуть набувати лише значень 0 або 1.

Доведемо, що коли формули A і A ®B є тотожно істинними, тоді формула B , яку ми дістаємо з них за правилом висновку, також є тотожно істинною. Припустімо супротивне: нехай B не є тотожно істинною формулою, тобто існує набір значень її змінних, на якому вона набуває значення 0. Тоді підставимо цей набір у формулу A ®B , оскільки A є тавтологією, то дістанемо вираз 1®0, значенням якого є 0. Останнє суперечить припущенню про тотожну істинність формули A ®B .

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

Справедливою є й обернена теорема, яку подамо без доведення.

Теорема 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. Числення висловлень ЧВ є розв’язною теорією.

Доведення. Нехай A - довільна формула числення ЧВ. Побудуємо для неї таблицю істинності і розглянемо її останній стовпчик. Якщо він містить лише одиниці, то A - тотожно істинна формула і за теоремою 5.6 є теоремою ЧВ. У противному разі (останній стовпчик таблиці істинності містить хоча б один нуль), A - не тавтологія і значить, A не є теоремою.

Зрозуміло, що всі ці дії можна зробити за скінченне число кроків.

Нарешті, розглянемо ще одну важливу проблему для формальних теорій.

Система аксіом числення називається незалежною , якщо жодна з аксіом цієї системи не може бути виведена з інших аксіом системи.

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

Можна довести, що системи аксіом числень висловлень ЧВ і ЧВ1 є незалежними.

Iснують й інші формальні теорії, що означаються і досліджуються у математичній логіці: числення предикатів , різноманітні числення (теорії ) першого порядку , числення з рівностями , формальна арифметика тощо. У наступних розділах розглянемо основні ідеї і принципи побудови однієї з таких теорій - числення предикатів.

Похожие работы

  • Математичне забезпечення САПР

    Тема : Математичне забезпечення САПР. 1. Загальні поняття та вимоги до МЗ. 2. Способи отримання математичних моделей. 3. Постановка задач оптимізації.

  • Встановлення кольору тксту та фону документа Описані основні теги що до встановлення фону доку

    Лабораторна робота Тема: Встановлення кольору фону та тексту. Мета: Навчитись застосовувати кольори для оформлення елементів HTML-документа. Теоретичні відомості.

  • Елементи логіки

    Пошукова робота на тему: Елементи логіки 1. Висловлення та формули Одним з основних понять логіки є висловлення – розповідне речення, про яке можна стверджувати, що воно є або істинним, або хибним.

  • Інтегральне числення Невизначений інтеграл

    ІНТЕГРАЛЬНЕ ЧИСЛЕННЯ НЕВИЗНАЧЕНИЙ ІНТЕГРАЛ Означення : Функція F(x) називається первісною для функції f(x) на проміжку І, якщо на цьому проміжку F'(x) = f(x) або dF(x) = f(x)dx .

  • Поняття предиката

    Реферат на тему: Поняття предиката Числення висловлень, що розглядалось у попереднiх роздiлах, як алгебра висловлень i як формальна (аксiоматична) теорiя, є важливою i невiд’ємною складовою частиною всiх числень математичної логiки. Однак воно є занадто бiдним для опису та аналiзу найпростiших логiчних мiркувань науки i практики.

  • Покоління ЕОМ

    Удосконалення комп’ютерів ведеться в декількох напрямках. По-перше, змінюється елементна база комп’ютерів. По-друге, змінюється програмне забезпечення. Крім того, удосконалюються технічні пристрої, що використовуються комп’ютером, організація та взаємозв’язок його різних частин. Згідно з цим і виник поділ комп’ютерів на покоління.

  • Диференціальне числення функції Область визначення Елементарні функції Означення функції

    Реферат з дисципліни „Вища математика” Диференціальне числення Функції. Область визначення. Елементарні функції Означення функції План Область визначення.

  • Формули Рiвносильнiсть формул Тотожно iстиннi формули

    Реферат на тему: Формули. Рiвносильнiсть формул. Тотожно iстиннi формули Наведемо iндуктивне означення поняття формули логiки предикатiв (предикатної формули або просто формули ) на предметнiй областi M.

  • Боголюбов Микола Миколайович - український математик механік фізик

    Реферат На тему: Боголюбов Микола Миколайович - український математик, механік, фізик Народився у 1909 р. в Нижньому Новгороді. Після завершення семирічки самостійно займався математикою і фізикою. У віці 17 років закінчив аспірантуру при Академії наук України. В 1934—1958 рр. працював у Київському університеті (з 1936 р. — професор).

  • Первісна функція і неозначений інтеграл Основні властивості неозначеного інтеграла Таблиця осно

    Пошукова робота на тему: Первісна функція і неозначений інтеграл. Основні властивості неозначеного інтеграла.Таблиця основних інтегралів. План Первісна функція