离散数学数理逻辑部分.ppt

离离离离   散散散散   数数数数   学学学学Discrete MathematicsDiscrete Mathematics张清华张清华 蒲兴成蒲兴成 尹邦勇尹邦勇 刘勇刘勇重庆邮电大学重庆邮电大学离散数学课程地位：离散数学课程地位：Ø计算机系核心课程计算机系核心课程Ø信息类专业必修课程信息类专业必修课程Ø其它类专业的重要选修课程其它类专业的重要选修课程离散数学的后继课程：离散数学的后继课程：Ø数据结构、操作系统、数据结构、操作系统、Ø算法分析与设计、算法分析与设计、Ø数据库、数据库、c++c++语言语言………… 学习该课程的目的：学习该课程的目的： 一方面一方面，它给后继课，如数据结构、编，它给后继课，如数据结构、编译系统、操作系统、数据库原理、软件工程与译系统、操作系统、数据库原理、软件工程与方法学、计算机网络、程序设计等，提供必要方法学、计算机网络、程序设计等，提供必要的数学基础；的数学基础； 另一方面另一方面，通过学习离散数学，可以培养，通过学习离散数学，可以培养和提高自己的抽象思维和逻辑推理能力，为以和提高自己的抽象思维和逻辑推理能力，为以后的软、硬件学习和研究开发工作，打下坚实后的软、硬件学习和研究开发工作，打下坚实的数学基础。

的数学基础教学要求：教学要求： 通过该课程的学习，学生应当了解并掌通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用的离散数学中的一握计算机科学中普遍采用的离散数学中的一些基本概念、基本思想、基本方法些基本概念、基本思想、基本方法自学要求自学要求：： 通过反复看书及做课后习题，来加深对通过反复看书及做课后习题，来加深对该课程中的一些基本概念的理解，逐步提高该课程中的一些基本概念的理解，逐步提高自己的抽象思维和逻辑推理能力自己的抽象思维和逻辑推理能力离散数学课程的学习方法离散数学课程的学习方法: :Ø强调：逻辑性、抽象性；强调：逻辑性、抽象性；Ø注重：概念、方法与应用注重：概念、方法与应用离散数学的学习要领：离散数学的学习要领：Ø概念（正确）概念（正确） 必须掌握好离散数学中大量的概念必须掌握好离散数学中大量的概念 Ø判断（准确）判断（准确） 根据概念对事物的属性进行判断根据概念对事物的属性进行判断 Ø推理（可靠）推理（可靠） 根据多个判断推出一个新的判断根据多个判断推出一个新的判断 离散数学的内容离散数学的内容Ø第一部分第一部分 数理逻辑数理逻辑：：命题逻辑、谓词逻辑命题逻辑、谓词逻辑Ø第二部分第二部分 集合论集合论：：集合、关系、函数集合、关系、函数 Ø第三部分第三部分 代数系统代数系统：：运算、代数系统、半群、运算、代数系统、半群、群、环、域、格、布尔代数群、环、域、格、布尔代数 Ø第四部分第四部分 图论图论：：点与边、点与边、 路与圈、最短路、路与圈、最短路、 EulerEuler图、图、HamiltonHamilton图、平面图、树图、平面图、树 离散数学与计算机的关系离散数学与计算机的关系第一部分第一部分 数理逻辑数理逻辑 计算机是数理逻辑和电子学相结合的产物。

计算机是数理逻辑和电子学相结合的产物 第二部分第二部分 集合论集合论 集合是一种重要的数据结构关系，关系数据库的理论基集合是一种重要的数据结构关系，关系数据库的理论基础函数，所有计算机语言中不可缺少的一部分础函数，所有计算机语言中不可缺少的一部分 第三部分第三部分 代数系统代数系统 计算机编码和纠错码理论数字逻辑设计基础计算机使用计算机编码和纠错码理论数字逻辑设计基础计算机使用的各种运算的各种运算第四部分第四部分 图论图论 数据结构、操作系统、编译原理计算机网络原理的基础数据结构、操作系统、编译原理计算机网络原理的基础 第一章第一章 命题逻辑命题逻辑Ø数数理理逻逻辑辑是是研研究究推推理理（（即即研研究究人人类类思思维维的的形形式式结结构构和和规规律律））的的科科学学，，起起源源于于1717世世纪纪，，它它采采用用数数学学符号化的方法，因此也称为符号逻辑符号化的方法，因此也称为符号逻辑Ø从从广广义义上上讲讲，，数数理理逻逻辑辑包包括括四四论论、、两两演演算算————即即集集合合论论、、模模型型论论、、递递归归论论、、证证明明论论和和命命题题逻逻辑辑演演算算、、谓谓词词逻逻辑辑演演算算，，但但现现在在提提到到数数理理逻逻辑辑，，一一般般是是指指命命题题逻逻辑辑和和谓谓词词逻逻辑辑。

本本书书也也只只研研究究这这两两个个逻辑演算逻辑演算Ø数数理理逻逻辑辑的的创创始始人人是是LeibnizLeibniz，，为为了了实实现现把把推推理理变变为为演演算算的的想想法法，，他他把把数数学学引引入入了了形形式式逻逻辑辑其其后后，，又又经经多多人人努努力力，，逐逐渐渐使使得得数数理理逻逻辑辑成成为为一门专门的学科一门专门的学科Ø上上个个世世纪纪3030年年代代以以后后，，数数理理逻逻辑辑进进入入一一个个崭崭新新的的发发展展阶阶段段，，逻逻辑辑学学不不仅仅与与数数学学结结合合，，还还与与计计算机科学等密切关联算机科学等密切关联Ø19311931年年GodelGodel不不完完全全性性定定理理的的提提出出，，以以及及递递归归函函数数可可计计算算性性的的引引入入，，促促使使了了19361936年年TuringTuring机机的产生，十年后，第一台电子计算机问世的产生，十年后，第一台电子计算机问世Ø数数理理逻逻辑辑与与计计算算机机学学、、控控制制论论、、人人工工智智能能的的相相互互渗渗透透推推动动了了其其自自身身的的发发展展，，模模糊糊逻逻辑辑、、概概率率逻逻辑辑、、归归纳纳逻逻辑辑、、时时态态逻逻辑辑等等都都是是目目前前比比较较热热门的研究领域。

门的研究领域Ø本本章章和和下下一一章章我我们们只只从从语语义义出出发发，，对对数数理理逻逻辑辑中中的的命命题题逻逻辑辑与与谓谓词词逻逻辑辑等等作作一一简简单单的的、、直直接接的、非形式化的介绍，将不涉及任何公理系统的、非形式化的介绍，将不涉及任何公理系统第一章 命题逻辑命题逻辑1. 1. 命题及其表示命题及其表示Ø命命题题：：是是指指具具有有确确定定真真值值的的陈陈述述句句或或者者能能够够判判断断真真假假的陈述句的陈述句Ø命命题题的的真真值值：：命命题题的的判判断断结结果果真真值值只只取取两两个个值值：： 真真（（1 1或或T T）、假（）、假（0 0或或F F）Ø真命题：真值为真的命题真命题：真值为真的命题Ø假命题：真值为假的命题假命题：真值为假的命题判断命题的两个步骤判断命题的两个步骤：： 1 1、是否为陈述句；、是否为陈述句； 2 2、是否有确定的、唯一的真值、是否有确定的、唯一的真值1.11.1节节 命题及联结词命题及联结词 注意: 感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题. . 陈述句中陈述句中的悖论以及判断结果不惟一确定的也不是命题。

的悖论以及判断结果不惟一确定的也不是命题例例1.1 1.1 下列句子中那些是命题？下列句子中那些是命题？ （（1 1）重庆是直辖市重庆是直辖市2 2）教师是人类灵魂的工程师教师是人类灵魂的工程师3 3））4 4是素数4 4））1+11+1＝＝2 25 5））21002100年的春节是晴天年的春节是晴天6 6）火星上有生物火星上有生物7 7）请安静！）请安静！（（8 8）今天天气多好啊）今天天气多好啊! !（（9 9）现在是几点钟）现在是几点钟? ?（（1010）我正在说假话我正在说假话1111））Ø（（1 1）、（）、（2 2）、（）、（3 3）、（）、（4 4）、（）、（5 5）和（）和（6 6）都是命题其中）都是命题其中（（1 1）、（）、（2 2）、（）、（4 4）是真命题，（）是真命题，（3 3）是假命题是假命题Ø至于（至于（5 5）和（）和（6 6）真假值是确定的，只是现在无法知道，因此它）真假值是确定的，只是现在无法知道，因此它是命题Ø（（7 7）、（）、（8 8）、（）、（9 9）、（）、（1010）、（）、（1111）都不是命题原因在于）都不是命题原因在于（（7 7）是祈使句，（）是祈使句，（8 8）是感叹句，（）是感叹句，（9 9）是疑问句，而（）是疑问句，而（1010）是）是悖论，即若悖论，即若(10)(10)的真值为真，即的真值为真，即““我正在说假话我正在说假话””为真，也就是为真，也就是我说的是假话，因此（我说的是假话，因此（1010）又是错误的；反之，若）又是错误的；反之，若(10)(10)的真值为的真值为假，即假，即““我正在说假话我正在说假话””为假，也就是我在说真话，因此为假，也就是我在说真话，因此 (10)(10)的真值应为真。

