请输入您要查询的字词:

 

单词 CompletenessTheoremForPropositionalLogic
释义

completeness theorem for propositional logic


The completeness theorem of propositional logicPlanetmathPlanetmath is the statement that a wff is tautologyMathworldPlanetmath iff it is a theorem. The if part of the statement is the soundness theorem, and the only if part is the completeness theorem. We will prove the two parts separately here. We begin with the easier one:

Theorem 1.

Propositional logic is sound with respect to truth-value semantics.

Proof.

Basically, we need to show that every axiom is a tautology, and that the inference rule modus ponensMathworldPlanetmath preserves truth. Since theorems are deduced from axioms and by applications of modus ponens, they are tautologies as a result.

Using truth tablesMathworldPlanetmath, one easily verifies that every axiom is true (under any valuation). For example, if the axiom is of the form A(BA), then we have

Before proving the completeness portion of the theorem, we need the following

Theorem 2.

Propositional logic is completePlanetmathPlanetmathPlanetmathPlanetmathPlanetmath with respect to truth-value semantics.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 12:35:49