第二章 命题逻辑的等值和推理演算 推理形式和推理演算是数理逻辑研究的基本内容 推理过程是从前提出发,根据所规定的规则来推导出结论的过程

Slides:



Advertisements
Similar presentations
2.8 函数的微分 1 微分的定义 2 微分的几何意义 3 微分公式与微分运算法则 4 微分在近似计算中的应用.
Advertisements

2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
3.4 空间直线的方程.
圆的一般方程 (x-a)2 +(y-b)2=r2 x2+y2+Dx+Ey+F=0 Ax2+Bxy+Cy2+Dx+Ey+ F=0.
第五章 二次型. 第五章 二次型 知识点1---二次型及其矩阵表示 二次型的基本概念 1. 线性变换与合同矩阵 2.
第三章 函数逼近 — 最佳平方逼近.
离散数学 薛广涛 计算机科学与工程系 上海交通大学.
《高等数学》(理学) 常数项级数的概念 袁安锋
§1 线性空间的定义与性质 ★线性空间的定义 ★线性空间的性质 ★线性空间的子空间 线性空间是线性代数的高等部分,是代数学
第二章 命题逻辑(上) 主讲人:耿国华.
四种命题 2 垂直.
常用逻辑用语复习 知识网络 常用逻辑用语 命题及其关系 简单的逻辑联结词 全称量词与存在量词 四种命题 充分条件与必要条件 量词 全称量词 存在量词 含有一个量词的否定 或 且 非或 并集 交集 补集 运算.
简易逻辑.
1.1.2四种命题 1.1.3四种命题间的相互关系.
1.1.3四种命题的相互关系 高二数学 选修2-1 第一章 常用逻辑用语.
常用逻辑用语复习课 李娟.
1-5重言式与蕴含式 1-5.1重言式(tautology) 定义1-5.1 [重言式]:
第一章 行列式 第五节 Cramer定理 设含有n 个未知量的n个方程构成的线性方程组为 (Ⅰ) 由未知数的系数组成的n阶行列式
第8讲 命题公式的真值表与等值 主要内容: 1.命题公式的真值表. 2.命题公式的等值的定义,记住常见的命题公式的等值式.
一、原函数与不定积分 二、不定积分的几何意义 三、基本积分公式及积分法则 四、牛顿—莱布尼兹公式 五、小结
第四章 函数的积分学 第六节 微积分的基本公式 一、变上限定积分 二、微积分的基本公式.
第三节 格林公式及其应用(2) 一、曲线积分与路径无关的定义 二、曲线积分与路径无关的条件 三、二元函数的全微分的求积 四、小结.
内容:推理形式和推理演算是数理逻辑研究的基本内容。
第二章 命题逻辑的等值和推理演算 推理形式和推理演算是数理逻辑研究的基本内容 推理形式是由前提和结论经蕴涵词联结而成的
第5章 §5.3 定积分的积分法 换元积分法 不定积分 分部积分法 换元积分法 定积分 分部积分法.
§3.7 热力学基本方程及麦克斯韦关系式 热力学状态函数 H, A, G 组合辅助函数 U, H → 能量计算
第二章 矩阵(matrix) 第8次课.
元素替换法 ——行列式按行(列)展开(推论)
!!! 请记住:矩阵是否等价只须看矩阵的秩是否相同。
§2 求导法则 2.1 求导数的四则运算法则 下面分三部分加以证明, 并同时给出相应的推论和例题 .
第一章 函数 函数 — 研究对象—第一章 分析基础 极限 — 研究方法—第二章 连续 — 研究桥梁—第二章.
第二章 逻辑和证明 2.2 命题等价 命题演算:用真值相同的命题取代另一个 在证明时广泛使用 定义1. 永真式(重言式):真值总是真
若2002年我国国民生产总值为 亿元,如果 ,那么经过多少年国民生产总值 每年平均增长 是2002年时的2倍? 解:设经过 年国民生产总值为2002年时的2倍, 根据题意有 , 即.
公式的真值表 离散结构 西安工程大学 计算机学院 王爱丽.
数列.
§4 谓词演算的性质 谓词逻辑Pred(Y)。 是Y上的关于类型 {F,→,x|xX}的自由代数 赋值 形式证明
6.4不等式的解法举例(1) 2019年4月17日星期三.
实数与向量的积.
§4 命题演算的形式证明 一个数学系统通常由一些描述系统特有性质的陈述句所确定,这些陈述句称为假设,
第 一 篇 数 理 逻 辑.
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
5.2 常用统计分布 一、常见分布 二、概率分布的分位数 三、小结.
第2章 命题逻辑 2.1 命题逻辑的基本概念 命题与真值 简单命题与复合命题 命题符号化 五个联结词 命题常项、命题变项与合式公式
复习.
第十章 双线性型 Bilinear Form 厦门大学数学科学学院 网址: gdjpkc.xmu.edu.cn
正切函数的图象和性质 周期函数定义: 一般地,对于函数 (x),如果存在一个非零常数T,使得当x取定义域内的每一个值时,都有
定理21.9(可满足性定理)设A是P(Y)的协调子集,则存在P(Y)的解释域U和项解释,使得赋值函数v(A){1}。
第16讲 相似矩阵与方阵的对角化 主要内容: 1.相似矩阵 2. 方阵的对角化.
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
定义19.13:设p,qP(Y),若{p}╞q且{q}╞p,则称p,q语义等价,记为p │==│ q
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
第三章 函数的微分学 第二节 导数的四则运算法则 一、导数的四则运算 二、偏导数的求法.
4) 若A可逆,则 也可逆, 证明: 所以.
第4课时 绝对值.
2.2矩阵的代数运算.
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
第二章 逻辑和证明 2.7小结 数理逻辑的基本思想:逻辑推理机械(演算)化 数理逻辑的基本方法:符号化
正弦、余弦函数的性质 华容一中 伍立华 2017年2月24日.
《离散结构》 二元运算性质的判断 西安工程大学计算机科学学院 王爱丽.
§2 方阵的特征值与特征向量.
Xn到A中的映射,(xi)=ai,a1,a2,…an为A 中的任何元素(允许ai=aj,ij)。
主讲教师 欧阳丹彤 吉林大学计算机科学与技术学院
定义21.17:设P1=P(Y1)和P2=P(Y2),其个体变元与个体常元分别为X1,C1和 X2,C2,并且或者C1=或者C2。一个半同态映射(,):(P1,X1∪C1)→(P2,X2∪C2)是一对映射: P1→P2; : X1∪C1→X2∪C2,它们联合实现了映射p(x,c)→(p)((x),
第三节 函数的微分 3.1 微分的概念 3.2 微分的计算 3.3 微分的应用.
第四节 向量的乘积 一、两向量的数量积 二、两向量的向量积.
第三节 数量积 向量积 混合积 一、向量的数量积 二、向量的向量积 三、向量的混合积 四、小结 思考题.
§4.5 最大公因式的矩阵求法( Ⅱ ).
一元一次方程的解法(-).
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
1.2.2 充要条件 高二数学 选修 1-1 第一章 常用逻辑用语.
Presentation transcript:

第二章 命题逻辑的等值和推理演算 推理形式和推理演算是数理逻辑研究的基本内容 推理过程是从前提出发,根据所规定的规则来推导出结论的过程 第二章 命题逻辑的等值和推理演算 推理形式和推理演算是数理逻辑研究的基本内容 推理过程是从前提出发,根据所规定的规则来推导出结论的过程 重言式是重要的逻辑规律,正确的推理形式,等值式都是重言式。

本章对命题等值和推理演算进行讨论,是以语义的观点进行的非形式的描述,不仅直观且容易理解,也便于实际问题的逻辑描述和推理。 严格的形式化的讨论见第三章所建立的公理系统。

2.1 等值定理 在命题逻辑里也同样可建立一些重要的等值式。 2.1 等值定理 若把初等数学里的+、-、×、÷等运算符看作是数与数之间的联结词,那么由这些联结词所表达的代数式之间,可建立许多等值式如下: x2-y2 = (x+y)(x-y) (x+y)2 = x2+2xy+y2 sin2x+cos2x = 1 …… 在命题逻辑里也同样可建立一些重要的等值式。

2.1.1 等值的定义 给定两个命题公式A和B, 而P1…Pn是出现于A和B中的所有命题变项, 那么公式A和B共有2n个解释, 若对其中的任一解释, 公式A和B的真值都相等, 就称A和B是等值的(或等价的)。记作A = B或A  B。

显然,可以根据真值表来判明任何两个公式是否是等值的。

例1: 证明(P∧P)∨Q = Q 证明: 画出(P∧P)∨Q与Q的真值表可看出等式是成立的。

例2: 证明P∨P = Q∨Q 证明: 画出P∨P, Q∨Q的真值表, 可看出它们是等值的, 而且它们都是重言式。

从例1、2还可说明, 两个公式等值并不要求它们一定含有相同的命题变项。若仅在等式一端的公式里有变项P出现, 那么等式两端的公式其真值均与P无关。例1中公式(P∨P) ∨Q与Q的真值都同P无关, 例2中P∨P, Q∨Q都是重言式, 它们的真值也都与P、Q无关。

2.1.2 等值定理 定理 对公式A和B, A = B的充分必要条件是A  B是重言式。 2.1.2 等值定理 定理 对公式A和B, A = B的充分必要条件是A  B是重言式。 若A  B为重言式(A、B不一定都是简单命题, 可能是由简单命题P1, …, Pn构成的对A, B的一个解释, 指的是对P1, …, Pn的一组具体的真值设定), 则在任一解释下A和B都只能有相同的真值, 这就是定理的意思。

证明 若A  B是重言式, 即在任一解释下, A  B的真值都为T。依A  B的定义只有在A、B有相同的值时, 才有A  B = T。于是在任一解释下, A和B都有相同的真值, 从而有A=B。反过来,若有A = B, 即在任一解释下A和B都有相同的真值, 依A  B的定义, A  B只有为真, 从而A  B是重言式。

有了这个等值定理,证明两个公式等值,只要证明由这两个公式构成的双条件式是重言式即可。

不要将“=”视作联结词,在合式公式定义里没有“=”出现。A = B是表示公式A与B的一种关系。这种关系具有三个性质: 1. 自反性 A = A。 2. 对称性 若A = B则B = A。 3. 传递性 若A = B, B = C则A = C。 这三条性质体现了“=”的实质含义。

2.2 等值公式 2.2.1 基本的等值公式(命题定律) 1. 双重否定律 P = P 2. 结合律 2.2 等值公式 2.2.1 基本的等值公式(命题定律) 1. 双重否定律 P = P 2. 结合律 (P∨Q) ∨R = P∨(Q∨R) (P∧Q) ∧R = P∧(Q∧R) (P  Q)  R = P  (Q  R)

3. 交换律 P∨Q = Q∨P P∧Q = Q∧P P  Q = Q  P 4. 分配律 P∨(Q∧R) = (P∨Q)∧(P∨R) P∧(Q∨R) = (P∧Q)∨(P∧R) P(QR) = (PQ)(PR) 5. 等幂律(恒等律) P∨P = P P∧P = P PP = T PP = T

6. 吸收律 P∨(P∧Q) = P P∧(P∨Q) = P 7. 摩根律 (P∨Q) = P∧Q (P∧Q) = P∨Q 对蕴涵词、双条件词作否定有 (PQ) = P∧Q (PQ) = PQ = PQ = (P∧Q)∨(P∧Q)

8. 同一律 P∨F = P P∧T = P TP = P TP = P 还有 PF = P FP = P

9. 零律 P∨T = T P∧F = F 还有 PT = T FP = T 10. 补余律 P∨P = T P∧P = F PP = P PP = P PP = F

所有这些公式,都可使用直值表加以验证。

Venn图 若使用Venn图也容易理解这些等值式, 这种图是将P、Q理解为某总体论域上的子集合, 而规定P∧Q为两集合的公共部分(交集合), P∨Q为两集合的全部(并集合), P为总体论域(如矩形域)中P的余集。

从Venn 图因P∧Q较P来得“小”, P∨Q较P来得“大”,从而有 P∨(P∧Q) = P P∧(P∨Q) = P

对这些等式使用自然用语加以说明,将有助于理解。如P表示张三是学生, Q表示李四是工人, 那么(P∨Q)就表示并非“张三是学生或者李四是工人”。这相当于说,“张三不是学生而且李四也不是工人”,即可由P∧Q表示, 从而有 (P∨Q) = P∧Q。

2.2.2 若干常用的等值公式 由于人们对、∨、∧更为熟悉,常将含有和的公式化成仅含有、∨、∧的公式。这也是证明和理解含有,的公式的一般方法。 公式11-18是等值演算中经常使用的,也该掌握它们, 特别是能直观地解释它们的成立。

11. PQ = P ∨Q 通常对PQ进行运算时, 不如用P∨Q来得方便。而且以P∨Q表示PQ帮助我们理解如果P则Q的逻辑含义。问题是这种表示也有缺点,丢失了P、Q间的因果关系。

12. PQ = QP 如将PQ视为正定理, 那么QP就是相应的逆否定理, 它们必然同时为真, 同时为假, 所以是等值的。

13. P(QR) = (P∧Q)R P是(QR)的前提, Q是R的前提, 于是可将两个前提的合取P∧Q作为总的前提。 即如果P则如果Q则R, 等价于如果P与Q则R。

14. PQ = (P∧Q)∨(P∧Q) 这可解释为PQ为真, 有两种可能的情形, 即(P∧Q)为真或(P∧Q)为真。而P∧Q为真, 必是在P = Q = T的情况下出现, P∧Q为真, 必是在P = Q = F的情况下出现。从而可说, PQ为真, 是在P、Q同时为真或同时为假时成立。这就是从取真来描述这等式。

15. PQ = (P∨Q)∧(P∨Q) 这可解释为PQ为假, 有两种可能的情形, 即(P∨Q)为假或(P∨Q)为假, 而P∨Q为假, 必是在P = F, Q = T的情况下出现, P∨Q为假, 必是在P = T, Q = F的情况下出现。从而可说PQ为假, 是在P真Q假或P假Q真 时成立。这就是从取假来描述这等式

16. PQ = (PQ)∧(QP) 这表明PQ成立, 等价于正定理PQ和逆定理QP都成立。

17. P(QR) = Q(PR) 前提条件P、Q可交换次序。

18. (PR) ∧(QR)=(P∨Q)R 左端说明的是由P而且由Q都有R成立。从而可以说由P或Q就有R成立, 这就是等式右端。

2.2.3 置换规则 定理: 对公式A的子公式, 用与之等值的公式来代换便称置换。 2.2.3 置换规则 定理: 对公式A的子公式, 用与之等值的公式来代换便称置换。 置换规则 公式A的子公式置换后A化为公式B, 必有A = B。 当A是重言式时, 置换后的公式B必也是重言式。 置换与代入是有区别的。置换只要求A的某一子公式作代换, 不必对所有同一的子公式都作代换。

2.2.4 等值演算举例 例1: 证明(P∧(Q∧R))∨(Q∧R)∨(P∧R) = R 证明: 2.2.4 等值演算举例 例1: 证明(P∧(Q∧R))∨(Q∧R)∨(P∧R) = R 证明: 左端= (P∧(Q∧R)) ∨((Q∨P)∧R) (分配律) =((P∧Q)∧R))∨((Q∨P)∧R) (结合律) =((P∨Q)∧R)∨((Q∨P)∧R) (摩根律) =((P∨Q)∨(Q∨P))∧R (分配律) =((P∨Q)∨(P∨Q))∧R (交换律) =T∧R (置 换) =R (同一律)

