11. Поняття теореми. Основна теорема логічного висновку та її доказ.
Формула G теорії L називається теоремою теорії L, якщо існує висновок у L, у якому останньою формулою є G. Взагалі кажучи, може не існувати алгоритму, що дозволяє за формулою визначити існування її висновку. Теорія, на яку такий алгоритм існує, називається розв'язною, інакше – неразрешимой.
Довести теорему означає побудувати висновок у цій Формальній Теорії.
Лемма: формула, що використовується у процесі виведення і сама має висновок у даній формальній теорії.
Побудова висновку для заданої формули є складним завданням. Ще складнішим завданням може бути відповідь на запитання: А чи існує цей висновок?
Однією з найважливіших завдань сучасної науки є:
1) Побудова алгоритмів, що визначають доказ алгоритмів чи ні. Якщо такий алгоритм вдається побудувати для теорії, теорія називається розв'язною.
2) Побудова методів алгоритмічного підтвердження теореми.
12. Основна теорема логічного висновку
Теорема. Формула G є логічним наслідком формул F1, F2, . . . Fn тоді і тільки тоді, коли формула F1&F2&. . .&Fn → G є тавтологією.
(А≡В)=(А→В)&(В→А)Для доказу теореми необхідно довести необхідність і достатність
Лемма 1. Якщо формула А→В є тавтологією, то приймає справжнє значення при тих інтерпретаціях при яких істина А.
Припустимо, що У приймає таке значення за тієї інтерпретації коли істинно А. Але тоді функція прийматиме кожне значення, що суперечить умові, т. е. А – істина і У – істина.
Згідно з Лемме1 можна сформулювати інше визначення логічного слідства, а саме:
Формула є логічним наслідкомформули А, якщо вона істина при інтерпретаціях при яких істина А.
Припустимо, що G є логічним наслідком F 1 , F 2 ... Fn . Потрібно довести, що (*) – тавтологія.
Нехай I – довільна інтерпретація.
Якщо всі формули F 1 F 2 ... Fn істина на I
I(f1)=I(F2)=….I(Fn)=І за визначенням логічного слідства I(G)=І, то формула
Якщо хоча б одна з F набуває значення Л, то (*) однаково Істина (т.к. Л → І). Отже формула (*) – тавтологія.
Припустимо, що (*) - тавтологія. Треба довести, що G є логічним наслідком.
Для всякої інтерпретації I, де всі Fi істинні, формула (**) теж істинна, і оскільки (*) - тавтологія, G - теж істинна. .
Теорема Формула G є логічним наслідком формул F1, F2, . . . Fn тоді і тільки тоді, коли формула F1&F2&. . .&Fn → ך G є протиріччям.
13. . Помилкові докази та парадокси.
14. Дедуктивні та індуктивні докази. Приклади індуктивних доказів.
Складається в послідовності тверджень істинність яких випливає з деяких вихідних тверджень посилок (гіпотез). Кінцеві твердження називаються висновки.
Існуючий принцип індукції спостереження явища Х яке відповідає теорії Т і збільшує ймовірність того, що Т істинно
Парадокс воронів, відомий також як парадокс Гемпеля або ворони Гемпеля - логічний парадокс, сформульований німецьким математиком Гемпелем, для ілюстрації того, що індуктивна логіка іноді входить у протиріччя з інтуїцією.
Припустимо, що існує теорія, за якою всі ворони чорні. Відповідно до формальної логіки, ця теорія еквівалентна теорії, що це предмети, які є чорними, є воронами.Якщо людина побачить багато чорних воронів, його впевненість у тому, що ця теорія вірна, збільшиться. Якщо ж він побачить багато червоних яблук, то це збільшить його впевненість у тому, що всі не чорні предмети не є воронами, і, згідно з вищесказаним, має також збільшити його впевненість у тому, що всі чорні ворони.
Однак цей висновок суперечить інтутивному сприйняттю ситуації людиною — у реальному житті так не відбувається. Спостереження червоних яблук збільшить упевненість спостерігача у цьому, що це не чорні предмети є воронами, але у своїй не збільшить його упевненість у цьому, що це ворони чорні.
У парадоксі чорних воронів «законом», що перевіряється, є твердження «Всі ворони чорні» . Оскільки це твердження еквівалентно твердженню «Всі предмети, що не є чорними, не є воронами» , а ймовірність істинності останнього має, відповідно до принципу індукції, збільшуватися при спостереженні будь-яких не чорних предметів, які не є воронами, виходить, що спостереження червоних яблук збільшувати ймовірність того, що всі чорні ворони.
Альтернативою використанню принципу індукції є застосування теореми Байєса, яка є однією з фундаментальних теорем у теорії ймовірностей та математичної статистики.
Нехай X - явище, що підтверджує теорію T, і нехай I - наші знання про навколишнє оточення, крім самого явища X.
Нехай Pr(T XI) - ймовірність того, що теорія T вірна, за умови, що відомо, що X та I вірні. Тоді