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