例2: 试证 ((P∨Q)∧(P∧(Q∨R))) ∨(P∧Q)∨(P∧R) = T 证明: 左端=((P∨Q)∧(P∨(Q∧R)))∨((P∨Q)∧(P∨R)) (摩根律) =((P∨Q)∧(P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R)) (分配律) =((P∨Q)∧(P∨R))∨((P∨Q)∧(P∨R)) (等幂律) =T

2.6 范式 n 个命题变项所能组成的具有不同真值的命题公式仅有22n个, 然而与任何一个命题公式等值而形式不同的命题公式可以有无穷多个。这样,首先就要问凡与命题公式A等值的公式,能否都可以化为某一个统一的标准形式。希望这种标准形能为我们的讨论带来些方便,如借助于标准形对任意两个形式上不同的公式,可判断它们的是否等值。借助于标准形容易判断任一公式是否为重言式或矛盾式。

求解公式的成真指派和成假指派 一个公式,其中含有命题变元P1, ,Pn, 表示为 [P1, ,Pn],(P1, ,Pn)称为变元组,公式的变元组(P1, ,Pn)的任意一组确定的值,称为对该公式的关于该变元组(P1, ,Pn)的一个完全指派。如果仅对变元组中的部分变元确定值,其余变元没有赋以确定的值,则称这样的一组值为该公式的关于变元组的一个部分指派。

