Условное доказательство — это доказательство , которое принимает форму утверждения условного предложения и доказывает, что его антецедент обязательно приводит к консеквенту .
Предполагаемое антецедент условного доказательства называется предположением условного доказательства ( CPA ). Таким образом, цель условного доказательства — продемонстрировать, что если CPA истинен, то желаемый вывод обязательно следует . Обоснованность условного доказательства не требует, чтобы CPA был истинным, а только того, что если бы он был истинным, то это привело бы к следствию.
Условные доказательства имеют большое значение в математике . Условные доказательства существуют, связывая несколько иначе недоказанных предположений , так что доказательство одного предположения может немедленно подразумевать справедливость нескольких других. Гораздо проще показать, что истинность предложения следует из другого предложения, чем доказывать его независимо.
Знаменитая сеть условных доказательств — это NP-полный класс теории сложности. Существует большое количество интересных задач (см. Список NP-полных задач ), и хотя неизвестно, существует ли решение за полиномиальное время для какой-либо из них, известно, что если такое решение существует для некоторых из них, то оно существует и для всех. Аналогично, гипотеза Римана имеет много уже доказанных следствий.
В качестве примера условного доказательства в символической логике предположим, что мы хотим доказать A → C (если A, то C) из первых двух посылок ниже: