下载文档原格式
离散数学第二章一阶逻辑知识点总结数理逻辑部分第2章一阶逻辑2.1 一阶逻辑基本概念个体词（个体）: 所研究对象中能够独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示个体变项：抽象的事物，用x, y, z表示个体域: 个体变项的取值范围有限个体域，如{a, b, c}, {1, 2}无限个体域，如N, Z, R, …全总个体域: 宇宙间一切事物组成谓词: 表示个体词性质或相互之间关系的词谓词常项：F(a)：a是人谓词变项：F(x)：x具有性质F一元谓词: 表示事物的性质多元谓词(n元谓词, n2): 表示事物之间的关系如L(x,y)：x与y有关系L，L(x,y)：x y，…0元谓词: 别含个体变项的谓词, 即命题常项或命题变项量词: 表示数量的词全称量词: 表示任意的, 所有的, 一切的等如x 表示对个体域中所有的x存在量词: 表示存在, 有的, 至少有一具等如x表示在个体域中存在x一阶逻辑中命题符号化例1 用0元谓词将命题符号化要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1) 墨西哥位于南美洲在命题逻辑中, 设p:墨西哥位于南美洲符号化为p, 这是真命题在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲符号化为F(a)例2 在一阶逻辑中将下面命题符号化(1) 人都爱美; (2) 有人用左手写字分不取(a) D为人类集合, (b) D为全总个体域.解：(a) (1) 设G(x)：x爱美, 符号化为x G(x)(2) 设G(x)：x用左手写字, 符号化为x G(x)(b) 设F(x)：x为人，G(x)：同(a)中(1) x (F(x)G(x))(2) x (F(x)G(x))这是两个基本公式, 注意这两个基本公式的使用.例3 在一阶逻辑中将下面命题符号化(1) 正数都大于负数(2) 有的无理数大于有的有理数解注意: 题目中没给个体域, 一律用全总个体域(1) 令F(x): x为正数, G(y): y为负数, L(x,y): x>y x(F(x)y(G(y)L(x,y))) 或x y(F(x)G(y)L(x,y)) 两者等值(2) 令F(x): x是无理数, G(y): y是有理数,L(x,y)：x>yx(F(x)y(G(y)L(x,y)))或x y(F(x)G(y)L(x,y)) 两者等值几点注意：1元谓词与多元谓词的区分无特殊要求，用全总个体域量词顺序普通别能随便颠倒否定式的使用考虑：①没有别呼吸的人②别是所有的人都喜爱吃糖③别是所有的火车都比所有的汽车快以上命题应怎么符号化？2.2 一阶逻辑合式公式及解释字母表定义字母表包含下述符号：(1) 个体常项：a, b, c, …, a i, b i, c i, …, i1(2) 个体变项：x, y, z, …, x i, y i, z i, …, i 1(3) 函数符号：f, g, h, …, f i, g i, h i, …, i1(4) 谓词符号：F, G, H, …, F i, G i, H i, …, i1(5) 量词符号：,(6) 联结词符号：, , , ,(7) 括号与逗号：(, ), ，定义项的定义如下：(1) 个体常项和个体变项是项.(2) 若(x1, x2, …, x n)是任意的n元函数，t1,t2,…,t n是任意的n个项，则(t1, t2, …, t n) 是项.(3) 所有的项基本上有限次使用(1), (2) 得到的.个体常项、变项是项，由它们构成的n元函数和复合函数依然项定义设R(x1, x2, …, x n)是任意的n元谓词，t1,t2,…, t n 是任意的n个项，则称R(t1, t2, …, t n)是原子公式.原子公式是由项组成的n元谓词.例如，F(x,y), F(f(x1,x2),g(x3,x4))等均为原子公式定义合式公式（简称公式）定义如下：(1) 原子公式是合式公式.(2) 若A是合式公式，则(A)也是合式公式(3) 若A, B是合式公式，则(A B), (A B), (A B),(A B)也是合式公式(4) 若A是合式公式，则xA, xA也是合式公式(5) 惟独有限次地应用(1)~(4)形成的符号串是合式公式.请举出几个合式公式的例子.定义在公式xA和xA中，称x为指导变元，A为相应量词的辖域. 在x和x的辖域中，x的所有浮现都称为约束浮现，A中别是约束浮现的其他变项均称为是自由浮现的.例如, 在公式x(F(x,y)G(x,z)) 中,A=(F(x,y)G(x,z))为x的辖域，x为指导变元, A中x的两次浮现均为约束浮现，y与z均为自由浮现.闭式: 别含自由浮现的个体变项的公式.给定公式A=x(F(x)G(x))成真解释: 个体域N, F(x): x>2, G(x): x>1代入得A=x(x>2x>1) 真命题成假解释: 个体域N, F(x): x>1, G(x): x>2 代入得A=x(x>1x>2) 假命题咨询: xF(x)x F(x) 有成真解释吗？xF(x)x F(x) 有成假解释吗？被解释的公式别一定全部包含解释中的4部分.闭式在任何解释下基本上命题，注意别是闭式的公式在某些解释下也也许是命题.永真式（逻辑有效式）：无成假赋值矛盾式（永假式）：无成真赋值可满脚式：至少有一具成真赋值几点讲明：永真式为可满脚式，但反之别真谓词公式的可满脚性（永真性,永假性)是别可判定的利用代换实例可判某些公式的类型定义设A0是含命题变项p1, p2, …,p n的命题公式，A1,A2,…,A n是n个谓词公式，用A i处处代替A0中的p i (1i n)，所得公式A称为A0的代换实例.例如:F(x)G(x), xF(x)yG(y) 等基本上p q的换实例，x(F(x)G(x)) 等别是p q 的代换实例.定理重言式的代换实例基本上永真式，矛盾式的代换实例基本上矛盾式.2.3 一阶逻辑等值式等值式定义若A B为逻辑有效式，则称A与B是等值的，记作A B，并称A B 为等值式.基本等值式:命题逻辑中16组基本等值式的代换实例如，xF(x)yG(y) xF(x)yG(y)(xF(x)yG(y)) xF(x)yG(y) 等消去量词等值式设D={a1,a2,…,a n} xA(x)A(a1)A(a2)…A(a n)xA(x)A(a1)A(a2)…A(a n)量词否定等值式设A(x)是含x自由浮现的公式xA(x)x A(x)xA(x)x A(x)量词分配等值式x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)注意：对无分配律，对无分配律例将下面命题用两种形式符号化(1) 没有别犯错误的人(2) 别是所有的人都爱看电影解(1) 令F(x)：x是人，G(x)：x犯错误.x(F(x)G(x))x(F(x)G(x))请给出演算过程，并讲明理由.(2) 令F(x)：x是人，G(x)：爱看电影.x(F(x)G(x))x(F(x)G(x))给出演算过程，并讲明理由.前束范式定义设A为一具一阶逻辑公式, 若A具有如下形式Q1x1Q2x2…Q k x k B, 则称A为前束范式, 其中Q i(1i k)为或，B为别含量词的公式.例如，x y(F(x)(G(y)H(x,y)))x(F(x)G(x))是前束范式, 而x(F(x)y(G(y)H(x,y)))x(F(x)G(x))别是前束范式.定理（前束范式存在定理）一阶逻辑中的任何公式都存在与之等值的前束范式注意:公式的前束范式别惟一求公式的前束范式的办法: 利用重要等值式、置换规则、换名规则、代替规则举行等值演算.换名规则: 将量词辖域中浮现的某个约束浮现的个体变项及对应的指导变项，改成其他辖域中未曾浮现过的个体变项符号，公式中其余部分别变，则所得公式与原来的公式等值.代替规则: 对某自由浮现的个体变项用与原公式中所有个体变项符号别同的符号去代替，则所得公式与原来的公式等值.例求下列公式的前束范式(1) x(M(x)F(x))解x(M(x)F(x))x(M(x)F(x)) （量词否定等值式）x(M(x)F(x))两步结果基本上前束范式，讲明前束范式别惟一.(2) xF(x)xG(x)解xF(x)xG(x)xF(x)x G(x) （量词否定等值式）x(F(x)G(x)) （量词分配等值式）另有一种形式xF(x)xG(x)xF(x)x G(x)xF(x)y G(y) ( 换名规则) x y(F(x)G(y)) ( 量词辖域扩张) 两种形式是等值的(3) xF(x)xG(x)解xF(x)xG(x)xF(x)x G(x)x(F(x)G(x)) （为啥？）或x y(F(x)G(y)) （为啥？）(4) xF(x)y(G(x,y)H(y))解xF(x)y(G(x,y)H(y))zF(z)y(G(x,y)H(y)) （换名规则）z y(F(z)(G(x,y)H(y))) （为啥？）或xF(x)y(G(z,y)H(y)) （代替规则）x y(F(x)(G(z,y)H(y)))(5) x(F(x,y)y(G(x,y)H(x,z)))解用换名规则, 也可用代替规则, 这个地方用代替规则 x(F(x,y)y(G(x,y)H(x,z)))x(F(x,u)y(G(x,y)H(x,z)))x y(F(x,u)G(x,y)H(x,z)))注意：x与y别能颠倒。
离散数学第2版课后习题答案离散数学是计算机科学和数学领域中一门重要的学科，它研究离散对象及其关系、结构和运算方法。
离散数学的应用非常广泛，包括计算机科学、信息科学、密码学、人工智能等领域。
而离散数学第2版是一本经典的教材，它系统地介绍了离散数学的基本概念、原理和方法。
本文将为读者提供离散数学第2版课后习题的答案，帮助读者更好地理解和掌握离散数学的知识。
第一章：基本概念和原理1.1 命题逻辑习题1：命题逻辑的基本符号有哪些？它们的含义是什么？答：命题逻辑的基本符号包括命题变量、命题联结词和括号。
命题变量用字母表示，代表一个命题。
命题联结词包括否定、合取、析取、条件和双条件等，分别表示“非”、“与”、“或”、“如果...则...”和“当且仅当”。
括号用于改变命题联结词的优先级。
习题2：列举命题逻辑的基本定律。
答：命题逻辑的基本定律包括德摩根定律、分配律、结合律、交换律、吸收律和否定律等。
1.2 集合论习题1：什么是集合？集合的基本运算有哪些？答：集合是由一些确定的对象组成的整体，这些对象称为集合的元素。
集合的基本运算包括并、交、差和补等。
习题2：列举集合的基本定律。
答：集合的基本定律包括幂等律、交换律、结合律、分配律、吸收律和德摩根定律等。
第二章：数理逻辑2.1 命题逻辑的推理习题1：什么是命题逻辑的推理规则？列举几个常用的推理规则。
答：命题逻辑的推理规则是用来推导命题的逻辑规则。
常用的推理规则包括假言推理、拒取推理、假言三段论和析取三段论等。
习题2：使用推理规则证明以下命题：如果A成立，则B成立；B不成立，则A不成立。
答：假言推理规则可以用来证明该命题。
根据假言推理规则，如果A成立，则B成立。
又根据假言推理规则，如果B不成立，则A不成立。
2.2 谓词逻辑习题1：什么是谓词逻辑？它与命题逻辑有何区别？答：谓词逻辑是一种扩展了命题逻辑的逻辑系统，它引入了谓词和量词。
与命题逻辑不同，谓词逻辑可以对个体进行量化和描述。
离散数学上海课后习题答案离散数学是一门研究离散结构和离散对象的数学学科，其应用广泛，涉及到计算机科学、信息科学、电子工程等领域。
在学习离散数学的过程中，课后习题是巩固知识、提高能力的重要环节。
本文将为大家提供一些离散数学上海课后习题的答案，希望能够帮助大家更好地理解和掌握这门学科。
第一章命题逻辑1. 命题逻辑是研究命题之间关系的数学分支。
其中，命题是指可以判断真假的陈述句。
命题逻辑的基本运算有与、或、非、蕴含和等价等。
2. 真值表是用来表示命题逻辑中命题的真假取值的表格。
通过真值表，可以判断命题之间的逻辑关系。
3. 简化命题是指将复杂的命题通过逻辑运算简化为更简单的形式。
常用的简化方法有代入法、等价变换法和逻辑运算法则等。
4. 命题公式是由命题变量和逻辑运算符组成的表达式。
命题公式可以通过真值表来验证其真假。
第二章集合论1. 集合是由一些确定的对象组成的整体。
集合论是研究集合性质、集合间关系以及集合运算的数学理论。
2. 集合的基本运算有并、交、差和补运算。
并集是指将两个或多个集合中的元素合并在一起；交集是指两个或多个集合中共有的元素；差集是指一个集合中去掉与另一个集合中相同的元素；补集是指一个集合中不属于另一个集合的元素。
3. 集合的基数是指集合中元素的个数。
对于有限集合，可以通过数数的方式确定其基数；对于无限集合，可以通过一一对应的方式确定其基数。
4. 集合的运算律是指集合运算满足的一些基本性质。
常见的集合运算律有交换律、结合律、分配律等。
第三章关系与函数1. 关系是指集合之间元素之间的一种对应关系。
关系可以用集合的形式表示，也可以用矩阵的形式表示。
2. 函数是一种特殊的关系，它将一个集合中的每个元素映射到另一个集合中的唯一元素。
函数可以用箭头图表示，也可以用公式表示。
3. 函数的性质有单射、满射和双射等。
单射是指函数中不同的输入对应不同的输出；满射是指函数的值域等于其陪域；双射是指函数既是单射又是满射。
第一篇数理逻辑数理逻辑是应用数学方法引进一套符号系统来研究思维的形式结构和规律的学科，它起源于公元十七世纪。
十九世纪英国的德·摩根和乔治·布尔发展了逻辑代数，二十世纪三十年代数理逻辑进入了成熟时期，基本内容（命题逻辑和谓词逻辑）有了明确的理论基础，成为数学的一个重要分支，同时也是电子元件设计和性质分析的工具。
冯·诺意曼，图灵，克林，…等人研究了逻辑与计算的关系。
基于理论研究和实践，随着1946年第一台通用电子数字计算机的诞生和近代科学的发展，计算技术中提出了大量的逻辑问题，逻辑程序设计语言的研制，更促进了数理逻辑的发展。
除古典二值（真，假）逻辑外，还研究了多值逻辑、模态逻辑、概率逻辑、模糊逻辑、非单调逻辑等。
不仅有演绎逻辑，也还有归纳逻辑。
计算机科学中还专门研究计算逻辑、程序逻辑、时序逻辑等。
现代数理逻辑分为四论：证明论，递归论（它们与形式语言语法有关），模型论，公理化集合论（它们与形式语言的语义有关）。
第1-1章命题逻辑学习要求: 掌握命题，命题公式，重言式，等价式，蕴涵式等基本概念，能利用逻辑联结词或真值表，等价式与蕴涵式进行命题演算和推理；学习范式时与集合的范式进行对比。
表述客观世界的各种现象，表述人们的思想，表述各门学科的规则、理论等，除使用自然语言（这常常是上有歧异性的）外，还要使用一些特定的术语、符号、规律等“对象语言”，这些是所研究学科的一种特殊的形式化语言，研究思维结构与规律的逻辑学也有其对象语言。
本章就是讨论逻辑学中的对象语言—命题及其演算，它相当于自然语言中的语句。
§1-1-1 命题逻辑联结词与真值表一、命题的基本概念首先我们从下面的例子加以分析。
例1-1-1.1人总是要死的。
例1-1-1.2苏格拉底是人。
例1-1-1.3苏格拉底是要死的。
例1-1-1.4中国人民是勤劳和勇敢的。
例1-1-1.5鸵鸟是鸟。
例1-1-1.6 1是质（素）数。
