L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,1
基础部分,
逻辑 (Logic)
集合 (Sets)
算法 (Algorithms)
数论 (Number Theory)
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,2
1.1.1 命题逻辑
Proposition Logic
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,3
逻辑学：
研究推理的一门学科数理逻辑：
用数学方法研究推理的一门数学学科
-------- 一套符号体系 + 一组规则
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,4
数理逻辑的内容：
古典数理逻辑：
命题逻辑、谓词逻辑现代数理逻辑：
公理化集合论、递归论、模型论、证明论
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,5
Proposition:
一个有确定真或假意义的语句,
命题逻辑
Proposition Logic
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,6
EXAMPLE1
All the following statements are propositions.
1,Washington,D.C.,is the capital of the United States of
America.
2,Toronto is the capital of Canada.
3,1+1=2.
4,2+2=3.
Propositions 1 and 3 are true,
whereas 2 and 4 are false,
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,7
EXAMPLE 2
Consider the following sentences.
1,What time is it?
2,Read this carefully.
3,x+1 =2.
4,x+y = z.
Sentences 1 and 2 are not propositions because they are not
statements,Sentences 3 and 4 are not propositions because
they are neither tree nor false,since the variables in these
sentences have not been assigned values,Various ways to
form propositions from sentences of this type will be
discussed in Section 1.3,
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,8
命题的语句形式陈述句非命题语句：
疑问句命令句感态句非命题陈述句：悖论语句
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,9
命题的符号表示：
大小写英文字母,P,Q,R、
p,q,r、。。。
命题真值（ Truth Values）的表示：
真,T,1
假,F,0
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,10
命题语句真值确定的几点说明：
1、时间性
2、区域性
3、标准性命题真值间的关系表示：
真值表（ Truth Table)
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,11
DEFINITION 1,
Let p be a proposition,The statement
"It is not the case that p."
is another proposition,called the negation of p,
The negation of p is denoted by p,The proposition
p is read "not p."
p的否定
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,12
EXAMPLE 3
Find the negation of the proposition
"Today is Friday"
and express this in simple English.
The negation is
"It is not the case that today is Friday."
This negation can be more simply expressed by
''Today is not Friday."
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,13
Table 1
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,14
DEFINITION 2,
Let p and q be propositions,The proposition "p and q,"
denoted by p∧ q,is the proposition that is true when both p
and q are true and is false otherwise,The proposition p∧ q is
called the conjunction of p and q,
The truth table for p∧ q is shown in Table 2.
p和 q的合取
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,15
Table 2
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,16
EXAMPLE 4
Find the conjunction of the propositions p and q where p is
the proposition "Today is Friday" and q is the proposition "It
is raining today."
Solution,
The conjunction of these propositions,p∧ q,is the proposition
"Today is Friday and it is raining today." This proposition is
true on rainy Fridays and is false on any day that is not a
Friday and on Fridays when it does not rain.
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,17
DEFINITION 3.
Let p and q be propositions.The proposition "p or q,"
denoted by p∨ q,is the proposition that is false when p and q
are both false and true otherwise,The proposition p∨ q is
called the disjunction of p and q.
The truth table for p∨ q is shown in Table 3.
p和 q的析取
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,18
Table 3
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,19
EXAMPLE 5
What is the disjunction of the propositions p and q where
p and q are the same propositions as in Example 4?
Solution,
The disjunction ofp and q,p∨ q,is the proposition
"Today is Friday or it is raining today."
This proposition is true on any day that is either a
Friday or a rainy day (including rainy Fridays),It is only
false on days that are not Fridays when it also does not rain.
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,20
DEFINITION 4.
Let p and q be propositions.The exclusive or of p and
q,denoted by p q,is the proposition that is true when
exactly one of p and q is true and is false otherwise.
The truth table for the exclusive or of two propositions
is displayed in Table 4.
p和 q的对称差
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,21
Table 4
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,22
DEFINITION 5.
Let p and q be propositions.The implication p→q is the
proposition that is false when p is true and q is false and
true otherwise,In this implication p is called the
hypothesis (or antecedent or premise) and q is called the
conclusion (or consequence).
如果 p,则 q 单条件,蕴涵P:前提
Q:结论
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,23
Table 5
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,24
EXAMPLE 6
What is the value of the variable x after the statement
if 2+2=4 then x,= x+ 1
if x = 0 before this statement is encountered? (The
symbol,= stands for assignment,The statement x,= x + 1
means the assignment of the value of x + 1 to x.)
Solution,
Since 2 + 2 = 4 is true,the assignment statement x,= x + 1
is executed,Hence,x has the value 0+1=1 after this
statement is encountered.
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,25
EXAMPLE 7
Find the converse and the contrapositive of the
implication
"If today is Thursday,then I have a test today."
Solution,
The converse is
"If I have a test today,then today is Thursday."
And the contrapositive of this implication is
"If I do not have a test today,then today is not Thursday."
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,26
DEFINITION 6.
Let p and q be propositions,The biconditional p q is
the proposition that is true when p and q have the same truth
values and is false otherwise.
The truth table for p q is shown in Table 6.
P当且仅当 q 双条件，等价
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,27
Table 6
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,28
EXAMPLE 8
How can the following English sentence be translated into a
logical expression?
"You can access the Internet from campus only if you are
a computer science major or you are not a freshman,"
Solution:
a → (c ∨ f ),?
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,29
EXAMPLE 9
How can the following English sentence be translated into
a logical expression?
"You cannot ride the roller coaster if you are under 4 feet
tall unless you are older than 16 years old."
Solution:
(r∧ s) → q.
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,30
EXAMPLE 10
说离散数学是枯燥无味的或毫无价值的，那是不对的。
P：离散数学是有味道的；
Q：离散数学是有价值的；
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,31
EXAMPLE 11
Web Page Searching,Most Web search engines support
Boolean searching techniques,which usually can help find
Web pages about particular subjects,For instance,using
Boolean searching to find Web pages about universities in
New Mexico,we can look for pages matching NEW AND
MEXICO AND UNIVERSITIES,The results of this search
will include those pages that contain the three words NEW,
MEXICO,and UNIVERSITIES,
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,32
DEFINITION 7,
A bit string is a sequence of zero or more
bits.The length of this string is the number of bits
in the string.
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,33
Table 7
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,34
EXAMPLE 12
Find the bitwise OR,bitwise AND,and bitwise XOR of
the bit strings 01 1011 0110 and 11 0001 1101,(Here,and
throughout this book,bit strings will be split into blocks of
four bits to make them easier to read.)
Solution:
The bitwise OR,bitwise AND,and bitwise XOR of
these strings are obtained by taking the OR,AND,and
XOR of the corresponding bits,respectively,This gives us
01 1011 0110
11 0001 1101
11 1011 1111 bitwise OR
01 0001 0100 bitwise AND
10 1010 1011 bitwise XOR
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,35
P,Q,R…… 称为原子命题（ Atomic Proposition）。
原子命题或加上逻辑联结词组成的表达式成为复合命题
（ Compositional Proposition）。
从命题常量 到 命题变量 (Propositional Variable)
命题公式：
1、原子命题是命题公式；
2、设 P是命题公式，则?P 也是命题公式；
3、设 P,Q是命题公式，则（ P ∧ Q）、（ P ∨ Q）、
（ P → Q ）、（ PQ）也是命题公式；
4、有限次地使用 1,2,3所得到的也是命题公式。
Proposition Formulas,Well-Formed Formulas(wff)
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,36
命题公式的运算规则：
逻辑联接词的优先级：
,∧,∨,→,
命题公式的表达式的运算规律：
同代数表达式命题公式的运算方法：
所有公式中的命题变量用指定命题（真值）代入（或指派），得到一个公式对应的真值。
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,37
性质 1：
如果一个命题公式有 N个互异的命题变量，则命题公式对应的真值有 2的 N次幂种可能分布。
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,38
永真命题公式（ Tautology）
公式中的命题变量无论怎样代入，公式对应的真值恒为 T。
永假命题公式（ Contradiction)
公式中的命题变量无论怎样代入，公式对应的真值恒为 F。
可满足命题公式（ Satisfaction）
公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为 T。
一般命题公式（ Contingency）
既不是永真公式也不是永假公式。
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,39
性质 2：
（ 1）设 P是永真命题公式，则 P的否定公式是永假命题公式；
（ 2）设 P是永假命题公式，则 P的否定公式是永真命题公式；
（ 3）设 P,Q是永真命题公式，则 P （ P ∧ Q）、（ P
∨ Q）、（ P → Q ）、（ PQ）也是永真命题公式
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,40
小 结
1、命题的概念：定义、逻辑值,符号化表示
2、从简单命题到复合命题：
逻辑联接词：运算方法、运算优先级
3、从命题常量到命题变量，
从复合命题到命题公式：
命题公式的真值描述：真值表
4、命题公式的分类：
永真公式、永假公式、可满足公式,一般公式
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,41
进一步的思考：
1、从二值逻辑到多值逻辑
2、从确定值到模糊值模糊逻辑（ Fuzzy Logic)
练习题：
2,7,21（ d）,25（ d）
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,1
基础部分,
逻辑 (Logic)
集合 (Sets)
算法 (Algorithms)
数论 (Number Theory)
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,2
1.1.1 命题逻辑
Proposition Logic
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,3
逻辑学：
研究推理的一门学科数理逻辑：
用数学方法研究推理的一门数学学科
-------- 一套符号体系 + 一组规则
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,4
数理逻辑的内容：
古典数理逻辑：
命题逻辑、谓词逻辑现代数理逻辑：
公理化集合论、递归论、模型论、证明论
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,5
Proposition:
一个有确定真或假意义的语句,
命题逻辑
Proposition Logic
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,6
EXAMPLE1
All the following statements are propositions.
1,Washington,D.C.,is the capital of the United States of
America.
2,Toronto is the capital of Canada.
3,1+1=2.
4,2+2=3.
Propositions 1 and 3 are true,
whereas 2 and 4 are false,
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,7
EXAMPLE 2
Consider the following sentences.
1,What time is it?
2,Read this carefully.
3,x+1 =2.
4,x+y = z.
Sentences 1 and 2 are not propositions because they are not
statements,Sentences 3 and 4 are not propositions because
they are neither tree nor false,since the variables in these
sentences have not been assigned values,Various ways to
form propositions from sentences of this type will be
discussed in Section 1.3,
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,8
命题的语句形式陈述句非命题语句：
疑问句命令句感态句非命题陈述句：悖论语句
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,9
命题的符号表示：
大小写英文字母,P,Q,R、
p,q,r、。。。
命题真值（ Truth Values）的表示：
真,T,1
假,F,0
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,10
命题语句真值确定的几点说明：
1、时间性
2、区域性
3、标准性命题真值间的关系表示：
真值表（ Truth Table)
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,11
DEFINITION 1,
Let p be a proposition,The statement
"It is not the case that p."
is another proposition,called the negation of p,
The negation of p is denoted by p,The proposition
p is read "not p."
p的否定
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,12
EXAMPLE 3
Find the negation of the proposition
"Today is Friday"
and express this in simple English.
The negation is
"It is not the case that today is Friday."
This negation can be more simply expressed by
''Today is not Friday."
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,13
Table 1
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,14
DEFINITION 2,
Let p and q be propositions,The proposition "p and q,"
denoted by p∧ q,is the proposition that is true when both p
and q are true and is false otherwise,The proposition p∧ q is
called the conjunction of p and q,
The truth table for p∧ q is shown in Table 2.
p和 q的合取
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,15
Table 2
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,16
EXAMPLE 4
Find the conjunction of the propositions p and q where p is
the proposition "Today is Friday" and q is the proposition "It
is raining today."
Solution,
The conjunction of these propositions,p∧ q,is the proposition
"Today is Friday and it is raining today." This proposition is
true on rainy Fridays and is false on any day that is not a
Friday and on Fridays when it does not rain.
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,17
DEFINITION 3.
Let p and q be propositions.The proposition "p or q,"
denoted by p∨ q,is the proposition that is false when p and q
are both false and true otherwise,The proposition p∨ q is
called the disjunction of p and q.
The truth table for p∨ q is shown in Table 3.
p和 q的析取
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,18
Table 3
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,19
EXAMPLE 5
What is the disjunction of the propositions p and q where
p and q are the same propositions as in Example 4?
Solution,
The disjunction ofp and q,p∨ q,is the proposition
"Today is Friday or it is raining today."
This proposition is true on any day that is either a
Friday or a rainy day (including rainy Fridays),It is only
false on days that are not Fridays when it also does not rain.
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,20
DEFINITION 4.
Let p and q be propositions.The exclusive or of p and
q,denoted by p q,is the proposition that is true when
exactly one of p and q is true and is false otherwise.
The truth table for the exclusive or of two propositions
is displayed in Table 4.
p和 q的对称差
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,21
Table 4
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,22
DEFINITION 5.
Let p and q be propositions.The implication p→q is the
proposition that is false when p is true and q is false and
true otherwise,In this implication p is called the
hypothesis (or antecedent or premise) and q is called the
conclusion (or consequence).
如果 p,则 q 单条件,蕴涵P:前提
Q:结论
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,23
Table 5
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,24
EXAMPLE 6
What is the value of the variable x after the statement
if 2+2=4 then x,= x+ 1
if x = 0 before this statement is encountered? (The
symbol,= stands for assignment,The statement x,= x + 1
means the assignment of the value of x + 1 to x.)
Solution,
Since 2 + 2 = 4 is true,the assignment statement x,= x + 1
is executed,Hence,x has the value 0+1=1 after this
statement is encountered.
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,25
EXAMPLE 7
Find the converse and the contrapositive of the
implication
"If today is Thursday,then I have a test today."
Solution,
The converse is
"If I have a test today,then today is Thursday."
And the contrapositive of this implication is
"If I do not have a test today,then today is not Thursday."
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,26
DEFINITION 6.
Let p and q be propositions,The biconditional p q is
the proposition that is true when p and q have the same truth
values and is false otherwise.
The truth table for p q is shown in Table 6.
P当且仅当 q 双条件，等价
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,27
Table 6
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,28
EXAMPLE 8
How can the following English sentence be translated into a
logical expression?
"You can access the Internet from campus only if you are
a computer science major or you are not a freshman,"
Solution:
a → (c ∨ f ),?
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,29
EXAMPLE 9
How can the following English sentence be translated into
a logical expression?
"You cannot ride the roller coaster if you are under 4 feet
tall unless you are older than 16 years old."
Solution:
(r∧ s) → q.
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,30
EXAMPLE 10
说离散数学是枯燥无味的或毫无价值的，那是不对的。
P：离散数学是有味道的；
Q：离散数学是有价值的；
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,31
EXAMPLE 11
Web Page Searching,Most Web search engines support
Boolean searching techniques,which usually can help find
Web pages about particular subjects,For instance,using
Boolean searching to find Web pages about universities in
New Mexico,we can look for pages matching NEW AND
MEXICO AND UNIVERSITIES,The results of this search
will include those pages that contain the three words NEW,
MEXICO,and UNIVERSITIES,
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,32
DEFINITION 7,
A bit string is a sequence of zero or more
bits.The length of this string is the number of bits
in the string.
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,33
Table 7
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,34
EXAMPLE 12
Find the bitwise OR,bitwise AND,and bitwise XOR of
the bit strings 01 1011 0110 and 11 0001 1101,(Here,and
throughout this book,bit strings will be split into blocks of
four bits to make them easier to read.)
Solution:
The bitwise OR,bitwise AND,and bitwise XOR of
these strings are obtained by taking the OR,AND,and
XOR of the corresponding bits,respectively,This gives us
01 1011 0110
11 0001 1101
11 1011 1111 bitwise OR
01 0001 0100 bitwise AND
10 1010 1011 bitwise XOR
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,35
P,Q,R…… 称为原子命题（ Atomic Proposition）。
原子命题或加上逻辑联结词组成的表达式成为复合命题
（ Compositional Proposition）。
从命题常量 到 命题变量 (Propositional Variable)
命题公式：
1、原子命题是命题公式；
2、设 P是命题公式，则?P 也是命题公式；
3、设 P,Q是命题公式，则（ P ∧ Q）、（ P ∨ Q）、
（ P → Q ）、（ PQ）也是命题公式；
4、有限次地使用 1,2,3所得到的也是命题公式。
Proposition Formulas,Well-Formed Formulas(wff)
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,36
命题公式的运算规则：
逻辑联接词的优先级：
,∧,∨,→,
命题公式的表达式的运算规律：
同代数表达式命题公式的运算方法：
所有公式中的命题变量用指定命题（真值）代入（或指派），得到一个公式对应的真值。
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,37
性质 1：
如果一个命题公式有 N个互异的命题变量，则命题公式对应的真值有 2的 N次幂种可能分布。
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,38
永真命题公式（ Tautology）
公式中的命题变量无论怎样代入，公式对应的真值恒为 T。
永假命题公式（ Contradiction)
公式中的命题变量无论怎样代入，公式对应的真值恒为 F。
可满足命题公式（ Satisfaction）
公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为 T。
一般命题公式（ Contingency）
既不是永真公式也不是永假公式。
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,39
性质 2：
（ 1）设 P是永真命题公式，则 P的否定公式是永假命题公式；
（ 2）设 P是永假命题公式，则 P的否定公式是永真命题公式；
（ 3）设 P,Q是永真命题公式，则 P （ P ∧ Q）、（ P
∨ Q）、（ P → Q ）、（ PQ）也是永真命题公式
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,40
小 结
1、命题的概念：定义、逻辑值,符号化表示
2、从简单命题到复合命题：
逻辑联接词：运算方法、运算优先级
3、从命题常量到命题变量，
从复合命题到命题公式：
命题公式的真值描述：真值表
4、命题公式的分类：
永真公式、永假公式、可满足公式,一般公式
L o g i c
命题逻辑
7/31/2009 11:26 AM Deren Chen,ZheJiang Univ,41
进一步的思考：
1、从二值逻辑到多值逻辑
2、从确定值到模糊值模糊逻辑（ Fuzzy Logic)
练习题：
2,7,21（ d）,25（ d）