完全指派与部分指派 例如公式 : p(qr)。 变元组为(p,q,r), 一个完全指派为(T,F,F),在此指派下,公式取真值。即 = T。 可这样来表示:(p,q,r)=(T,F,F)├  = T 或者有时记为:  (p,q,r)=(T,F,F) = T 一个部分指派为(T,T,╳)这时候  的值不能确定,当r = T时, = T,当r = F时,= F。这一点通常都能理解,因为一个公式的值取决于公式中所含变元的值,当其中某些变元未确定时,公式最终的值也不能定。但是这一点也未必绝对,例如,赋(p,q,r)以(F,X,X)时,公式肯定是取假值,即= F。这时候可看出对q,r 的指派已经无关紧要了。

成真指派与成假指派 定义:对于任一公式,凡是使得  取真值 = T 的指派,不管是完全指派还是部分指派,都称为  的成真指派。凡是使  取假值 = F 的指派,不管是完全指派还是部分指派,都称为  的成假指派。

例子 :P 的成真指派 P=F, 成假指派P=T。 :PQ 的成真指派(P,Q)=(T,T) 成假指派(P,Q)=(F,F),(F,T),(T,F) :PQ 的成真指派(P,Q)=(T,T),(T,F),(F,T) 成假指派(P,Q)=(F,F)

