有序整数集合a和b的交集函数.doc

离散数学期中课程设计作业班级： 09计算机班 组员： 梁新新 数理逻辑的应用参考文献：1离散数学耿素云、屈婉玲、张立昂编著清华大学出版社2离散数学及其应用美Kenneth H.Rosen著机械工业出版社3/gxlw/index.html亚洲论文网4 论文网5 中国论文下载中心6 中国知网 摘要离散数学是计算机科学的基础,我们计算机专业的学生学习离散数学是有其现实意义的,可以说它是构筑在数学和计算机科学之间的桥梁，对它的研究离不开数理逻辑。数理逻辑是用数学的方法来研究推理的形式结构和推理规律的数学学科。它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系，并且日益显示它的重要作用和更加广泛的应用前景。数理逻辑的应用十分广泛，本文主要研究其在逻辑门电路设计、布尔查询、计算机程序中的应用。关键字：数理逻辑；逻辑门；电路设计；布尔逻辑；计算机程序1、什么是数理逻辑1.1数理逻辑的概念数理逻辑又称符号逻辑、理论逻辑。它是数学的一个分支，是用数学方法研究逻辑或形式逻辑的学科。其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。数理逻辑是数学基础的一个不可缺少的组成部分。虽然名称中有逻辑两字，但并不属于单纯逻辑学范畴。所谓数学方法就是指数学采用的一般方法，包括使用符号和公式，已有的数学成果和方法，特别是使用形式的公理方法。简而言之，数理逻辑就是精确化、数学化的形式逻辑。它是现代计算机技术的基础。新的时代将是数学大发展的时代，而数理逻辑在其中将会起到很关键的作用。1.2数理逻辑的内容数理逻辑是离散数学中的重要组成部分，它主要包括命题演算和谓词逻辑两部分，现在我们主要来研究一下它这两方面的性质。1.21命题演算命题演算是研究关于命题如何通过一些逻辑连接词构成更复杂的命题以及逻辑推理的方法。命题是指具有具体意义的又能判断它是真还是假的句子。如果我们把命题看作运算的对象，如同代数中的数字、字母或代数式，而把逻辑连接词看作运算符号，就象代数中的“加、减、乘、除”那样，那么由简单命题组成复和命题的过程，就可以当作逻辑运算的过程，也就是命题的演算。这样的逻辑运算也同代数运算一样具有一定的性质，满足一定的运算规律。例如满足交换律、结合律、分配律，同时也满足逻辑上的同一律、吸收律、双否定律、狄摩根定律、三段论定律等等。利用这些定律，我们可以进行逻辑推理，可以简化复和命题，可以推证两个复合命题是不是等价，也就是它们的真值表是不是完全相同等等。命题演算的一个具体模型就是逻辑代数。逻辑代数也叫做开关代数，它的基本运算是逻辑加、逻辑乘和逻辑费，也就是命题演算中的“或”、“与”、“非”，运算对象只有两个数0和1，相当于命题演算中的“真”和“假”。逻辑代数的运算特点如同电路分析中的开和关、高电位和低电位、导电和截至等现象完全一样，都只有两种不同的状态，因此，它在电路分析中得到广泛的应用。利用电子元件可以组成相当于逻辑加、逻辑成和逻辑非的门电路，就是逻辑元件。还能把简单的逻辑元件组成各种逻辑网络，这样任何复杂的逻辑关系都可以有逻辑元件经过适当的组合来实现，从而使电子元件具有逻辑判断的功能。因此，在自动控制方面有重要的应用1.22谓词逻辑谓词演算也叫做命题涵项演算。在谓词演算里，把命题的内部结构分析成具有主词和谓词的逻辑形式，由命题涵项、逻辑连接词和量词构成命题，然后研究这样的命题之间的逻辑推理关系。命题涵项就是指除了含有常项以外还含有变项的逻辑公式。常项是指一些确定的对象或者确定的属性和关系；变项是指一定范围内的任何一个，这个范围叫做变项的变域。命题涵项和命题演算不同，它无所谓真和假。如果以一定的对象概念代替变项，那么命题涵项就成为真的或假的命题了。命题涵项加上全程量词或者存在量词，那么它就成为全称命题或者特称命题了。2、数理逻辑在逻辑门电路设计中的应用2.1逻辑门的概念逻辑门是在集成电路（也称：集成电路）上的基本组件。简单的逻辑门可由晶体管组成。这些晶体管的组合可以使代表两种信号的高低电平在通过它们之后产生高电平或者低电平的信号。高、低电平可以分别代表逻辑上的“真”与“假”或二进制当中的1和0，从而实现逻辑运算。常见的逻辑门包括“与”门，“或”门，“非”门，“异或”门（也称：互斥或）等等。逻辑门可以组合使用实现更为复杂的逻辑运算。以下是逻辑门的符号表：2.2在电路设计中应用数字电路或数字集成电路是由许多的逻辑门组成的复杂电路。它处理的信号是数字信号，因此抗干扰能力强。数字集成电路有各种门电路、触发器以及由它们构成的各种组合逻辑电路和时序逻辑电路。一个数字系统一般由控制部件和运算部件组成，在时脉的驱动下，控制部件控制运算部件完成所要执行的动作。数字电路中研究的主要问题是输出信号的状态（“0”或“1”）和输入信号（“0”或“1”）之间的逻辑关系，既电路的逻辑功能。数字电路的研究方法是逻辑分析和逻辑设计，所需要的工具是逻辑代数。（在正逻辑下，“0”是低电平，“1”是高电平，高低电平没有明确的界限）数理逻辑在电子工程中的电路设计中有广泛应用；这里的0和1表示在数字电路中某一个位的不同状态，典型的是高和低电压。使用包含变量的表达式描述电路，并且对于这些变量的所有的值两个这种表达式是等价的，当且仅当对应的电路有相同的输入-输入行为。进一步的说，每种可能的输入-输出行为都被建模为适合的布尔表达式。基本的逻辑闸比如与闸、或闸、非闸可以单独使用，或者联合成与非闸、或非闸和异或闸来控制数字电子和电路。这些闸的串联或并联控制了运算的优先级。3、数理逻辑在布尔查询中的应用布尔逻辑得名于乔治布尔，他是爱尔兰科克的皇后学院的英国数学家，他在十九世纪中叶首次定义了逻辑的代数系统。现在，布尔逻辑在电子学、计算机硬件和软件中有很多应用。在1937年，克劳德艾尔伍德香农展示了布尔逻辑如何在电子学中使用。使用集合代数作为介绍布尔逻辑的一种方式。还使用文氏图来展示各种布尔逻辑陈述所描述的集合联系。例如：3.1数据库查询关系数据库使用SQL语言，或者其他特定于数据库的语言，来进行查询，它可以包含布尔逻辑。对于这种应用，在表中每个记录都可以被当作集合的元素。例如，在SQL中，下列SELECT语句被用来从在数据库中的表格中检索数据:SELECT*FROMEMPLOYEESWHERELAST_NAME=SmithANDFIRST_NAME=John;SELECT*FROMEMPLOYEESWHERELAST_NAME=SmithORFIRST_NAME=John;SELECT*FROMEMPLOYEESWHERENOTLAST_NAME=Smith;在有多个运算出现的时候，可以使用圆括号来明确的指定布尔运算发生的次序:SELECT*FROMEMPLOYEESWHERE(NOTLAST_NAME=Smith)AND(FIRST_NAME=JohnORFIRST_NAME=Mary);在需要的时候可以使用嵌套的圆括号。联合两个(或更多)表格的任何布尔运算在关系数据库术语中都被称为连接。3.2搜索引擎查询BooleanLogic对于这种应用，在互联网上的每个web页面都被当作是集合的元素。各种在线搜索引擎使用各自不同的语法。下面描述Google使用的语法。逻辑与不使用符号。所以，它是连接两个搜索项的缺省方式:（1）搜索项1搜索项2，使用关键字OR表示逻辑或:搜索项1OR搜索项2。（2）使用减号表示逻辑非:-搜索项1（3）不支持使用圆括号来明确指定运算的次序。4、数理逻辑在计算机程序中的应用离散数学是一门重要的计算机学科，是计算机科学与技术的理论基础，所以又称为计算机数学。说到底，计算机科学与技术就是离散数学的技术。离散数学是计算机的核心课程，一方面，它给后续课程：如数据结构、OS、编译系统、数据库原理、人工智能等提供了必要的数学基础，另一方面，学习离散数学，能提高学生的抽象思维的逻辑推理能力。数理逻辑作为离散数学的一个重要部分在计算机硬件和软件中有很多应用。计算机逻辑描述应用于计算机科学和人工智能的逻辑。它包括：（1）以在计算机科学中的应用为导向的逻辑学研究。例如：组合子逻辑和抽象释义；（2）以逻辑形式自然表达的计算机科学基本概念。例如：编程语言的形式语义，霍尔逻辑和逻辑编程；计算理论的关注形式逻辑的基本问题的方面。例如：Curry-Howard对应和博弈语义；被当作应用计算机科学的逻辑工具。例如：自动定理证明和模型效验。软件(和硬件)开发的形式方法，比如在Z符号中使用谓词逻辑。基本数理逻辑比如命题逻辑和谓词逻辑(通常联合上集合论)的研究被认为是对任何大学计算机科学课程都非常重要的理论基础。高阶逻辑通常不教，但在定理证明工具如HOL中是很重要的。逻辑编程的要点是将正规的逻辑风格带入电脑程式设计之中。需要解答一个问题，通常与解答一个新的假设是否跟现在的理论无冲突等价。逻辑提供了一个证明问题是真还是假的方法。建立证明的方法是人所皆知的，故逻辑是解答问题的可靠方法。逻辑编程系统则自动化了这个程序。人工智能在逻辑编程的发展中发挥了重要的影响。猴子和香蕉问题是逻辑编程社群的著名问题。电脑须自行找出令猴子接触香蕉的可行方法，取代程式设计师指定猴子接触香蕉的路径和方法。逻辑编程建立了描述一个问题里的世界的逻辑模型。逻辑编程的目标是对它的模型建立新的陈述。世界上知识不断澎涨。传统来说，我们会将一个问题陈述成单一的假设。逻辑编程的程式透过证明这个假设在模型里是否为真来解决问题。计算机科目有序整数集合a和b的交集函数问题描述：有两个有序整数集合a和b，写一个函数找出它们的交集？下面是三种几种解决方案：一：import java.util.Arrays;public class Test public static void main(String args)int b = 4, 6, 7, 7, 7, 7, 8, 8, 9, 10, 100, 130, 130, 140, 150;int a = 2, 3, 4, 4, 4, 4, 7, 8, 8, 8, 8, 9, 100, 130, 150, 160;int c = intersect(a, b);System.out.println(Arrays.toString(c);public static int intersect(int a, int b) if(a0 bb.length - 1 | b0 aa.length - 1) return new int0;int intersection = new intMath.max(a.length, b.length);int offset = 0;for(int i = 0, s = i; i a.length & s bs) s+;if(ai = bs) intersectionoffset+ = bs+;while(i (a.length - 1) & ai = ai + 1) i+;if(intersection.length = offset) return intersection;int duplicate = new intoffset;System.arraycopy(intersection, 0, duplicate, 0, offset);return duplicate;二：import java.util.ArrayList;public class jiaojipublic static void main(String args) / TODO Auto-generated method stubint b = 4, 6, 7, 7, 7, 8, 8, 9, 10, 100, 130, 140, 150 ;int a = 2, 3, 4, 4, 4, 7, 8, 8, 8, 8, 9, 100, 130, 150, 160 ;ArrayList c = sect(a, b);for (int i = 0; i bb.length - 1 | b0 aa.length - 1) return new ArrayList();ArrayList arraylist = new ArrayList();for (int i = 0; i a.length; i+) for (int j = startposb; j b.length; j+) if (ai = bj) arraylist.add(k, ai);k+;startposb = j + 1;break;return arraylist;三：import java.util.HashSet;import java.util.Iterator;import java.util.Set;public class NumberCross