广东自考网欢迎各位自考生,今天是
广东自考网

广东自考网上报名系统 2020年广东自考报名时间 自考专本套读

免费咨询:020-89338633

自考办电话| 自考提问 | 公众号

广东省自学考试管理系统 广东自考成绩查询入口 低学历提升方案 自考准考证打印 2020年广东自考开考科目查询 2020年广东自考报名考试时间 广东自考公开课 近期自考热点问题关注
您当前所在位置: 首页 > 工学类> 2019年自考离散数学基础串讲资料汇总

2019年自考离散数学基础串讲资料汇总

日期:2019-07-25  编辑整理:广东自考网  【 】 【打印

第一讲 引言

一、课程内容

·数理逻辑:是计算机科学的基础,应熟练掌握将现实生活中的条件化成逻辑公式,并能做适当的推理,这对程序设计等课程是极有用处的。

·集合论:数学的基础,对于学习程序设计、数据结构、编译原理等几乎所有计算机专业课程和数学课程都很有用处。熟练掌握有关集合、函数、关系等基本概念。

·代数结构:对于抽象数据类型、形式语义的研究很有用处。培养数学思维,将以前学过的知识系统化、形式化和抽象化。熟练掌握有关代数系统的基本概念,以及群、环、域等代数结构的基本知识。

·图论:对于解决许多实际问题很有用处,对于学习数据结构、编译原理课程也很有帮助。要求掌握有关图、树的基本概念,以及如何将图论用于实际问题的解决,并培养其使用数学工具建立模型的思维方式。

·讲课时间为两个学期,第一学期讲授数理逻辑与集合论,第二学期讲授代数结构和图论。考试内容限于书中的内容和难度,但讲课内容不限于书中的内容和难度。

 

二、数理逻辑发展史

1.目的

·了解有关的背景,加深对计算机学科的全面了解,特别是理论方面的了解,而不限于将计算机看成是一门技术或工程性的学科。

·通过重要的历史事件,了解计算机科学中的一些基本思维方式和一些基本问题。

 

2.数理逻辑的发展前期

·前史时期——古典形式逻辑时期:亚里斯多德的直言三段论理论

·初创时期——逻辑代数时期(17世纪末)

·资本主义生产力大发展,自然科学取得了长足的进步,数学在认识自然、发展技术方面起到了相当重要的作用。

·人们希望使用数学的方法来研究思维,把思维过程转换为数学的计算。

·莱布尼兹(Leibniz, 1646~1716)完善三段论,提出了建立数理逻辑或者说理性演算的思想:

·提出将推理的正确性化归于计算,这种演算能使人们的推理不依赖于对推理过程中的命题的含义内容的思考,将推理的规则变为演算的规则。

·使用一种符号语言来代替自然语言对演算进行描述,将符号的形式和其含义分开。使得演算从很大程度上取决与符号的组合规律,而与其含义无关。

·布尔(G. Boole, 1815~1864)代数:将有关数学运算的研究的代数系统推广到逻辑领域,布尔代数既是一种代数系统,也是一种逻辑演算。

 

3.数理逻辑的奠基时期

·弗雷格(G. Frege, 1848~1925):《概念语言——一种按算术的公式语言构成的纯思维公式语言》(1879)的出版标志着数理逻辑的基础部分——命题演算和谓词演算的正式建立。

·皮亚诺(Giuseppe Peano, 1858~1932):《用一种新的方法陈述的算术原理》(1889)提出了自然数算术的一个公理系统。

·罗素(Bertrand Russell, 1872~1970):《数学原理》(与怀特黑合著,1910, 1912, 1913)从命题演算和谓词演算开始,然后通过一元和二元命题函项定义了类和关系的概念,建立了抽象的类演算和关系演算。由此出发,在类型论的基础上用连续定义和证明的方式引出了数学(主要是算术)中的主要概念和定理。

·逻辑演算的发展:甘岑(G. Gentzen)的自然推理系统(Natural Deduction System),逻辑演算的元理论:公理的独立性、一致性、完全性等。

·各种各样的非经典逻辑的发展:路易斯(Lewis, 1883~1964)的模态逻辑,实质蕴涵怪论和严格蕴涵、相干逻辑等,卢卡西维茨的多值逻辑等。

 

