1.数理逻辑-03.ppt

离散数学(Discrete Mathematics) 第一部分 数理逻辑（Mathematical Logic) 第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives) 1.6.1 不可兼析取(排斥或/异或)(exclusive or) 1.6.2 与非联结词(Nand) 1.6.3 或非联结词(Nor) 1.6.4 条件否定联结词(Non-conditional) 1.6.5 最小联结词组(The minimal set of connectives) 第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives) 在第二节(1.2)中我们定义了五种基本的联结词┐，?， ?，→ ，?,但在命题逻辑中,这些联结词还不能很广泛 地直接表达命题之间的联系(例如, “P异或Q”只能间接地 表示为(P?┐Q)?(┐P?Q)),为此本节再给出逻辑设计中 常用的另外四种联结词. 1.6.1 不可兼析取(排斥或/异或)(exclusive or) 定义1.6.1:设P,Q为二命题，复合命题“P, Q之中恰有一个为真” 称为P与Q的不可兼析取，记作P Q，符号“ ” 称为异或联结词. P Q 为真当且仅当P和Q的真值不同. 第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives) 联结词“ ”的定义真值表 第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives) 说明：“ ” 属于二元(binary)运算符. 联结词“ ”的性质: 设P, Q, R为命题公式, 则有 (1) P Q ? Q P (交换律) (2) (P Q) R ? P (Q R) (结合律) (3) P∧(Q R) ? (P∧Q ) (P∧R) (分配律) (4) (P Q) ? (P∧? Q) ∨(? P∧Q) (5) (P Q) ? ? (P?Q) (6) P P ? F, F P ? P, T P ? ? P 第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives) 定理1.6.1:设P, Q, R为命题公式, 如果 P Q?R,则 P R?Q ,Q R?P, 且P Q R 为一矛盾式. 证: 由 P Q?R 得 P R?P (P Q)?(P P) Q?F Q?Q Q R?Q (P Q)?F P?P P Q R?R R?F 第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives) 1.6.2 与非联结词(Nand　↑) 定义1.6.2 设P,Q为二命题，复合命题“P与Q的否定” 称为P与Q的与非式，记作P↑Q，符号“↑” 称为与非联结词. P↑Q 为真当且仅当P和Q不同时为真. 联结词“↑”的定义真值表 第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives) 说明: (1) 由定义可知, P↑Q ?? (P∧Q) (2)“↑” 属于二元(binary)运算符. 联结词“↑”的性质: (1) P↑P ?? ( P∧P) ?? P (2) (P↑Q)↑(P↑Q) ?? ( P↑Q)?(P∧Q) (3)(P↑P)↑(Q↑Q)?? P↑? Q??(?P∧?Q)? P∨Q 第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives) 1.6.3 或非联结词(Nor) 定义1.6.3 设P,Q为二命题，复合命题“P或Q的否定” 称为P与Q的或非式，记作P↓Q ，符号“↓”称为或非联结词. P↓Q为真当且仅当 P与Q同为假. 联结词“↓”的定义真值表 第一章 命题逻辑（Propositional Logic） 1.6其它联结词(Other Connectives) 说明: (1) 由定义可知, P↓Q ? ? (P∨Q) (2)“↓” 属于二元(binary)运算符.↓ 联结词