Redundant proof

In mathematical logic, a redundant proof is a proof that has a subset that is a shorter proof of the same result.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematical logic, a redundant proof is a proof that has a subset that is a shorter proof of the same result. In other words, a proof is redundant if it has more proof steps than are actually necessary to prove the result.

Formally, a proof \psi of \kappa is considered redundant if there exists another proof \psi^{\prime} of \kappa^{\prime} such that \kappa^{\prime}\subseteq\kappa (i.e. \kappa^{\prime} \;\text{subsumes}\; \kappa ) and |\psi^{\prime}| where |\varphi| is the number of nodes in \varphi . \psi_1 [-] = \psi_2 [-] =\_\odot\eta_3 \text{ and }\psi [-] = \_ But it is not globally redundant because the replacement terms according to the definition contain \psi_1 [\eta_1] \odot \psi_2 [\eta_2] in all the cases and \psi_1 [\eta_1] \odot \psi_2 [\eta_2] = (\eta_1 \odot \eta_3) \odot (\eta_2 \odot \eta_3) does not correspond to a proof. In particular, neither \eta_1 nor \eta_2 can be resolved with \eta_3 , as they do not contain the literal q . The second pattern of potentially globally redundant proofs appearing in global redundancy definition is related to the well-known notion of regularity .

Informally, a proof is irregular if there is a path from a node to the root of the proof such that a literal is used more than once as a pivot in this path.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1191444096 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001191444096 · captured 1703343452.0 · version history

Cite this page as: encyclopegia.org, “Redundant proof”, snapshot enwiki-001191444096. https://encyclopegia.org/a/redundant-proof

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.