第一篇数理逻辑.ppt

第一章 命题演算及其形式系统 1.3 范式 1.3.1 析取范式和合取范式 文字(letters)：指命题常元、变元及它们的否定， 前者又称正文字，后者则称负文字。 析取子句(disjunctive clauses)：指文字或若干文字 的析取。 合取子句(conjunctive clauses)：指文字或若干文字的合取。 互补文字对(complemental pairs of letters) ： 指形如L，┐L（L为文字）的一对字符。 第一章 命题演算及其形式系统 1.3 范式 1.3.1 析取范式和合取范式 ◆定义1.6 命题公式A‘称为公式A的析取范式 （disjunctive normal form），如果 （1）A┝┥A （2）A为一合取子句或若干合取子句的析取。 ◆定义1.7 命题公式A‘称为公式A的合取范式 （conjunctive normal form）如果 （1）A┝┥A （2）A为一析取子句或若干析取子句的合取。 第一章 命题演算及其形式系统 1.3 范式 1.3.2 主析取范式与主合取范式 ◆定义1.8 设A为恰含命题变元p1,…,pn的公式。 公式A,称为A的主析（合）取范式 （majordisjunctive（conjunctive）normal form）， 如果A,是A的析（合）取范式，并且其每个 合（析）取子句中p1,…,pn均恰出现一次。 第一章 命题演算及其形式系统 1.3 范式 △1.3.3 联结词的扩充与归约 ◆定义1.9 称n元联结词h是用m 个联结词g1, g2,…, gm 可表示的，如果 h(p1, p2,. . ., pn ) ┝┥A 而A中所含联结词仅取自g1, g2,. . ., gm。 第一章 命题演算及其形式系统 1.3 范式 △1.3.3 联结词的扩充与归约 ◆定义1.10 当联结词组g1, g2,. . ., gm可表示所有 一元、二元联结词时，称其为完备联结 词组（complete group of connectives）。 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 1.4.1 证明、演绎和推理 ◆定义1.11 公式序列A1, A2, …, Am称为Am的一个证明（proof）， 如果Ai(1 ≤ i ≤ m) 或者是公理，或者由Aj1 …, Ajk (j1,…,jk?i)用推理规则推得。当这样的证明存在时， 称Am为系统的定理（theorems），记为 ├*Am, ( ?为所讨论的系统名),或简记为├Am 。 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 1.4.1 证明、演绎和推理 ◆定义1.12 设?为一公式集合。公式序列A1,A2,…,Am称为Am的 以?为前提的演绎（diduction），如果Ai(1≤i≤m) 或者是 ? 中公式，或者是公理，或者由 Aj1…,Ajk(j1,…,jk?i)用推理规则导出。当有这样的 演绎时，Am称为 ? 的演绎结果，记为 ?├*Am, ( ?为所讨论的系统名)，或简记为?├Am。 称 ? 和 ? 的成员为Am的前提(hypothesis)。 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 △1.4.2 命题演算形式系统PC ◆定理1.6 （合理性，sondness） 若公式A是系统PC的定理，则A为永真式。 若A是公式集 ? 的演绎结果，那么A是 ?的逻辑结果。即 若├PC A，则┝ A .若 ?├PC A，则 ?┝ A . ◆定理1.7 PC是一致的，即没有公式A使得├PC A与 ├PC┐A同时成立。 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 △1.4.2 命题演算形式系统PC ◆定理1.8 （完备性，completeness） 若公式A永真，则A必为PC的定理；若公式A是公式集 ? 的逻辑结果，那么A必为 ? 的演绎结果。即若┝ A，那么 ├PC A . 若 ?┝ A，那么 ?├PC A . 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 △1.4.2 命题演算形式系统PC ◆定理1.9 （演绎定理） 对任意公式集 ? 和公式A，B，?├A→B当且仅当 ? ??A?├ B（当 ? = ?时，├A→B当且仅当?A?├ B，或A├ B） 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 △1.4.2 命题演算形式系统PC ◆定理1.10 （归谬定理） 对任何公式