的真值应为真Ø像像(10)(10)这样既不为真又不为假的陈述句不是命题，这种陈述句称这样既不为真又不为假的陈述句不是命题，这种陈述句称为悖论凡是悖论都不是命题凡是悖论都不是命题1111）中的）中的x x、、y y 的值不确定，的值不确定，某些某些x x、、y y使为真，某些使为真，某些x x、、y y使为假，即的真假随使为假，即的真假随x x、、y y的变化而变的变化而变化因此，的真假无法确定，所以不是命题因此，的真假无法确定，所以不是命题 练习练习 判断下列句子是否为命题判断下列句子是否为命题1. 1001. 100是自然数是自然数2. 2. 太阳从西方升起太阳从西方升起3. 3. 北京是中国的首都北京是中国的首都4. 4. 重庆是中国最大的城市重庆是中国最大的城市5. 5. 关门关门! !6. 6. 你去哪里你去哪里? ?7. How do you do ?7. How do you do ?8. 8. 凡石头均可炼成金凡石头均可炼成金9. x+3>99. x+3>910. 10. 皇马中国之行没有提升国家队的水平皇马中国之行没有提升国家队的水平命题表示命题表示 在本书中，用大写的英文字母在本书中，用大写的英文字母P,Q,R,…P,Q,R,…，，P1,P2,P3…P1,P2,P3…，，[1][1]，，[2][2]等表示命题等表示命题, ,用用““1(1(或者或者T T））””、、““0 0（或者（或者F F））””分别表示真值的真、假。

分别表示真值的真、假 如如 P P：太阳从东边升起太阳从东边升起 Q Q：：5 5是负数 [1][1]：：20082008北京举办奥运会北京举办奥运会 其真值依次为其真值依次为1 1、、0 0、、1 1命题的分类命题的分类简简单单/ /原原子子命命题题：：由由不不能能再再分分解解为为更更简简单单的的陈陈述句的陈述句构成述句的陈述句构成 复复合合命命题题：：由由简简单单命命题题通通过过联联结结词词联联结结而而成成的陈述句的陈述句如：如： 命题命题““如果如果2 2是素数，则是素数，则3 3也是素数也是素数””通过通过““如果如果…………，则，则……” ……” 组合而成，是复合命题，而组合而成，是复合命题，而““2 2是素数是素数””和和““3 3是素数是素数””是简单命题是简单命题2. 2. 命题联结词命题联结词Ø在日常语言中，一些简单的陈述句，可以通过某些联在日常语言中，一些简单的陈述句，可以通过某些联结词联结起来，组成较为复杂的语句结词联结起来，组成较为复杂的语句 例如可以说：例如可以说：““如果下星期日是晴天，那么我就去如果下星期日是晴天，那么我就去春游。

春游这里就是用：这里就是用：““如果如果…………，那么，那么……”……”把两把两个陈述句个陈述句““下星期日是晴天下星期日是晴天””和和““我去春游我去春游””联结起联结起来组成的一个新复合命题来组成的一个新复合命题 在日常语言中还有许多联结词，如在日常语言中还有许多联结词，如““不不””、、““并且并且””、、““或者或者””、、““当且仅当当且仅当””，，““只要只要…………就就……”……”，，““除非除非…………否则否则……”……”等都是联结词等都是联结词Ø使用它们可以将一个命题加以否定或将两个命题连接使用它们可以将一个命题加以否定或将两个命题连接起来得到新的复合命题起来得到新的复合命题Ø下面介绍常用的下面介绍常用的5 5种常用的联结词种常用的联结词（（1 1）否定联结词）否定联结词 设设 p p为为 命命 题题 ，， 复复 合合 命命 题题 ““非非 P”P”（（ 或或 ““P P的的 否否定定””））称称为为P P的的否否定定式式，，记记作作  P P，， 符号符号  称为否定联结词。

称为否定联结词 运算规则运算规则：属于单目运算符：属于单目运算符P P1001（（2 2）合取联结词）合取联结词设设 P,QP,Q为为 二二 命命 题题 变变 元元 ，， 复复 合合 命命 题题 ““P P并并 且且 Q” Q” （（或或““P P与与Q”Q”））称称为为P P与与Q Q的的合合取取式式，，记记 作作P ∧ QP ∧ Q，，符号符号∧∧称为合取联结词称为合取联结词 运算规则：运算规则：属于双目运算符属于双目运算符PQP ∧∧ Q000 0 10 10 0 111合取运算特点合取运算特点：： 只只有有参参与与运运算算的的二二命命题题全全为为真真时时，，运运算算结结果果才才为为真真，，否否则则为为假假自自然然语语言言中中的的表表示示“并并且且”意意思思的的联联结结词词，，如如“既既…又又…”、、“不不但但…而而且且…”、、“虽然虽然…但是但是”等都可以符号化为等都可以符号化为∧∧例如例如：将下列命题符号化：将下列命题符号化(1) (1) 北京不仅是中国的首都而且是一个故都。

北京不仅是中国的首都而且是一个故都 解：解：设设P P：：北京是中国的首都；北京是中国的首都；Q Q：北京是一个故都；：北京是一个故都； 则原命题符号化为：则原命题符号化为： P∧QP∧Q（（2））小丽既聪明，又能干小丽既聪明，又能干   解：解：设设P：：小丽聪明；小丽聪明；Q：小丽能干；：小丽能干；   则原命题符号化为：则原命题符号化为： P∧∧Q3）小刚聪明但不努力小刚聪明但不努力   解：解：设设P：：小刚聪明；小刚聪明；Q：小刚努力；：小刚努力；   则原命题符号化为：则原命题符号化为： P∧∧Q4）小刚和小明是同学小刚和小明是同学  解：解：这是一个原子命题，不能分解为更细的命题这是一个原子命题，不能分解为更细的命题（（3 3）析取联结词）析取联结词       设设P,QP,Q为为二二命命题题变变元元，，复复合合命命题题“P P或或Q Q” 称称为为 P P与与Q Q的的析析取取式式，，记记作作P P ∨ ∨ Q Q，，符号符号∨∨称为析取联结词称为析取联结词 运算规则：运算规则：属于双目运算符。

属于双目运算符PQP ∨ Q00 0 011101111 说明说明：联结词析取：联结词析取∨∨的意义与日常所使用的意义与日常所使用的的““或或””意思并不完全相同在日常生活意思并不完全相同在日常生活中，中，““或或””实际上分为实际上分为 “ “排斥或排斥或””和和““可可兼或兼或””，还有一种是描述，还有一种是描述模糊数据模糊数据本书将析取表示将析取表示““可兼或可兼或””排斥或排斥或””用等用等价的联结词代替价的联结词代替例如例如: :(1)(1)今天晚上我在家看电视或听音乐今天晚上我在家看电视或听音乐 解：设解：设P P：今天晚上我在家看电视；：今天晚上我在家看电视； Q Q：今天晚上我在家听音乐；：今天晚上我在家听音乐；则原命题符号化为：则原命题符号化为： P ∨ QP ∨ Q 可兼或）可兼或）（（2 2）从重庆到北京的）从重庆到北京的T10T10次列车是中午次列车是中午1 1点或点或1 1点半开解：该命题中的解：该命题中的““或或””不是不是““可兼或可兼或””，不能用联结词析，不能用联结词析取我们用一种等价形式来代替我们用一种等价形式来代替。

设设P P：重庆到北京的：重庆到北京的T10T10次列车是中午次列车是中午1 1点开；点开； Q Q：重庆到北京的：重庆到北京的T10T10次列车是中午次列车是中午1 1点半开；点半开； 则原命题符号化为：则原命题符号化为： (P∧(P∧ Q) ∨(Q) ∨( P∧Q).P∧Q). 例如例如: :（（3 3）小刚是山东或山西人小刚是山东或山西人解：设解：设P P：小刚是山东人；：小刚是山东人；Q Q：小刚是山西人；：小刚是山西人；则原命题符号化为：则原命题符号化为： (P∧(P∧ Q) ∨(Q) ∨( P∧Q).P∧Q).（排斥或）（排斥或）（（4 4）小刚是有）小刚是有2020或或3030岁解：这是一个原子命题，这里的解：这是一个原子命题，这里的““或或””表示一个模糊数表示一个模糊数据 在遇到含有在遇到含有““或或””的命题符号化时，要分清它是的命题符号化时，要分清它是““可兼或可兼或””、、““排斥或排斥或””、还是表示模糊数的、还是表示模糊数的““或或””，析取联结词表示，析取联结词表示““可兼或可兼或””。

（（4 4）单条件联结词）单条件联结词 设设P,QP,Q为二命题变元为二命题变元, ,复合命题复合命题““如果如果P,P,则则Q” Q” 称为称为P P与与Q Q的单条件（蕴涵式），记作的单条件（蕴涵式），记作P PQ Q，并称，并称P P为单条为单条件的前件，件的前件，Q Q为单条件的后件，符号为单条件的后件，符号称为单条件结称为单条件结词 运算规则：运算规则：属于双目运算符属于双目运算符 与自然语言的不同：与自然语言的不同：前件与后件可以没有任何内在联系！前件与后件可以没有任何内在联系！PQP  Q001011100111说明：说明：P PQ Q 的逻辑关系：的逻辑关系：Q Q 为为 P P 的必要条件的必要条件““如果如果 P P，则，则 Q ” Q ” 的不同表述法很多：的不同表述法很多： “ “若若P P，就，就Q”Q” “ “只要只要P P，就，就Q”Q” “P “P仅当仅当Q”Q” “ “只有只有Q Q才才P”P” “ “除非除非Q,Q,才才P”P”或或““除非除非Q, Q, 否则非否则非P” ...P” ...等等。

等等 当当P P为假时，无论为假时，无论Q Q是什么，是什么，P PQ Q均为真 常出现的错误：常出现的错误：不分充分与必要条件！！不分充分与必要条件！！例如：例如：（（1 1）） 如果天下雨，那么我们在室内活动如果天下雨，那么我们在室内活动 解：设解：设P P：天下雨；：天下雨；Q Q：我们在室内活动；：我们在室内活动； 原命题符号化为：原命题符号化为：P PQ Q 2 2）只要天下雨，我们就在室内活动只要天下雨，我们就在室内活动 解：设解：设P P：天下雨；：天下雨；Q Q：我们在室内活动；：我们在室内活动； 原命题符号化为：原命题符号化为：P PQ Q 3 3）因为天下雨，所以我们在室内活动因为天下雨，所以我们在室内活动 解：设解：设P P：天下雨；：天下雨；Q Q：我们在室内活动；：我们在室内活动； 原命题符号化为：原命题符号化为： P PQ Q 在实际的语言中，很多联结词可以转化为用单条在实际的语言中，很多联结词可以转化为用单条件，但是要注意前件和后件的关系件，但是要注意前件和后件的关系（（4 4）只有天下雨，我们才在室内活动。

只有天下雨，我们才在室内活动解：设解：设P P：天下雨；：天下雨；Q Q：我们在室内活动；：我们在室内活动；原命题符号化为：原命题符号化为：Q QP P 5 5）） 仅当天下雨，我们在室内活动仅当天下雨，我们在室内活动解：设解：设P P：天下雨；：天下雨；Q Q：我们在室内活动；：我们在室内活动；原命题符号化为：原命题符号化为：Q QP P 6 6）） 除非天下雨，否则我们不在室内活动除非天下雨，否则我们不在室内活动解：设解：设P P：天下雨；：天下雨；Q Q：我们在室内活动；：我们在室内活动；原命题符号化为：原命题符号化为：Q QP P ，或者，或者  P P   Q Q （（5 5）双条件联结词）双条件联结词 设设P,QP,Q为为二二命命题题变变元元，，复复合合命命题题““P P当当且且仅仅当当Q” Q” 称称为为P P与与Q Q的的双双条件，记作条件，记作P P Q Q，， 符号符号称为双条件联结词称为双条件联结词说明说明:(1) P:(1) PQ Q 的逻辑关系的逻辑关系:P:P与与Q Q互为充分必要条件互为充分必要条件 (2) P(2) PQ Q为真当且仅当为真当且仅当P P与与Q Q同真或同假。

同真或同假 运算规则：运算规则：属于双目运算符属于双目运算符PQP  Q001010 10 0 111例如：例如： ( (1) 2+21) 2+2＝＝4 4 当且仅当当且仅当 3+33+3＝＝6.6. 解：设解：设P P：： 2 + 2 2 + 2 ＝＝ 4 4 ；；Q Q：： 3 + 3 3 + 3 ＝＝ 6.6.；；原命题符号化为：原命题符号化为：P P  Q Q （（2 2））1+1=21+1=2当且太阳从东边升起当且太阳从东边升起 解：设解：设P P：：1+1=21+1=2；；Q Q：太阳从东边升起；：太阳从东边升起；原命题符号化为原命题符号化为： P P  Q Q 3命题公式与真值表命题公式与真值表 将命题将命题 “ “如果明天天晴，且我有空，我就去踢球如果明天天晴，且我有空，我就去踢球””符号符号化 设设P P：明天天晴；：明天天晴；Q Q：我有空；：我有空；R R：我去踢球我去踢球 本命题符号化为：本命题符号化为： （（P P Q QR R。

命题变元和联结词构成复合命题的形式化描述，为了能命题变元和联结词构成复合命题的形式化描述，为了能够更加准确的描述命题，本节主要讨论命题公式及其命够更加准确的描述命题，本节主要讨论命题公式及其命题公式的赋值题公式的赋值 命题公式命题公式（（1 1）单个命题变项是合式公式，并称为原子命题公式单个命题变项是合式公式，并称为原子命题公式2 2）若）若A A是合式公式，则是合式公式，则( ( A)A)也是合式公式也是合式公式3 3））若若A A，，B B是是合合式式公公式式，，则则(A∧B)(A∧B)，，(A∨B)(A∨B)，，(A(AB)B)，，(A(AB) B) 也是合式公式也是合式公式4 4））只只有有有有限限次次地地应应用用(1)(1)、、（（2 2））、、(3)(3)形形成成的的包包含含命命题题变变元、联结词和圆括号的符号串是命题合式公式元、联结词和圆括号的符号串是命题合式公式 命题合式公式也称为命题公式或命题形式，并简称为公式命题合式公式也称为命题公式或命题形式，并简称为公式例如：例如： (P(PQ)Q)，， (R∧S)∨(R∧S)∨ Q Q，， Q QP P等均为合式公式等均为合式公式; ; 而而PQ∨S PQ∨S , , (P,Q(P,Q））R R，， (P∨∧Q)(P∨∧Q)R R，， (P(PW)∧Q)W)∧Q)等等不不是合式公式是合式公式。

联联结结词词之之间间的的运运算算有有不不同同的的优优先先级级，，联联结结词词运运算算的的优优先先次次序序为为:{:{ ，，∧∧，，∨∨，，，，} }如如果果有有括括号号，，则则先先进进行行括括号内的运算号内的运算真值表真值表 设设A A是一个命题公式，是一个命题公式，P P1 1，， P P2 2 ，，......，， P Pn n是出现在是出现在A A中的所有命题变元，对这些命题变元赋予一个确定的真中的所有命题变元，对这些命题变元赋予一个确定的真值称为对命题公式的一种赋值值称为对命题公式的一种赋值 不同的赋值，命题公式有不同真值情况将命题公不同的赋值，命题公式有不同真值情况将命题公式在所有的赋值下的真值情况汇成一个表，这个表就称式在所有的赋值下的真值情况汇成一个表，这个表就称为真值表如果一个命题公式有为真值表如果一个命题公式有n n个命题变元，每个命题个命题变元，每个命题变元有两种真值情况，则共有变元有两种真值情况，则共有n n2 2种不同的赋值情况种不同的赋值情况 对公式对公式A A构造真值表的具体步骤为：构造真值表的具体步骤为：      (1)找找出出公公式式中中所所有有的的全全体体命命题题变变项项p1 ，， p2 ，， … ，， pn，，列出列出2n个赋值。

个赋值      (2)按按从从高高到到低低（（从从低低到到高高））的的顺顺序序写写出出公公式式的的各各个层次      (3)对对应应各各个个赋赋值值计计算算出出各各层层次次的的真真值值，，直直到到最最后后计算出公式的真值计算出公式的真值例如例如：求命题公式：求命题公式 (P(PQ)∧RQ)∧R的真值表的真值表PQR PQ(P  Q) ∧R00 0 10 0 0 11 1 0 1 0 1 0 0 1 1 1 1 1 0 0 00 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 例如例如：求命题公式：求命题公式 (P∧(P∧ Q)Q)R R的真值表的真值表PQR (P∧(P∧ Q)Q)R R00 0 10 0 110 1 0 10 1 1 11 0 0 01 0 1 11 1 0 11 1 1 1例如例如：求命题公式：求命题公式(P(PQ)Q)( (  Q Q P P) )的真值表的真值表PQ P QPQ Q  P(PQ)(Q  P)00 11 1 110 11 01 1 1 1 0 0 1 0 01 1 1 0 0 1 1 1 例如例如：求命题公式：求命题公式 (P(PQ)∧Q Q)∧Q 的真值表。

的真值表PQ (P  Q)  (P  Q)   (P Q) ∧∧Q00 1000 11 0 0 1 0 010 1 1 1 0 0 PQP Q (P ∧  Q)0011011110001111例如例如：求命题公式：求命题公式P PQ Q和和 (P∧ Q)的真值表的真值表命题公式等值命题公式等值 设设A,BA,B是是两两个个命命题题公公式式，，若若A A，，B B构构成成的的等等价价式式A AB B为为重重言言式式，，则则称称A A与与B B是是等等值值的的记记作作A A  B. B. 即即A A  B B的充要条件是的充要条件是A AB B为重言式为重言式判断两个公式等值的方法判断两个公式等值的方法1 1：真值表法真值表法PQRP∧∧Q Q  RP(Q R )(P∧∧Q) R 00 0 0 111 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 例如：例如：P P( (Q QR)R)与与(P(P∧∧Q)Q)R R等价等价•命题公式中有很多公式都是等价的；命题公式中有很多公式都是等价的；•要记住大量的等价公式是困难的；要记住大量的等价公式是困难的；•然而一些然而一些基本的、重要的基本的、重要的等价公式是应等价公式是应该掌握的。

该掌握的•下面列出一些最基本的等价公式也称下面列出一些最基本的等价公式也称命题定律命题定律双重否定律双重否定律 : : P PP P等幂律等幂律：： P P P PP; PP; P P PP P交换律交换律: P: P Q QQ Q P; PP; P Q QQ Q P P结合律结合律: (P: (P Q)Q) R RP P (Q(Q R) R) (P (P Q)Q) R RP P (Q(Q R)R)分配律分配律: P: P (Q(Q R)R)(P(P Q)Q) (P(P R) R) P P (Q(Q R)R)(P(P Q)Q) (P(P R)R)德德··摩根律摩根律 : :  (P(P Q)Q)P PQ Q  (P(P Q)Q)P PQ Q吸收律吸收律: P: P (P(P Q)Q)P, PP, P (P(P Q)Q)P P零零 律律: P: P 1 11, P1, P 0 00 0 同一律同一律: P: P 0 0P, PP, P 1 1P P排中律排中律: P: PP P1 1矛盾律矛盾律: P: PP P0 0等值蕴涵律等值蕴涵律: P: PQ Q  P P Q Q假言异位律假言异位律: P: PQ Q  Q Q    P P等价等值律等价等值律: P: PQ Q（（P PQ Q）） （（Q Q P P））置换规则置换规则：若：若A AB B, , 则则 ( (B B) ) ( (A A) )。

用等值公式可以进行等值演算，证明等值公式、用等值公式可以进行等值演算，证明等值公式、判定公式类型判定公式类型. .下面举例说明下面举例说明. .试证试证:证明：证明：又如又如：验证：验证 P P( (Q QR) R)  (P (P ∧∧ Q) Q) R R 右右 (P(P∧∧Q)Q)∨∨R R    P P∨∨  Q Q∨∨R RÛ  P P∨∨( (  Q Q∨∨R) R) Û  P P∨∨（（Q QR) R) ÛP P(Q(QR)R) 公式的分类公式的分类 重言式重言式：给定一个命题公式，若无论对其中的命：给定一个命题公式，若无论对其中的命题变元作何种赋值，其对应的真值永为题变元作何种赋值，其对应的真值永为1 1，则称，则称该命题公式为重言式或永真式。

