Условное доказательство
 | Эта статья включает список литературы , связанную литературу или внешние ссылки , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( Июль 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.