4.集合论的发展

·看待无穷集合的两种观点:实无穷与潜无穷

·康托尔(G. Cantor, 1845~1918):以实无穷的思想为指导,建立了朴素集合论

·外延原则(集合由它的元素决定)和概括原则(每一性质产生一集合)。

·可数集和不可数集,确定无穷集合的本质在于集合本身能与其子集一一对应。能与正整数集合对应的集合是可数的,否则是不可数的。证明了有理数集是可数的,使用对角线法证明了实数集合是不可数的。

·超穷基数和超穷序数

·朴素集合论的悖论:罗素悖论

·公理集合论的建立:ZFC系统

 

6.第三次数学危机与逻辑主义、直觉主义与形式主义

·集合论的悖论使得人们觉得数学产生了第三次危机,提出了数学的基础到底是什么这样的问题。

·罗素等的逻辑主义:数学的基础是逻辑,倡导一切数学可从逻辑符号推出,《数学原理》一书是他们这一思想的体现。为解决悖论产生了逻辑类型论。

·布劳维尔(Brouwer, 1881~1966)的直觉主义:数学是心灵的构造,只承认可构造的数学,强调构造的能行性,与计算机科学有重要的联系。坚持潜无穷,强调排中律不能用于无穷集合。海丁(Heyting)的直觉主义逻辑。

·希尔伯特(D. Hilbert)的形式主义:公理化方法与形式化方法,元数学和证明论,提倡将逻辑演算和数学证明本身形式化,把用普通的语言传达的内容上的数学科学变为用数学符号和逻辑符号按一定法则排列的一堆公式。为了消除悖论,要数学建立在公理化基础上,将各门数学形式化,构成形式系统,并证明其一致性,这是希尔伯特的数学纲领。

 

7.数理逻辑的发展初期

·哥德尔(Godel, 1906~1978)不完全性定理:一个足够强大的形式系统,如果是一致的则不是完全的,即有的判断在其中是不可证的,既不能断定其为假,也不能证明其为真。

·各种计算模型:哥德尔的递归函数理论,邱吉尔的l演算,图灵机模型

·这些计算模型是计算机科学的理论基础,是计算机的理论模型。

三、预备知识

1.集合的基本概念

·集合(set):集合是数学中最基本的概念之一,不能以更简单的概念来定义(define),只能给出它的描述(description)。一些对象的整体就称为一个集合,这个整体的每个对象称为该集合的一个元素(member或element)。

·用大写字母A, B, C等表示集合,用小写字母a, b, c等表示集合的元素

·aÎA表示:a是集合A的元素,或说a属于集合A

·aÏA表示:a不是集合A的元素,或说a不属于集合A

·集合中的元素是无序的,不重复的。通常使用两种方法来给出一个集合:

·列元素法:列出某集合的所有元素,如:

·A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}表示所有小于10的自然数所构成的集合

·B = {a, b, …, z} 表示所有小写英文字母所构成的集合

·性质概括法:使用某个性质来概括集合中的元素,如:

·A = { n | n 是小于10的自然数}

·C = { n | n 是质数} 表示所有质数所构成的集合

·集合由它的元素所决定,换句话说,两个集合A和B相等,记为A = B,如果A和B具有相同的元素,即a属于集合A当且仅当a属于集合B。 

·子集(subset):说集合A是集合B的子集,记为AÍB,如果a属于集合A则a也属于集合B。因此A=B当且仅当AÍB且BÍA。说集合A是集合B的真子集(proper subset),如果AÍB且A不等于B(A ¹ B)。

·空集(empty set):约定存在一个没有任何元素的集合,称为空集,记为f,有时也用{}来表示。按子集的定义,空集是任何集合的子集(为什么?)。

·幂集(power set):集合A的幂集,记为P(A),是A的所有子集所构成的集合,即:

·P(A) = { B | B Í A }

·例如,A = {0, 1},则P(A) = { {}, {0}, {1}, {0, 1} }

·显然,对任意集合A,有fÎ P(A)和AÎP(A) 

·补集(complement set):集合A的补集,记为A,是那些不属于集合A的元素所构成的集合,即A = {x | xÏA}。通常来说,是在存在一个全集U的情况下讨论集合的补集。全集U是所讨论的问题域中所有元素所构成的集合。

