十命题逻辑

《十命题逻辑》由会员分享，可在线阅读，更多相关《十命题逻辑（75页珍藏版）》请在金锄头文库上搜索。

1、数理逻辑数理逻辑 数理逻辑 数理逻辑是用数学方法研究形式逻辑中推 理规律的一种理论. 数理逻辑的研究对象： 从宏观上讲, 数理逻辑是数学的基础, 它的研 究分证明论、模型论、递归论和集合论等四 大理论 从狭义上讲, 它是研究形式逻辑推理规则的一 门数学. 数理逻辑 数理逻辑的研究方法 采用数学的方法研究演绎性推理形式逻辑的 规律. 引进一套符号体系的方法, 因此数理逻辑又称 符号逻辑. 本篇内容： 命题逻辑 谓词逻辑 命题逻辑和谓词逻辑的公理化证明 第十章 命题逻辑 命题逻辑是数理逻辑的基础, 它以命题为 研究对象, 研究基于命题的符号逻辑体系 及推理规律, 它也可称命题演算. 10.1.1

2、命题 命题：能判断真假的陈述句 真值：命题的值称真值，真值有T,F两种 例： 1)雪是黑的 2) 1+101=110 3) 别的星球有生物 4) 我正在说谎 5) 天气多好啊！ 6) 我学英语, 或者我学日语 7) 明天是否开大会？ 命题 命题 命题 悖论，不是命题 不是陈述句 命题 不是陈述句 10.1.1 命题 原子命题：最简单的不可再分的命题 复合命题：由联结词, 标点符号和原子命题复合构 成的命题 一般用P,Q,R等大写拉丁字母表示命题 命题常量：命题标识符如表示确定的命题 命题变元：命题标识符只表示任意命题的位置标志 命题变元可以表示任意命题, 所以它不能确定真值, 故不是 命题 1

3、0.1.2 命题联结词 常用的5个命题联结词 1) “并且” (合取) PQ：“P并且Q”, P与Q的合取式, 而P、Q分别 叫做此合取式的合取项. 真值表 PQ PQ TTT TFF FTF FFF 10.1.2 命题联结词 例：王华的成绩很好并且打得一手好球 解： P: 王华的成绩很好 Q: 王华打得一手好球 王华的成绩很好并且打得一手好球: PQ 对“并且”可以有多种不同表达方式： “同时”、“和”、“与”、“同”、“以及”、“而且”、“不 但而且”、“既又”、“又”、“尽管仍然 ”、“虽然依旧” 例：尽管他生病但他仍坚持工作 10.1.2 命题联结词 2) “或者” (析取) PQ：”

4、P或者Q”, P与Q的析取式, 而P、Q分别 叫做此析取式的析取项. 真值表 PQ P Q TTT TFT FTT FFF 10.1.2 命题联结词 例： 今天晚上我写字或看书 解： P: 今天晚上我写字 Q: 今天晚上我看书 今天晚上我写字或看书: PQ 对“或者”可以有多种不同表达方式： “或”、“或许”、“可能” 例：明天我可能看电影也可能逛公园 10.1.2 命题联结词 3) “否定” P ：“非P” 真值表 PP TF FT 10.1.2 命题联结词 例：赵玲不是个好学生 解： P: 赵玲是个好学生 赵玲不是个好学生: P 对“否定”可以有多种不同表达方式： “非”、“不”、“没有”

5、、“无”、“并非”、“并不” 例：他并不喜欢打球 10.1.2 命题联结词 4) “蕴含” (条件) PQ：”P蕴含Q”, “如果P则Q”. P称为PQ的前 件, Q称为PQ的后件. 真值表 PQPQ TTT TFF FTT FFT 10.1.2 命题联结词 例：如果明天天气晴朗, 则举行运动会 解： P: 明天天气晴朗 Q:举行运动会 如果明天天气晴朗, 则举行运动会: PQ 对“蕴含”可以有多种不同表达方式： “当则”、“若那么”、“假如那么” 例：倘若他生病了他就不参加这次会议 10.1.2 命题联结词 5) “等价” (双条件) PQ：P与Q的等价式, “P等价Q”, P、Q分别叫 此

