高级数理逻辑第二章.ppt

经典命题逻辑 命题：具有唯一真值的陈述句。 联结词（命题运算符） 否定—”不” 析取—”或” 合取—”与” 条件—”若…，则…” 双条件—”…当且仅当…” 复合命题&简单命题 在命题逻辑中，逻辑形式由联结词决定 命题语言L p 命题语言L p是经典命题逻辑的形式语言 命题语言L p是符号的集合 命题符号：p q r … 联结符号： 标点符号：（ ） 命题语言L p的含义本质上不涉及语义，而只有语法。 表达式 表达式： L p中有限个符号组成的字符串 表达式的长度：表达式中的符号数目 空表达式：长度为0的表达式，记为 表达式相等：U=V iff 表达式U和V中符号依次相同 表达式U和V依次并列形成新的表达式UV，且 若表达式U=W1VW2，则V是U的段。若V是U的段且V和U不相等，则V是U的真段。 初始段、结尾段、真初始段、真结尾段 公式集的归纳定义 并不是所有表达式都是研究对象 研究对象必须符合语法 原子公式集Atom(L p)={U|U是由单个命题符号构成的表达式} 合式公式集Form(L p) i） Atom(L p)?Form(L p) ii）若A∈Form(L p)，则(﹁A)∈Form(L p) iii）若A，B∈Form(L p)，则(A*B)∈Form(L p)。其中*表示∧，∨，→，?中的任何一个 iv）A是能由有限次应用i）—iii）形成的表达式 iff A∈Form(L p) 公式集的归纳定义 合式公式集Form(L p)是满足的以下i）—iii） 的S中的最小集 i） Atom(L p)?S ii）若A∈S，则(﹁A)∈S iii）若A，B∈S，则(A*B)∈S。其中*表示∧，∨，→，?中的任何一个 公式集的归纳证明 定理：设R是一个性质，若 i）对于任何p∈Atom(L p)，R(p)； ii）对于任何A∈Form(L p)，若R(A)，则R((﹁A))； iii）对于任何A，B∈Form(L p)，若R(A)且R(B)，则R((A*B)) 。其中*表示∧，∨，→，?中的任何一个； 则对于任何A∈Form(L p)，R(A)。 公式结构 引理：对于任何A∈Form(L p)，有 A为不空的表达式。 A中的左括号与右括号的数目相同。 A的任何不空的真初始段中，左括号的数目比右括号的数目多； A的任何不空的真结尾段中，左括号的数目比右括号的数目少。 定理：L p的每一公式恰好具有以下6种形式之一：原子公式， (﹁A)， (A∧B)， (A∨B)， (A→B)，(A?B)；并且在各种情形公式所具有的那种形式是唯一的。 公式的语法分类 原子公式 复合公式 设A，B为公式，则 否定式 (?A) 合取式 (A∧B) 析取式 (A∨B) 蕴含式 (A→B)，其中A为前件，B为后件。 等值式 (A?B) 辖域 设A，B，C为公式 若(﹁A)是C的段，则称A为它左方的﹁在C中的辖域 若(A*B)是C的段，则称A和B分别为它们之间的*在C中的左辖域和右辖域。其中*表示∧，∨，→，?中的任何一个 定理：任何A中的任何﹁（如果有）有唯一的辖域；任何A中的任何*（如果有）有唯一的左辖域和右辖域 定理：若A是(﹁B)的段，则A= (﹁B)或A是B的段；若A是(B*C)的段，则A= (B*C)或A是B的段或A是C的段 形式可推演 用∑表示任何公式集，即∑?Form(L p) 。 ∑∪{A}可以记为∑，A。 ∑∪∑’可以记为∑，∑’。 若∑={A1, A2, A3, …}，则∑可以记为A1, A2, A3, …。 ∑├A表示A由∑形式可推演（形式可证明）的。其中， ∑为前提，A为结论。 ├不是L p中符号。 ∑├A不是公式。 A├┤B表示“A├B并且B├A”，并称A和B是语法等值的。 命题逻辑的推演规则 共11条，A，B，C为公式 (Ref) A├A (+)若∑├A， 则∑， ∑’├A (﹁-)若∑， ﹁A ├B， ∑ ， ﹁A ├﹁B， 则∑├A (→-)若∑├A→B， ∑ ├A， 则∑├B (→+)若∑，A├B， 则∑├A→B (∧-)若∑├A∧B， 则∑├A， ∑├B 形式推演的定义 A是在命题逻辑中由∑形式可推演（形式可证明）的，记为∑├A，当且仅当∑├A能有限次使用形式推演规则生成。 这是一个归纳定义。定义了以下集合 {∑├A| ∑?Form(L p) 且A∈Form(L p) } 关于归纳证明（定理2.6.2） 一个有限序列∑1├A1，∑2├A2，…，∑n├An被称为∑n├An的形式证明。其中， ∑k├Ak（1≤k≤n）由使用某