命题演算.pptx

7/8/2017 9:09 PM
Deren Chen, Zhejiang Univ.
1
命题演算
Propositional Equivalences
7/8/2017 9:09 PM
Deren Chen, Zhejiang Univ.
2
1、命题(Proposition)
2、从简单命题(atomic proposition)到
positional proposition)
3、从命题常量(propositional constant)到
命题变量(propositional variable)
4、positional proposition)到
命题公式(propositional formulas)
7/8/2017 9:09 PM
Deren Chen, Zhejiang Univ.
3
永真命题公式(Tautology)
公式中的命题变量无论怎样代入,公式对应的真值恒为T。
永假命题公式(Contradiction)
公式中的命题变量无论怎样代入,公式对应的真值恒为F。
可满足命题公式(Satisfaction)
公式中的命题变量无论怎样代入,公式对应的真值总有一种情况为T。
一般命题公式(Contingency)
既不是永真公式也不是永假公式。
7/8/2017 9:09 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.
7/8/2017 9:09 PM
Deren Chen, Zhejiang Univ.
5
Table 1
7/8/2017 9:09 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.
逻辑等值,或逻辑等价
7/8/2017 9:09 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-eenth 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 binations of the truth values of p and q, it follows that these propositions are logically equivalent.
7/8/2017 9:09 PM
Deren Chen, Zhejiang Univ.
8
Table 2
7/8/2017 9:09 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