Реферат на тему:
Числення висловлень і алгебра висловлень. Основні проблеми числення висловлень.
Довільну формулу 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. Числення висловлень ЧВ є розв’язною теорією.
Доведення. Нехай A - довільна формула числення ЧВ. Побудуємо для неї таблицю істинності і розглянемо її останній стовпчик. Якщо він містить лише одиниці, то A - тотожно істинна формула і за теоремою 5.6 є теоремою ЧВ. У противному разі (останній стовпчик таблиці істинності містить хоча б один нуль), A - не тавтологія і значить, A не є теоремою.
Зрозуміло, що всі ці дії можна зробити за скінченне число кроків.
Нарешті, розглянемо ще одну важливу проблему для формальних теорій.
Система аксіом числення називається незалежною, якщо жодна з аксіом цієї системи не може бути виведена з інших аксіом системи.
Зрозуміло, що аксіому, яку можна вивести з інших, можна виключити зі системи аксіом, і при цьому множина теорем теорії залишиться тією ж самою (тобто отримаємо рівносильне числення). Отже, залежна система аксіом у певному розумінні менш досконала, ніж незалежна система, бо вона містить зайві аксіоми.
Можна довести, що системи аксіом числень висловлень ЧВ і ЧВ1 є незалежними.
Iснують й інші формальні теорії, що означаються і досліджуються у математичній логіці: числення предикатів, різноманітні числення (теорії) першого порядку, числення з рівностями, формальна арифметика тощо. У наступних розділах розглянемо основні ідеї і принципи побудови однієї з таких теорій - числення предикатів.
Другие работы по теме:
Принципи, цілі й завдання сімейної психотерапії
Медичний і психологічний етапи розвитку сімейної психотерапії. Вимоги до терапевта, що працює з родиною. Сімейне консультування й психотерапія в практиці О.О. Бодальова й В.В. Століна. Висновки про сучасні напрямки й принципи сімейної психотерапії.
Выпускная
Проблема обучения математике в профильных классах на примере темы «Логарифмические уравнения»
Числення висловлень
Реферат на тему: Числення висловлень Числення висловлень ) згідно з поданою у розділі 1 схемою означається таким чином. Алфавіт числення висловлень складається з елементарних і змінних висловлень (пропозиційних змінних): a,b,c,d,...,x,y,z (можливо з індексами), знаків логічних операцій ,,, і круглих дужок ( та ).
Алгебра висловлень
Реферат на тему: Алгебра висловлень Носієм алгебри висловлень є множина так званих простих висловлень. Просте елементарне висловлення (висловлювання) - це просте твердження, тобто розповідне речення, щодо змісту якого доречно ставити питання про його правильність або неправильність.
Значення міжнародних конгресів математиків для становлення математики як науки
Реферат на тему: Значення міжнародних конгресів математиків для становлення математики як науки Основними заходами міжнародного масштабу, що об’єднують математиків різних країн, були (і тепер є) міжнародні конгреси математиків (МКМ), які проводяться, як правило, раз в чотири роки (крім перерв, викликаних війнами).
Сучасна логіка 2
РЕФЕРАТ на тему: „СУЧАСНА ЛОГІКА” Термін “логіка” сьогодні загалом застосовується у трьох головних значеннях. По-перше, ним позначають будь-яку необхідну закономірність у взаємозв’язку об’єктивних явищ – “логіка фактів”, “логіка історичного розвитку” тощо. По-друге, словом “логіка” позначають закономірності у зв’язках і у розвитку думок – “логіка міркування”, “логіка мислення”.
Комбінаторика
Розділ I. Елементи теорії множин §1.1. Поняття множини Поняття множини є одним з фундаментальних у математиці. Воно належить до понять яким не можна дати строге означення, тобто до так званих первісних, які не можна визначити через простіші поняття. Інтуєтивно множину розуміють як сукупність (сімейство, набір, зібрання, клас) деяких, обєктів об’єднаних за певною ознакою чи властивістю.
Алгоритмічні проблеми
Поняття та особливості алгоритмів обчислювальних процедур. Операторні та предикатні алгоритми, їх характеристика, порядок та принципи формування, етапи розв'язання. Алгоритмічні проблеми для L. Логіка висловлень та предикатів в представленні знань.
Математична логіка
Побудова математичної логіки як алгебри висловлень і алгебри предикатів. Основні поняття логіки висловлювань та їх закони і нормальні форми. Основні поняття логіки предикатів і її закони, випереджена нормальна форма. Процедури доведення законів.
Перетворення чисел з однієї системи числення в іншу
Методи алгоритмiчного описаня задач, програмування на основi стандартних мовних засобiв. Переклад з однієї системи числення в іншу при програмуванні. Системи числення. Двійкові системи числення. Числа з фіксованою і плаваючою комою. Програмна реалізація.
Доведення теоретико-математичних тотожностей і тверджень
Розробка алгоритму та написання програми обчислення множин. Доведення теоретико-математичних тотожностей і тверджень. Побудова диз’юнктивної нормальної форми. Розробка алгоритму та написання програми знаходження множини елементарних циклів у графі.
Оператори й основні типи даних мови С++
Базові типи змінних. Елементарний ввід-вивід. Умовні оператори та оператори множинного вибору. Основні функції вводу даних із клавіатури scanf, gets, getchar. Визначення основних (базових) типів даних. Вивід повідомлення при невірно заданому ключі.
Системи числення
МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ Бердичівський політехнічний коледж Контрольна робота «Комп’ютерна схемотехніка» (варіант №21) студента групи Пзс-503
Програма переводу з однієї системи числення у іншу
ЗМІСТ Розділ 2. Методи та засоби розв'язку задачі 5 Розділ 3. Практична реалізація розв'язку задачі 8 Вступ Головним напрямком науково-технічного прогресу в наш час є розвиток методів і засобів обчислювальної техніки. Використання методів математичного моделювання і розв’язування інженерних задач на ЕОМ позволяє значно підвищити ефективність процесів проектування і управління.
Контекстний аспект мовленнєвого акту оцінки
Реферат на тему: Контекстний аспект мовленнєвого акту оцінки Дослідження мовленнєвого акту оцінки (далі – МАО) потребує виокремлення різних аспектів, за якими він вивчається в системі прагмалінгвістики, важливим із яких вважається контекстний (Н.Д. Арутюнова, О.В. Падучева, Д. Франк, Р.І. Павільоніс, П.В.
ЗНО математика 2008 с ответами
ВІДПОВІДІ НА ЗАВДАННЯ ТЕСТУ З МАТЕМАТИКИ (Затверджені експертною комісією Українського центру оцінювання якості освіти 29 квітня 2008 року) Частина 1
Етапи розвитку сучасної логіки
Реферат з логіки на тему: Етапи розвитку сучасної логіки” План: Сучасна логіка Логіка в Україні В історії логіки виділяють два етапи: 1. Від логіки Давнього світу до виникнення у другій половині XIX ст. сучасної логіки.
Екологічні проблеми 9
Екологічні проблеми Поруч із вище перерахованими проблемами харчової промисловості важливе місце посідає екологічні проблеми. Ця проблема має дві сторони:
Елементи логіки
Пошукова робота на тему: Елементи логіки 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 практики.
Покоління ЕОМ
Удосконалення комп’ютерів ведеться в декількох напрямках. По-перше, змінюється елементна база комп’ютерів. По-друге, змінюється програмне забезпечення. Крім того, удосконалюються технічні пристрої, що використовуються комп’ютером, організація та взаємозв’язок його різних частин. Згідно з цим і виник поділ комп’ютерів на покоління.
Функції модифікатора
Реферат на тему: Функції модифікатора Функції модифікатора виконують переадресацію вказівників в структурах даних мови програмування Лісп. 1. RPLACA <об’єкт1> <об’єкт2>.
Математичне забезпечення САПР
Тема : . Загальні поняття та вимоги до МЗ. Способи отримання математичних моделей. Постановка задач оптимізації. Класифікація і характеристика методів оптимізації.
Боголюбов Микола Миколайович - український математик механік фізик
Реферат На тему: Боголюбов Микола Миколайович - український математик, механік, фізик Народився у 1909 р. в Нижньому Новгороді. Після завершення семирічки самостійно займався математикою і фізикою. У віці 17 років закінчив аспірантуру при Академії наук України. В 1934—1958 рр. працював у Київському університеті (з 1936 р. — професор).