·集合的并(union):集合A和B的并AÈB定义为:AÈB = {x | xÎA或者xÎB},集合的并可推广到多个集合,设A1, A2, …, An都是集合,它们的并定义为:

A1ÈA2…ÈAn = {x | 存在某个i,使得xÎAi}

·集合的交(intersection):集合A和B的并AÇB定义为:AÇB = {x | xÎA而且xÎB},集合的交也可推广到多个集合,设A1, A2, …, An都是集合,它们的交定义为:

A1ÈA2…ÈAn = {x | 对所有的i,都有xÎAi}

·集合的差(difference):集合A和B的差A-B定义为:A-B = {x | xÎA而且xÏB}。

 

2.关系和函数的基本概念

·有序对(ordered pair):设A和B是两个集合,aÎA, bÎB是两个元素,a和b的有序对,记为<a, b>,定义为集合{{a}, {a, b}}。

·设<a1, b1>和<a2, b2>是两个有序对,可以证明<a1, b1> = <a2, b2>当且仅当a1 = a2且b1 = b2。(如何证?)

·有序对可推广到n个元素,设A1, A2, …, An是集合,a1ÎA1, a2ÎA2, …, anÎAn是元素,定义有序n元组(ordered n-tuple)<a1, a2, …, an>为<<a1, a2, …, an-1>, an>,注意这是一个归纳(inductive)定义,将有序n元组的定义归结为有序n-1元组的定义。

·显然有<a1, a2, …, an> = <b1, b2, …, bn>当且仅当a1 = b1且a2 = b2且…且an = bn。 

·集合的笛卡尔积(cartesian product):两个集合A和B的笛卡尔积A´B定义为:

A´B = {<a, b> | aÎA且bÎB}

·例如,设A = {a, b, c},B = {1, 2},则:

A´B = {<a, 1>, <a, 2>, <b, 1>, <b, 2>, <c, 1>, <c, 2>}

·笛卡尔积可推广到多个集合的情况,集合A1, A2, …, An的笛卡尔积定义为:

A1´A2´…´An = {<a1, a2, …, an> | a1ÎA1且a2ÎA2且…且anÎAn} 

·集合之间的关系(relation):定义n个集合A1, A2, …, An之间的一个n元关系R为集合A1, A2, …, An的笛卡尔积A1´A2´…´An的一个子集。设<a1, a2, …, an>ÎA1´A2´…´An,若<a1, a2, …, an>ÎR,则称a1, a2, …, an间具有关系R,否则称它们不具有关系R。特别地:

·当A1 = A2 = … = An = A时,称R为A上的n元关系。

·当n = 2时,有RÍA1´A2,称R为A1与A2间的一个二元关系(binary relation)。这时若<a1, a2>ÎR则简记为a1Ra2,否则(即<a1, a2>ÏR)记为a1Ra2。通常研究得最多的是二元关系,n元关系的许多性质可从二元关系的性质扩充而得到。如果没有特别指明的话,说R是一个关系则是指R是一个二元关系。

·当n = 1时,这时可认为R是集合A上满足某种性质的子集。

·关系的一些性质:设R是A上的二元关系:

·说R是自反的(reflexive),如果对任意的aÎA有aRa。

·说R是反自反的(irreflexive),如果对任意的aÎA有aRa。

·说R是对称的(symmetric),如果对任意的a, bÎA有若aRb则bRa。

· 说R是反对称的(antisymmetric),如果对任意的a, bÎA有若aRb且bRa则a = b。

·说R是传递的(transitive),如果对任意的a, b, c ÎA有若aRb且bRc则aRc。

·说R是等价关系(equivalence),如果R是自反的、对称的和传递的。 

·集合之间的函数(function,或说映射mapping):定义集合A到B的函数f是A和B的笛卡尔积A´B的一个子集,且满足若<x, y>Îf及<x, z>Îf则y = z。因此函数是A和B之间的一个特殊的二元关系。通常记集合A到B的函数f为f : A®B。

·函数f : A®B的定义域(domain)dom(f )定义为:

dom(f ) = {x | 存在某个yÎB使得<x, y>Îf }

·函数f : A®B的值域(range)ran(f )定义为:

