第六讲 命题演算系统

6
§5.联结词归约 范式(NF)
证. 对于任一真值函项f(p1, p2, , pn)(n1),设f所有的证实赋值 构成的集合为 {v|f(v)=t}={v1, v2, , vm} (m2n) 其中:vi= (p1vi , p2vi, , pnvi) (1 i m) 。 对于每一个vi ,构造如下的合取式: i= q1i q2i qni (1 i m) 其中: vi
注. 在《数字逻辑》与《数字电路》中称为“与非门(NAND) ” 。3Leabharlann §5.联结词归约 范式(NF)
(3)“或非(not-or) ” 表示“或非”的符号是: 符号 称为谢孚竖(Sheffer stroke)。 对于两个命题p和q, p和q的或非命题“p或q不成立”表 示为：pq 。 pq称为p和q的或非式。 p q pq pq为真p且q为假。 t t f “或非”的真值表见表3: t f f pq (pq) pq ； f t f p pp; f f t pq (pp)(qq) ; 表3 pq (pq)(pq) 。

p q为真p、q之一为真(不能同时为真) 。
1
§5.联结词归约 范式(NF)
“异或”的真值表见表1: 常见的析取词还有: 不是,就是;可能,可能; 或者, 或者；。 p q (pq) (pq)(pq) (pq)(pq) p q ⊨pq , 反之不成立。
w(p,q, r) f
例1.表4给出了一个三元真值函项w: 于是w(p,q, r) (pqr)(pqr) qr (qr) ; p w(q,p, p) ; (q任意) pq p q w(r, p, q) w(r, w(r,p, p) , w(r,q, q) ) (r, r, r任意)

¬p, p∧q，p∨q, p→q； (p∧q)→r，p∧(q→r)，…； ((p→∨q→pq)，(((p→q∧r)∨)，… 按照形成规则形成的符号串称为合式公式。
2011年4月5日星期二
3
形成规则
(1)任何单个的命题变元p是合式公式； (2)如果A是合式公式，则(¬A)是合式公式； (3)如果A和B是合式公式，则(A∧B)、(A∨B)、 (A→B)是合式公式； 只有（1）----到（3）形成的符号串是合式公式。
推演规则
（1）整推规则 ） （2）置换规则 ） （3）条件证明规则 ） （4）间接证明规则 ）
2011年4月5日星期二
8
整推规则
1.合取引入规则(记为∧+)： 从A和B推出A∧B； 2.合取消去规则(记为∧_): 从A∧B推出A；从A∧B推出B； 3.析取引入规则(记为∨+)： 从A推出A∨B；从B推出A∨B； 4.析取消去规则(记为∨_): 从A∨B和¬A推出B；从A∨B和¬B推出A； 5.肯定前件（记为MP) 从A→B和A推出B; 6.否定后件规则（记为MT); 从A→B和¬B推出¬A;
主联结词： 主联结词：辖域最大的联结词。
(((p∨q)∧(¬p))→q)的主联结词是→。
省略括号的约定： 省略括号的约定：
(1)公式最外层的括号可以省略。 (2)联结词的结合力依下列次序递减：¬，∧，∨，→，↔。 如：(((p∨q)∧(¬p))→q)可简记为(p∨q)∧¬p→q。
2011年4月5日星期二 7
2011年4月5日星期二
前提 前提 前提 前提 ⑵⑷否后 ⑵⑷否后 ⑴⑸肯前 ⑴⑸肯前 ⑶⑹假言三段论 ⑶⑹假言三段论
11
例2：B→┐A ： B∧（C→D） ∧ ） A∨C ∨ ∴ D ⑴ B→┐A ⑴B→┐A ⑵ B∧（C→D） ∧ ） ⑶ A∨C ∨ ⑷B ⑸ C→D ⑹ ┐A ⑺C ⑻D

• 公理集
–公理是用于表达推理由之出发的初始肯定命题；
• 推理规则集
计算机学院
–推理规则是由公理及已证定理得出新定理的规则；
• 定理集
–表达了肯定的所有命题。
计算机学院
2
2
命题逻辑的公理系统
▪ 定义3.1 命题逻辑的公理系统定义:
▪ 符号
• 命题变元p1,p2,…pn
• 联结词符号，; • 括号(,)
▪ 推理序列 • Γ=Q，公式集——前提 • A1、A2、A3 ——推理序列 • A3 ——结论
A1
QΓ
计算机学院
计算机学院
8
8
演绎与推理序列
▪ 定义3.2 设Γ是合式公式集, Q是合 式公式，有推理步骤A1,A2,…An， 公式序列α1, α2,… αn ，其中
▪ Γ称为推演的前提集， 称α为结论
A2
▪ A3=((QQ)(QQ))((QQ)Q) A2=A1 A3
▪ A4= (QQ) (QQ)
A1
▪ A5=(QQ)Q
计算机学院A3=A4 A5
计算机学院
30
30
▪ ├QRQ ▪ A1= Q(RQ) ▪ A2= QRQ
A1
QR=(QR)
计算机学院
计算机学院
31
31
▪ ├ QR RQ
▪ A1=(RQ)(Q R)
▪ A2=((RQ)(Q R))
▪
((QR)(RQ))
▪ A3= (QR)(RQ) ▪ A4= QR RQ
├ (RQ)(Q R) ├ (RQ)(Q R) QR =(QR)
计算机学院
计算机学院
32
32
▪ ├ QRQ
▪ A1= Q(R Q) ▪ A2= (RQ)(QR) ▪ A3= Q(Q R)

命题逻辑命题逻辑以逻辑运算符结合原子命题来构成代表“命题”的公式，以及允许某些公式建构成“定理”的一套形式“证明规则”。

（相对于谓词逻辑，它是量化的并且它的原子公式是谓词函数；和模态逻辑，它可以是非真值泛函的。

）目录1简介2文法3演算4推理规则1简介演算是用来证明有效的公式（就是说它的定理）和论证（argument）的逻辑系统。

它是公理或公理模式的集合（它可以为空或是可数无限集合），和推导有效的推理的推理规则。

形式文法（或语法）递归定义语言的表达式和合式公式（well-formed formula 经常缩写为wff）。

此外给出定义真值和求值（或释义）的语义。

它允许我们确定哪个 wff 是有效的（也就是定理）。

在命题演算中语言由命题变量（或者叫占位符（placeholder））和句子/判决算子（或者叫连结词）。

wff 是任何原子公式或在句子操作符之上建造的公式。

在下文中我们描述一种标准命题演算。

很多不同的公式系统存在，它们都或多或少等价但在下列方面不同：⑴它们的语言（就是说哪些操作符和变量是语言的一部分）；⑵ 它们有哪些（如果有的话）公理；⑶采用了哪些推理规则。

2文法语言的构成：字母表的大写字母，表示命题变量。

它们是原子公式。

惯例上，使用拉丁字母（A,B,C）或希腊字母（χ，φ，ψ），但是不能混合使用。

表示连结词（connective)（或逻辑算子）的符号： &not；、∧、∨、→、?。

（我们可以使用更少的算子（和相应的符号），因为一些算子是简写形式—例如，P → Q 等价于¬ P ∨ Q）。

左右圆括号：（，）。

合式公式（wff）的集合右如下规则递归的定义：基础：字母表的字母（通常是大写的，如A、B、φ、χ 等）是 wff。

归纳条款 I: 如果φ 是 wff，则¬ φ 是 wff。

归纳条款Ⅱ 如果φ 和ψ 是 wff，则（φ ∧ ψ）、（φ ∨ ψ）、（φ → ψ）和（φ ψ）是 wff。