该命题公式为重言式或永真式 永假式永假式：给定一个命题公式，若无论对其中的命：给定一个命题公式，若无论对其中的命题变元作何种赋值，其对应的真值永为题变元作何种赋值，其对应的真值永为0 0，则称，则称该命题公式为矛盾式或永假式该命题公式为矛盾式或永假式 可满足式可满足式：给定一个命题公式，若存在一种赋值：给定一个命题公式，若存在一种赋值使得公式的真值为使得公式的真值为1 1，则称该命题公式为可满足，则称该命题公式为可满足式用等值演算法判断公式用等值演算法判断公式Q Q(P(PQ)Q)的类型解：解： Q Q(P(PQ)Q)  Q Q( ( P P Q)Q)  Q Q (P(PQ)Q)  P P (Q(QQ)Q)  P P 0 0  0 0该式为矛盾式该式为矛盾式. . 用等值演算法判断公式用等值演算法判断公式(P(PQ)Q)( ( Q QP)P)的类型解解: (P: (PQ)Q)( ( Q QP)P)  ( ( P P Q)Q)(Q(QP)P)  ( ( P P Q)Q)( ( P P Q) Q)  1 1该式为重言式该式为重言式. .1.3 1.3 命题公式的范式与主范式命题公式的范式与主范式文字文字：命题变项及其否定统称为文字。

命题变项及其否定统称为文字 如：如：P , Q P , Q ，， Q Q等等简单析取式简单析取式：仅有有限个文字组成的析取式仅有有限个文字组成的析取式 如：如：P P ，，  Q Q，， P ∨ QP ∨ Q，， P∨P∨ Q∨RQ∨R简单合取式简单合取式：仅有有限个文字组成的合取式仅有有限个文字组成的合取式 如：如：P P ，，  P P ，，P∧Q P∧Q ，， P ∧ P ∧  Q ∧ Q ∧   R R而而P∧P∧ （（Q∧R)Q∧R)不是简单合取不是简单合取, ,  （（P ∨R)P ∨R)不是简不是简单析取•显然，简单析取式是重言式当且仅当它含显然，简单析取式是重言式当且仅当它含有同一个变元及其该变元的否定；有同一个变元及其该变元的否定； 简单合取式是矛盾式当且仅当它含有简单合取式是矛盾式当且仅当它含有同一个变元及其该变元的否定同一个变元及其该变元的否定•命题公式是千变万化的，这给研究命题演命题公式是千变万化的，这给研究命题演算带来困难，这里我们研究如何由一个命算带来困难，这里我们研究如何由一个命题公式化归为一个标准形式的问题，这种题公式化归为一个标准形式的问题，这种标准形式就叫标准形式就叫范式和主范式范式和主范式。

•将一个命题公式转化为析取范式和合取范式的将一个命题公式转化为析取范式和合取范式的主要方法是利用基本的命题等价公式如主要方法是利用基本的命题等价公式如德摩根德摩根律、分配律、蕴涵等值律、同一律、排中律和律、分配律、蕴涵等值律、同一律、排中律和吸收律吸收律等将公式转化为要求的范式等将公式转化为要求的范式•由此可以看出，一个命题公式总可以通过等值由此可以看出，一个命题公式总可以通过等值变化化为与之等值的析取范式和合取范式，但变化化为与之等值的析取范式和合取范式，但是一个命题公式的析取范式和合取范式分别有是一个命题公式的析取范式和合取范式分别有多个，多个，不一定是惟一不一定是惟一的为了能够惟一的表示的为了能够惟一的表示一个命题公式，下面我们主要讨论命题公式的一个命题公式，下面我们主要讨论命题公式的主范式主范式说明：说明：    (1)n个个命命题题变变项项产产生生2n个个极极小小项项和和2n个个极极大大项项, 2n个个极小项（极大项）均互不等值极小项（极大项）均互不等值.    (2)用用mi表示第表示第i个极小项，其中个极小项，其中i是该极小项成真赋值是该极小项成真赋值的十进制表示的十进制表示. 用用Mi表示第表示第i个极大项，其中个极大项，其中i是该极是该极大项成假赋值的十进制表示大项成假赋值的十进制表示, mi(Mi)称为极小项称为极小项(极大极大项项)的名称的名称.        mi与与Mi的关系的关系:    mi  Mi ,     Mi  mi 公式公式 成真赋成真赋值值名称名称 公式公式 成假赋成假赋值值名称名称    p    q   p   q p q p   q0  0  0  1  1  0  1  1 m0m1m2m3  p   q    p   q   p   q   p    q  0  0 0  1 1  0 1  1 M0M1M2M3 极小项极小项 极大项极大项 由由p, q两个命题变项形成的极小项与极大项两个命题变项形成的极小项与极大项 由由p p, , q q, , r r三个命题变项形成的极小项与极大项三个命题变项形成的极小项与极大项 极小项极小项 极大项极大项 公式公式 成真成真赋值赋值名称名称 公式公式 成假成假赋值赋值名称名称  p q r p q   r p   q r p   q   rp q    rp q   rp  q rp  q   r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1m0m1m2m3m4m5m6m7p   q   r p   q r p    q   r p    q r  p   q   r  p   q r  p    q   r  p    q r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1M0M1M2M3M4M5M6M7 我们容易归纳得到我们容易归纳得到极小项极小项的如下性质：的如下性质：Ø每个极小项有且仅有一个成真赋值，该成真赋值每个极小项有且仅有一个成真赋值，该成真赋值与该极小项的编码下标一致。

