1、离离散散数数学学DiscreteMathematics计算机科学与工程学院计算机科学与工程学院 金金 忠忠智能楼智能楼(337幢幢)305室室84317297-305,13770713373http:/ 合合 论论 (6-8)图图 论论(9-10)(9-10)代代 数数(11-12)(11-12)刘嘉忆刘嘉忆3/37对计算机专业系统知识辐射作用4/37数理逻辑数理逻辑第一章第一章 命题演算基础命题演算基础第二章第二章 命题演算推理理论命题演算推理理论第三章第三章 谓词演算基础谓词演算基础第四章第四章 谓词演算推理理论谓词演算推理理论第五章第五章 递归函数论递归函数论5/37第一章第一章 命题演
2、算基础命题演算基础1.11.1 命题和联结词命题和联结词1.1.1 命题命题 (一一)命题定义命题定义定义定义1凡是能够凡是能够判断真假判断真假陈说句陈说句称为称为命题命题。命题值命题值 真真,用用T(或或1)表示表示假假,用用F(或或0)表示表示6/37例：以下句子都是命题吗？雪是白。雪是白。雪是黑。雪是黑。好大雪啊！好大雪啊！8大于大于12。1+101=110。7/37例：以下句子都是命题吗？上海世博会开幕时天晴 二十一世纪末，人类将住在月球 大于2偶数可表示成两个素数之和X0，则则 x20。例例 若两圆面积相等，则它们半径相等。若两圆面积相等，则它们半径相等。27/37是否命题？是否复合
3、命题？是否命题？是否复合命题？例例 若两圆面积相等，则它们半径相等若两圆面积相等，则它们半径相等。例例 若两圆若两圆A、B面积相等，则它们半径相等。面积相等，则它们半径相等。例例 吃一堑，长一智吃一堑，长一智。AB28/37真值函项定义以真假为以真假为定义域定义域并以真假为并以真假为值域值域函数函数T,F(T,T),(T,F),(F,T),(F,F)T,F一元真值函项一元真值函项二元真值函项二元真值函项T,F29/37一元联结词真值表一个命题变项一个命题变项P，可取，可取“T”和和“F”两种值。两种值。可定义四个一元真值函项可定义四个一元真值函项 f0，f1，f2，f3。P f0(P)f1(P
4、)f2(P)f3(P)T T T F FF T F T F永永真真恒恒等等否否定定 P永永假假30/37二元联结词 P Q f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15T T T F T T T F F F T T T T F F F FT F T T F T T F T T F F T F T F F FF T T T T F T T F T F T F F F T F FF F T T T T F T T F T F F F F F T Ff4为析取f2为蕴含f8为等价f11为合取31/37三元联结词共有多少个？f0f1f2f?
5、(0,0,0)0101(0,0,1)0011(0,1,0)0001(0,1,1)0001(1,0,0)0001(1,0,1)0001(1,1,0)0001(1,1,1)00012832/371.1.3 合式公式合式公式为以下定义式子，简称为公式：合式公式为以下定义式子，简称为公式：任何命题变元均是公式；任何命题变元均是公式；假如假如P为公式，则为公式，则 P为公式；为公式；假如假如P，Q为公式，则为公式，则 P Q,P Q,PQ,PQ 为公式；为公式；当且仅当经过有限次使用当且仅当经过有限次使用、所组成所组成符号串才是公式，不然不为公式符号串才是公式，不然不为公式。Wellformedform
6、ulae33/37n 元公式 若公式若公式 中有中有n n个不一样命题变元，个不一样命题变元，就说就说 为为n n 元公式。元公式。3元公式例子：元公式例子：（P Q）R）（P Q）（P Q R）（P Q）34/37优先级约定 、优先级相同 比其它联结词有更高优先级比其它联结词有更高优先级 括号括号（）（）内运算优先内运算优先例例令令P：北京比天津人口多。：北京比天津人口多。Q：2+24。R：乌鸦是白色。：乌鸦是白色。求以下公式真值：求以下公式真值：(1)(Q R)(P R)(2)(P R)(P R)35/37命题符号化l分析出简单命题，符号化分析出简单命题，符号化l用联结词联结简单命题用联结
7、词联结简单命题提醒：依据命题实际含义，不拘泥于原句形式地确定提醒：依据命题实际含义，不拘泥于原句形式地确定原子命题和选取联结词。原子命题和选取联结词。例例 将下述命题符号化，并指出真值将下述命题符号化，并指出真值:（1）肉包子是由面粉和猪肉做成。）肉包子是由面粉和猪肉做成。（2）2是质数且偶数，是质数且偶数，3是质数或偶数。是质数或偶数。（3）假如我只有知道希腊文才能了解柏拉图，那）假如我只有知道希腊文才能了解柏拉图，那么我不了解柏拉图。么我不了解柏拉图。（4）假如他喜欢）假如他喜欢QQ，他就喜欢微信；当小红心情，他就喜欢微信；当小红心情愉快时，她就唱歌；反之，当她唱歌时，一愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快。定心情愉快。36/37例4(p5)已知三个命题：已知三个命题：P：今晚我在家上网；：今晚我在家上网；Q：今晚我去球场看足球比赛；：今晚我去球场看足球比赛；R：今晚我在家上网或去球场看足球比赛。：今晚我在家上网或去球场看足球比赛。试问试问P Q和和R是否表示同一命题？是否表示同一命题？请用真值表说明之。请用真值表说明之。R=(P Q)(PQ)P Q PQ R T T T F T F T T F T T T F F F F不可兼 或或 37/37