ran(f ) = {y | 存在某个xÎA使得<x, y>Îf }

·若<x, y>Îf,通常记y为f(x),并称y为x在函数f下的像(image),x为y在函数f下的原像。

·函数也可推广到n元的情形:f : A1´A2´…´An®B,意味着:

·f是A1´A2´…´An´B的一个子集,且

·<x1, x2, …, xn, y>Î f且<x1, x2, …, xn, z>Î f则y = z。 

·函数的一些性质:设f : A®B是集合A到B的函数:

·说f是全函数(total function),若dom(f )=A,否则称f是偏函数(partial function)。下面如果没有特别指明的话,都是指全函数。

·说f是满射(surjection, 或说f maps A onto B),如果ran(f ) = B,即对任意的yÎB都有原像。

·说f是单射(injection,或说f is one-one),如果有f (x1) = f(x2)则x1 = x2,即对任意的yÎB,如果它有原像的话,则有唯一的原像。

·说f是双射(bijection,或说f是一一对应),如果f既是满射,又是单射,即对任意的yÎB,都有唯一的原像,同样根据全函数的定义,对于任意xÎA都有唯一的像。这时可以定义f的逆函数(inverse function),记为f -1 : B®A,f -1(y) = x当且仅当f(x) = y。显然f -1也是双射。 

·集合的基数(cardinal number)或说势:集合A的基数记为|A|,且有:

·对于有限集合A,令A的基数为A中元素的个数。

·定义无限集合,不直接定义基数,而是通过定义两个集合之间的等势关系来刻划集合的基数或势,说集合A和集合B是等势的(equipotent),如果存在一个从A到B的双射。根据双射的性质,可以证明等势是集合上的一个等价关系。

·称与自然数集等势的集合为可列集(enumerable),有限集和可列集统称为可数集(countable)。

·设A和B是有限集合,有|P(A)| = 2|A|,|A´B| = |A| ´ |B|。

. 归纳定义和归纳证明

·一个集合的归纳定义(inductive definition)通常分为三步:

·归纳基:一些基本的元素属于该集合;

·归纳步:定义一些规则(或者说操作),从该集合中已有的元素来生成该集合的新的元素;

·最小化:该集合中的所有元素都是通过基本元素以及所定义的规则生成的,换句话说,该集合是由基本元素及规则所生成的最小的集合。

·自然数集N的归纳定义:

[1]. 归纳基:0是一个自然数,即0Î N。

[2]. 归纳步:若n是自然数,则n的后继也是自然数。记n的后继为succ(n),即若nÎN,则succ(n)ÎN。为方便起见,后面也记n的后继为n+1。

[3]. 最小化:所有的自然都通过步骤[1]和[2]得到,或者说自然数集是通过步骤[1]和[2]得到的最小集合。

·这种定义方式可推广到对其他一些概念的定义,例如上述多个集合的并、交、笛卡尔积以及多个元素的有序n元组都可通过递归的方式定义。例如,对于多个集合的并可定义为:

·归纳基:A1ÈA2 = {x | xÎA1或者xÎA2}

·归纳步:A1ÈA2…ÈAn = (A1ÈA2…ÈAn-1) È An

·这里不需要最小化,因为这里不是定义集合。

·数学归纳法:关于自然数的许多性质都可通过数学归纳法来证明,对于性质R,如果它对0成立,而且如果对于n成立的话,能够得到它对于n+1也成立,那么性质R对所有的自然数成立。这种证明方法的正确性本身可通过自然数的归纳定义来得到证明:

·定义集合S = {nÎN | 性质R对n成立}

·归纳基:根据上面的定义有0ÎS

·归纳步:根据上面的定义有如果nÎS,则n+1ÎS,所以S是满足上面自然数集的归纳定义中的1、2点的一个集合,而自然数集N是满足这两点的最小集合,所以有N ÍS,而显然有SÍN,所以S = N。

·数学归纳法举例:使用数学归纳法证明1 + 2 + … + n = (n * (n+1))/2

·归纳基:当n = 0时显然成立。

·归纳步:如果对于n成立,则有1 + 2 + … + n = (n * (n+1))/2(这称为归纳假设),现在要证对于n+1也成立。显然有:

