PropOSItIonal Equvalence 命题演 1.12命题演算 Propositional equivalences 2/24/202111:14PM Deren Chen Zhejiang univ
Propositional Equivalences 命题演算 2/24/2021 11:14 PM Deren Chen, Zhejiang Univ. 1 1.1.2 命题演算 Propositional Equivalences
PropOSItIonal Equvalence 命题演 1、命题( Proposition) 2、从简单命题( atomic proposition到 复合命题( compositional proposition) 从命题常量( propositional constant)到 命题变量( propositional variable 4、从复合命题( compositional proposition)到 命题公式( propositional formulas) 2/24/202111:14PM Deren Chen Zhejiang univ 2
Propositional Equivalences 命题演算 2/24/2021 11:14 PM Deren Chen, Zhejiang Univ. 2 1、命题(Proposition) 2、从简单命题(atomic proposition)到 复合命题(compositional proposition) 3、从命题常量(propositional constant)到 命题变量(propositional variable) 4、从复合命题(compositional proposition)到 命题公式(propositional formulas)
PropOSItIonal Equvalence 命题演算 永真命题公式( Tautology) 公式中的命题变量无论怎样代入,公式对应的真值恒为T 永假命题公式( Contradiction) 公式中的命题变量无论怎样代入,公式对应的真值恒为F。 可满足命题公式( Satisfaction) 公式中的命题变量无论怎样代入,公式对应的真值总有 种情况为T。 般命题公式( Contingency) 既不是永真公式也不是永假公式 2/24/202111:14PM Deren Chen zhejiang univ 3
Propositional Equivalences 命题演算 2/24/2021 11:14 PM Deren Chen, Zhejiang Univ. 3 永真命题公式(Tautology) 公式中的命题变量无论怎样代入,公式对应的真值恒为T。 永假命题公式(Contradiction) 公式中的命题变量无论怎样代入,公式对应的真值恒为F。 可满足命题公式(Satisfaction) 公式中的命题变量无论怎样代入,公式对应的真值总有一 种情况为T。 一般命题公式(Contingency) 既不是永真公式也不是永假公式
EXAMPLE 1 PropOSItIonal Equvalence 命题演算 We can construct examples of tautologies and contradictions using just one proposition. Consider the truth tables of p∨ p and p∧→p, shown in table 1. Since pv- p is always true, it is a tautology. Since pM p is always false, it is a contradiction. 2/24/202111:14PM Deren Chen Zhejiang univ
Propositional Equivalences 命题演算 2/24/2021 11:14 PM Deren Chen, Zhejiang Univ. 4 EXAMPLE 1 We can construct examples of tautologies and contradictions using just one proposition. Consider the truth tables of p∨ p and p∧ p, shown in Table 1. Since p∨ p is always true, it is a tautology. Since p∧ p is always false, it is a contradiction.
Table 1 PropOSItIonal Equvalence 命题演算 TABLE 1 Examples of a Tautology and a Contradiction pppV→p|p∧→p T F T T F 2/24/202111:14PM Deren Chen Zhejiang univ
Propositional Equivalences 命题演算 2/24/2021 11:14 PM Deren Chen, Zhejiang Univ. 5 Table 1
DEFINTION2 PropOSItIonal Equvalence 命题 The propositions p and g are called logically equivalent if p t,q is a tautotogy. The notation p e q denotes that p and g are logically equivalent. 逻辑等值,或逻辑等价 2/24/202111:14PM Deren Chen Zhejiang univ
Propositional Equivalences 命题演算 2/24/2021 11:14 PM Deren Chen, Zhejiang Univ. 6 DEFINITION 2 The propositions p and q are called logically equivalent if p q is a tautotogy. The notation p q denotes that p and q are logically equivalent. ⎯→ 逻辑等值,或逻辑等价
EXAMPLE2 PropOSItIonal Equvalence 命题演算 Show that(pVg) and- pA g are logically equivalent. This equivalence is one of De morgan's laws for propositions, named after the English mathematician Augustus De Morgan, of the mid-nineteenth century Solution: The truth tables for these propositions are displayed in Table 2 Since the truth values of the propositions (pVg and pA q agree for all possible combinations of the truth values of p and g, it follows that these propositions are logically equivalent. 2/24/202111:14PM Deren Chen, Zhejiang Univ
Propositional Equivalences 命题演算 2/24/2021 11:14 PM Deren Chen, Zhejiang Univ. 7 EXAMPLE 2 Show that (p∨q) and p∧ q are logically equivalent. This equivalence is one of De Morgan's laws for propositions, named after the English mathematician Augustus De Morgan, of the mid-nineteenth century. Solution: The truth tables for these propositions are displayed in Table 2. Since the truth values of the propositions (p∨q) and p∧ q agree for all possible combinations of the truth values of p and q, it follows that these propositions are logically equivalent.
Table 2 PropOSItIonal Equvalence 命题演算 TABLE 2 Truth Tables for - (pVg and pAq pqp√q|-@p∨q) p PAq T T T T F T F F T T FF F T 2/24/202111:14PM Deren Chen Zhejiang univ
Propositional Equivalences 命题演算 2/24/2021 11:14 PM Deren Chen, Zhejiang Univ. 8 Table 2
EXAMPLE 3 PropOSItIonal Equvalence 命题演 Show that the propositions p-q and -pvgare logically equivalent. Solution: We construct the truth table for these propositions in Table 3. Since the truth values of mpVq and pq agree, these propositions are logically equivalent 2/24/202111:14PM Deren Chen Zhejiang univ
Propositional Equivalences 命题演算 2/24/2021 11:14 PM Deren Chen, Zhejiang Univ. 9 EXAMPLE 3 Show that the propositions p→q and p∨q are logically equivalent. Solution: We construct the truth table for these propositions in Table 3. Since the truth values of p∨q and p→q agree, these propositions are logically equivalent.
Table 3 PropOSItIonal Equvalence 命题演算 TABLE 3 Truth Tables for pvq and p-q p q pVq P→q TTFF TFTF LLⅡd TFTT TFTT 2/24/202111:14PM Deren Chen Zhejiang univ
Propositional Equivalences 命题演算 2/24/2021 11:14 PM Deren Chen, Zhejiang Univ. 10 Table 3