永真式、永假式、可满足式 有的公式没有成真指派,如:PP, 称为永假式(反驳式); 永假式,又称为矛盾式,不可满足。 如果一个公式,有成真指派,则称为公式  可满足。与它相对的,如果没有成真指派,就是不可满足的。 如果一个公式,有成假指派,则称该公式为非永真公式。

部分指派 公式  的变元组(P1, ,Pn),一个部分指派 :(V1, Vi-1, X, Vi+1, Vn),其中Vi为具体真假值。它为公式  的成真指派,当且仅当: (V1, Vi-1, T, Vi+1, Vn)及(V1, Vi-1, F, Vi+1, Vn)均为成真指派。 成假指派情况是相似的。

求解成真指派和成假指派的方法 一个直截了当的办法是将公式  的所有完全指派全都列举出来,逐个验算该指派下  取的真假值,从而确定每个完全指派是成真指派还是成假指派。但是,含n个变元的公式,共有2n个完全指派,当n为5、6、……时,指数的总数就会相当可观,按指数级数增长,难以全部枚举。因此应当选择更为简单、可行的办法——部分指派。求部分指派的前提是将原来的公式  化简,使得原来含有n个变元的公式化为可能含变元数更少的公式,于是便大大地削减了运算的数量。

部分指派的步骤 第一步,否定深入。将外层的否定深入到内层,一直深入到变元为止。 第二步,部分指派。选定一个变元对其作真和假两种指派,得到两个不含该变元但较原式简单的公式。如果这两个公式直接得到真假值,则得部分指派,否则 第三步,化简。得到的两公式虽然较原公式简单,但仍含有变元,于是重复第二步,逐个减少变元,直到确定真假值为止。 第二步中如何选定一个变元,希望化简效果最好,因此选择在公式中出现次数最多的变元作指派。还有一种情况就是对该变元赋以一个指派后,立即使整个公式有确定的真假值。

试求给定公式的成真成假指派 :(p   r)   ( (p  q)   ( p   (q  r) ) ) 第一步 否定深入: (p   r)  ( (p  q)  (p  (q  r) ) ) 第二步 部分指派:选择出现最多的命题,指派以T, F。(分别情况)。 上式中,P出现最多,故  分为   p = T   p = F两种情况。

  p = T :(T   r ) ((T  q )(T  (q  r))) 化简 (q (q  r))    也可最终化简为r,      p = F :(F   r ) ((F  q )(F  (q  r))) 化简得   r (T F) 最终化简得 r 组合起来,的成真指派(p, q, r)= ( T, X, F ), (F, X, T ), 成假指派(p, q, r)= ( T, X, T ), (F, X, F )。

不完全成真指派 (p, q, r): (T, X, F)可以生成相应的完全成真指派 (T, T, F ) 和 (T, F, F )。     (p, q, r): (F, X, T)  (F, T, T ) 和 (F, F, T )。 因此,写完整的话,的完全成真指派:   (T, T, F ),(T, F, F ),(F, T, T ),(F, F, T )。 相仿地,的完全成假指派:   (T, X, T ) (T, T, T) ,(T, F, T ),     (F, X, F ) (F, T, F ),(F, F, F ) 完全成假指派:(T, T, T) ,(T, F, T ),(F, T, F ),(F, F, F )。