1 + 2 + … + n + (n + 1) = (n * (n+1))/2 + (n+1) // 根据归纳假设

= (n * (n+1) + 2 * (n+1))/2 = ((n+1) * ((n+1) + 1))/2

因此要证的公式对于n+1成立,所以对于所有的自然数成立。

·显然在数学归纳法中,对于归纳基改为R对于自然数k成立,归纳步不变的话,则可证明R对于所有大于k的自然数都成立。

·在数学归纳法中,也可将归纳步改为如果R对于所有小于n的自然数成立,则推出R对于n也成立,即归纳步是假设对于所有小于n的自然数性质R成立来导出性质R对于自然数n成立。这种形式的数学归纳法通常称为第二数学归纳法。
 

5. 形式系统

·形式系统的定义:一个形式系统S由下列4个集合构成:

·一个非空集合SS,称为形式系统S的字母表或说符号(Symbol)表;

·一个由SS中字母的有限序列(字符串)所构成的集合FS,称为形式系统S的公式(Formula)集;

·从FS中选取一个子集AS,称为形式系统S的公理(Axiom)集;

·FS上有一个部分函数集RS = {Rn | Rn : FS ´ FS ´…´ FS ®FS , n = 1, 2, …},称为形式系统S的规则(Rule)集,其中Rn : FS ´ FS ´…´ FS ®FS是n元的部分函数,我们称其为n元规则。

·形式系统中的定理(Theorem):

·归纳基:t Î AS 是形式系统S中的定理。

· 归纳步:t1, t2, …, tn是形式系统S中的定理,而RnÎ是S中的规则,那么Rn(t1, t2, …, tn)也是形式系统S中的定理。

·对于形式系统中的规则Rn : FS ´ FS ´…´ FS ®FS,通常表示成下面的形式:

t1, t2, …, tn

Rn(t1, t2, …, tn)

·形式系统具有两个特征:

·形式化实际上是一个可机械实现的过程,在它里面,符号、规则和演算等被表示得严密、精确。在形式系统S中,只能使用字母表SS中的符号,只承认公式集FS中的符号串的合理性,只能由公理集,根据规则推出有意义的东西来。

·形式系统一旦完成,就成了符号串及根据规则进行的符号串的改写,系统与一切实际意义就毫不相干,或者说已经通过这种符号,从实际问题中抽象出了我们所需要研究的内容。在形式系统内部,所能认识的只能是符号串及其改写,只能在形式系统外对这种符号串及规则赋予意义。 

·对象语言(Object language)与元语言(Meta language):

·数理逻辑所研究的是“数学推理”,而使用的方法也是数学推理,所以有必要区分这两个层次的推理。

·把作为研究对象的“推理”形式化,使用形式语言来表示作为研究对象的“推理”的前提、结论和规则等,这种形式语言是我们所研究的对象语言。

·另一方面,关于形式系统的性质、规律的表达和作为研究方面的推理方式使用另一种语言来表达,这个语言称为研究的元语言,通常使用半数学化的自然语言。

·形式语言的语法(Syntax)与语义(Semantic):

·形式语言的语法是构成形式系统的公式集、公理集和规则集的法则。

·形式语言的语义是关于形式系统的解释和意思。

·形式语言本身没有含义,但我们在构造它们时是假想它们能代表某种意义的,特别的当我们在选择形式系统的公理时,总是选择所研究的问题域中那些最为明显或最容易公认为正确的性质。

 

6. 习题

1. 令集合A = { n | n £ 10且n 是奇数},B = {n | n £ 10且n是素数},请回答下列问题:

a) 请用列元素的方法列出集合A和集合B,请问集合B是否是集合A的子集?

b) 请计算AÈB、AÇB、A-B、A´B以及P(A)(即A的幂集)。

2. 设关系R = {<a, b> | a和b是互质的自然数},请问R是自反的吗?对称的吗?传递的吗?为什么?

3. 设f : A®B是函数,R是A上的如下二元关系:R = {<a, b> | a, bÎA, f (a) = f (b) },  证明R是A上的一个等价关系。

4. 使用数学归纳法证明:12 + 22 + 32 + … + n2 = (n * (n + 1) * (2n + 1)) / 6

