Условное доказательство
 | Эта статья включает список литературы , связанную литературу или внешние ссылки , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( Июль 2021 г. ) |
| Правила трансформации |
|---|
| Пропозициональное исчисление |
| Правила вывода |
| Правила замены |
| Логика предикатов |
| Правила вывода |
Условное доказательство — это доказательство , которое принимает форму утверждения условного утверждения и доказательства того, что антецедент условного выражения обязательно ведет к последующему .
Обзор [ править ]
Предполагаемый предшественник условного доказательства называется предположением условного доказательства ( CPA ). Таким образом, цель условного доказательства — продемонстрировать, что если бы CPA было истинным, то из этого обязательно следует желаемый вывод . Для достоверности условного доказательства не требуется, чтобы CPA было истинным, а только то, что, если бы оно было истинным, это привело бы к последствию.
Условные доказательства имеют большое значение в математике . Существуют условные доказательства, связывающие несколько гипотез , которые иначе не были бы доказаны , так что доказательство одной гипотезы может сразу подразумевать обоснованность нескольких других. Гораздо проще показать, что истинность предложения следует из другого предложения, чем доказывать ее независимо.
Знаменитая сеть условных доказательств — это NP-полный класс теории сложности. Существует большое количество интересных задач (см. Список NP-полных задач ), и хотя неизвестно, существует ли для какой-либо из них решение за полиномиальное время, известно, что если такое решение существует для некоторых из них, один существует для всех из них. Точно так же гипотеза Римана имеет множество уже доказанных следствий.
Символьная логика [ править ]
В качестве примера условного доказательства в символической логике предположим, что мы хотим доказать A → C (если A, то C) из первых двух посылок ниже:
| 1. | А → Б | («Если А, то Б») |
| 2. | Б → С | («Если Б, то С») |
| 3. | А | (предположение условного доказательства: «Предположим, что А истинно») |
| 4. | Б | (следует из строк 1 и 3, modus ponens ; «Если А, то Б; А, следовательно, Б») |
| 5. | С | (следует из строк 2 и 4, modus ponens ; «Если B, то C; B, следовательно, C») |
| 6. | А → С | (следует из строк 3–5, условное доказательство; «Если А, то С») |
См. также [ править ]
Ссылки [ править ]
- Роберт Л. Кози, Логика, множества и рекурсия , Джонс и Барлетт, 2006.
- Дов М. Габбай, Франц Гентнер (ред.), Справочник по философской логике , Том 8, Springer, 2002.