与该极小项的编码下标一致Ø任意两个不同极小项的合取为矛盾式任意两个不同极小项的合取为矛盾式Ø全体极小项的析取为重言式全体极小项的析取为重言式同样，我们容易得到同样，我们容易得到极大项极大项的如下性质：的如下性质：Ø每个极大项有且仅有一个成假赋值，该成假赋值每个极大项有且仅有一个成假赋值，该成假赋值与该极大项的编码下标一致与该极大项的编码下标一致Ø任意两个不同极大项的析取为重言式任意两个不同极大项的析取为重言式Ø全体极大项的合析取为矛盾式全体极大项的合析取为矛盾式主析取范式与主合取范式主析取范式与主合取范式定定理理 任任何何命命题题公公式式都都存存在在着着与与之之等等值值的的主主析析取范式和主合取范式取范式和主合取范式, 并且是惟一的并且是惟一的.  求公式的主范式的主要方法：求公式的主范式的主要方法： 方法一（等值添项法）方法一（等值添项法） 方法二（真值表法）方法二（真值表法）方法一（等值添项法）方法一（等值添项法）求主析取范式的主要步骤：求主析取范式的主要步骤：Ø第第1 1步：将命题公式化为析取范式；步：将命题公式化为析取范式；Ø第第2 2步：在每个不是极小项的简单合取式中用否定律增加缺少的文字；步：在每个不是极小项的简单合取式中用否定律增加缺少的文字；（注意按照一定顺序添加）（注意按照一定顺序添加）Ø第第3 3步：用分配律展开得到新的析取范式；如果还存在简单合取式不步：用分配律展开得到新的析取范式；如果还存在简单合取式不是极小项时，重复第是极小项时，重复第2 2步；步；Ø第第4 4步：删除重复的极小项，得到主析取范式。

步：删除重复的极小项，得到主析取范式求主合取范式的主要步骤：求主合取范式的主要步骤：Ø第第1 1步：将命题公式化为合取范式；步：将命题公式化为合取范式；Ø第第2 2步：在每个不是极大项的简单析取式中用否定律增加缺少的文字；步：在每个不是极大项的简单析取式中用否定律增加缺少的文字；（注意按照一定顺序添加）（注意按照一定顺序添加）Ø第第3 3步：用分配律展开得到新的合取范式；如果还存在简单析取式不步：用分配律展开得到新的合取范式；如果还存在简单析取式不是极大项时，重复第是极大项时，重复第2 2步；步；Ø第第4 4步：删除重复的极大项，得到主合取范式步：删除重复的极大项，得到主合取范式方法二（真值表法）方法二（真值表法）定理：定理： 一个命题公式的真值表中，成真赋值对应一个命题公式的真值表中，成真赋值对应的极小项的析取是该公式的主析取范式；成假赋的极小项的析取是该公式的主析取范式；成假赋值对应的极大项的合取是该公式的主合取范式值对应的极大项的合取是该公式的主合取范式真值表法求主析取范式的主要步骤：真值表法求主析取范式的主要步骤：Ø第第1 1步：求公式的真值表；步：求公式的真值表；Ø第第2 2步步: : 找出所有的成真赋值，并形成对应的极小项的编码；找出所有的成真赋值，并形成对应的极小项的编码；Ø第第3 3步步: : 将极小项的编码转化成极小项，得到主析取范式。

将极小项的编码转化成极小项，得到主析取范式真值表法求主合取范式的主要步骤：真值表法求主合取范式的主要步骤：Ø第第1 1步：求公式的真值表；步：求公式的真值表；Ø第第2 2步步: : 找出所有的成假赋值，并形成对应的极大项的编码；（注意找出所有的成假赋值，并形成对应的极大项的编码；（注意编码的转化问题）编码的转化问题）Ø第第3 3步步: : 将极大项的编码转化成极大项，得到主合取范式将极大项的编码转化成极大项，得到主合取范式由真值表法很容易得到主范式的如下由真值表法很容易得到主范式的如下性质性质：：Ø主析取范式和主合取范式具有主析取范式和主合取范式具有互补性互补性（即它们（即它们的编码恰好构成全体赋值情况），知道主析取的编码恰好构成全体赋值情况），知道主析取范式可以得到主合取范式，知道主合取范式也范式可以得到主合取范式，知道主合取范式也可以得到主析取范式可以得到主析取范式Ø重言式的主析取范式是全体极小项的析取，其重言式的主析取范式是全体极小项的析取，其主合取范式规定为主合取范式规定为1 1；矛盾式的主合取范式是；矛盾式的主合取范式是全体极大项的合取，其主析取范式规定为全体极大项的合取，其主析取范式规定为0 0。

Ø如果两个不同形式的公式等值，则它们的真值如果两个不同形式的公式等值，则它们的真值表相同，因而它们有相同的主范式表相同，因而它们有相同的主范式 一个公式的主范式是惟一的（除去一个公式的主范式是惟一的（除去极小项和极小项的顺序外）极小项和极小项的顺序外）主范式的主范式的主要用途在于主要用途在于：：Ø规范命题公式的形式；规范命题公式的形式；Ø求公式的成真和成假赋值；求公式的成真和成假赋值；Ø判定公式是否等值；判定公式是否等值；Ø实际应用实际应用 又例又例 某公司要从赵、钱、孙、李、周五名新毕业的大学生中某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习选派一些人出国学习. . 选派必须满足以下条件：选派必须满足以下条件： (1)(1)若赵去，钱也去；若赵去，钱也去； (2)(2)李、周两人中至少有一人去；李、周两人中至少有一人去； (3)(3)钱、孙两人中有一人去且仅去一人；钱、孙两人中有一人去且仅去一人； (4)(4)孙、李两人同去或同不去；孙、李两人同去或同不去； (5)(5)若周去，则赵、钱也去若周去，则赵、钱也去. . 试用主析取范式法分析该公司如何选派他们出国？试用主析取范式法分析该公司如何选派他们出国？解此类问题的步骤为：解此类问题的步骤为：① ① 将简单命题符号化将简单命题符号化② ② 写出各复合命题写出各复合命题③ ③ 写出由写出由②②中复合命题组成的合取式中复合命题组成的合取式 ④ ④ 求求③③中所得公式的主析取范式中所得公式的主析取范式 解解 ① ① 设设p p：派赵去，：派赵去，q q：派钱去，：派钱去，r r：派孙：派孙 去，去，s s：派李去，：派李去，u u：派周去：派周去. . ② (1) ( ② (1) (p pq q) ) (2) ( (2) (s s u u) ) (3) (( (3) ((q qr)r) ( ( q q r r)))) (4) (( (4) ((r r s)s) ( ( r rs s)))) (5) ( (5) (u u(p(p q q)) )) ③ (1) -(5) ③ (1) -(5)构成的合取式为构成的合取式为 A=(A=(p pq)q) (s(s u)u) ((q((qr)r) ( ( q q r r))))  (( ((r r s)s) ( ( r rs))s)) (u(u(p(p q q)))) ④④   A  ( pq r su) (p qrs u)结论：由结论：由④④可知，可知，A的成真赋值为的成真赋值为00110与与11001，，因而派孙、李去（赵、钱、周不去）或派赵、钱、因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）周去（孙、李不去）.    A的演算过程如下的演算过程如下:   A  ( p q) ((qr) ( q r)) (s u) ( u (p q))          ((r s) ( rs))                         （交换律（交换律)B1= ( p q) ((qr) ( q r))   (( p qr) ( pq r) (qr))  (分分配律配律)B2= (s u) ( u (p q))   ((su) (p q s) (p q u))    （分配（分配律）律）B1 B2  ( p qr su) ( pq r su)                  (qr su) (p qr s) (p qr u)再令再令 B3 = ((r s) ( rs))得得 A  B1 B2 B3      ( pq r su) (p qrs u)又如又如：某公司需要从：某公司需要从A,BA,B和和C C这这3 3名骨干人员中派名骨干人员中派2 2名到国外考察，名到国外考察，由于工作需要，选派时需要满足以下条件：由于工作需要，选派时需要满足以下条件：Ø若若A A去，则去，则C C同去；同去；Ø若若B B去，则去，则C C不能去；不能去；Ø若若C C不去，则不去，则A A或或B B可以去。

可以去 请问如何安排？请问如何安排？4 4 联结词的完备集联结词的完备集单元素联结词构成的联结词完备集单元素联结词构成的联结词完备集 人们还可构造形式上更为简单的联结词完备集在计算人们还可构造形式上更为简单的联结词完备集在计算机硬件设计中，用与非门或者或非门来设计逻辑线路时，就需机硬件设计中，用与非门或者或非门来设计逻辑线路时，就需要构造新联结词完备集要构造新联结词完备集5 5 命题推理理论命题推理理论 Ø人人工工智智能能的的重重要要研研究究内内容容是是知知识识的的表表示示与与推推理理，，如如果果将将知知识识用用命命题题符符号号化化的的形形式式给给出出后后，，如如何何按按照照一一定定的的规规则则推导出新的结论和知识是一个重要的内容推导出新的结论和知识是一个重要的内容Ø本本节节将将介介绍绍一一些些经经典典的的命命题题推推理理规规则则和和推推理理方方法法一一般般说说来来，，根根据据经经验验，，如如果果前前提提是是真真的的，，根根据据提提供供的的推推理理规规则所推出的结论也应该是真的则所推出的结论也应该是真的Ø给给出出一一些些推推理理规规则则，，从从前前提提出出发发推推导导出出结结论论，，这这种种结结论论称为有效结论，这种论证过程称为有效论证。

称为有效结论，这种论证过程称为有效论证Ø在在数数理理逻逻辑辑中中，，重重点点研研究究的的是是推推理理的的有有效效性性，，而而不不是是通通常所说的正确性常所说的正确性 推推理理是是从从前前提提推推出出结结论论的的思思维维过过程程，，前前提提是是指指已已知知的的命命题题公公式式，，结结论论是是从从前前提提出出发发应应用用推推理理规规则则推推出出的的命命题题公公式式，，前前提提可可多多个个，，由由前前提提A A1 1，，A A2 2，，……A Ak k推推出出结结论论B B的的严严格格定定义义如如下：下： 有有效效结结论论（（1 1））：：若若(A(A1 1∧∧A A2 2∧∧……∧∧A Ak k) )B B 为为重重言言式式，，则则称称A A1 1，，A A2 2，，……A Ak k，，推推结结论论B B的的结结论论正正确确，，B B是是A A1 1，，A A2 2，，……A Ak k，，的的逻逻辑辑结结论论或或有有效效结结论论，，称称(A(A1 1∧∧A A2 2∧∧……∧∧A Ak k) )B B 为为由由前前提提A A1 1，，A A2 2，，……A Ak k推结论推结论B B的推理的形式结构。