6、等价式的两端. 真值表 PQ PQ TTT TFF FTF FFT 10.1.2 命题联结词 例：20 解： P: 20 20: PQ 对“等价”可以有多种不同表达方式： “充分必要”、“只有才能”、“相同”、“相等”、“ 一样” 、“等同” 例：只有睡觉才能消除疲劳 10.1.2 命题联结词 在命题联结词中有些地方与一般习惯用语是不同 的： 1) 两个逻辑上完全没有联系的命题可加以命题联结 词而形成新的复合命题. 2) 有的联结词在日常用语中可有多种逻辑含义, 但 在命题逻辑中有确定含义, 如命题逻辑中的“或” 是“可兼或”的或. 3) 对于“蕴含”, 在命题逻辑中, 当其前件为假时, 则

7、不论其后件是真还是假其整个蕴含式一定为真. 4) 命题联结词是命题间的联结词而不是名词或形容 词间的联结词. 10.1.3 复合命题 由原子命题经命题联结词可构成各种形式的复合 命题, 在复合命题中，为减少括号的使用，作出 以下规定： 1) 5个联结词的结合能力强弱顺序为： “否定” “合取” “析取” “蕴含” “等 价” 2) 规定具有相同结合能力的联结词, 按其出现的 先后次序, 先出现者先运算 3) 最外层括号可省去 例: (P(Q)R) (RP)Q) 可写成：(PQR) RPQ 10.1.3 复合命题 例10.13 设命题P为“明天上午七点下雨”, Q为“明 天上午七点下雪”, R为

8、“我去学校” 1) 如果明天上午七点不是雨夹雪则我去学校 (PQ)R 2) 如果明天上午七点不下雨并且不下雪则我去学校 PQR 3) 如果明天上午七点下雨或下雪则我不去学校 PQR 4) 明天上午七点我将雨雪无阻一定去学校 PQR PQR PQR PQR 10.1.3 复合命题 5) 只有当明天上午七点不下雪并且不下雨时我才去 学校 PQR 例10.14： 命题“说数理逻辑枯燥无味或毫无价值 , 那是不对的”, 翻译成命题公式. 解； P: 数理逻辑有味 Q: 数理逻辑有价值 (PQ) 10.1.3 复合命题 例10.15 “除非你陪伴我或代我叫辆车子, 否则我 不出去”, 翻译成命题公式.

9、解： P: 你陪伴我 Q: 你代我叫辆车 R: 我出去 PQR 或 PQR 例10.16 “天黑了, 我得回家了” 解： P:天黑了 Q: 我得回家了 PQ 10.1.3 复合命题 例10.17 计算机机房规则: “凡进入机房者, 必须 换拖鞋, 穿工作服; 否则罚款人民币10元”, 翻译成 命题公式. 解： P: 某人进入机房 Q: 某人换拖鞋 R: 某人穿工作服 S: 某人需罚款人民币10元 凡进入机房者, 必须换拖鞋, 穿工作服 PQR 否则罚款人民币10元： (PQR)S 10.1.3 复合命题 例: “除非你年满18岁，否则只要你身高不足1.6 米就不能乘坐过山车”,翻译成命题公式.

10、 解： 找出原子命题： P: 你年满18岁 Q: 你身高不足1.6米 R: 你乘坐过山车 A：只要你身高不足1.6米就不能乘坐过山车: =只要Q就非R：QR 除非你年满18岁，否则A: =如果非P则A: P(QR) 10.1.3 复合命题 关于物质有以下两种定义： 1) 占据空间、有质量并且不断变化的客体称为物质 . 2) 占据空间、有质量的客体称为物质, 而物质是不 断变化的. 请问关于物质的这两种定义有什么区别? 试用命 题逻辑进行分析. 10.1.3 复合命题 解：设命题 P: 它占据空间 Q: 它有质量 R: 它不断变化 S: 它是物质 定义(1): PQRS 定义(2): (PQS)

