离散数学（屈婉玲）命题逻辑

前言：

Hello，小伙伴们，经过辣么长的时间跨度，离散数学的图论部分终于更新完啦！（尬笑）

现在正式开始从离散数学的正常顺序开始更新~

---

命题的逻辑

命题：能够判断真假的陈述句！（但不能既真又假的陈述句）

举个栗子：

1.明天星期六? ? ? ? ? ? ? ?（不是命题吼！无法判断他是真假）

2.你去教室吗？? ? ? ? ? ?（不是命题吼！??? ? ? 他是疑问句~）

3.?这个苹果真大呀！? ? ? （不是命题吼！??? ? ? 他是感叹句~）? ? ? ? ? ?

4.x+y>10? ? ? ? ? ? ? ? ? ? ? ? （不是命题吼！? ? ? ? ? ? 陈述句，无法判断真假）

5.苹果是红色的? ? ? ? ? ? ? ?（命题）

复合命题：

简单命题用联结词来联结的叫做复合命题（大白话就是由多个简单命题组合而成的）

联结词：(命题的真假通常用真“1”假“0”表示）

是逻辑联结词或命题联结词的简称

• 联结词【非】------>[???P], 表示否定；??
• 联结词【合取】---->[^],表示且；只要有一个为0，则为0；
• 联结词【析取】---->[?∨?],表示或；只要有一个1，则1；
• 联结词【蕴涵】---->[?→?]，表如果...，则...;只有当前件P的真值为1,后条Q真值为0时，则P->Q的真值为0

P	Q	P--->Q
0	0	1
0	1	1
1	0	0
1	1	1

他的真值表记法是（先判断P 和Q谁在前，当前面为假时，后面无论为啥结果都为真

而前面为真时，真假取决于后面那个）

• ? ? ?联结词【等价】---->[???],表示，当且仅当；

P	Q	P<->Q
0	0	1
0	1	0
1	0	0
1	1	1

他的真值表记法是（P 和Q真假一样时为真，不一样时为假）

真值表：

直接看栗子吧

例题：

利用真值表求公式┐（P→Q）∧Q∧R

P	Q	R	?P→Q	┐(P→Q)	Q∧R?	┐(P→Q)∧Q∧R
0	0	0	1	0	0	0
0	0	1	1	0	0	0
0	1	0	1	0	0	0
0	1	1	1	0	1	0
1	0	0	0	1	0	0
1	0	1	0	1	0	0
1	1	0	1	0	0	0
1	1	1	0	1	0	0

重言式，矛盾式，可满足式

1.重言式：在各种赋值下取值都是1（真）又称永真式

2.矛盾式：在各种赋值下取值都是0（假）-------例如上面用真值表法举得那个栗子又称永假式

3.可满足式：矛盾式外都是；（包含重言式可满足式和非重言式可满足式）

等值演算

1.双重否定律? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??A<=>┐┐A

2.幂等律? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?A<=>Av A,? ?A<=>A∧A

3.交换律? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Av B<=>Bv A ，A∧B<=>B∧A

4.结合律? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(AvB)vC<=>Av(BvC)，(A∧B)∧C<=>A∧(B∧C)

5.分配律? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Av(B∧C)<=>(AvB)∧(AvC)，A∧(BvC)<=>(A∧B)v(A∧C)

6.德摩根律? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?┐(AvB)<=>┐A∧┐B，┐(A∧B)<=>┐Av┐B

7.吸收律? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??Av(A∧B)<=>A，A∧(AvB)<=>A

8.零律? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? Av1<=>1，A∧0<=>0

9.同一律? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Av0<=>A，A∧1<=>A

10.排中律? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Av┐A<=>1

11.矛盾律? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?A∧┐A<=>0

12.蕴涵等值式? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??A→B<=>┐AvB

13.等价等值式? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??A<->B<=>(A→B)∧(B→A)

14.假言易位? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? A→B<=>┐B→┐A

15.等价否定等值式? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?A<->B<=>┐A<->┐B

16.归谬论? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(A→B)∧(A→┐B) <=>┐A

例题：

（1）（P→Q）→R<=>（┐Q∧P）vR? ? ?—? 验证等值式

解：（P→Q）→R

? ? ??<=>（┐PvQ）→R

? ? ??<=>┐（┐PvQ）vR

? ? ??<=>（P∧┐Q）vR

? ? ? <=>（┐Q∧P）vR

---

析取范式和合取范式

---

定义：（1）有限个简单合取式构成的析取式称为析取范式

? ? ? ? ? ? （2）有限个简单析取式构成的合取式称为合取范式

性质：（1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式

? ? ? ? ? ? （2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式

举个栗子

若变元是 P，Q，R

析取范式：例如：(P ∧ Q) ∨ (?P ∧ )

合取范式：例如：（P∨Q）∧（?P∨R）∧（Q∨R）

---

---

主析取范式和主合取范式（每个括号内必须包含所有变元）

---

举个栗子

若变元是 P，Q，R

主析取范式：例如：(P ∧ Q ∧R) ∨ (?P ∧ R ∧ Q?)

主合取范式：例如：（P∨QvR）∧（?P∨QvR）∧（PvQ∨R）

---

极大项和极小项

极大项M对应的是? ? ? ----主析取范式（使得每个括号成为0的赋值）

极小项m对应的是? ? ? ----主合取范式（使得每个括号成为1的赋值）

举个栗子

p，q两个命题变项生成的4个极小项对应的二进制和十进制数如下：(数字为下标)

P	Q	P∧Q（计算方法）	m
1	1	1*2^1+1*2^0	m3

┐P∧┐Q? ? ? ? ?——00——0，记做m0;

┐P∧Q? ? ? ? ? ?——01——1，记做m1;

?P∧┐Q? ? ? ? ? ——10——2，记做m2;

?P∧Q? ? ? ? ? ? ?——11——3，记做m3

同理---变项为多个也是这么做

公式：从最右边那个开始依次是2^0,2^1,2^2……

用真值情况乘相对应的2的多少次方就行

主合取范式为:(数字为下标)

pvq ? ? ? ? ? ? ? ? ? ——00——0，记做M0;

pv┐q ? ? ? ? ? ? ? ?——01——1，记做M1;

┐pvq ? ? ? ? ? ? ? ?——10——2，记做M2;

┐pv┐q ? ? ? ? ? ? ——11——3，记做M3;

例题：

求公式p→((q∧r)∧(p v(┐q∧┐r)))的主析取范式，再由主析取范式求出公式的主合取范式，并判断公式的类型。

解：p→((q∧r)∧(p v(┐q∧┐r)))

?┐p v((p∧q∧r)v((q∧r)∧(┐q∧┐r)))

?┐p v (p∧q∧r)

? ? ? ?(┐p∧(q v┐q)∧(r v┐r)) v (p∧q∧r)

? ? ? ?(┐p∧q∧r) v(┐p∧┐q∧r) v(┐p∧q∧┐r) v(┐p∧┐q∧┐r) v(p∧q∧r)

? ? ? ?m3 v m1 v m2 v m0 v m7

? ? ? ?m0 v m1 v m2 v m3 v m7 ? (主析取：使得每个括号值都为1的赋值)

? ? ? ?M4 ∧ M5 ∧ M6 ? ? ? ? ? ? ?(主合取：使得每个括号值都为0的赋值)

结论：公式为可满足式
?

?M4 ∧ M5 ∧ M6 ? ? ? ? ? ? ?(主合取)----------这个是如何直接看出来的呢？

别急，让我给你慢慢道来：

已知变项有n个：则它一共有2^n个M和m这样的式子

他是从0开始的，例如该题，他已经有了m0，m1，m2，m3，m7

而他有3个变元（p，q，r），则它有2^3=8个M和m这样的式子，又因为从0开始的，所以极大项就是 M4，M5，M6

------------同理若知道极大项，也可以用这种方法直接求极小项

补充：

1.像这种给你俩个式子让你判断他俩是不是等值的，用真值表法~~

例如：

证明Gv（G∧r）与G是否等值，即证明：Gv(G∧r）<-->G是否为永真式，用真值表法

2.如果给你式子让你求极大项或者极小项，但是给你的括号内变项又不全，那么如何去凑呢？

排中律? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Av┐A<=>1

矛盾律? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?A∧┐A<=>0

利用这俩来解决吼~~

当然还有更简单的

例如：

（pvq）∧（┐pvq┐R）

让它变成含极小项的式子

（pvqvR）∧（pvqv┐R）∧（┐pvq┐R）

缺哪个直接给他补上，后面别忘记添加一个他的┐的情况；

---

命题逻辑的推理理论
8条推理定律

1.A=>(AvB) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 附加

2.(A∧B)=>A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?化简

3.(A→B)∧A=>B ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?假言推理

4.(A→B)∧┐B=>┐A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?拒取式

5.(AvB)∧┐B=>A ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?析取三段论

6.(A→B)∧(B→C)=>(A→C) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?假言三段论 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

7.(A<=>B)∧(B<=>C)=>(A<=>C) ? ? ? ? ? ? ? ? ? ? ? ? ? ?等价三段论

8.(A→B)∧(C→D)∧(AvC)=>(BvD) ? ? ? ? ? ? ? ? ? ? ? ? ?构造性二难
?

规则：

1.前提引入规则：在证明的任何步骤上，都可引入前提。

2.结论引入规则：在证明的任何步骤上，所得到的结论都可以作为后续证明的前提，加以引用。

3.置换规则：在证明的任何步骤上，命题公式中的任何子公式都可以用与之等值的公式置换，得到公式序列中又一公式。

4.假言推理规则：若证明的公式序列中已出现过A→B和A，则由假言推理定律可知。B是A→B和A的逻辑结论，由推理规则2，可引入B。

5.附加规则：若证明的公式序列中已出现A，由附加律可知，AvB是A的逻辑结论，由规则2，可引入A或B。

6.化简规则：若证明的公式序列中已出现A∧B,由化简律可知，A,B都是A∧B的逻辑结论。由规则2可引入A或B。

7.拒取式规则：若证明的公式序列中已出现A→B和┐B，则可以引入┐A。

8.假言三段论规则：若证明的公式序列中已出现A→B和B→C，则可以引入A→C。

9.析取三段论规则：若证明的公式序列中已出现过AvB和┐B，则可以引入A。

10.构造性二难规则：若证明的公式序列中已出现过A→B，C→D，AvC，则可以引入BvD

例题：

1.用直接证明法证明下面的推理

前提：p→r，q→s，q，p

结论：r∧s

证明：① p→r ? ? ? ? ? ? ?

? ? ? ? ? ② p ? ? ? ? ? ? ? ??

? ? ? ? ? ③ r ? ? ? ? ? ? ? ??

? ? ? ? ? ④ q→s ? ? ? ? ? ? ?

? ? ? ? ? ⑤ q ? ? ? ? ? ? ? ??

? ? ? ? ? ⑥ s ? ? ? ? ? ? ? ?

? ? ? ? ? ⑦ r∧s ? ? ? ? ? ??

2.用附加前提法证明下面的推理

前提： ┐p v (q→r)，s→p，q

结论：┐r→┐s

证明：① ┐p v (q→r) ? ? ? ? ? ? ??

? ? ? ? ? ② ┐r ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ③ ┐p v ┐q ? ? ? ? ? ? ? ? ?

? ? ? ? ? ④ q ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ⑤ ┐p ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ⑥ s→p ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ⑦ ┐s ? ? ? ? ? ??

3.用归谬法证明下面的推理 ??

前提： p→(q→r)，p∧q

结论：r v s ? ? ??

证明：① ┐(r v s) ? ? ? ? ? ? ? ? ??

? ? ? ? ? ② ┐r∧┐s ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ③ ┐r ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ④ p→(q→r) ? ? ? ? ? ? ? ? ??

? ? ? ? ? ⑤ p→┐q ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ⑥ p∧q ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ⑦ p ? ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ⑧ ┐q ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ⑨ ┐p ? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ⑩ p∧┐p ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? 结论：p∧┐p为矛盾式

---

---

第一节的分享就到这里啦~

如果哪里写错了，或者对于某个知识点有更好的理解，欢迎在评论区留言吼~

谢谢大家哈~