的推理的形式结构对于任一组赋值，前提和结论的取值有以下四种对于任一组赋值，前提和结论的取值有以下四种情况：情况： ① ① {A1{A1，，A2A2，，……AkAk} }为为0 0，，B B为为0 0 √√ ② ② {A1{A1，，A2A2，，……AkAk} }为为0 0，，B B为为1 1 √√ ③ ③ {A1{A1，，A2A2，，……AkAk} }为为1 1，，B B为为0 0 ×× ④ {A1 ④ {A1，，A2A2，，……AkAk} }为为1 1，，B B为为1 1 √√推理的另一种形式：推理的另一种形式：命题公式命题公式A A1 1，，A A2 2，，……A Ak k推推B B的推理正确当且仅当的推理正确当且仅当 (A(A1 1 ∧∧ A A2 2 ∧∧ … … ∧∧ A Ak k) ) B B 为重言式为重言式于是推理的一般形式可转化为：于是推理的一般形式可转化为： (A(A1 1 ∧∧ A A2 2 ∧∧ … … ∧∧ A Ak k) ) B B推理正确转化为：推理正确转化为： A A1 1 ∧∧ A A2 2 ∧∧ … … ∧∧ A Ak k  B B 证明证明(A(A1 1 ∧∧ A A2 2 ∧∧ … … ∧∧ A Ak k) ) B B的方法有：的方法有： 1 1、、真真值值表表法法；； 2 2、、等等值值演演算算法法；； 3 3、、主析取范式法。

主析取范式法 但但是是，，在在前前提提和和结结论论中中，，若若命命题题变变元元的的数数目目较较大大时时，，使使用用真真值值表表的的方方法法、、等等值值演演算算、、等等值值添添项项和和主主范范式式的的方方法法都都显显得得很很麻麻烦烦此此时时可可以以采采用用推理的方法进行证明推理的方法进行证明 因因此此，，接接下下来来引引入入构构造造论论证证的的方方法法，，这这种种方方法需要一些等值定律和推理规则法需要一些等值定律和推理规则 等值定律推理规则推理规则下面举例说明推理定律和推理规则的应用下面举例说明推理定律和推理规则的应用 判定推理是否有效：判定推理是否有效： 如如果果今今天天是是星星期期六六，，我我们们就就要要到到西西湖湖或或大大清清谷谷去去玩玩如如果果西西湖湖游游人人太太多多，，我我们们就就不不到到西西湖湖去去玩玩今今天天是是星星期期六六西西湖湖游游人人太太多所以我们到大清谷玩所以我们到大清谷玩解解：首先将命题符号化：：首先将命题符号化： p: p: 今天是星期六今天是星期六 q: q: 我们到西湖去玩。

我们到西湖去玩 r: r: 我们到大清谷去玩我们到大清谷去玩 s: s: 西湖游人多西湖游人多前提前提：：p p (q (q ∨∨ r r) , s) , s  ¬ ¬ q , p , sq , p , s结论结论：：r r证明证明：： ① ① s s  ¬ ¬ q q 前提引入前提引入 ② ② s s 前提引入前提引入 ③ ③ ¬ ¬ q ① ② q ① ②假言推理假言推理 ④ ④ p p 前提引入前提引入 ⑤ ⑤ p p (q (q ∨∨ r ) r ) 前提引入前提引入 ⑥ ⑥ q q ∨∨ r ④⑤ r ④⑤假言推理假言推理 ⑦ ⑦ r ③⑥r ③⑥析取三段论析取三段论以上两个例子主要是直接证明的方法，下面讨论以上两个例子主要是直接证明的方法，下面讨论两种间接证明方法。

两种间接证明方法一）附加前提法（（一）附加前提法（CPCP规则法）规则法）欲证明欲证明(A1 (A1 ∧∧ A2 A2 ∧∧ … … ∧∧ AkAk ) ) (A (A  B ) B ) ，只需证明，只需证明 　　 (A1 (A1 ∧∧ A2 A2 ∧∧ … … ∧∧ AkAk ∧∧ A ) A )  B B 即可，因为即可，因为: : (A1 (A1 ∧∧ A2 A2 ∧∧ … … ∧∧ AkAk ) ) (A (A  B ) B )   (A1 (A1 ∧∧ A2 A2 ∧∧ … … ∧∧ AkAk ) ∨) ∨ (A (A  B ) B )   (A1 (A1 ∧∧ A2 A2 ∧∧ … … ∧∧ AkAk ) ∨) ∨ ( (  A ∨ B ) A ∨ B ) ( ( A1 A1 ∨∨   A2 A2 ∨∨ … … ∨∨   AkAk ) ∨) ∨ ( (  A ∨ B ) A ∨ B )  A1 A1 ∨∨   A2 A2 ∨∨ … … ∨∨   AkAk ∨ ∨   A ∨ B A ∨ B ( ( A1 A1 ∨∨   A2 A2 ∨∨ … … ∨∨   AkAk ∨ ∨   A )∨ B A )∨ B  (A1 (A1 ∧∧ A2 A2 ∧∧ … … ∧∧ AkAk ∧ A) ∨∧ A) ∨ B B  (A1 (A1 ∧∧ A2 A2 ∧∧ … … ∧∧ AkAk ∧ A) ∧ A)  B B 注注: A : A B B   A∨B A∨B  (A(A∧B) ∧B)   A A∨∨  B B 例例：用附加前提证明法证明下面推理：用附加前提证明法证明下面推理前提前提：：p p (q (q  r r) , ) ,   s∨s∨p p , q , q结论结论：：s s r r证明：证明： ① ①   s∨s∨p p 前提引入前提引入 ② ② s s 附加附加前提引入前提引入 ③ ③ p ① ②p ① ②析取三段论析取三段论 ④ ④ p p (q (q  r r) ) 前提引入前提引入 ⑤ ⑤ q q  r ③④ r ③④ 假言推理假言推理 ⑥ ⑥ q q 前提引入前提引入 ⑦ ⑦ r ⑤⑥r ⑤⑥假言推理假言推理 由附加前提证明法知由附加前提证明法知 (A(A1 1 ∧∧ A A2 2 ∧∧ … ∧∧ A Ak k ) ) (A (A  B ) B ) 可归结为证明可归结为证明 (A(A1 1 ∧∧ A A2 2 ∧∧ … ∧∧ A Ak k ∧∧ A ) A )  B B例例 如果小张和小王去看电影，则小李也去看电影；小赵如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。