5. 设有函数f : N®N ´ N,f(n) = <n, n+1>,请问f是不是单射、满射或双射?

*6.设R1和R2都是A上的等价关系,请问R1ÈR2和R1ÇR2是否还是A上的等价关系?如果是请证明,否则请举一反例。

*7.设R是集合A上的等价关系,aÎA,可定义:

a) [a] = {bÎA | aRb },称[a]为a关于R的等价类;

b) A/R = {[a] | aÎA},称A关于R的商集。

设函数f : A®A/R定义为对任意aÎA有f(a) = [a],请问R满足怎样的条件时f是单射?

*8 请给出<x, y, z>的集合方式的定义。若定义:[x, y, z] = {{x}, {x, y}, {x, y, z}},则如果有[x1, y1, z1] = [x2, y2, z2]是否意味着有x1 = x2且y1 = y2且z1 = z2?
 

3.命题逻辑公式

【定义1.1】命题逻辑公式(propositional logic formula)由以下子句归纳定义:

[1]. 归纳基:命题常量或命题变量是命题逻辑公式,称为命题逻辑公式的原子项。

[2]. 归纳步:如果A, B是逻辑公式,则(ØA)、(AÙB)、(AÚB)、(A®B)和(A«B)也是命题逻辑公式。

[3]. 最小化:所有的命题逻辑公式都通过1和2得到。

在这里我们隐含地使用的字母表是大小写的英文字母、命题联结符和园括号。英文字母还可带下标。其它的符号都不属于我们的符号表,即在命题逻辑公式中不能出现这些符号。后面我们将命题逻辑公式简称为命题公式,或在没有二义的情况下进一步简称为公式。

【例子1.1】((p Ú q) ® ((Øp) « (q Ù r)))是命题公式,它通过以下步骤生成:

1.p是公式;  // 根据定义1.1的[1]

2.q是公式;  // 根据定义1.1的[1]

3.(p Ú q)是公式;// 根据定义1.1的[2]

4.(Øp)是公式; // 根据定义1.1的[2]

5.r是公式;  // 根据定义1.1的[1]

6.(q Ù r)是公式;// 根据定义1.1的[2]

7.((Øp) « (q Ù r))是公式;// 根据定义1.1的[2],以及4, 6

8.((p Ú q) ® ((Øp) « (q Ù r)))是公式。  // 根据定义1.1的[2],以及3, 7



【定理1.2】设R是某个性质,如果有:

[1]. 对于所有的原子项p,都满足性质R;

[2]. 如果对任意的公式A和B都满足性质R,就有(ØA)、(AÙB)、(AÚB)、(A®B)和(A«B)也满足性质R。

那么,所有的公式A就都满足性质R。□

该定理的证明类似数学归纳法的证明,很容易根据定义1.1得到。

 

【定义1.3】命题公式A的复杂程度deg(A)定义为:

[1]. 如果A是原子项,则deg(A) = 0;

[2]. deg(ØA) = deg(A) + 1;

[3]. deg(A * B) = max(deg(A), deg(B)) + 1,其中*代表Ù、Ú、®、«之一。 

此定义等价于教材p11的定义1.7。只不过我们在这里给出的是递归定义。使用归纳法,我们可证明下面定理:

 

【定理1.4】deg(A)小于等于命题公式A中的命题联结符号的数目。

 

【证明】根据命题公式A的结构进行归纳证明:

1. 归纳基:如果A是原子项,则根据定义1.3有deg(A) = 0,显然定理成立。

2. 归纳步:假设定理对于命题公式A和B成立(归纳假设),记命题公式A中的命题联结符号数为Sym(A),即有deg(A) £ Sym(A)和deg(B) £ Sym(B)。那么由于deg(ØA) = deg(A) + 1,而Sym(ØA) = Sym(A) + 1,所以定理对于ØA也成立。同样由于deg(A * B) = max(deg(A), deg(B)) + 1,而Sym(A * B) = Sym(A) + Sym(B) + 1,因而有deg(A * B)£ Sym(A * B),从而定理对所有的命题公式都成立。

 

【定理1.5】任意命题逻辑公式A中出现相等数目的左右园括号,实际上,左右园括号的个数都等于A中的命题联结符号数。

 

