The Foundations: Logic and Proofs
Chapter 1, Part I: 命题逻辑
大连东软信息学院-大数据科学系 褚娜
Copyright By PowCoder代写 加微信 powcoder
Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.
Section 1.1
命题是一个陈述句，它或真或假。
一个命题是真命题，其真值为真，表示为T ，反之为F。
命题变元: p, q, r, s, …
原子命题：命题不能分解为更简单的陈述语句。
2050年的元旦下雪。
复合命题：以命题作为直接构成成分的命题，或者，包含有其他命题成分的命题。
a) 我学英语，或者我学日语
b) 如果天气好，那么我去散步。
c) 我不去看电影。
命题 p 的否定是 ¬p ，真值表为:
例: p 表示“地球是圆的。”
¬p 表示“并非地球是圆的” 或者“地球不是圆的”
命题 p 和q 的合取表示为p ∧ q ，真值表为:
例: 命题p ：“我在家”
命题q ： “天在下雨”
p ∧q ： “我在家并且天在下雨”
合取联结词常用表述方式
命题p 和q的析取表示为p ∨q ，真值表为:
例: 命题p ：“我在家”
命题q ：“天在下雨”
p ∨q： “我在家或者天在下雨”
“或” 有两个不同的含义
“兼或” – “他可能是100米或400米赛跑的冠军”p ∨q 是真, p 和q之一或都为真。
“异或Xor” – “开胃菜：汤或沙拉”。
p ⊕ q , p和q , 只有一个为真. ⊕ 的真值表是：
析取联结词常用的表述方式
p 和q 是命题, p →q是条件语句，意思是 “如果 p, 那么 q ” 真值表:
例 命题p ：“我在家”
命题q ：“天在下雨”
p →q ： “如果我在家，那么天在下雨”
p →q , p 称为假设(前件、前提) ， q 称为结论(后件)。
p →q 假设和结论之间没有必然的联系。p →q 的值仅依赖于p 和 q 的真值。
数学推理中考虑的条件语句比自然语言中使用的广泛。
“如果月饼是奶酪做的, 那么我比盖茨有钱。”
“如果今日天晴，那么我们就去海滩。”
“如果 1 + 1 = 3, 那么你奶奶穿战斗靴。”
将蕴含理解为合同或义务
“如果我当选了，那么我将会减税。”
“如果你在期末考试得了100分, 那么你将得到一个A。”
如果政治家当选了却没有减税，选民认为政治家违背了竞选诺言。
对应p是真q 是假。
p →q常用的表述方式
如果 p, 那么 q p 蕴含 q
如果 p, q p 仅当q
q 如果 p q 当 p
q 除非 ¬p q 每当 p
p 的必要条件是q q 的充分条件是p
p 是 q的充分条件
q 是 p的必要条件
逆命题, 反命题, 逆反命题
由 p →q(原命题)可以构成新的条件语句
q →p 是p →q 的逆命题
¬q → ¬ p 是p →q 的逆否命题
¬ p → ¬ q 是p →q 的反命题
例: 找出如下语句的逆否命题、逆命题和反命题“每当下雨时，主队就能获胜。”
逆否命题：如果主队没有获胜，那么没有下雨。
逆命题：如果主队获胜，那么下雨了。
反命题：如果没有下雨，那么主队没有获。
双条件语句，双向蕴含
p 和q 是命题, p ↔q 是双条件语句, 读作 “p 当且仅当 q”。
p ↔q 真值表：
命题p ：“我在家”
命题q ：“天在下雨”
p ↔q ：“我在家当且仅当天在下雨”
p ↔ q 的一些表达方式
p是q的充分必要条件
如果 p 那么 q , 反之亦然
确认原子命题 ，用命题变元表示。
“如果我去Harry家或乡下，我就不去购物.”
p：我去Harry家
如果 p 或 q 那么非 r.
王强身体很好，成绩也很好。
如果a和b是偶数，则a+b是偶数。
当机的原因在于语法错误或程序错误。
如果你不看电影，那么我也不看电影。
控制台打字机既可作输入设备，又可作输出设备。
你能够毕业仅当你已经完成了专业的要求并且你不欠大学学费并且你没有逾期不归还图书馆的书。
Operator Precedence
p q r 是(p q) r
如果意思是p ( q r ) 则必须使用括号。
原子命题每一个可能的值。
p q r p q r p q → r
p q r p q r p q → r
T F T T F
p q r p q r p q → r
T T T T F F
T T F T T T
T F T T F F
T F F T T T
F T T T F F
F T F T T T
F F T F F T
F F F F T T
对于n 个命题变元，真值表中有多少行?
n 个命题变元, 构建2n 个 不同的(不等价的)命题。
两个命题是等价的，总是有相同的真值
例: 由真值表可知，原命题等价于逆否命题。
p q ¬ p ¬ q p →q ¬q → ¬ p
T T F F T T
T F F T F F
F T T F T T
F F T T T T
例：由真值表可知，逆命题、反命题与原命题是不等价的
p q ¬ p ¬ q p →q ¬ p →¬ q q → p
T T F F T T T
T F F T F T T
F T T F T F F
F F T T T T T
蕴含; 逆命题, 反命题, 逆反命题
Section 1.2
把语句翻译成逻辑表达式
“你可以在校园访问因特网，仅当你主修计算机科学或者你不是新生。”
令a 表示你可以在校园访问因特网
c 表示你主修计算机科学
a→ (c ∨ ¬ f )
系统和软件工程师根据自然语言的需求，生成精确无二义性的规范说明。
“当文件系统已满时，不能够发送自动应答”
解: 令 p 表示 “能够发送自动应答”
q 表示 “系统文件已满”
系统规范说明书的一致性
定义:命题列表是一致的，如果分配的命题变量的真值，使每个命题是真。
“诊断消息存储在缓冲区或者被重传” p ∨ q
“诊断消息没有存储在缓冲区” ¬p
“如果诊断消息存储在缓冲区中，那么它被重传” p → q
解: 令p 表示 “诊断消息存储在缓冲区”
q 表示 “诊断消息被重传”
当 p 是F ， q 是T， 上述三个命题均为T。所以这些规范说明是一致的。
如果加入一个系统规范说明“诊断消息没有被重传”
解: ¬q ，不满足一致性。
一个岛上居住着两类人——骑士和无赖。骑士说的话都是真话，而无赖只会说假话。
你在岛上碰到两个人 A 和 B
A 说 “B 是骑士”
B 说 “我们两个是两类人”
说明: A 和 B到底是什么样的人?
(Born 1919)
解: 令 p 表示“A是骑士” q 表示“B是骑士”
那么 p 表示“A是无赖”，q 表示“B是无赖”
如果A是骑士, p 的真值为 T，则q 的真值必为T，因此A和B是一类人。
如果B是骑士，B 说 “我们两个是两类人”，
即(p ∧ q)∨ ( p ∧ q) 应该为T。 因此p 为真，即p为假，A不是骑士。
同理，如果 A 是无赖, 那么 B 也是无赖。 p 和 q 的真值为T。
如果 B 是无赖，这与A和B都是无赖是一致的。
(Born 1919)
数字电路; 每个输入/输出信号用0或1表示
0 表示 False
1 表示 True
复杂电路可以通过三种基本的门电路构造。
非门 (NOT gate)接受一个输入位，输出该位的否。
或门 OR gate 接受两个输入位，输出这两个位的析取值。
与门 AND gate接受两个输入位，输出这两个位的合取值。
有一会议室，四周都有出入门，门旁装有开关（双态开关）。为了控制全室的照明，要求设计一个线路，使得改变任一个开关的状态，就能改变全室的明暗。假设，室中无人时灯暗，有人时亮。
写出控制电路的逻辑表达式并画出电路图。
Section 1.3
重言式, 矛盾式, 可能式
重言式是命题的真值永远为真。
矛盾式是命题的真值永远为假。
可能式是命题既不是永真式也不是矛盾式。
P ¬p p ∨¬p p ∧¬p
两个复合命题 p 和 q 是逻辑等价的，即为 p ↔ q 是永真式
写成 p⇔q 或者 p≡q
当且仅当真值表中对应的两列的真值相同
p q ¬p ¬p ∨ q p→ q
¬p ∨ q ≡ p → q
(¬p ∨ q ) ↔ (p → q) ≡ T
p q ¬p ¬q (p∨q) ¬(p∨q) ¬p∧¬q
T T F F T F F
T F F T T F F
F T T F T F F
F F T T F T T
德摩根第二定律真值表如下：
恒等律: ,
支配律: ,
幂等律: ,
否定律: ,
重要的逻辑等价式(续)
交换律: ,
涉及条件语句的逻辑等价
涉及双条件语句的逻辑等价
通过一系列逻辑等价语句说明两个表达式在逻辑上等价。
证明 从 A 到 B展开一系列的逻辑等价式。
注意：等值演算过程中出现的命题，可以由任意复杂的复合命题所取代。
例: 证明 和 是逻辑等价的。
¬(p∨(¬p∧q)) ≡ ¬p ∧ ¬(¬p∧q) 由德摩根定律
≡ ¬p ∧ (¬(¬p)∨¬q) 由德摩根定律
≡ ¬p ∧ (p ∨¬q) 由双重否定律
≡ (¬p ∧ p) ∨(¬p ∧ ¬q)由分配律
≡ F ∨(¬p ∧ ¬q) 因为¬p ∧p ≡ F
≡ ¬p ∧ ¬q 由F的恒等律
例: 证明 是永真式
由析取的结合律和交换律
在空格中写出等值演算的依据：
p→(q∨r)≡¬p ∨(q ∨r)
≡ ¬p ∨ ¬p ∨ q ∨r
≡ (¬p ∨ q) ∨(¬p ∨ r)
≡(p →q) ∨(p →r)
化简下列命题公式并将最后结果用只含和表示
证明(p∧(p→q)) →q为重言式
一个复合命题是可满足 的，如果存在一个对其真值得赋值使其为真。
一个复合命题是不可满足 的，即复合命题对其所有变元的真值赋值的都是假的，即 当且仅当 它的否定对所有变元的真值赋值都是真的。
Example: 确定下列复合命题是否可满足
Solution: 可满足。令 p, q, 和 r的真值为T。
Solution: 可满足。令 p 的真值为T，q的真值为F。
Solution: 不可满足。检测每一个可能的真值组合情况，均为假。
数独谜题 表示为一个99 格，每格由 33 子格构成，称为 块。81 单元中的部分都赋予1,2, …, 9中的数字之一。
谜题的解释通过给每个空白单元赋予一个数字来实现，使得每一行、每一列、每个小九宫格都包含九个不同的数字。
n皇后问题 要求在一个n×n的棋盘上放置n个皇后，目的是使皇后之间不能相互吃掉。
意味着没有两个皇后被放置在同一行、同一列或同一对角线上。如图是8皇后问题的一个解。
设：第i行第j列放置一个皇后
真值表可以用于判定复合命题是否为可满足的。但是，当变量数目很大时，就变得困难了。
重言式, 矛盾式, 可能式
/docProps/thumbnail.jpeg
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com