Формальное доказательство
- Формальное доказательство или вывод представляет собой конечную последовательность предложений, каждое из которых является аксиомой, предположением или следует из предыдущих предложений по правилу вывода.
- Формальные доказательства отличаются от аргументации на естественном языке своей строгостью, недвусмысленностью и поддающейся механической проверке.
- Понятие теоремы обычно неэффективно, и не существует метода, позволяющего всегда находить доказательство данного предложения или определить его отсутствие.
- Концепции доказательства в стиле Фитча, последовательного исчисления и естественной дедукции являются обобщениями концепции доказательства.
- Теорема является синтаксическим следствием всех правильно сформулированных формул, предшествующих ей в доказательстве.
- Формальные доказательства часто создаются с помощью компьютеров при интерактивном доказательстве теорем.
- Проверка формальных доказательств обычно проста, в то время как проблема поиска доказательств обычно трудноразрешима с точки зрения вычислений и/или наполовину разрешима, в зависимости от используемой формальной системы.
Полный текст статьи: