南京大学：《离散数学》作业习题（无答案）

（续）命题逻辑离散数学一逻辑和证明南京大学计算机科学与技术系致谢：部分内容改编自中科大肖明军老师的《离散数学》slides

命题逻辑（续） 离散数学─逻辑和证明 南京大学计算机科学与技术系 致谢：部分内容改编自中科大肖明军老师的《离散数学》slides

前情回顾数理逻辑（符号逻辑）命题问题：逻辑运算符我们给出的五个逻辑运算符是否够用？命题表达式命题的真值表逻辑等价2

前情回顾 ⚫ 数理逻辑（符号逻辑） ⚫ 命题 ⚫ 逻辑运算符 ⚫ 命题表达式 ⚫ 命题的真值表 ⚫ 逻辑等价 2 问题： 我们给出的五个逻辑运算符是否够用？

内容提要常用的命题公式逻辑等价命题逻辑的推理问题命题逻辑公式的范式自然演绎规则及论证命题逻辑的正确性及完备性3

内容提要 ⚫ 常用的命题公式逻辑等价 ⚫ 命题逻辑的推理问题 ⚫ 命题逻辑公式的范式 ⚫ 自然演绎规则及论证 ⚫ 命题逻辑的正确性及完备性 3

常用的逻辑等价(1)名称等价双重否定律p--p幂等律p=ppp=p交换律==结合律（pvg)vr=pv(qvr)(paq)r=p(qar)分配律pv(qr)=(pvq)(pvr)pA(ar)=(pag)(pAr)德摩根律（pq)=pq()吸收律(pq)=pq)(ppp4

常用的逻辑等价(1) 名称 等价 双重否定律 p ¬¬ p 幂等律 p  p  p, p  pp 交换律 pq  qp, pq  qp 结合律 (pq)r  p(qr) (pq)r  p(qr) 分配律 p(qr) (pq)(pr) p(qr) (pq)(pr) 德摩根律 ¬(pq)  ¬p¬q ¬(pq)  ¬p¬q 吸收律 p(pq)  p p (p q) p 4

常用的逻辑等价(2)名称等价支配律A1=1, A0=0恒等律AV0丰A.AΛ1=A排中律AV-A=1否定律矛盾律A^一A=0A-→B=-AVBAB=(A→B)^(B → A)假言易位 A十B=-B→~AAB=-BTA归缪论(A→B)^(A→-B)=-A5

常用的逻辑等价(2) 5 否定律 名称 等价 支配律 A 1≡1, A 0≡0 恒等律 A0≡A, A1≡A 排中律 A¬A ≡ 1 矛盾律 A¬A ≡ 0 A→B≡¬AB AB≡(A→B)(B → A) 假言易位 A→B≡¬B→¬A AB≡¬B¬A 归缪论 (A→B)(A→¬B)≡¬A