析取范式 如果一个完全指派能使一个合取式取真值,那么这个完全指派和合取式之间是1-1对应的。例如: 如果一个完全指派能使一个合取式取真值,那么这个完全指派和合取式之间是1-1对应的。例如:  (T, T, F ),  (T, F, F ),   (F, T, T ),   (F, F, T ) 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, T, T) ,(T, F, T ),(F, T, F ),(F, F, F ) pqr pqr pqr  p q r 将四个析取式再合取,即得合取范式: (pqr)(pqr)(pqr)(pqr)

求范式等值变换法 消去和 否定深入到变元 等值变换

主范式 主析取范式 主合取范式

2.4 联结词的完备集 除了所详述过的五个联结词外, 还可定义更多的联结词。像计算机的硬件电路设计分析就常使用 异或(半加) 2.4 联结词的完备集 除了所详述过的五个联结词外, 还可定义更多的联结词。像计算机的硬件电路设计分析就常使用 异或(半加) ∨: P∨Q = (P∧Q)∨(P∧Q) 与非: P  Q = (P∧Q) 或非: P  Q = (P∨Q) 等联结词。 问题是对n 个命题变项P1…Pn 来说, 共可定义出多少个联结词? 还可以问, 在那么多联结词中有多少是独立的?

2.4.1 命题联结词的个数 按照合式公式的定义,由命题变项和命题联结词可以构造出无限多个合式公式。可把所有的合式公式加以分类 ,将等值的公式视为同一类,从中选一个作代表称之为真值函项。对一个真值函项就有一个联结词与之对应。

