| 【离散数学】数理逻辑 第一章 命题逻辑(4) 联结词的完备集 | 您所在的位置：网站首页 › 逻辑等价定义是什么 › 【离散数学】数理逻辑 第一章 命题逻辑(4) 联结词的完备集 |
|
本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动，欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外，在本系列学习文章中，为了透彻理解数学知识，本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录，在后续学习中还会逐渐补充： 离散数学及其应用 第七版 Discrete Mathematics and Its Applications 7th ，作者是 Kenneth H.Rosen离散数学 第二版，武波等编著，西安电子科技大学出版社 文章目录 4. 其他联结词4.1 所有一元和二元运算符4.2 异或、与非、或非的一些性质4.3 全功能联结词集合及其证明方法之前学习了五个联结词 ¬ , ∨ , ∧ , → , ↔ \lnot, \vee, \wedge, \to, \leftrightarrow ¬,∨,∧,→,↔ ，包括一个一元联结词和四个二元联结词。那么使用这五个联结词，就能够表达所有命题吗？ 为此，本节讨论其他联结词和联结词的完备性理论。 4. 其他联结词 4.1 所有一元和二元运算符对于一元运算符，它只作用于一个命题变元，该命题变元只有 T , F T, F T,F 两个值，则可能的运算结果就只有四种： P P P f 1 f_1 f1 f 2 f_2 f2 f 3 f_3 f3 f 4 f_4 f40001110101因此，一元运算符最多只能定义四种，即 f 1 P ⇔ F f_1P \Leftrightarrow F f1P⇔F、 f 2 P ⇔ P f_2P\Leftrightarrow P f2P⇔P、 f 3 P ⇔ ¬ P f_3P \Leftrightarrow \lnot P f3P⇔¬P、 f 4 P ⇔ T f_4P \Leftrightarrow T f4P⇔T 。所以，无需定义新的联结词。 对于二元运算符，它作用于两个命题变元，一个命题变元只有 T , F T, F T,F 两个值，则可能的运算结果就只有 2 2 2 = 16 2^{2^2} = 16 222=16 种： P P PQ f 1 f_1 f1 f 2 f_2 f2 f 3 f_3 f3 f 4 f_4 f4 f 5 f_5 f5 f 6 f_6 f6 f 7 f_7 f7 f 8 f_8 f8 f 9 f_9 f9 f 10 f_{10} f10 f 11 f_{11} f11 f 12 f_{12} f12 f 13 f_{13} f13 f 14 f_{14} f14 f 15 f_{15} f15 f 16 f_{16} f16000000000011111111010000111100001111100011001100110011110101010101010101因此，二元运算符最多只能定义十六种，其中十一种无需定义新的联结词（可以定义，比如与或、与或非等）： P f 1 Q ⇔ F Pf_1Q \Leftrightarrow F Pf1Q⇔F、 P f 2 Q ⇔ P ∧ Q Pf_2Q \Leftrightarrow P\wedge Q Pf2Q⇔P∧Q、 P f 4 Q ⇔ P Pf_4Q \Leftrightarrow P Pf4Q⇔P、 P f 6 Q ⇔ Q Pf_6Q \Leftrightarrow Q Pf6Q⇔Q P f 8 Q ⇔ P ∨ Q Pf_8Q \Leftrightarrow P \vee Q Pf8Q⇔P∨Q、 P f 10 Q ⇔ P ↔ Q Pf_{10}Q \Leftrightarrow P \leftrightarrow Q Pf10Q⇔P↔Q、 P f 11 Q ⇔ ¬ Q Pf_{11}Q \Leftrightarrow \lnot Q Pf11Q⇔¬Q、 P f 12 Q ⇔ Q → P Pf_{12}Q \Leftrightarrow Q \to P Pf12Q⇔Q→P P f 13 Q ⇔ ¬ P Pf_{13}Q \Leftrightarrow \lnot P Pf13Q⇔¬P、 P f 14 Q ⇔ P → Q Pf_{14}Q \Leftrightarrow P\to Q Pf14Q⇔P→Q、 P f 16 Q ⇔ T Pf_{16}Q \Leftrightarrow T Pf16Q⇔T其余五个运算可以定义新的联结词： f 3 , f 5 f_3, f_5 f3,f5 定义为条件否定 negation of conditional ↛ \nrightarrow ↛： P f 3 Q ⇔ P ↛ Q ⇔ ¬ ( P → Q ) P f 5 Q ⇔ Q ↛ P ⇔ ¬ ( Q → P ) Pf_3Q \Leftrightarrow P \nrightarrow Q \Leftrightarrow \neg (P \to Q)\quad Pf_5Q \Leftrightarrow Q \nrightarrow P \Leftrightarrow \neg (Q \to P) Pf3Q⇔P↛Q⇔¬(P→Q)Pf5Q⇔Q↛P⇔¬(Q→P) f 7 f_7 f7 定义为异或/不可兼或 exclusive-Or, XOR ⊕ \oplus ⊕ ： P f 7 Q ⇔ P ⊕ Q ⇔ ¬ ( P ↔ Q ) ⇔ ( P ∧ ¬ Q ) ∨ ( ¬ P ∧ Q ) Pf_7Q \Leftrightarrow P\oplus Q \Leftrightarrow \lnot (P \leftrightarrow Q) \Leftrightarrow (P \land \lnot Q) \lor (\lnot P\land Q) Pf7Q⇔P⊕Q⇔¬(P↔Q)⇔(P∧¬Q)∨(¬P∧Q) f 9 f_9 f9 定义为或非 NOR ↓ \downarrow ↓ ： P f 9 Q ⇔ P ↓ Q ⇔ ¬ ( P ∨ Q ) Pf_9Q \Leftrightarrow P \downarrow Q \Leftrightarrow \lnot (P \lor Q) Pf9Q⇔P↓Q⇔¬(P∨Q) f 15 f_{15} f15 定义为与非 NAND ↑ \uparrow ↑ ： P f 9 Q ⇔ P ↑ Q ⇔ ¬ ( P ∧ Q ) Pf_9Q \Leftrightarrow P \uparrow Q \Leftrightarrow \lnot (P \land Q) Pf9Q⇔P↑Q⇔¬(P∧Q) 4.2 异或、与非、或非的一些性质这些新的联结词，有以下性质（逻辑等价式）。证明这些性质，相当于要证明逻辑等价关系（回想一下之前总结的证明方法）： P ⊕ Q ⇔ Q ⊕ P P \oplus Q \Leftrightarrow Q\oplus P P⊕Q⇔Q⊕P 交换律 ( P ⊕ Q ) ⊕ R ⇔ P ⊕ ( Q ⊕ R ) (P\oplus Q) \oplus R \Leftrightarrow P \oplus (Q \oplus R) (P⊕Q)⊕R⇔P⊕(Q⊕R) 结合律 P ∧ ( Q ⊕ R ) ⇔ ( P ∧ Q ) ⊕ ( P ∧ R ) P \land (Q \oplus R) \Leftrightarrow (P \land Q) \oplus (P\land R) P∧(Q⊕R)⇔(P∧Q)⊕(P∧R) 分配律 P ⊕ P ⇔ F P \oplus P \Leftrightarrow F P⊕P⇔F、 F ⊕ P ⇔ P F\oplus P \Leftrightarrow P F⊕P⇔P、 T ⊕ P ⇔ ¬ P T\oplus P \Leftrightarrow \lnot P T⊕P⇔¬P P ↓ P ⇔ ¬ ( P ∨ P ) ⇔ ¬ P P \downarrow P \Leftrightarrow \lnot (P \lor P) \Leftrightarrow \lnot P P↓P⇔¬(P∨P)⇔¬P ( P ↓ P ) ↓ ( Q ↓ Q ) ⇔ ¬ P ↓ ¬ Q ⇔ P ∧ Q (P \downarrow P) \downarrow (Q \downarrow Q) \Leftrightarrow \lnot P \downarrow \lnot Q \Leftrightarrow P \land Q (P↓P)↓(Q↓Q)⇔¬P↓¬Q⇔P∧Q ( P ↓ Q ) ↓ ( P ↓ Q ) ⇔ ¬ ( P ↓ Q ) ⇔ P ∨ Q (P \downarrow Q) \downarrow (P \downarrow Q) \Leftrightarrow \lnot (P \downarrow Q) \Leftrightarrow P \lor Q (P↓Q)↓(P↓Q)⇔¬(P↓Q)⇔P∨Q P ↑ P ⇔ ¬ ( P ∧ P ) ⇔ ¬ P P \uparrow P \Leftrightarrow \lnot (P \land P) \Leftrightarrow \lnot P P↑P⇔¬(P∧P)⇔¬P ，用与非门 NAND 表示非门 NOT ，在数字逻辑以及From Nand To Tetris中会用到 ( P ↑ P ) ↑ ( Q ↑ Q ) ⇔ ¬ P ↑ ¬ Q ⇔ P ∨ Q (P \uparrow P) \uparrow (Q \uparrow Q) \Leftrightarrow \lnot P \uparrow \lnot Q \Leftrightarrow P \lor Q (P↑P)↑(Q↑Q)⇔¬P↑¬Q⇔P∨Q ( P ↑ Q ) ↑ ( P ↑ Q ) ⇔ ¬ ( P ↑ Q ) ⇔ P ∧ Q (P \uparrow Q) \uparrow (P \uparrow Q) \Leftrightarrow \lnot (P \uparrow Q)\Leftrightarrow P \land Q (P↑Q)↑(P↑Q)⇔¬(P↑Q)⇔P∧Q ，用与非门 NAND 表示与门 AND ，在数字逻辑以及From Nand To Tetris中会用到 4.3 全功能联结词集合及其证明方法现在一共定义了九个命题联结词，但是这些联结词并非是独立的，比如 ↛ , ⊕ , ↓ , ↑ \nrightarrow, \oplus, \downarrow, \uparrow ↛,⊕,↓,↑ ——含有这些联结词的命题公式，可以用含有另外一些联结词的命题公式等价表示。 又由双条件律 E 15 : P ↔ Q ⇔ ( P → Q ) ∧ ( Q → P ) E_{15}:\ P\leftrightarrow Q\Leftrightarrow (P \to Q) \land (Q \to P) E15: P↔Q⇔(P→Q)∧(Q→P) 知， ↔ \leftrightarrow ↔ 可由 → , ∧ \to, \land →,∧ 表示；由蕴含律 E 14 : P → Q ⇔ ¬ P ∨ Q E_{14}:\ P \to Q \Leftrightarrow \lnot P\lor Q E14: P→Q⇔¬P∨Q 知， → \to → 可由 ¬ , ∨ \lnot, \lor ¬,∨ 表示。于是所有命题公式都可用 ¬ , ∧ , ∨ \lnot, \land, \lor ¬,∧,∨ 表示。 更进一步，由德摩根定律知， ∨ , ∧ \lor, \land ∨,∧ 可以互相表示。所以任意命题公式都可由仅含有 { ¬ , ∨ } \{\lnot, \lor\} {¬,∨} 或 { ¬ , ∧ } \{\lnot, \land\} {¬,∧} 的命题公式来等价表示。 定义4.1 给定一个联结词集合，如果所有命题公式都能用其中的联结词等价表示出来，则称该联结词集合为全功能联结词集合，或称该联结词集合为功能完备的 functionally complete 。 例如， { ¬ , ∨ , ∧ } \{\lnot, \lor, \land\} {¬,∨,∧}、 { ¬ , ∨ } \{\lnot, \lor\} {¬,∨}、 { ¬ , ∧ } \{\lnot, \land\} {¬,∧} 都是全功能联结词集合，还有 { ¬ , → } \{\lnot, \to\} {¬,→}、 { ↑ } \{\uparrow\} {↑}、 { ↓ } \{\downarrow\} {↓} 也是。 定义4.2 一个联结词集合是全功能的，并且去掉其中任意一个联结词后均不是全功能的，则称其为极小全功能联结词集合。 证明方法：如果要证明联结词集合 A A A 是全功能的，可选择一个已知的全功能联结词集合 B B B ，比如 { ¬ , ∧ } \{\lnot, \land\} {¬,∧} 或 { ¬ , ∨ } \{\lnot, \lor\} {¬,∨} ，若 B B B 中每个联结词都能用 A A A 中的联结词等价表示，则 A A A 也是全功能的，否则 A A A 不是全功能的。若要进一步证明 A A A 是极小全功能联结词集合，则需再证明， A A A 中去掉任何一个联结词后均不是全功能的。 例1：证明 { ↛ , ¬ } \{ \nrightarrow, \lnot \} {↛,¬} 是全功能联结词集合。 解答：由于 { ∧ , ¬ } \{ \land, \lnot\} {∧,¬} 是全功能联结词集合，要证明 { ↛ , ¬ } \{ \nrightarrow, \lnot \} {↛,¬} 也是全功能联结词集合，即要证明 { ∧ , ¬ } \{ \land, \lnot\} {∧,¬} 中的联结词 ∧ \land ∧ 能用 { ↛ , ¬ } \{ \nrightarrow, \lnot \} {↛,¬} 中的联结词等价表示。 因为 P ∧ Q ⇔ ¬ ( ¬ P ∨ ¬ Q ) ⇔ ¬ ( P → ¬ Q ) ⇔ P ↛ ¬ Q P \land Q \Leftrightarrow \lnot (\lnot P \lor \lnot Q) \Leftrightarrow \lnot (P \to \lnot Q) \Leftrightarrow P \nrightarrow \lnot Q P∧Q⇔¬(¬P∨¬Q)⇔¬(P→¬Q)⇔P↛¬Q ，所以凡是能够用 { ∧ , ¬ } \{ \land, \lnot \} {∧,¬} 表示的命题公式都能够用 { ↛ , ¬ } \{ \nrightarrow, \lnot\} {↛,¬} 表示，则 { ↛ , ¬ } \{ \nrightarrow, \lnot \} {↛,¬} 也是全功能联结词集合。 例2：证明 { ↑ } \{ \uparrow \} {↑} 是极小全功能联结词集合。 解答：由于 { ∧ , ¬ } \{ \land, \lnot\} {∧,¬} 是全功能联结词集合，又由 ¬ P ⇔ P ↑ P \lnot P \Leftrightarrow P \uparrow P ¬P⇔P↑P， P ∧ Q ⇔ ( P ↑ Q ) ↑ ( P ↑ Q ) P \land Q \Leftrightarrow (P \uparrow Q) \uparrow (P \uparrow Q) P∧Q⇔(P↑Q)↑(P↑Q) ，得 { ↑ } \{ \uparrow \} {↑} 是全功能联结词集合。显然，由于 { ↑ } \{ \uparrow \} {↑} 中只有一个联结词，故其是极小全功能联结词集合。 例3：证明 { ⊕ , ¬ } \{ \oplus, \lnot \} {⊕,¬} 不是全功能联结词集合。 例4：已知 { ↔ , ¬ } \{ \leftrightarrow, \lnot \} {↔,¬} 不是全功能联结词集合，证明 { ⊕ , ¬ } \{ \oplus , \lnot\} {⊕,¬} 也不是全功能联结词集合。 |
| CopyRight 2018-2019 实验室设备网 版权所有 |