11、(SR) 不同点在于： 定义(2)含有“如若PQ为真, 则必有R为真”的意 思, 即“占据空间并且有质量的客体一定是不断变 化的客体”, 而定义(1)没有这个含义. 10.2 命题变元与命题公式 常值命题是一个特定的命题, 它只有“T”与“F”两种 命题变元是一个任意的没有赋予具体内容的命题 . 定义10.1 以“真”“假”为其变域的变元称为命题变元, 用 P,Q,R表示, 它也可以称为命题. 10.2 命题变元与命题公式 由命题经命题联结词可构成命题逻辑公式, 亦可 叫命题公式或公式 定义10.2 命题逻辑公式(简称公式)可按如下法则生成: 1) 命题是公式 2) 如果P是公式, 则(P)是

12、公式 3) 如果P,Q是公式, 则(PQ), (PQ), (PQ), (PQ)是公式 4) 公式由且仅由有限次使用(1)(2)(3)而得. 即，命题公式是一个按上述法则由命题变元、命 题联结词及圆括号组成的字符串. 10.2 命题变元与命题公式 一个命题公式的真假由组成它的命题的真假唯一 确定, 故命题公式可看成是一个以真、假为定义 域, 以真、假为值域的函数. 可以用真值表方法来确定一个命题公式的真假, 此真值表称为命题公式真值表. 设有一个由n个命题变元P1, P2, , Pn个所组成 的公式, 则此公式的真假由此n个命题变元所唯一 确定. 给n个命题变元P1, P2, , Pn一组确定的

13、值 后, 则公式亦可以得到一个确定的值. 命题变元的 一组确定的值叫做公式的一个指派. 所有指派构 成的公式的值即组成了此公式真值表. 10.2 命题变元与命题公式 例：(PQ)(PQ)的真值表 PTTFF QTFTF PQTFFF (PQ)FTTT QFTFT PQFTFF (PQ)TFTT (PQ) (PQ) TFTT 10.3 重言式 定义10.3 一个公式如果对其所有指派均取值为真, 则称此 类公式为永真公式或叫重言式(tautology). 反之,一个公式如果对其所有指派均取值为假, 则 称此类公式为永假公式或叫矛盾. 定义10.4 一个公式如果至少存在一个指派使其取值为真, 则称此

14、公式为可满足公式. 10.3 重言式 重言式的性质: 1) 两个重言式的否定是矛盾, 矛盾的否定式重言式. 2) 两个重言式的合取、析取、蕴含、等价均为重言 式. 3) 若两个公式的等价是重言式, 则这两公式对任何 指派必同真假. 如果等价式PQ为永真, 则称为等价重言式, 并 记为 它们也可称为P与Q相等, 记为P=Q 如果等价式PQ为永真, 则称为蕴含重言式, 并 记为 10.4 命题逻辑的基本等式 交换律： (1) PQ = QP (2) PQ = QP (3) PQ = QP 结合律： (4) (PQ)R = P(QR) (5) (PQ)R = P(QR) (6) (PQ)R = P(

15、QR) 10.4 命题逻辑的基本等式 分配律： (7) P( QR) = (PQ)(QR) (8) P(QR) = (PQ)(QR) (9) P(QR) = (PQ)(QR) 否定深入： (10) P = P双否定律 (11) (PQ) = PQ德摩根定律 (12) (PQ) = PQ德摩根定律 (13) (PQ) = PQ (14) (PQ) = PQ = PQ 10.4 命题逻辑的基本等式 变元等同： (15) PP = P (16) PP = P (17) PP = F (18) PP = T (19) PP = T (20) PP = P (21) PP = P (22) PP = T (23) PP = PP = F PQPQ TTT TFF FTT FFTPQPQ TTT TFF FTF FFT 10.4 命题