一元联结词是联结一个命题变项的,如P。它取值只有真假两种情形,于是联结词作用于P , 可建立四种不同的真值函项, 相应的可定义出四个不同的一元联结词f0f1f2f3。图6.2.4.1给出这些联结词fi或说真值函数fi(P)的定义。

写出真值函项: f0(P) = F f1(P) = P f2(P) = P f3(P) = T 其中f0(P)是永假式, f3(P)是永真式, 均与P无关, 而f1(P)就是变项P本身, 从而新的公式只有f2(P), 这就是由否定词所建立的真值函项。

二元联结词联结两个命题变项,两个变项PQ共有四种取值情形, 于是联结词作用于PQ可建立起16种不同的真值函项, 相应的可定义出16个不同的二元联结词g0, g1, …, g15 。图2.4.2给出了这些联结词gI或说真值函项gi(P, Q)的定义。

写出各真值函项: g0 (P,Q) = F g1(P,Q) = P∧Q g2(P,Q) = P∧Q g3(P,Q) = (P∧Q)∨(P∧Q) = P∧(Q∨Q) = P g4(P,Q) = P∧Q g5(P,Q) = (P∧Q)∨(P∧Q) = (P∨P)∧Q = Q g6(P,Q) = P∨Q g7(P,Q) = P∨Q g8(P,Q) = P∧Q = P  Q g9(P,Q) = P Q g10(P,Q) = (P∧Q)∨(P∧Q) = (P∨P)∧Q = Q g11(P,Q) = P∨Q = QP g12(P,Q) = (P∧ Q)∨(P∧Q) = P∧(Q∨Q) = P g13(P,Q) = P∨Q = P  Q g14(P,Q) = P∨Q = P  Q g15(P,Q) = T

一般地说,对n 个命题变元P1…Pn,, 每个Pi有两种取值, 从而对P1…Pn来说共有2n种取值情形。于是相应的直值函项就有22n个, 或说可定义22n个n元联结词。

2.4.2 联结词的完备集 由于可定义的联结词的数量是极大的, 需要考虑它们是否都是独立的? 也就是说这些联结词是否能相互表示呢? 2.4.2 联结词的完备集 由于可定义的联结词的数量是极大的, 需要考虑它们是否都是独立的? 也就是说这些联结词是否能相互表示呢? 定义: 设C是联结词的集合,如果对任一命题公式都有由C中的联结词表示出来的公式与之等值,就说C是完备的联结词集合,或说C是联结词的完备集。

显然全体联结词的无限集合是完备的, 而{∨}, {∨, ∧}就不是完备的。 定理 { , ∨, ∧}是完备的联结词集合 从节2.3介绍的由真值表列写逻辑公式的过程可知, 任一公式都可由, ∨, ∧表示出来, 从而{, ∨, ∧}是完备的, 一般情形下, 这定理的证明可使用数学归纳法, 施归纳于联结词的个数来论证。

又由于 P∧Q = (P∨Q) P∨Q = (P∧Q) 这说明, ∧可由{, ∨}表示, ∨可由{, ∧}表示, 故{, ∨}, {, ∧}都是联结词的完备集。还可证明{, }, {}, {}也都是联结词的完备集。但{∨, ∧}, {, }不是完备的。 尽管{,∨}, {, ∧}是完备的, 但使用起来并不够方便, 我们愿意采取折衷方案, 不是仅用两个也不是使用过多的联结词, 还是选用详细讨论过的五个联结词集{, ∧, ∨, , }, 当然是完备的, 只是相互并不独立。

最小的联结词的完备集——基底 基底:完备的联结词集合的联结词是独立的, 也就是说这些联结词不能相互表示

