离散数学(Discrete Mathematics1.3等值演算2026/3/15
2026/3/15 1 离散数学(Discrete Mathematics) 1.3等值演算
真值函敷问题：含n个命题变项的所有公式共产生多少个互不相同的真值函数？答案为22"个，为什么？定义称定义域为00..0,00....1,...,11...1)，值域为{0,1)的函数是n元真值函数，定义域中的元素是长为n的0,1串.常用F:[0,1)n→[0,1]表示F是n元真值函数.共有2"个n元真值函数例如 F:{0,1)2→[0,1}，且F(00)=F(01)=F(11)=0,F(01)=1，则F为一个2元真值函数2026/3/15
2026/3/15 真值函數 n 2 2 n 2 2 问题：含n个命题变项的所有公式共产生多少个互 不相同的真值函数？ 答案为 个，为什么？ 定义 称定义域为{00.0, 00.1, ., 11.1}，值域 为{0,1}的函数是n元真值函数，定义域中的元素是 长为n的0,1串. 常用F:{0,1} n→{0,1} 表示F是n元真值 函数. 共有 个n元真值函数. 例如 F:{0,1}2→{0,1}，且F(00)=F(01)=F(11)=0， F(01)=1，则F为一个2元真值函数
命题公式与真值函数每个真值函数可对应无穷多个命题公式，他们彼此都是等值的。下表给出所有2元真值函数对应的真值表，每一个含2个命题变项的公式的真值表都可以在下表中找到例如：p→>,pq,(pvq)v((p-→>)^) 等都对应表中的Fg)2026/3/15
2026/3/15 命题公式与真值函数 (2) F13 每个真值函数可对应无穷多个命题公式，他们彼此 都是等值的。 下表给出所有2元真值函数对应的真值表, 每一个含 2个命题变项的公式的真值表都可以在下表中找到. 例如：p→q, pq, (pq)((p→q)q) 等都对应 表中的
2元真值函数对应的真值表0F(2)F(2)3F(2)F,(2)F,(2)F(2)qP1000000000D00001-100000一111000011111 1F,(2)F,(2)Fle)Fl2)FEFe)FlC)FG)qP1111111100000000000100001112026/3/15
2026/3/15 2元真值函数对应的真值表 p q 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 (2) 7 (2) 6 (2) 5 (2) 4 (2) 3 (2) 2 (2) 1 (2) F0 F F F F F F F p q 0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 (2) 1 5 (2) 1 4 (2) 1 3 (2) 1 2 (2) 1 1 (2) 1 0 (2) 9 (2) F8 F F F F F F F
PQ-PVQP→Q01100111001011112026/3/15
2026/3/15 P Q PQ P→Q 0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1
第一章命题逻辑（PropositionalLogic）1.3等值演算给定n个(n≥1)命题变元,按合式公式的形成规则可以形成无数多个命题公式，但这些无穷尽的命题公式中，有些具有相同的真值表。由n个命题变元组成的命题公式共有2组赋值能生成2^2^n种真值（表）不同的命题公式2026/3/15
2026/3/15 第一章 命题逻辑（Propositional Logic） 1.3等值演算 ◼ 给定n个 命题变元, 按合式公式的形成 规则可以形成无数多个命题公式, 但这些无穷 尽的命题公式中，有些具有相同的真值表。 ◼ 由n个命题变元组成的命题公式共有2 n组赋值 ◼ 能生成2^2^n种真值(表)不同的命题公式 (n 1)
第一章命题逻辑（PropositionalLogic）定义：给定两个命题公式A和B,设Pi,P2，.,P,为出现于A和B中的所有命题变项,若给Pi,P2,P,任一组真值指派.A和B的真值都相同，则称A和B是等值的.记作A台B（或书本P8定义）注：（1）“台”不是逻辑联结词(2)命题公式之间的逻辑相等关系具有：自反性：A台A；对称性：若A台B，则B台A;传递性： 若A台 B且B 台 C， 则A 台 C。2026/3/15
2026/3/15 第一章 命题逻辑（Propositional Logic） 定义: 给定两个命题公式A和B,设P1 , P2 ,.,Pn为出现 于A和B中的所有命题变项,若给P1 , P2 ,.,Pn任一 组真值指派, A和B的真值都相同,则称A和B是等值 的.记作A B（或书本P8定义） ◼ 注: (1) “ ”不是逻辑联结词. ◼ (2)命题公式之间的逻辑相等关系具有： 自反性：A A ；对称性：若A B，则B A； 传递性：若A B且B C，则A C
第一章命题逻辑（Propositional Logic）证明公式等值的方法：1真值表法：设A和B为两命题公式，由定义判断A和B是否等值，应判断A>B是否为重言式，若AB的真值表最后一列全为1，则AB 为重言式，因而A 台 B。但最后一列全为1当且仅当再各赋值之下，A与B的真值相同，因而判断A与B是否等值等价于判断A，B的真值表是否相同2.等值演算法2026/3/15
2026/3/15 第一章 命题逻辑（Propositional Logic） ◼ 证明公式等值的方法： ◼ 1. 真值表法:设A和B为两命题公式，由定义 判断A和B是否等值，应判断AB 是否为重 言式，若 AB的真值表最后一列全为1，则 AB 为重言式，因而A B。但最后一列 全为1当且仅当再各赋值之下，A与B的真值 相同，因而判断A与B是否等值等价于判断A、 B的真值表是否相同。 ◼ 2. 等值演算法
第一章命题逻辑（PropositionalLogic）■例1.证明: PQ 台(P→Q)^(Q→P)PQPQQ→PP→Q(P→Q)^(Q→P)0011110001010010011111112026/3/15
2026/3/15 第一章 命题逻辑（Propositional Logic） ◼ 例1. 证明: PQ (P→Q)(Q→P) P Q PQ Q→P P→Q (P→Q)(Q→P) 0 0 1 1 1 1 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 1
第一章命题逻辑（PropositionalLogic）例2：头判断公式P→(Q→R)、(P^Q)→R是否等值。PQRPΛQQ-RP→(Q→R)(P ^ Q)→R011000101110010001101011011101001110011111000111011111112026/3/15
2026/3/15 第一章 命题逻辑（Propositional Logic） 例2：判断公式 P→(Q→R)、(P∧Q)→R是否等值。 P Q R P ∧ Q Q → R P →(Q → R) (P ∧ Q )→ R 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1