【定理1.6】任意命题逻辑公式A具有下列6种形式之一,且只具有其中一种形式:

[1]. A为原子项;[2]. (ØA)[3]. (AÙB)

[4]. (AÚB)[5]. (A®B)[6]. (A«B)



【定理1.6】的确切含义包括以下几点:

1. 任意命题公式必然具有上述6中形式之一;

2. 这6中形式都互不相同;

3. 如果(ØA)与(ØA1)相同,则必有A与A1相同;

4. 如果(A * B)与(A1 * B1)相同,则必有A与A1相同,且B与B1相同。 

根据定理1.5和定理1.6,我们不难明白例子1.1是如何得到该其中命题公式的语法分析树的。实际上每个命题公式的最左边都是左园括号,如果从第二个符号不是左园括号,那么这个公式只有一个命题联结符。否则找与第二个左园括号配对的右园括号,从而将命题公式划分为这样的形式:((…) * (…)),如果原来的命题公式为根的话,那么左右两边的两个命题公式分别为它的左右子树了,而且对这两个公式可作类似的分析,最后到原子项。

在后面,为了书写方便起见,我们省略最外边的括号,并规定各个命题联结符的优先级别为Ø大于Ù,Ù大于Ú,Ú大于®,®大于«,从而可省略命题公式中一些不必要的园括号,例如例子1.1中的公式可写为:p Ú q ® Øp « q Ù r。不过在后面我们书写公式的原则是尽量简便,但又能让读者容易理解。而有关命题公式的性质的讨论,则只针对可由上面定义1.1所能生成的公式形式。

上面讨论的命题公式的语法结构,下面讨论命题公式的赋值。

 

【定义1.7】 对命题公式的一次真值赋值t是从所有命题变量所组成的集合到集合{0, 1}的函数。实际上,对于某个命题公式A来说,我们只关心t在A中的命题变量上的值。这里我们假定存在一个所有命题变量所组成的集合U,或者说我们所有命题公式中的变量都取之于集合U,我们记命题公式A中的所有命题变量所组成的集合为Var(A)。设有一个真值赋值t : U®{0, 1},而对于命题公式A的真值赋值来说,我们只关心t在Var(A)上的值。

【例子1.3】对于命题公式A = ((p Ú q) ® ((Øp) « (q Ù r))),有:

Var(A) = {p, q, r}

这里不妨假定U = Var(A),真值赋值就是一个函数t : {p, q, r}®{0, 1},例如可令:

t(p) = 0, t(q) = 1, t(r) = 0

 

【定义1.8】命题公式A在真值赋值t : U®{0, 1}下的真值t(A)递归定义如下:

[1].如果命题公式A是一个命题常量p,则如果p为真,t(A) = 1,否则t(A) = 0;

[2].如果命题公式A是一个命题变量p,则t(A) = t(p)

[3].若t(A) = 0则t(ØA) = 1,否则t(ØA) = 0。

[4].若t(A) = t(B) = 1,则t(AÙB) = 1,否则t(AÙB) = 0。

[5].若t(A) = t(B) = 0,则t(AÚB) = 0,否则t(AÚB) = 1。

[6].若t(A) = 0或者t(B) = 1,则t(A®B) = 1,否则t(A®B) = 0。

[7].若t(A) = t(B),则t(A«B) = 1,否则t(A«B) = 0。

【例子1.3,续】对于命题公式A = ((p Ú q) ® ((Øp) « (q Ù r))),及真值赋值函数t:

t(p) = 0, t(q) = 1, t(r) = 0

有:

1.  t(p) = 0, t(q) = 1;

2.  t(p Ú q) = 1;// 根据定义1.8的[5]

4.  t(Øp) = 1;// 根据定义1.8的[3]

 

 



热点关注:

2019年自考计算机系统结构复习精讲资料汇总

2019年自考计算机应用技术知识点汇总

声明:
(一)由于考试政策等各方面情况的不断调整与变化,本网站所提供的考试信息仅供参考,请以权威部门公布的正式信息为准。
(二)本网站在文章内容来源出处标注为其他平台的稿件均为转载稿,免费转载出于非商业性学习目的,版权归原作者所有。如您对内容、版权等问题存在异议请与本站联系,我们会及时进行处理解决。
标签:

相关推荐