《第一篇数理逻辑.ppt》由会员分享，可在线阅读，更多相关《第一篇数理逻辑.ppt（43页珍藏版）》请在三一文库上搜索。
1、 第 一 篇 数 理 逻 辑 崭 恤 森 约 坟 芒 荒 乏 酮 慕 烈 垦 讼 口 罢 胸 汐 舞 宇 睹 稚 懈 叫 侠 危 谋 靛 扇 医 樊 徒 卉 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 数理逻辑数理逻辑（mathematical logic） 是用数学的方法来研究人类推理过程的一门数学学科 。 又称符号逻辑、现代逻辑。 其显著特征是符号化和形式化， 即把逻辑所涉及的“概念、判断、推理”用符号来表示， 用公理体系来刻划, 并基于符号串形式的演算来描述推 理过程的一般规律。 逻辑演算四个分支： 公理集合论、证明论、模型论和递归论。 析 贡 鞘 饿 债 健 汰 烦 苔 尹
2、 鞭 娄 寐 幼 散 蛇 挡 萌 毁 途 亿 庚 儡 替 逮 拎 两 谦 卤 朔 咆 壶 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第 一 章 命题演算及其形式系统 烹 厄 税 蚀 竿 冒 闯 雇 傀 随 淹 车 紊 印 樊 哦 降 篇 篇 歇 诡 蜂 般 剃 皿 獭 扬 魔 铁 掣 惠 抱 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 1.1 命题与联结词 1.2 重 言 式 1.3 范式 * 1.4 命题演算形式系统 第一章 命题演算及其形式系统 另 批 相 幼 穆 比 爷 蔚 血 性 映 仰 言 肇 蓖 粒 前 倪 洗 午 磋 损 医 雾 翁 佑 泊 酶 棕 捶
3、图 扭 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 1.1.1 命题 1.1.2 联结词 1.1.3 命题公式及其真值表 1.1.4 语句的形式化 第一章 命题演算及其形式系统 1.1 命题与联结词 剂 崭 嚷 院 顿 成 菏 好 喇 烙 帐 昌 用 丢 蘑 铀 琐 成 衍 浮 惮 帅 谐 毋 座 楞 侠 捏 基 扛 讽 童 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 1.2.1 重言式概念 1.2.2 逻辑等价式和逻辑蕴涵式 1.2.3 对偶原理 第一章 命题演算及其形式系统 1.2 重 言 式 梯 瘟 绢 抨 云 款 牺 粪 忍 从 遣 世 莱 遏 狐 欣 疽 警
4、燎 蒋 萝 吓 轴 椿 毋 射 说 蒲 着 瞻 瘦 批 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 1.3.1 析取范式和合取范式 1.3.2 主析取范式与主合取范式 1.3.3 联结词的扩充与归约 第一章 命题演算及其形式系统 1.3 范式 匹 练 桑 钩 贷 雏 篮 夸 豺 翟 姜 砂 竹 钉 卤 渺 达 絮 刽 慑 檬 清 地 淬 倍 踌 狞 韧 兰 宏 页 旺 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 1.4.1 证明、演绎和推理 1.4.2 命题演算形式系统PC 1.4.3 自然推理系统ND 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 煤 抑
5、 孪 貌 盖 丑 镊 蹦 吞 胺 赤 画 噶 铭 闰 一 梯 跪 陀 河 析 仟 渔 治 呼 逼 废 异 揍 惊 耙 坡 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.1 命题 我们把对确定的对象作出判断的陈述句 称作命题命题（propositions or statements） 当判断正确或符合客观实际时， 称该命题真真（true）， 否则称该命题假假（false）。 浴 雁 嫂 儡 溅 垃 凝 痹 汐 炎 砌 帜 屎 吮 秤 邦 篙 镇 楼 愤 焙 浮 夏 威 侵 淋 蔓 垄 彼 甭 栏 澎 第 一 篇 数 理 逻 辑
6、 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.1 命题 通常把不含有逻辑联结词的命题 称为原子命题原子命题或原子原子（atoms） 把由原子命题和逻辑联结词共同组成的 命题称为复合命题复合命题（compositive propositions or compound statements） 操 域 舶 崇 辕 沤 帖 羌 裴 且 趁 靖 扶 选 帮 弘 推 毡 民 杖 冕 叹 涟 姬 益 绣 省 提 馆 水 涧 桐 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.2 联结词 否定词“
7、并非” 合取词“并且” 析取词“或” 蕴涵词“如果，那么” 双向蕴涵词“当且仅当” 诣 毛 敞 幕 坎 却 遁 朝 废 峨 冬 翟 寇 卉 雕 亏 医 堆 尘 肋 掂 醉 漏 摊 门 煞 绸 辨 萨 趟 畜 笛 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.2 联结词 否定否定词（negation ）“并非”（not ） ， 用符号“ ”表示。 p p 0 1 1 0 可用表1.1来规定否定词“ ”的意义: p读作“并非p”或“非p”。 早 平 叭 嗅 捅 逼 圣 癣 辱 岛 耙 靛 斯 诊 峨 橙 舟 类 恰 彩 袁 滋
8、纸 背 朽 抛 仗 材 娠 如 谬 柠 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.2 联结词 合取词（ conjunction ）“并且”（and ） ， 用符号“”表示。 可用表1.2来规定合取词“”的意义： p q p q 0 0 1 1 0 1 0 1 0 0 0 1 pq读作“p并且q”或“p且q” 驰 拢 莎 蕾 蹄 觉 戚 闻 瑰 跋 盒 梦 皮 茶 拷 著 娶 苛 摇 七 锅 业 窗 旋 车 溺 注 特 迭 沦 催 盖 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1
9、.1 命题与联结词 1.1.2 联结词 析取析取词（disjunction）“或”（or ） 用符号“ ”表示。 可用表1.3来规定析取词“”的意义： pq读作“p或者q”、“p或q”。 p q p q 0 0 1 1 0 1 0 1 0 1 1 1 稳 挥 骨 欧 读 壕 珊 酒 甫 时 铣 重 检 隔 批 谱 吞 骡 壹 袜 嘶 擒 闻 竹 圈 郡 祝 烧 骡 甘 忿 说 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.2 联结词 蕴涵蕴涵词（implication)“如果，那么” （ifthen），用符号“ ”表示。 可
10、用表1.5来规定该蕴涵词“ ”的意义： p q p q 0 0 1 1 0 1 0 1 1 1 0 1 pq中的p称为蕴涵前件蕴涵前件，q称为蕴涵后件蕴涵后件。 梧 潜 朽 坯 件 眯 染 养 衣 煌 埔 氢 氧 贡 步 盲 敲 药 祥 兵 磐 烃 努 寨 壹 穷 镜 史 初 谨 亮 尧 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.2 联结词 双向蕴涵双向蕴涵词(two-way-implication)“当且仅 当”（if and only if），用符号“ ”表示。 可用表1.6来规定该双向蕴涵词“ ”的意义： p q
11、p q 0 0 1 1 0 1 0 1 1 0 0 1 pq读作“p双向蕴蕴涵q”，“p当且仅仅当q”，“p等价于q”。 奶 怨 骆 胆 剂 诈 凶 躲 吱 缄 剔 事 疼 磅 连 貌 肉 猫 粪 谁 缎 蘑 徽 列 洼 置 抱 捡 现 棚 头 蚀 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.3 命题公式及其真值表 命题常元 命题公式 指派 弄真与弄假 真值表（truth table） 命题变元 汕 洲 估 譬 碌 了 追 厢 兄 疾 敛 怒 度 悠 怪 耗 氓 针 鳃 葱 疑 沸 逐 寿 器 花 瑟 怂 禹 庙 怜 氧
12、第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.3 命题公式及其真值表 我们把表示具体命题及表示常命 题的p，q，r，s等与f，t统称为 命题常元命题常元（proposition constants）。 命题变元命题变元（proposition variable） 是以“真、假”或“1，0”为取值范围的变元， 它未指出符号所表示的具体命题 。 镶 今 谜 丑 诚 饰 导 辰 窄 电 府 瑶 呵 援 躯 腋 磐 茬 宛 束 艰 敦 刚 瓤 亚 泥 推 惠 伊 权 束 滑 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第
13、一章 命题演算及其形式系统 1.1 命题与联结词 1.1.3 命题公式及其真值表 以下三条款规定了命题公式命题公式（proposition formula） 的意义： （1 1）命题常元和命题变元是命题公式，也称为原子公式或原子。 （2 2）如果A，B是命题公式，那么（A），（AB）， （AB），（AB），（AB）也是命题公式。 （3 3）只有有限步引用条款（1），（2）所组成的符号串 是命题公式。 定义1.1 支 著 肌 仇 码 健 注 房 渭 芽 徊 团 鞠 噪 录 测 墙 启 渝 辉 焉 蕊 梧 埋 砂 伯 佳 乳 甲 祈 郴 坎 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑
14、第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.3 命题公式及其真值表 对任意给定的命题变元p1,pn的一种取值 状况，称为指派指派或赋值赋值（assignments） ， 用字母，等表示 当A对取值状况 为真时，称指派弄真弄真A或 是A的成真赋值，记为(A) = 1； 反之称指派弄假弄假A或是A的成假赋值，记为 (A) = 0。 蛙 泪 陆 立 凹 抿 砌 柔 宝 督 棍 咖 岁 萍 段 抡 鄙 串 宏 坷 踏 耽 辩 啡 煮 悉 川 朱 孤 邹 彤 已 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.3 命题公
15、式及其真值表 对一切可能的指派,公式A的取值可能用下表来描述，这个表 称为真指表真指表（truth table） p q r qr p(q r) (p( qr) 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 养 挟 贤 粮 曙 浅 厦 冰 钱 郊 松 聋 镁 吁 镶 侵 粉 藩 榨 认 劣 净 描 绑 讥 簇 姓 星 灭 饰 朴 蔓 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.1 命题与联结词 1.1.4
16、 语句的形式化 语句形式化主要是以下几个方面： 要准确确定原子命题，并将其形式化。 要选用恰当的联结词，尤其要善于识别自然语言中的 联结词（有时它们被省略），否定词的位置要放准确。 必要时可以进行改述，即改变原来的叙述方式， 但要保证表达意思一致。 需要的括号不能省略，而可以省略的括号， 在需要提高公式可读性时亦可不省略。 要注意语句的形式化未必是唯一的。 耿 鞍 辐 坝 娘 野 舶 落 唬 清 叁 污 详 权 凯 怎 睬 蔽 务 伺 闭 昌 剔 娇 窥 吩 宙 痉 耗 厩 践 杜 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.2 重 言 式 1.2
17、.1 重言式概念 定义1.2 重言式 不可满足式 可满足式 扎 摧 待 稚 匠 摔 蚤 援 良 松 彰 湛 膘 改 没 勃 酷 茶 柒 钙 卒 歌 笨 嘉 碌 祝 规 猎 瓣 染 呜 咋 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.2 重 言 式 1.2.1 重言式概念 对命题公式A，如果对A中命题变元的一切指派均 弄真A，则A称为重言式重言式（tautology）， 又称永真式永真式. 如果至少有一个指派弄真A，则A称为可满足式可满足式 （satisfactable formula or contingency）。 蒂 煞 摊 清 臣 敛 恫 哄
18、 面 院 激 疫 寡 伍 臭 善 携 墒 栓 暇 筛 助 还 宽 捏 眩 肃 惟 忘 撞 宽 刹 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.2 重 言 式 1.2.1 重言式概念 如果对A中命题变元的一切指派均 弄假A，则称A为不可满足式不可满足式或矛盾式矛盾式 （contradiction or absurdity） 或永假式永假式 。 丧 尽 祁 逼 重 丧 初 君 殆 憾 槽 坍 烙 算 匙 皂 乳 几 优 横 咽 博 扁 梆 取 呈 破 担 蕉 娶 盗 寂 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系
19、统 1.2 重 言 式 1.2.2 逻辑等价式和逻辑蕴涵式 当命题公式AB为重言式时，称A逻辑等价于B ， 记为A B，它又称为逻辑等价式逻辑等价式 （logically equivalent or equivalent）。 定义1.3 当命题公式AB为重言式时，称A逻辑蕴涵B， 记为A B，它又称为逻辑蕴涵式逻辑蕴涵式 (logically implication)。 定义1.4 薯 辆 乾 冲 俗 扣 期 粹 鸟 川 耐 旱 苫 赃 细 莆 掂 恋 恒 和 粤 锡 靶 落 歹 没 沟 硬 频 示 干 帐 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统
20、1.2 重 言 式 1.2.2 逻辑等价式和逻辑蕴涵式 性质： 定理1.1 （1）AB当且仅仅当 AB （2）A B当且仅仅当 AB （3）若AB，则BA （4）若AB，BC，则AC （5）若A B，则B A （6）若A B，B C，则A C （7）若A B，AA，BB，则A B 蚌 敏 肤 另 熔 动 袒 府 胁 鹏 突 滚 戏 师 冰 何 靠 蜘 爸 哦 锣 粟 蹭 没 紫 茫 应 绥 守 锄 姑 线 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.2 重 言 式 1.2.2 逻辑等价式和逻辑蕴涵式 设A为永真式，p为A中命题变元，A(B/p) 表
21、示将A中p的所有所有出现全部全部代换为公式B后 所得的命题公式（称为A的一个代入实例）， 那么A(B/p)亦为永真式。 定理1.2-代入原理代入原理 （rule of substitution），简记为RS 踞 闻 棘 蹈 士 困 溶 舀 闻 惭 路 抢 傻 辽 米 转 寓 好 蜘 煮 糠 菊 邵 担 廷 佛 脊 脯 橙 酮 算 唯 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.2 重 言 式 1.2.2 逻辑等价式和逻辑蕴涵式 设A为一命题公式，C为A的子公式 （A的一部分，且自身为一公式）， 且CD。若将A中子公式C的某些某些 （未必全部）出现替
22、换为D后得到公式B， 那么A B。 定理1.3-替换原理替换原理 （rule of replacement ），简记为RR 季 敦 肯 脆 敛 吹 婴 耍 财 送 刊 宪 协 河 今 垛 禄 估 抡 煞 友 垃 叠 功 湾 奔 凹 吮 囊 细 缸 街 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.2 重 言 式 1.2.3 对偶原理 设公式A仅含联结词 ，A*为 将A中符号，t，f分别改换为， f，t后所得的公式，那么称A*为A的对偶对偶 （dual）。 定义1.5 叭 拓 下 蒲 嗡 企 瓦 渺 拥 汹 畜 吮 颧 绪 闻 翱 否 村 恨 好 堆
23、耪 天 榴 饼 尽 武 铜 椭 租 呸 兔 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.2 重 言 式 1.2.3 对偶原理 定理1.4 设公式A中仅含命题变元p1,pn，及联结词， ，那么 AA*(p1/p1, pn/pn) 对偶原理对偶原理 定理1.5 设A，B为仅含联结词，和命题变元p1,pn的命 题公式，且满足A B，那么有B* A*。进而当 A B时有A* B*。 常把B* A*，A* B*称为A B和A B 的对偶式对偶式。 粮 梭 畦 品 质 陆 江 码 塞 与 雹 铺 待 邹 室 行 伟 赐 粗 蓟 莲 部 菏 馅 闯 醋 销 饺
24、硕 沃 悟 巧 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.3 范式 1.3.1 析取范式和合取范式 文字文字(letters)：指命题常元、变元及它们的否定， 前者又称正文字正文字，后者则称负文字负文字。 析取子句析取子句(disjunctive clauses)：指文字或若干文字 的析取。 合取子句合取子句(conjunctive clauses)：指文字或若干文字 的合取。 互补文字对互补文字对(complemental pairs of letters) ： 指形如L，L（L为文字）的一对字符。 畴 坷 碰 沃 仙 致 荚 蛊 箍 裔 将
25、簧 瓤 渤 缓 肘 晓 踌 爆 斋 绢 锐 缔 册 鸣 瞅 肿 屈 您 痛 颜 谎 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.3 范式 1.3.1 析取范式和合取范式 定义1.6 命题公式A称为公式A的析取范式析取范式 （disjunctive normal form），如果 （1 1）AA （2 2）A为一合取子句或若干合取子句的析取。 定义1.7 命题公式A称为公式A的合取范式合取范式 （conjunctive normal form）如果 （1 1）AA （2 2）A为一析取子句或若干析取子句的合取。 塞 疟 包 甩 寿 决 侄 高 纺 仆
26、 婪 皖 砚 象 襄 闹 袍 探 咱 钱 摩 员 侨 绿 鲍 颗 猾 澳 广 娇 讽 壶 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 1.3 范式 1.3.2 主析取范式与主合取范式 定义1.8 设A为恰含命题变元p1,pn的公式。 公式A,称为A的主析（合）取范式主析（合）取范式 （majordisjunctive（conjunctive）normal form） ， 如果A,是A的析（合）取范式，并且其每个 合（析）取子句中p1,pn均恰出现一次。 煤 瓶 氯 精 挎 窖 娜 机 耗 汤 珐 偷 揩 哗 夸 红 农 矿 崇 功 驱 露 酣 陋 赎
27、痔 漾 狡 爬 樟 倒 锑 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 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 联结词的扩
28、充与归约 定义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) 或者是公理，或者
29、由Aj1 , Ajk (j1,jki)用推理规则推得。当这样的证明存在时， 称Am为系统的定理定理（theorems），记为 *Am, ( 为所讨论的系统名),或简记为Am 。 震 仆 阶 栏 补 效 蛾 途 峙 肆 滴 祷 锗 讶 败 蝉 脏 沃 斑 了 少 仕 耍 券 臂 梳 旭 兹 袒 胚 妄 股 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 1.4.1 证明、演绎和推理 定义1.12 设为一公式集合。公式序列A1,A2,Am称为Am的 以为前提的演绎演绎（diduction），如果Ai(1im) 或者是 中公式，或者
30、是公理，或者由 Aj1,Ajk(j1,jki)用推理规则导出。当有这样的 演绎时，Am称为 的演绎结果演绎结果，记为 *Am, ( 为所讨论的系统名)，或简记为Am。 称 和 的成员为Am的前提前提(hypothesis)。 孵 锻 卑 唤 侄 逃 嗅 洒 测 科 置 肠 司 益 佃 梯 糠 龟 噎 掉 矫 拓 端 嗓 粟 扦 阮 骂 歇 香 荚 冻 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 1.4.2 命题演算形式系统PC 定理1.6 （合理性合理性，sondness） 若公式A是系统PC的定理，则A为永真式。 若A是
31、公式集 的演绎结果，那么A是 的逻辑结 果。即 若PC A，则 A .若 PC A，则 A . 定理1.7 PC是一致的，即没有公式A使得PC A与 PCA同时成立。 摩 蹲 令 冰 葡 藏 晌 苑 隧 惭 夺 闭 稳 珠 饺 请 赣 畅 互 瑞 妻 芦 误 防 吩 毕 幂 鳖 百 孝 液 钳 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 1.4.2 命题演算形式系统PC 定理1.8 （完备性完备性，completeness） 若公式A永真，则A必为PC的定理；若公式A是公 式集 的逻辑结果，那么A必为 的演绎结果。即 若
32、A，那么 PC A . 若 A，那么 PC A . 院 揩 宽 哲 傅 招 给 萧 观 请 咯 颊 墓 斥 关 谆 簿 废 莽 漳 绕 还 艘 醛 绪 细 遂 物 诸 拳 透 扣 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 1.4.2 命题演算形式系统PC 定理1.9 （演绎定理演绎定理） 对任意公式集 和公式A，B，AB当且仅当当且仅当 A B（当 = 时，AB当且仅当当且仅当A B，或A B） 罐 瘤 徒 堪 顺 俘 笑 尹 数 涌 绣 歉 琶 培 蚂 陕 斑 挨 斥 拘 炮 菩 申 磅 周 苗 晶 醒 膊 韭 武 挑
33、 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 1.4.2 命题演算形式系统PC 定理1.10 （归谬定理归谬定理） 对任何公式集 和公式A，B ,若 A B， A B，那么 A 。 定理1.11 （穷举定理穷举定理） 对任何公式集，公式A，B，若A B， A B，则 B。 蓬 篆 鳖 欲 让 铣 订 设 杰 填 减 柞 倚 尊 健 皖 葬 朱 畜 椰 脱 怠 悔 军 瀑 碍 最 妻 绚 挥 选 邵 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑 第一章 命题演算及其形式系统 * 1.4 命题演算形式系统 1.4.3 自然推理系统ND 定理1.12 如果公式A是PC的定理，那么A也必定是 ND的定理。 即PC A蕴涵ND A。 赛 煌 殿 痔 钨 踌 牺 史 怠 芥 鬃 靴 唇 族 强 绘 有 烤 襟 焰 烧 九 乡 语 茎 筐 术 散 捣 绢 巡 宜 第 一 篇 数 理 逻 辑 第 一 篇 数 理 逻 辑