所以，当小赵不去看电影或小张去看电影；小王去看电影所以，当小赵去看电影时小李也去判断上述推理是否有效？去看电影时小李也去判断上述推理是否有效？（二）归谬法（反证法）（二）归谬法（反证法） 欲欲证证明明(A(A1 1 ∧∧ A A2 2 ∧∧ … … ∧∧ A Ak k ) )  B B ，，只只需需将将  B B作作为为前前提能推出矛盾来即可因为：提能推出矛盾来即可因为：(A(A1 1 ∧∧ A A2 2 ∧∧ … … ∧∧ A Ak k ) )  B B   (A(A1 1 ∧∧ A A2 2 ∧∧ … … ∧∧ A Ak k ) ) ∨ B ∨ B   (A(A1 1 ∧∧ A A2 2 ∧∧ … … ∧∧ A Ak k ∧∧   B B））若若 (A(A1 1 ∧∧ A A2 2 ∧∧ … … ∧∧ A Ak k ∧∧   B B））为矛盾式，则为矛盾式，则 (A(A1 1 ∧∧ A A2 2 ∧∧ … … ∧∧ A Ak k ) ) B B 为重言式为重言式 ，即，即 (A(A1 1 ∧∧ A A2 2 ∧∧ … … ∧∧ A Ak k ) => B) => B例例: :构造下面的推理证明构造下面的推理证明前提：前提：p p    q , q ,   r r ∨q , r ∧ ∨q , r ∧   s s结论：结论：   p p证明：证明： ① ① p p 结论否定结论否定引入引入 ② ② p p    q q 前提引入前提引入 ③ ③   q q ① ②① ②假言推理假言推理 ④ ④   r r ∨q ∨q 前提引入前提引入 ⑤ ⑤   r ③④r ③④析取三段论析取三段论 ⑥ ⑥ r ∧ r ∧   s s 前提引入前提引入 ⑦ ⑦ r ⑥r ⑥化简规则化简规则 ⑧ ⑧ r ∧ r ∧   r ⑤⑦ r ⑤⑦合取合取         数理逻辑是用数学方法研究逻辑的学科。

它的核心内容为数理逻辑是用数学方法研究逻辑的学科它的核心内容为命题逻辑和谓词逻辑本章是命题逻辑的基础知识，主要涉及命题逻辑和谓词逻辑本章是命题逻辑的基础知识，主要涉及命题逻辑的基本结构以及自然语言的形式化方法命题逻辑的基本结构以及自然语言的形式化方法本章中通过命题概念引出简单命题，再通过本章中通过命题概念引出简单命题，再通过5 5个常用的命题联结个常用的命题联结词构成新的复合命题，从而构成命题逻辑的理论基础词构成新的复合命题，从而构成命题逻辑的理论基础 由由5 5个常用的命题联结词所定义的运算是数理逻辑中最基本个常用的命题联结词所定义的运算是数理逻辑中最基本最常用的逻辑运算本章详细介绍了这最常用的逻辑运算本章详细介绍了这5 5个命题联结词的定义与个命题联结词的定义与真值表，并举例说明了它们的使用方法其中否定词属一元联真值表，并举例说明了它们的使用方法其中否定词属一元联结词，其它几个均为二元联结词联结词是由已有命题定义新结词，其它几个均为二元联结词联结词是由已有命题定义新命题的基本方法，是命题逻辑中最基本的内容之一命题的基本方法，是命题逻辑中最基本的内容之一本章小结本章小结        命题逻辑中的许多问题都可以化为计算复合命题的真假值问命题逻辑中的许多问题都可以化为计算复合命题的真假值问题，题，因而真值表方法是命题逻辑中一个极为有力的工具因而真值表方法是命题逻辑中一个极为有力的工具。

由命题由命题公式列写真值表以及下一章将介绍的由真值表列写命题公式，都公式列写真值表以及下一章将介绍的由真值表列写命题公式，都是学习命题逻辑需要熟练掌握的基本功是学习命题逻辑需要熟练掌握的基本功　　联结词　　联结词∧∧、、∨∨、、 同构成计算机的与门、或门和非门电路是相同构成计算机的与门、或门和非门电路是相对应的下一章中还要讲到的实际中常用的与非门和或非门电路对应的下一章中还要讲到的实际中常用的与非门和或非门电路则对应着与非和或非联结词从而命题逻辑是计算机硬件电路的则对应着与非和或非联结词从而命题逻辑是计算机硬件电路的表示、分析和设计的重要工具也正是数理逻辑应用于实际特别表示、分析和设计的重要工具也正是数理逻辑应用于实际特别是应用于计算机学科推动了数理逻辑的发展是应用于计算机学科推动了数理逻辑的发展 　　自然语句的形式化是研究命题逻辑的一个基本出发点和归宿　　自然语句的形式化是研究命题逻辑的一个基本出发点和归宿本章在引入命题联接词后，对自然语句的形式化方法进行了介绍，本章在引入命题联接词后，对自然语句的形式化方法进行了介绍，不论是简单自然语句还是较复杂的自然语句，都需要注意自然语不论是简单自然语句还是较复杂的自然语句，都需要注意自然语言与命题逻辑符号表示的特点与差别。

言与命题逻辑符号表示的特点与差别 第第2 2章章 谓词逻辑谓词逻辑Ø在命题逻辑中我们主要讨论了命题和命题推理在命在命题逻辑中我们主要讨论了命题和命题推理在命题逻辑中，原子命题是不可再分解的题逻辑中，原子命题是不可再分解的Ø但是，命题之间还可能有些共同的性质，可以作进一但是，命题之间还可能有些共同的性质，可以作进一步的描述，同时命题逻辑的推理结构还有很大的局限步的描述，同时命题逻辑的推理结构还有很大的局限性，有些很简单的论断也不能用命题逻辑进行推证性，有些很简单的论断也不能用命题逻辑进行推证Ø例如：例如： ““所有的人都是要死的所有的人都是要死的 苏格拉底是人苏格拉底是人 所以苏格拉底是要死的所以苏格拉底是要死的这是著名的这是著名的苏格拉底三段论苏格拉底三段论，它用命题推理无法完成这，它用命题推理无法完成这个简单推证个简单推证 Ø用命题逻辑解释逻辑学中著名的三段论用命题逻辑解释逻辑学中著名的三段论. . Ø设设p p：：所有的人都是要死的所有的人都是要死的；；q:q:苏格拉底是人苏格拉底是人；；r r：：苏苏格拉底是要死格拉底是要死表示成复合命题有。

表示成复合命题有 p p q qr rØ由于上式不是重言式，所以不能由它判断推理的正确由于上式不是重言式，所以不能由它判断推理的正确性究其原因，在于命题逻辑没有研究命题内部的逻性究其原因，在于命题逻辑没有研究命题内部的逻辑结构Ø事实上，原子命题实际上还可以作进一步地分解，分事实上，原子命题实际上还可以作进一步地分解，分解出个体词，谓词和量词，以达到表达出个体与总体解出个体词，谓词和量词，以达到表达出个体与总体的内在联系和数量关系，这就是一阶逻辑所研究的内的内在联系和数量关系，这就是一阶逻辑所研究的内容，本书称为谓词逻辑容，本书称为谓词逻辑Ø谓词逻辑在人工智能领域的知识表示、知识推理和机谓词逻辑在人工智能领域的知识表示、知识推理和机器证明等方面有重要的意义器证明等方面有重要的意义 在在谓谓词词逻逻辑辑中中，，简简单单命命题题分分解解成成个个体体词词和和谓谓词词两两部部分 个个体体词词是是可可以以独独立立存存在在的的客客体体，，它它可可以以是是具具体体事事物物或或抽抽象象的的概概念念，，如如小小张张，，房房子子，，杭杭州州，，大大米米，，思思想想，，实数实数2 2等等。

等等 谓谓词词是是用用来来刻刻划划个个体体词词的的性性质质或或事事物物之之间间的的关关系系的的词        我我们们知知道道，，命命题题是是具具有有真真假假意意义义的的陈陈述述句句从从语语法法上上分分析析，，一一个个陈陈述述句句由由主主语语和和谓谓语语两两部部分分组成我我们们可可以以这这样样做做：：为为揭揭示示命命题题内内部部结结构构及及其其不不同同命命题题的的内内部部结结构构关关系系，，就就按按照照这这两两部部分分对对命命题题进进行行分分析析，，并并且且把把主主语语称称为为个个体体或或客客体体，，把把谓谓语语称称为谓词为谓词１１. .个体词和谓词个体词和谓词Ø在原子命题中，所描述的对象称为在原子命题中，所描述的对象称为个体个体；；Ø用以描述个体的性质或个体间关系的部分，称为用以描述个体的性质或个体间关系的部分，称为谓词谓词Ø个体：个体：是指可以独立存在的事物，它可以是具体的，是指可以独立存在的事物，它可以是具体的，也可以是抽象的，如张明，计算机，精神等表示也可以是抽象的，如张明，计算机，精神等表示特定的个体，称为个体常元，以特定的个体，称为个体常元，以a a，，b b，，c…c…或带下标或带下标的的a ai i，，b bi i，，c ci i……表示；表示不确定的个体，称为个体表示；表示不确定的个体，称为个体变元，以变元，以x x，，y y，，z…z…或或x xi i，，y yi i，，z zi i……表示。

表示一阶逻辑命题符号化的一阶逻辑命题符号化的基本概念：基本概念：ü个体词个体词：可以独立存在的具体的或抽象的客体：可以独立存在的具体的或抽象的客体ü个体常项个体常项：具体的或特定：具体的或特定, ,一般用一般用a,b,ca,b,c,…,…表示表示ü个个体体变变项项：：抽抽象象的的或或泛泛指指的的，，一一般般用用x,y,zx,y,z,…,…表示表示ü个体域个体域：个体变项的取值范围：：个体变项的取值范围：ü全总个体域全总个体域: : 宇宙间的一切事物组成个体域宇宙间的一切事物组成个体域Ø 谓词谓词: : 表示个体词性质或相互之间关系的词表示个体词性质或相互之间关系的词Ø      谓词常项谓词常项：：F: …F: …是人，是人，F(aF(a) )：：a a是人是人Ø      谓谓词词变变项项：：F: F: ……具具有有性性质质F F，，F(xF(x) )：：x x具具有有性性质质F FØ    一元谓词一元谓词: : 表示事物的性质表示事物的性质Ø 多多元元谓谓词词( (n n元元谓谓词词, , n n 2): 2): 表表示示事事物物之之间间的的关关系系，，L(x,yL(x,y) )：：x x与与y y有关系有关系L L，，L(x,yL(x,y) )：：x x y y，，……Ø 0 0元谓词元谓词: : 不含个体变项的谓词不含个体变项的谓词, , 即命题常项或命即命题常项或命 题变项题变项 谓词符号化:例例: : (1)    ln5(1)    ln5是无理数；是无理数；      (2)    (2)    牛启飞比马腾云高牛启飞比马腾云高4cm4cm；； (3) (3) 杭州位于北京和广州之间。

杭州位于北京和广州之间 这是三个简单命题这是三个简单命题, , 其中其中ln5, ln5, 牛启飞，马腾云，牛启飞，马腾云，杭州，北京杭州，北京, ,广州等都是个体词广州等都是个体词, ,而而““…………是无理是无理数数””,“……,“……比比……高高4cm”4cm”，，““…………位于位于…………和和…………之间之间””等都是谓词等都是谓词         对于给定的命题，当用表示其个体的小写字母和表示对于给定的命题，当用表示其个体的小写字母和表示其谓词的大写字母来表示时，规定把小写字母写在大写字其谓词的大写字母来表示时，规定把小写字母写在大写字母右侧的圆括号母右侧的圆括号( )( )内例如例如，在命题，在命题“张明是位大学生张明是位大学生”中，中，“张明张明”是个体，是个体，“是位大学生是位大学生”是谓词，它刻划了是谓词，它刻划了“张明张明”的性质 设设 P P：：是位大学生是位大学生 a a：：张明张明则则“张明是位大学生张明是位大学生”可表示为可表示为P(aP(a) )，，或者写成或者写成P(aP(a) )：：张明是位大学生。

张明是位大学生 又如，在命题又如，在命题“杭州位于北京和广州之间杭州位于北京和广州之间”中，杭州、中，杭州、北京和广州是三个个体，北京和广州是三个个体， 而而“……位于位于……和和……之间之间”是是谓词，它刻划了杭州、北京和广州之间的关系谓词，它刻划了杭州、北京和广州之间的关系 设设 P P：：……位于位于……和和……之间，之间， a a：：杭州，杭州，b b：：北京，北京，c c：：广州，广州， 则则P(aP(a，，b b，，c)c)：：杭州位于北京和广州之间杭州位于北京和广州之间注意注意：命题的谓词形式中的个体出现的次序影响命题的：命题的谓词形式中的个体出现的次序影响命题的真值，不是随意变动，否则真值会有变化如上述例子真值，不是随意变动，否则真值会有变化如上述例子中，中，P(b,a,cP(b,a,c) )是假如如果果个个体体常常项项a a和和个个体体变变项项x x都都具具有有性性质质F F，，记记作作F(aF(a) )或或F(xF(x););个个体体常常项项a a与与b b或或个个体体变变项项x x与与y y具具有有关关系系L,L,记记作作L(a,bL(a,b) )或或L(x,yL(x,y) )。

用用F(aF(a) )表表示示a a是是无无理理数数，，其其中中a a表表示示ln5ln5，，F F表表示示的的是是“……是无理数是无理数”则F(aF(a) )表示表示ln5ln5是无理数是无理数当当F F的的含含义义不不变变时时，，则则F(xF(x) )表表示示x x是是无无理理数数，，x x是是个个体体变变项项，，F F谓谓词词常常项项，，F(xF(x) )不不是是命命题题，，而而是是命命题题变变项项，，F(aF(a) )是是命命题题用用M(x,y,zM(x,y,z) )表示表示“z=z=x x×y y””，，M(x,y,zM(x,y,z) )不是命题不是命题 a a表表示示3 3，，b b表表示示5 5，，c c表表示示1515，，M(a,b,cM(a,b,c) )表表示示“1515＝＝3 3×5 5”M(a,b,cM(a,b,c) )是是命命题题，，真真值值为为1 1，，若若c=12c=12，，那那么么M(a,b,cM(a,b,c) )是命题，真值为是命题，真值为0 0一般地，用一般地，用 P(xP(x1 1 , x, x2 2 , …, , …, x xn n) ) 表表示示含含有有n n个个命命题题变变项项的的n n元元谓谓词词，，也也可可以以看看作作是是以以个个体体域域为为定定义义域域，，以以{0{0，，1}1}为为值值域域的的n n元元函函数数或或关系。

关系 不带任何个体变项的谓词称为不带任何个体变项的谓词称为0 0元谓词元谓词特别提醒：特别提醒：n n元谓词不是命题，只有其中的个体变元元谓词不是命题，只有其中的个体变元用特定个体或个体常元替代时，才能成为一个命题用特定个体或个体常元替代时，才能成为一个命题但个体变元在哪些论域取特定的值，对命题的真值极但个体变元在哪些论域取特定的值，对命题的真值极有影响例如例如：令：令S(xS(x) )：：x x是大学生若是大学生若x x的论域为中医药大学的论域为中医药大学信息技术学院的全体同学，则信息技术学院的全体同学，则S(xS(x) )是真的；若是真的；若x x的论的论域是某中学的全体学生，则域是某中学的全体学生，则S(xS(x) )是假的；若是假的；若x x的论域的论域是某剧场中的观众，且观众中有大学生也有非大学生是某剧场中的观众，且观众中有大学生也有非大学生的其它观众，则的其它观众，则S(xS(x) )是真值是不确定的是真值是不确定的       注注意意，，单单独独的的个个体体词词和和谓谓词词不不能能构构成成命命题题，，将将个个体体词词和和谓谓词分开不是命题词分开不是命题。

例例 将下列命题符号化：将下列命题符号化：(1) (1) 丘华和李兵都是学生；丘华和李兵都是学生；(2) 2(2) 2既是偶数又是素数；既是偶数又是素数；(3) (3) 如如果果张张华华比比黎黎明明高高，，黎黎明明比比王王宏宏高高，，则则张张华华比比王王 宏高解解 (1) (1) 设个体域是人的集合设个体域是人的集合 P(xP(x) )：：:x:x是学生a a：：丘华丘华b b：：黎兵黎兵该命题符号化为该命题符号化为P(a)P(a) P(bP(b) )(2) (2) 设个体域为正整数集合设个体域为正整数集合N N＋＋F(xF(x) )：：x x是偶数，是偶数，G(xG(x) )：：x x是素数是素数a a：：2 2该命题符号化为该命题符号化为F(a)F(a) G(aG(a) )(3)(3) 设个体域是人的集合设个体域是人的集合 L(x,yL(x,y) )：：x x比比y y高 a a：：张华张华 b b：：黎明黎明 c c：：王宏王宏该命题符号化为该命题符号化为L(a,b)L(a,b) L L(b,c)(b,c)L L(a,c(a,c) )例例 令令G(xG(x，，y)y)：： “x x高于高于y y”，，于是，于是，G(xG(x，，y)y)是一个二元谓词。

将是一个二元谓词将x x代以个体代以个体 “张三张三”，，y y代代以个体以个体 “李四李四”，则，则G(G(张三，李四张三，李四) )就是命题：就是命题： “张三高于李四张三高于李四”随便将x x，，y y代以确定的个体，代以确定的个体，由由G(xG(x，，y)y)都能得到一个命题都能得到一个命题 但是，但是，G(xG(x，，y)y)不是命题，而是一个命题函不是命题，而是一个命题函数即谓词数即谓词例例 用用0 0元谓词将命题符号化元谓词将命题符号化 要要求求：：先先将将它它们们在在命命题题逻逻辑辑中中符符号号化化，，再再在在一一阶逻辑中符号化阶逻辑中符号化 墨西哥位于南美洲墨西哥位于南美洲 在命题逻辑中在命题逻辑中, , 设设 p: p: 墨西哥位于南美洲墨西哥位于南美洲 符号化为符号化为 p, p, 这是真命题这是真命题 在在一一阶阶逻逻辑辑中中, , 设设a a：：墨墨西西哥哥，，F(xF(x) )：：x x位位于于南南美洲美洲 符号化为符号化为F(aF(a) )量词量词 利用利用n n元谓词和它的论域概念，有时还是不能用元谓词和它的论域概念，有时还是不能用符号来很准确地表达某些命题。

符号来很准确地表达某些命题例如例如S(xS(x) )表示表示x x是大学生，而是大学生，而x x的个体域为某单位的职的个体域为某单位的职工，那么工，那么S(xS(x) )可表示某单位职工都是大学生，也可表可表示某单位职工都是大学生，也可表示某单位有一些职工是大学生，为了避免理解上的歧示某单位有一些职工是大学生，为了避免理解上的歧义，需要引入用以刻划义，需要引入用以刻划“所有的所有的”、、“存在一些存在一些”等等表示不同数量的词，即量词，其定义如下：表示不同数量的词，即量词，其定义如下：量词量词: :用来表示个体常项或变项之间数量关系的词用来表示个体常项或变项之间数量关系的词 量词分为两种：量词分为两种：全全称称量量词词：：““一一切切””、、““所所有有””、、““凡凡””、、““每每一一个个””、、““任任意意””等等意意，，符符号号记记作作 如如：： x x 表表示示个个体体域内所有的域内所有的x x x x称为全称量词，称称为全称量词，称x x为指导变元为指导变元存存在在量量词词：：““有有一一个个””、、““有有的的””、、““存存在在””、、““至至少少有有一一个个””等等，，符符号号记记作作 。

如如: : y y表表示示个个体体域域内内有的有的y y x x称为存在量词，称为存在量词，x x称为指导变元称为指导变元例例 将下列命题符号化将下列命题符号化(1)(1) 每个母亲都爱自己的孩子；每个母亲都爱自己的孩子；(2) (2) 所有的人都呼吸；所有的人都呼吸；(3) (3) 有某些实数是有理数有某些实数是有理数解解 (1) (1) 设个体域是所有母亲的集合设个体域是所有母亲的集合 M(xM(x) )：：x x表示爱自己的孩子；表示爱自己的孩子； 该命题符号化为（该命题符号化为（ x x））M(xM(x) )(2) (2) 设个体域为人的集合设个体域为人的集合H(xH(x) )：：x x表示要呼吸表示要呼吸该命题符号化为（该命题符号化为（ x x））H(xH(x) )或设个体域全总个体域，或设个体域全总个体域，M(xM(x) )：：x x是人H(xH(x) )：：x x表示要呼吸表示要呼吸该命题符号化为（该命题符号化为（ x x））( (M(x)M(x)H(xH(x))))(3) (3) 设个体域为数的集合。

设个体域为数的集合R(xR(x) )：：x x表示实数表示实数Q(xQ(x) )：：x x表示有理数表示有理数该命题符号化（该命题符号化（ x x））( (R(x)R(x) Q(xQ(x))))例例 用谓词对下列命题符号化用谓词对下列命题符号化1 1）凡是人都呼吸凡是人都呼吸2 2）有的人是左撇子有的人是左撇子解解 当个体域为人类集合时：当个体域为人类集合时： 令令F(xF(x): x): x呼吸G(xG(x): x): x是左撇子则是左撇子则 （（1 1）（）（ x x））F(xF(x) (2) ) (2) （（ x x））G(xG(x) ) 当个体域为全总个体域时：当个体域为全总个体域时：令令F(xF(x): x): x呼吸G(xG(x): x): x是左撇子；是左撇子；M(xM(x): x): x是人则则 (1) ((1) ( x)(M(x)x)(M(x)F(xF(x)) )) (2) ( (2) ( x)(M(xx)(M(x)∧)∧ G(xG(x))))说明：说明：（（1 1））在在不不同同的的个个体体域域，，同同一一命命题题的的符符号号化化形形式式可可能能相同也可能不同。

相同也可能不同2 2））在在不不同同的的个个体体域域，，同同一一命命题题的的真真值值可可能能相相同同也也可能不同可能不同3 3）约定以后如不指定个体域，默认为全总个体域约定以后如不指定个体域，默认为全总个体域例：用谓词将下列命题符号化例：用谓词将下列命题符号化1 1）所有的人都长头发所有的人都长头发2 2）有的人吸烟有的人吸烟3 3）没有人登上过木星没有人登上过木星4 4）清华大学的学生未必都是高素质的清华大学的学生未必都是高素质的解：令　解：令　M(xM(x): x): x是人1 1）） 令令F(xF(x): x): x长头发则符号化为：长头发则符号化为：　　　　　　 （（ x x））( (M(x)M(x)F(xF(x))))　　　　　　 （（2 2）） 令令S(xS(x): x): x吸烟则符号化为：吸烟则符号化为：　　　　　　 （（ x x））( (M(x)∧S(xM(x)∧S(x))))　　　　　　（（3 3）） 令令D(xD(x): x): x登上过木星则符号化为：登上过木星则符号化为：　　　　　　 ¬ ¬（（ x x））( (M(x)∧D(xM(x)∧D(x))))　　　　　　（（4 4）） 令令Q(x):xQ(x):x是清华大学的学生。

是清华大学的学生 H(x):xH(x):x是高素质的则符号化为：是高素质的则符号化为： 　　 ¬ ¬（（ x x））( (Q(x)Q(x)H(xH(x)) )) 例例 在一阶逻辑中将下列命题符号化在一阶逻辑中将下列命题符号化1 1）凡正数都大于零凡正数都大于零2 2）存在小于）存在小于2 2的素数3 3）没有不能表示成分数的有理数没有不能表示成分数的有理数4 4）并不是所有参加考试的人都能取得好成绩并不是所有参加考试的人都能取得好成绩解：（解：（1 1）） 令令F(xF(x): x): x是正数M(x):xM(x):x大于零 则符号化为：则符号化为： ( ( x)(F(x)x)(F(x)M(xM(x))))　　　　　　另外，全称量词和存在量词不仅可以单独出现，另外，全称量词和存在量词不仅可以单独出现，而且还可以以组合形式出现下面我们给出几而且还可以以组合形式出现下面我们给出几个用个用二元谓词二元谓词进行命题符号化的例子进行命题符号化的例子谓词公式谓词公式 合式公式合式公式/ /谓词公式谓词公式/ /公式公式定义如下：定义如下：（（1 1）原子公式是合式公式。

原子公式是合式公式2 2）若）若A A 是合式公式，则是合式公式，则( (¬ ¬A)A)也是合式公式也是合式公式3 3））若若A A，，B B是是合合式式公公式式, , 则则(A∧B)(A∧B)，，(A∨B)(A∨B)，，(A (A  B)B)，，(A (A  B) B)也是合式公式也是合式公式4 4））若若A A是是合合式式公公式式，，则则( ( x)x)A A , , ( ( x)x)A A ，，也也是是合合式式公式5) (5) 只只 有有 有有 限限 次次 应应 用用 (1)-(4)(1)-(4)构构 成成 的的 符符 号号 串串 才才 是是 合式公式合式公式•与命题公式一样，约定最外层的括号可以省与命题公式一样，约定最外层的括号可以省掉但是，量词后面有括号，则量词后面的掉但是，量词后面有括号，则量词后面的括号不能省略括号不能省略•下面讨论如何将一个用自然语言描述的命下面讨论如何将一个用自然语言描述的命题符号化成谓词公式，这在谓词逻辑中是题符号化成谓词公式，这在谓词逻辑中是非常重要的，它是进行推理的基础非常重要的，它是进行推理的基础。

辖域、约束变元与自由变元辖域、约束变元与自由变元 Ø在在公公式式（（ x x））A A和和（（ x x））A A中中，，称称x x为为指指导变元，导变元，A A为相应量词的为相应量词的辖域辖域Ø在在（（ x x）） 和和（（ x x））的的辖辖域域中中，，x x的的所所有有出出现现都都称称为为约约束束出出现现，，这这个个变变元元成成为为约约束束变变元元；；A A中中不不是是约约束束出出现现的的其其它它变变项项均均称为是称为是自由出现自由出现，这个变元成为，这个变元成为自由变元自由变元例例 指指 出出 下下 列列 公公 式式 中中 指指 导导 变变 项项 、、 量量 词词 的的 辖辖 域域 、、 个个 体体 变项的自由出项和约束出现变项的自由出项和约束出现1 1）） （（ x x））( (F(xF(x) ) G(x,yG(x,y)))) x x是是指指导导变变元元，，量量词词 的的辖辖域域( (F(xF(x) ) G(x,yG(x,y)), )), 在在辖辖域内，域内，x x是约束出现两次，是约束出现两次，y y是自由出现一次。

是自由出现一次2 2）（）（ x x）） F(x,yF(x,y) )  （（  y y）） G(x,yG(x,y) ) x x是是指指导导变变元元，，量量词词 的的辖辖域域 F(x,yF(x,y), ), 在在辖辖域域内内，，x x是是约约束束出出现现一一次次，，y y是是自自由由出出现现一一次次; ;同同时时，，y y也也是是指指导导变变元元，，量量词词  的的辖辖域域G(x,yG(x,y), ), 在在辖辖域域内内，，y y是是约约束束出出现现一次，一次，x x是自由出现一次是自由出现一次 3 3）） （（  x x）） （（   y y）） ( (F(x,yF(x,y) ) ∧ ∧ G(y,zG(y,z)) )) ∨ ∨ （（ x x）） H(x,y,zH(x,y,z) ) x x、、y y是指导变元是指导变元, ,对应量词对应量词 、、 的辖域为的辖域为( (F(x,yF(x,y)∧)∧ G(y,zG(y,z)),)),其其中中x x是是约约束束出出现现一一次次,y,y是是约约束束出出现现两两次次,z,z是是自自由由出出现现一一次次; ;后后一一个个x x也也是是指指导导变变元元, ,量量词词  的的辖辖域域为为H(x,y,zH(x,y,z),),其其中中x x是是约约束束出出现现一一次次,y,y、、z z是是自自由由出出现现一一次次. .约束变元的换名与自由变元的替换约束变元的换名与自由变元的替换•在一个公式中，某个变元可以既是约束的，又在一个公式中，某个变元可以既是约束的，又是自由的。

为了避免由于变元的约束与自由同是自由的为了避免由于变元的约束与自由同时出现，引起概念上的混乱，可以对约束变元时出现，引起概念上的混乱，可以对约束变元进行换名，原因是一个公式的约束变元和自由进行换名，原因是一个公式的约束变元和自由变元所使用的名称符号是无关紧要的变元所使用的名称符号是无关紧要的•对谓词公式中的约束变元更改名称符号，称为对谓词公式中的约束变元更改名称符号，称为约束变元约束变元换名换名•约束变元换名使得一个变元在一个公式中只呈约束变元换名使得一个变元在一个公式中只呈现一种形式，即呈自由出现或呈约束出现现一种形式，即呈自由出现或呈约束出现•约束变元换名的规则为：约束变元换名的规则为： (1)(1)换名时，更改的变元名称范围是量词中换名时，更改的变元名称范围是量词中的指导变元，以及该量词辖域中该变元的所有的指导变元，以及该量词辖域中该变元的所有出现公式其余部分不便公式其余部分不便 (2)(2)换名时一定要更改为辖域中没有出现的换名时一定要更改为辖域中没有出现的变元名称变元名称•注意：注意：将量词辖域中某个约束出现的个体变元将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。

个体变元，其余不变•例例 （（ x x）） F(x)∧G(x,yF(x)∧G(x,y) ) （（ z z））F(z)∧G(x,yF(z)∧G(x,y) ) ( (换名规则换名规则, ,将约束出现的将约束出现的x x改成改成z)z) 对公式中得自由变元也可以更改名称符号，这对公式中得自由变元也可以更改名称符号，这种更改叫做种更改叫做替换替换自由变元的替换规则是：自由变元的替换规则是： (1)(1)对于公式中得自由变元，可以做替换，对于公式中得自由变元，可以做替换，应该注意需对公式中出现该自由变元得每一处应该注意需对公式中出现该自由变元得每一处都进行替换都进行替换 (2)(2)用以替换的变元与原公式中所有变元用以替换的变元与原公式中所有变元得名称不能相同得名称不能相同 对某自由出现的个体变元可用个体常元或对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元用与原子公式中所有个体变元不同的个体变元去代入，且处处代入去代入，且处处代入 例例 （（ x x））F(x)∧G(x,yF(x)∧G(x,y) ) （（ x x））F(x)∧G(z,yF(x)∧G(z,y) ) ( (代替规则代替规则, ,将自由出现的将自由出现的x x改成改成z)z)谓词公式的赋值与分类谓词公式的赋值与分类•在谓词公式中常包含命题变元和客体变在谓词公式中常包含命题变元和客体变元，当客体变元由确定的客体取代，命元，当客体变元由确定的客体取代，命题变元用确定的命题所取代或指派一真题变元用确定的命题所取代或指派一真值时，一个谓词公式就有确定的真值值时，一个谓词公式就有确定的真值T T和和F F。

下面我们讨论谓词公式的赋值下面我们讨论谓词公式的赋值 谓词公式的分类谓词公式的分类 设设A A为一谓词公式，为一谓词公式，•若若A A在任何赋值下均为真，则称在任何赋值下均为真，则称A A为为永真式永真式•若若A A在任何赋值下均为假则称在任何赋值下均为假则称A A为为矛盾式矛盾式•若至少存在一个赋值使若至少存在一个赋值使A A为真则称为真则称A A是是可满可满足式足式谓词公式的等值演算谓词公式的等值演算 已经得证的重要等值式：已经得证的重要等值式： 全称量词对合取运算满足分配律，存在量词对析取满足全称量词对合取运算满足分配律，存在量词对析取满足分配律但是全称量词对析取运算是否满足分配律？存分配律但是全称量词对析取运算是否满足分配律？存在量词对合取运算是否满足分配律？答案是否定的在量词对合取运算是否满足分配律？答案是否定的但但是是：：谓词公式的前束范式谓词公式的前束范式定理定理 任何一个谓词公式都可以转化为与之等价的前束任何一个谓词公式都可以转化为与之等价的前束范式 谓词公式化为前束范式主要通过谓词公式化为前束范式主要通过2.42.4节的等价公节的等价公式，换名规则，替换规则和置换原理等。

式，换名规则，替换规则和置换原理等注意注意：一个谓词公式的前束范式不一定惟一一个谓词公式的前束范式不一定惟一谓词演算的推理理论谓词演算的推理理论1.1.推理定律的来源推理定律的来源 第一组：命题推理定律的代换实例第一组：命题推理定律的代换实例第二组：基本等价公式生成的推理定律第二组：基本等价公式生成的推理定律 第三组：几个非等价的重要推理定律第三组：几个非等价的重要推理定律 第四组：消、添量词定律第四组：消、添量词定律总的来说，我们常见的推理规则如下：总的来说，我们常见的推理规则如下：Ø前提引入规则；（相当于已知条件）前提引入规则；（相当于已知条件）Ø结论引入规则；（相当于已证的结论）结论引入规则；（相当于已证的结论）Ø置换规则；置换规则； （相当于等价公式）（相当于等价公式）Ø假言推理规则；假言推理规则；Ø附加规则；附加规则；Ø化简规则；化简规则；Ø拒取式规则；拒取式规则；Ø假言三段论规则；假言三段论规则；Ø析取三段论规则；析取三段论规则；Ø构造性二难规则；构造性二难规则；Ø合取引入规则；合取引入规则；ØUIUI规则规则ØUGUG规则；规则；ØEIEI规则；规则；ØEGEG规则。

规则 本书主要讨论单个量词的谓词推理，在使用本书主要讨论单个量词的谓词推理，在使用UIUI规则，规则，UGUG规则，规则，EIEI规则和规则和EGEG规则时，所用的公式都必须是前束范式规则时，所用的公式都必须是前束范式2. 2. 推理的实例推理的实例例：例：构造下列推理的证明构造下列推理的证明 凡是人都是凡是人都是 要死的 苏格拉底是人苏格拉底是人 苏格拉底是要死的苏格拉底是要死的设：设：M(x):xM(x):x是人；是人；D(xD(x): x ): x 是要死的；是要死的；a:a:苏格拉底则：苏格拉底则： 前提：前提： （（ x x））( (M(x)M(x)D(x))D(x))，，M(aM(a））. . 结论：结论： D(aD(a) ) . .证明：证明：① ① （（ x x））( (M(x)M(x)D(xD(x)) )) 前提引入前提引入 ② ② M(a)M(a)D(aD(a) ① UI) ① UI规则规则 ③ ③ M(aM(a) ) 前提引入前提引入 ④ ④ D(aD(a) ) ②③ ②③ 假言推理假言推理例例：构造下列推理的证明：构造下列推理的证明前提：（前提：（ x x））( (F(xF(x) ∨ ) ∨ G(xG(x))))，， ¬ ¬ （（ x x）） G(xG(x).).结论：结论： （（ x x）） F(xF(x) ) 。

证明：证明：① ① ¬ ¬ （（ x x）） G(xG(x) ) 前提引入前提引入 ② ② （（ x x）） ¬ ¬ G(xG(x) ① ) ① 置换规则置换规则 ③ ③ ¬ ¬ G(aG(a) ②UI) ②UI规则规则 ④ ④ （（ x x））( (F(x)∨G(xF(x)∨G(x)) )) 前提引入前提引入 ⑤ ⑤ F(aF(a) ∨ ) ∨ G(aG(a) ④UI) ④UI ⑥ ⑥ F(aF(a) ③⑤) ③⑤析取三段论析取三段论 ⑦ ⑦ （（ x x））F(xF(x) ) ⑥EG⑥EG规则规则 （（3 3）因为结论不是前束范式，所以直接证明不好处理，这里）因为结论不是前束范式，所以直接证明不好处理，这里我们采用类似于第我们采用类似于第1 1章章1.51.5节命题推理中的节命题推理中的CPCP规则法和反证法规则法和反证法分别证明。

分别证明 例：判断下面推理是否有效？例：判断下面推理是否有效？ 不存在能表示分数的无理数，有理数都能表不存在能表示分数的无理数，有理数都能表示分数，因此有理数都不是无理数示分数，因此有理数都不是无理数数理逻辑部分小结数理逻辑部分小结 这里我们介绍了数理逻辑的这里我们介绍了数理逻辑的两个最基本两个最基本的也是最重的也是最重要的组成部分，就是要的组成部分，就是““命题逻辑命题逻辑””和和““（一阶）谓词逻（一阶）谓词逻辑辑”” 命题逻辑是研究关于命题如何通过一些逻辑连接词命题逻辑是研究关于命题如何通过一些逻辑连接词构成更复杂的命题以及逻辑推理的方法如果我们把命构成更复杂的命题以及逻辑推理的方法如果我们把命题看作运算的对象，如同代数中的数字、字母或代数式，题看作运算的对象，如同代数中的数字、字母或代数式，而把逻辑连接词看作运算符号，就象代数中的而把逻辑连接词看作运算符号，就象代数中的““加、减、加、减、乘、除乘、除””那样，那么由简单命题组成复和命题的过程，那样，那么由简单命题组成复和命题的过程，就可以当作逻辑运算的过程，也就是命题的演算。

就可以当作逻辑运算的过程，也就是命题的演算  命题逻辑命题逻辑的一个具体模型就是的一个具体模型就是逻辑代数逻辑代数逻辑代数的运算特点如同电路分析中的开和关、高电位和低数的运算特点如同电路分析中的开和关、高电位和低电位等现象完全一样，都只有两种不同的状态，因此，电位等现象完全一样，都只有两种不同的状态，因此，它在电路分析中得到广泛的应用它在电路分析中得到广泛的应用 （一阶）谓词逻辑（一阶）谓词逻辑也叫做也叫做命题函数逻辑命题函数逻辑，它是把，它是把命题的内部结构分析成具有主词和谓词的逻辑形式，命题的内部结构分析成具有主词和谓词的逻辑形式，由命题变元、联结词和量词构成，然后研究它们的逻由命题变元、联结词和量词构成，然后研究它们的逻辑推理关系辑推理关系 数理逻辑数理逻辑和计算机的发展有着密切的联系，它为和计算机的发展有着密切的联系，它为机器证明、自动程序设计、计算机辅助设计等计算机机器证明、自动程序设计、计算机辅助设计等计算机应用和理论研究提供必要的理论基础应用和理论研究提供必要的理论基础数理逻辑部分结束！数理逻辑部分结束！ 谢谢！。