基底 只含一个联结词的: NK;NA 含两个联结词的:N,C; N,K; N,A; N,NC; F,C; T,NC; C,NE; E,NC; C,NC; 含三个联结词的:F,K,E; F,A,E; T,K,NE; T,A,NE; K,E,NE; A,E,NE; A-- ∨ K-- ∧ E--  C--  N-- 

基底 任取四个一元或二元联结词,它们必组不成基底。

加法器 Ai 0 0 0 0 1 1 1 1 Bi 0 0 1 1 0 0 1 1 Ei 0 1 0 1 0 1 0 1 _______________________ Ci 0 1 1 0 1 0 0 1 Ei+1 0 0 0 1 0 1 1 1 Ci=(Ai∧Bi∧Ei)∨(Ai∧Bi∧Ei)∨(Ai∧Bi∧Ei)∨(Ai∧Bi∧Ei) Ei+1=(Ai∧Bi∧Ei)∨(Ai∧Bi∧Ei)∨(Ai∧  Bi∧Ei)∨(Ai∧Bi∧Ei) E1=0 Cn+1=En+1

2.5 对偶式 假定公式A仅出现 、∨、∧这三个联结词 2.5 对偶式 假定公式A仅出现 、∨、∧这三个联结词 定义 将A中出现的∨、∧分别以∧、∨代换, 得到公式A*, 则称A*是A的对偶式, 或说A和A*互为对偶式。 (P∨Q)∧R 的对偶式为(P∧Q)∨R 不难知道, 若(P∨Q)∧R = (P∧R)∨(Q∧R) 成立, 相应的对偶式 (P∧Q)∨R = (P∨R)∧(Q∨R) 也成立。

为方便, 若A=A(P1, …, Pn) 令 A-= A(P1, …, Pn) 定理2.5.1 (A*) = (A*), (A-) = (A)- 定理2.5.2 (A*)* = A, (A-)-=A 定理2.5.3 A = A*-

可用数学归纳法, 施归纳于A中出现的联结词个数n来证明。 基始: 设n=0, A中无联结词, 便有 A=P, 从而 A = P 但 A*- = P ∴ n=0时定理成立。

归纳: 设n ≤k时定理成立,来证n = k+1时定理也成立 ∵ n = k + 1 ≥1, A中至少有一个联结词,可分为三种情形。 A = A1, A = A1∧A2, A = A1∨A2 其中A1, A2中联结词个数≤k。

依归纳法假设,A1 = A1*-, A2 = A2*- 当 A = A1时。 A = (A1) = (A1*-) 归纳法假设 = (A1)*- 定理2.5.1, 2.5.2 = A*-

当 A = A1∧A2时。 A = (A1∧A2) = A1∨A2 摩根律 = A1*-∨A2*- 归纳法假设 = (A1*∨A2*)- A-定义 = (A1∧A2)*- A*定义 = A*- 另一种情况同理,从而定理得证。这定理实为摩根律的另一种形式。它把、*、-联系起来了。

定理 2.5.4 若A = B必有A*=B* 证明: 因为A = B等价于AB 永真。 从而AB 永真。 依定理2.5.3, A = A*-, B = B*- 于是 A*-  B*- 永真 必有 A* B* 永真 故 A* = B*

定理2.5.5 若AB永真, 必有B*A*永真 定理2.5.6 A与A-同永真, 同可满足 A与A*同永真, 同可满足 对偶性是逻辑规律, 给证明公式的等值和求否定都带来了方便。

作业 (p37)1(1,3),2,3,5(8)

补充作业 给出一组满足下列要求的能用以设计四分邮票自动出售机的电路的布尔函数: (1)每次输入一个一分、二分、五分的硬币,电路中分别用c1,c2,c5三个量表示一分、二分、五分的硬币; (2)当输入值总和小于4分时,等待输入,当大于等于4分时,输出一张四分邮票并找零。电路中邮票用变量s表示,找零之数用r1,r2,r2’三个量分别表示一分、二分、二分的硬币。