该笔记适用于任何版本的数理逻辑！ 绪论 一、数理逻辑研究什么？ ★研究前提和结论的可推导性关系，它是由命题的逻辑形式而非内容所决定的 二、数理逻辑如何研究？ ★形式语言 第一章预备知识 第一节集合 一、集合 1、集合的内涵和外延（所有元素的共同性质/构成集合的所有元素） 2、有序偶和笛卡儿集 二、关系 1、概念：集合S上的n元关系R 2、特殊情况：集合S上的一元关系R（集合S上的性质R） 三、函数（映射） 1、概念：函数（集合＋有序偶＋性质）、定义域dom（f）、值域ran（f） 2、概念：f（x）（函数f在x处的值） 3、概念：f：S－>T（函数f是由S到T的映射）、满射、一一映射 四、等价 1、概念：关系R是集合S上的等价关系（自反＋对称＋传递） 2、概念：元素x的R等价类 3、性质：R等价类对集合S的一个划分（两两不相交，且并为S） 五、基数 1、概念：S～T（两个集合S和T是等势的） 2、概念：集合S的基数|S|（集合中的元素个数） 3、概念：可数无限集
第二节归纳定义和归纳证明 一、归纳定义 1、集合的归纳定义 ⑴、直接生成某些元素 ⑵、给出运算，将其作用在已有元素上，以产生新的元素 ⑶、只有这样才是集合中的元素，除此之外，再也没有了 2、典例：自然数集N的两个归纳定义 二、归纳证明 1、归纳定理：设R是一个性质，如果 ⑴、R（0） ⑵、对于任何n∈N，如果R（n），则R（n’） 那么，对于任何n∈N，都有R（n） 2、概念：归纳基础、归纳步骤（包括归纳变元和归纳假设）、归纳命题、归纳证明 3、概念：串值归纳法及其变形 三、递归定义 1、递归定义（在归纳定义的集合上，定义函数） 在自然数集N上定义一个这样的函数f：g，h是N上的已知函数 f（0）＝g（0） f（n’）＝h（f（n）） 2、递归定义原理（这样的函数是存在而且唯一的）
逻辑推理（一） 专题简析： 逻辑推理题不涉及数据，也没有几何图形，只涉及一些相互关联的条件。它依据逻辑汇率，从一定的前提出发，通过一系列的推理来获取某种结论。 解决这类问题常用的方法有：直接法、假设法、排除法、图解法和列表法等。 逻辑推理问题的解决，需要我们深入地理解条件和结论，分析关键所在，找到突破口，进行合情合理的推理，最后作出正确的判断。 推理的过程中往往需要交替运用“排除法”和“反正法”。要善于借助表格，把已知条件和推出的中间结论及时填入表格内。填表时，对正确的（或不正确的）结果要及时注上“√”（或“×”），也可以分别用“1”或“0”代替，以免引起遗忘或混乱，从而影响推理的速度。 推理的过程，必须要有充足的理由或重复内的根据，并常常伴随着论证、推理，论证的才能不是天生的，而是在不断的实践活动中逐渐锻炼、培养出来的。 例题1： 星期一早晨，王老师走进教室，发现教室里的坏桌凳都修好了。传达室人员告诉他：这是班里四个住校学生中的一个做的好事。于是，王老师把许兵、李平、刘成、张明这四个住校学生找来了解。 （1）许兵说：桌凳不是我修的。 （2）李平说：桌凳是张明修的。 （3）刘成说：桌凳是李平修的。 （4）张明说：我没有修过桌凳。 后经了解，四人中只有一个人说的是真话。请问：桌凳是谁修的？ 根据“两个互相否定的思想不能同真”可知：（2）、（4）不能同真，必有一假。 假设（2）说真话，则（4）为假话，即张明修过桌凳。 又根据题目条件了：只有1人说的是真话：可退知：（1）和（3）都是假话。由（1）说的可退出：桌凳是许兵修的。这样，许兵和张明都修过桌凳，这与题中“四个人中只有一个人说的是真话”相矛盾。 因此，开头假设不成立，所以，（2）李平说的为假话。由此可退知（4）张明说了真话，则许兵、刘成说了假话。所以桌凳是许兵修的。 练习1： 1、小华、小红、小明三人中，有一人在数学竞赛中得了奖。老师问他们谁是获奖者，小华说是小红，小红说不是我，小明也说不是我。如果他们当中只有一人说了真话。那么，谁是获奖者？ 2、一位警察，抓获4个盗窃嫌疑犯A、B、C、D，他们的供词如下： A说：“不是我偷的”。 B说：“是A偷的”。 C说：“不是我”。 D说：“是B偷的”。 他们4人中只有一人说的是真话。你知道谁是小偷吗？ 3、有500人聚会，其中至少有一人说假话，这500人里任意两个人总有一个说真话。说真话的有多少人？说假话的有多少人？ 例题2： 虹桥小学举行科技知识竞赛，同学们对一贯刻苦学习、爱好读书的四名学生的成绩作了
数理逻辑的心得 数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。是大四接触到的，现简单介绍一下数理逻辑的发展史，算是一点感悟吧 1数理逻辑的发展前期 ·前史时期——古典形式逻辑时期：亚里斯多德的直言三段论理论 ·初创时期——逻辑代数时期（17世纪末） ·资本主义生产力大发展，自然科学取得了长足的进步，数学在认识自然、发展技术方面起到了相当重要的作用。 ·人们希望使用数学的方法来研究思维，把思维过程转换为数学的计算。 ·莱布尼兹(Leibniz, 1646~1716)完善三段论，提出了建立数理逻辑或者说理性演算的思想： ·提出将推理的正确性化归于计算，这种演算能使人们的推理不依赖于对推理过程中的命题的含义内容的思考，将推理的规则变为演算的规则。 ·使用一种符号语言来代替自然语言对演算进行描述，将符号的形式和其含义分开。使得演算从很大程度上取决与符号的组合规律，而与其含义无关。 ·布尔(G. Boole, 1815~1864)代数：将有关数学运算的研究的代数系统推广到逻辑领域，布尔代数既是一种代数系统，也是一种逻辑演算。 数理逻辑的奠基时期 ·弗雷格(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)的模态逻辑，实质蕴涵怪论和严格蕴涵、相干逻辑等，卢卡西维茨的多值逻辑等。 集合论的悖论使得人们觉得数学产生了第三次危机，提出了数学的基础到底是什么这样的问题。 ·罗素等的逻辑主义：数学的基础是逻辑，倡导一切数学可从逻辑符号推出，《数学原理》一书是他们这一思想的体现。为解决悖论产生了逻辑类型论。 ·布劳维尔(Brouwer, 1881~1966)的直觉主义：数学是心灵的构造，只承认可构造的数学，强调构造的能行性，与计算机科学有重要的联系。坚持潜无穷，强调排中律不能用于无穷集合。海丁(Heyting)的直觉主义逻辑。 ·希尔伯特(D. Hilbert)的形式主义：公理化方法与形式化方法，元数学和证明论，提倡将逻辑演算和数学证明本身形式化，把用普通的语言传达的内容上的数学科学变为用数学符号和逻辑符号按一定法则排列的一堆公式。为了消除悖论，要数学建立在公理化基础上，将
离散数学 期中课程设计作业 班级：10级计算机 组员：杨鑫 学号：09
数理逻辑怎样用于实际的应用 我们现在在学离散数学,对于离散数学中的数理逻辑这一部分存在很多盲点,那么这看似高深莫测的数理逻辑在实际生活中有着怎样的用处呢,下面让我们来讨论一下. 我们先看数理逻辑的定义:数理逻辑又称符号逻辑、理论逻辑。它既是数学的一个分支，也是逻辑学的一个分支。是用数学方法研究逻辑或形式逻辑的学科。其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。数理逻辑是数学基础的一个不可缺少的组成部分。虽然名称中有逻辑两字，但并不属于单纯逻辑学范畴。数理逻辑是用数学的方法来研究推理的形式结构和推理规律的数学学科，它与数学的其他分支，计算机科学，人工智能，语言学等学科有密切的联系，并且日益显示出它的主要作用和更加广泛的应用前景. 数理逻辑中的逻辑运算又称布尔运算，它是用数学的方法解决或研究逻辑问题，即用离散的符号“1”和“0”表示逻辑中的“真”和“假”再加上一套与之相关的“与”、“或”、“非”为运算基础的逻辑运算规则解决实际逻辑问题的方法，从而实现复杂逻辑运算到简单的数值计算的转化。下面我们就逻辑运算在电路设计中的运用加以探讨： 某公司王某欲搬入新房，搬迁前需要完成电路的设计安装，由于该房深处闹市，四周楼房林立，严重影响了客厅的采光，于是王某想设计一个电路，要求客厅四盏灯由一个开关控制，开关按下一次亮一盏灯，再按一下亮两盏，以此类推，直到按下第五次时所有灯熄灭。假设四个灯依次为A、B、C、D，灯亮为1，灯灭为0，开关有脉冲输入为1，否则为0，则根据题意可得真值表（如图１）： 设第ｎ号灯的上一状态为Nｎ，第ｎ＋１号灯现在在的状态为Nｎ＋１，脉冲输入状态为M，则有： Nｎ＋１=Nｎ∧M（N0与M的且运算） 其中Ｎｎ＝ＮＡ∧ＮＢ．．．∧Ｎｎ－１ 灯亮的条件为（A∧┐B∧┐C∧┐D）∨（A∧B∧┐C∧┐D）∨（A∧B∧C∧┐D）∨（A∧B∧C∧D） 如Ｂ灯亮的条件是Ａ灯亮并且有脉冲输入，C灯亮的条件是ＡＢ都亮并且有脉冲输入。该电路功能由一个与门电路和一个计数触发器连接即可完成，当开关第5次输入后计数器输出信号置0，灯全部关闭，此时设备全部复位。如图２。
数理逻辑的现实意义 摘要：数理逻辑并不仅仅局限于抽象的符号运算，它同样可以帮助我们了解和解决很多现实问题。数理逻辑在写作、创新思维、人工智能应用等方面有着重要的作用。运用逻辑性思维能使我们正确的选题与写作；它与一个人的创新能力有着极为密切的关系；同时也是人工智能科学发展必不可少的。 关键词：数理逻辑写作创新思维人工智能 大多数人都认为数理逻辑是一门艰深、抽象甚至有点枯燥的学科,这一点也许除了很少一些从事数理逻辑研究的专家会反对。但是，在我们的生活中，数理逻辑也有着重要的现实意义。数理逻辑是用数学方法研究思维形式的逻辑结构及其规律的学科。所谓数学方法，是指用一套表意符号即形式语言系统表达思维的形式结构和规律，从而把对思维的研究转化为对符号的研究。以便摆脱自然语言的歧义性，构成能像算术或代数那样的严格精确的演算系统。由于它运用了数学方法来研究逻辑和数学基础，本身成为数学的一个分支，同时又由于它的基本研究对象仍然以逻辑为主，因而，作为现代化的逻辑, 它又渗透到现代数学的各个分支中。集论的深入研究必须严格地运用数理逻辑作为重要的工具，这不用多说翻开现代数学的各种教程，映入眼帘的是许许多多数理逻辑的符号和表示式。如果没有数理逻辑的初步知识，一些新出版的教科书和刊物上的论文就根本没法读。一个定理的证明，用古典数学的表达方法常常是不十分精确而且有时是冗长的，而用数理逻辑来进行证明，那就简明而且精确严密得多了。现代数学各大分支基本上都用了公理方法，于是，数理逻辑就更成为不可或缺的工具了。 一、数理逻辑在写作中的应用 从逻辑角度看，数理逻辑也是研究演绎的科学，演绎方法包括演绎推理，以演绎推理为基础的证明和公理方法。从根本上讲它是传统逻辑的发展，是现代的精确的形式逻辑。演泽推理是指由一般性的前提推出特殊的结论的推理。推理能力的强弱，直接关系到论文说理是否透彻，分析是否具体，论证是否严密，文章是否更具有逻辑性和说服力。因此，逻辑推理能力在论文写作中至关重要。在选题、立意、结构、表述中运用概念和判断进行推理的过程，也就构成了一个完整的形式逻辑思维运行的过程。而写作活动本身就是一种思维活动，而且对思维的要求比较高。一篇论文的写作总有几个步骤，即从纷繁的材料和模糊的意念中，经过抽象概括，使思维明确化，选择一个合适的选题；接着对资料加以深入分析，形成层次；最后，构建论文结构，表述论文思想。事实上，论文写作过程就是一
数理逻辑介绍 1.若干哲学观点 分析哲学也称为语言哲学和逻辑哲学，开始于德国数学家弗雷格对于自然语言的逻辑分析工作，后被奥地利哲学家维特根斯坦发扬光大，使得近代哲学研究成功转型为语言分析，并成为现代哲学研究的主流。学习分析哲学有利于澄清我们对于一些常用概念的认识。以下所列条目是基于本人的理解和独立思考而提出的观点，欢迎批评、指正。 认知对象：客观世界中存在的事物，这是第一认知对象。人们在认知过程中所形成的抽象概念是第二认知对象。概念是人们头脑中的观念，所反映的是对象的相似性（similarity）和不变性（invariance），也称为模式（mode），包括结构模式、行为模式和关系模式。这些抽象模式称为概念的内涵（intension）或者所指（referent）。概念是人们对于客观对象进行抽象所得的观念。一旦形成就拥有不依赖于客观对象的独立存在性。例如，“圆”这个概念来自于客观事物，又超越和独立于客观事物，有自己确定的内涵。因此，概念不是客观事物的附属，而是思维世界中的独立存在。柏拉图（Plato）称之为理念（idea），并且认为理念是独立于物质世界的另一种存在。概念是没有真假对错之分的，它是一个模式，按照该模式可以对现实对象进行归类。例如，我们可以用圆这个概念对事物进行归类，将所有近似圆形的事物归为一类。同类事物具有相同的性质，相同的性质具有相同的作用。因此，对事物进行归类有利于我们有效地认识和应用事物。当然，我们的认知并不满足于获得一些概念，还会继续探索这些概念的属性和相互作用，等等。因此，概念是人类认知的结果，也是进一步认知的对象。 命题：在思维中将某对象归于某模式，即认为某对象具有某性质或者模式，这种思维中的归属联系就是命题。因此，命题也是人们头脑中的一种观念，不过，命题与概念不同，它不是一种模式，不是由客观对象身上升华而成的模式，而仅仅是将一个给定对象与某概念进行联接，将对象归于这个概念所划定的类。如果说概念是进行思维概括操作的结果，那么命题可以说是简单的思维联接操作的结果。因此，命题是有真假对错之分的。如果命题所指代的归属关系是客观存在的，则该命题为真（true），否则为假（false）。 语言：是一个符号系统，用于表达和记录思维中的概念和命题。语言由符号（symbol）和语法（grammar）组成。语法是符号组成语句的规则。语句的功能就是描述我们思维中的概念和命题。在语言中，概念通常用一个简短的名字进行表示，称为词语（word），比较复杂的概念往往用固定词组（set phrase）表示。一个词语所表示的概念称为词语的含义（meaning）或者语义（semanteme）。在一个语言中，定义一个概念就是用词语和句子对概念内涵进行充分而明确地描述。仅仅是表达一个命题的句子称为陈述句（statement），被表达的命题称为该陈述句的语义（semanteme）或者含义（meaning）。有些感叹句、反问句其实也表达了命题，但是它们还有其它的语用表达功能，包括传递说话人的情感、意愿等等。需要注意的是，并非任何陈述句都表达一个命题。例如，“我正在说假话”是陈述句，但其所表达的语义不是命题。 思考：“今天是星期一”所表达的是命题吗？ 语句分析：弗雷格将一个句子的成分分为主词、谓词和量词等三个部分。主词表示对象。谓词表示对象的性质、状态和动作，相当于定语和谓语（把状语和补语视为谓语的一部分）。量词用以表示主词所表示的对象的数量，只有两种，即全称量词和存在量词，分别表示“所有”和“存在”。例如，“有的果子成熟了更可口”，其中量词是“有的”，主词是“果子”，谓词有两个，即“成熟了”和“更可口”。我们将要学习的一阶逻辑是对弗雷格的这种 1
数理逻辑发展史 *数理逻辑主要包括5个部分: 逻辑演算, 证明论, 公理集合论, 递归论和模型论. *数理逻辑从十七世纪末叶莱布尼茨(G. Leibniz, 1646-1716, 德国)起, 至今约有三百年历史. *数理逻辑的发展分为三阶段. *第一阶段: 这是开始用数学方法研究和处理形式逻辑的时期, 是初始阶段. *莱布尼茨: 1646-1716, 德国 *布尔(G. Boole): 1815-1864, 英国 *德?摩根(A. De Morgan): 1806-1876, 英国 *E. Schr?der: 1841-1902, 德国 共延续二百年, 其成果是逻辑代数和关系逻辑. *戈特弗里德?威廉?莱布尼茨(Gottfried Wilhelm Leibniz) 莱布尼茨生于莱比锡, 他的母亲是莱比锡大学哲学系副主任的第三个妻子. 虽然他的父亲在他6岁时就已去世, 但年幼的莱布尼茨经过父亲的谆谆教诲, 已经产生了读书和学习的愿望. 在他年轻时,他就自学了拉丁语并钻研了拉丁文的经典著作以及他父亲丰富藏书中的哲学和神学著作. 1661年, 他进入莱比锡大学学习, 在那里他用大部分时间学习哲学.他在1663年取得学士学位, 在1664年取得硕士学位, 但是
尽管准备了法学博士的学位论文, 大学却拒绝授予他学位, 也许因为教师中的一些政治问题. 莱布尼茨因此离开了莱比锡并于1667年从纽伦堡的阿尔特多夫大学取得了学位. 同时, 莱布尼茨在1663年在耶纳大学的一次短暂停留中接触到了高等数学, 并开始研究他希望是他对哲学最具创造性的贡献的细节问题, 创立一种人类思想的字母表, 即一种将所有基本概念用符号表示并通过符号的组合表示更复杂的思想的方法. 尽管莱布尼茨从未完成这一规划, 他的最初思想包含在他1666年的《论组合的艺术》里, 他在论文中独立推导出了帕斯卡的算术三角形以及其中包含的量的各种关系. 但这一寻找表达思想的适当符号和组合它们的方式的兴趣最终使他发明了我们今天使用的微积分的符号. 莱布尼茨结束大学学业后不久, 他首先为美茵茨选帝侯从事外交方面的工作, 而在他以后的生涯的大部分时间他是汉诺威公爵的顾问. 虽然有许多时期他的工作使他极为忙碌, 但他总能找到时间钻研数学思想并在这一领域同遍及欧洲的同事们维持着活跃的通信交流.
3命题逻辑形式系统（FSPC） 3.1 命题逻辑与命题演算 Leibniz提出逻辑推理变成符号演算不久，英国数学家BOOL提出了布尔代数。布尔代数把逻辑命题与逻辑推理归结为代数计算。把命题看作是计算对象；把联结词看作算子；讨论计算的性质。 1、命题（Propositions）：可以判断真假的陈述句。不涉及任何联结词的命题称为原 子命题。 2、联结词：?, →, ?, ∨, ∧为联结词，用于联结一个或者多个命题。 ~A=1-A →如果A成立则B成立，<->如果A成立则B成立，并且如果B成立则A成立； A→B A∨B，或者A成立或者B成立；A∧B，A成立并且B成立。 3、真值表：命题的真假称为命题的真值，用0表示假；用1表示真。 A←→B T(~A)=1-T(A) A=1, ~A=0, 1-A True(?A)＝1- True(A)，如果True(A)＝0，True(?A)=1：True(A)=1, True(?A) ＝0 T(A→B)=1 或者A不成立，或者B成立； A=1, B=1, A→B =1 A=0, B=1, A→B=1 A=0, B=0, A→B=1 A=1,B=0 A→B=0 或者A=0, 或者B＝1 ~AvB=A→B A<=B;;;; A<=B A=0,B=1 A=0时，B=?,1;A=1,B=1,1;A=1,B=0,0; A=0,B=0,T(A→B)=1;A=0,B=1,T(A→B)=1;A=1,B=0,T(A→B)=1;A=1,B=1,T(A→B) =1; A=0;T(A→B)=1 B=1;T(A→B)=1 A→B是或者A=0,或者B=1；=～AvB A<=B A∨B=MAX(A,B) A=1, B=0, 1;A=1,B=1, 1, A=0,B=1;1, A=0,B=0, 0 A∧B=MIN(A,B) =~(~A v ~B) DEMORGAN ~A ∨B True(A->B)：True（A）《＝True（B）
第一章数理逻辑 逻辑思维（又称抽象思维）是人运用概念、判断和推理反映事物本质与规律的认识过程（图1.1），它是人类特有的能力，是人类文明延绵不绝、科学技术持续进步的原动力。具备较强的逻辑思维能力是学习科技知识、进行科学研究、从事技术开发的先决条件。逻辑思维在信息科学技术领域显得尤为重要，只有具备强大的逻辑思维能力，才能胜任该领域的研究工作，才能胜任大型复杂软件的编写与调试工作。 图1.1. 逻辑思维 第一节逻辑学概论 逻辑思维是有规律的，逻辑学是专门研究逻辑思维规律性的学科。本节简述逻辑学的基本内容和发展历史。 1.1. 逻辑思维的基本规律 逻辑思维的作用，就是根据一定的前提，通过合理的推导，得到
一定的结论。 例1.1．苏格拉底是柏拉图的导师，柏拉图是亚里士多德的导师，因此，苏格拉底是亚里士多德的师爷。 分析：苏格拉底、柏拉图和亚里士多德是人类文明史上著名的哲学家，有着师徒传承关系。这是一个逻辑思维过程，其作用就是根据‘苏格拉底是柏拉图的导师’和‘柏拉图是亚里士多德的导师’这两个前提，得到‘苏格拉底是亚里士多德的师爷’这个结论。 例1.2. 子非鱼，安知鱼之乐？ 分析：这是惠子对庄子说的一句话。可以将这句话改写为‘你不是鱼，所以你不知道鱼的快乐’，这是一个逻辑思维过程，其作用就是根据‘你不是鱼’这个前提，导出‘你不知道鱼的快乐’这个结论。 逻辑学之父亚里士多德总结出了逻辑思维的以下四条基本规律。 表1.1. 逻辑思维的四条基本规律 下面来看看不满足这些基本规律的实例。 例1.3. 有个小伙子上了火车，一看座无虚席，就厚着脸皮硬往一位老
大爷身边挤座儿。老大爷不高兴了，说：“小伙子，别硬坐了，座位已经满了。”小伙子嘻皮笑脸地说：“老大爷，没办法,我买的就是硬坐票。”分析：这个小伙子在说话时故意把“硬座”变换成“硬坐”，这是偷换概念，违背了同一律。 图1.2. 自相矛盾 例1.4．楚国有个卖兵器的人在街上叫卖。他说：“我的矛是最锋利的，能刺穿任何东西。”他又说：“我的盾是最坚固的，不能被任何东西刺穿。”这时，人群中有人问道：“如果用你的矛去戳你的盾，会怎么样呢？”楚人听后哑口无言。 分析：假设楚人说的两句话都是真的，就可以做以下推理：一方面，因为‘楚人的矛能刺穿任何东西’，所以‘楚人的矛能刺穿楚人的盾’；另一方面，因为‘楚人的盾不能被任何东西刺穿’，所以‘楚人的矛不能刺穿楚人的盾’。这样一来，就得到了两个相互矛盾的结论，根据矛盾律，这两个结论不可能同时为真，因此，楚人的话至少有一句是假的。 例1.5．有个人说：“‘华盛顿是第一任美国总统’是不对的，‘华盛顿
简单逻辑推理练习 1. 丁丁、光光和园园三位小朋友分别出生在上海、北京和广州三个城市中。已知：（1）丁丁从未到过上海；（2）上海出生的小朋友不叫光光；（3）光光不出生在广州。问：三个小朋友 2. （1）每个老师只教一门课；（2）甲上课全用汉语；（3）外语老师是一个学生的哥哥；（4）丙是一位女教师，她比数学老师活泼。请问：三位老师各上什么课？ 3.图中有三个六面体，每一个六面体上A 、B 、C 、D 、E 、F 六个字母的排列顺序完全相同。判断图中A 、B 、C 三个字母的对面各是什么字母。 （1） （2） （3） A 对面是_________; B 对面是_________; C 对面是_________. 4.甲、乙、丙、丁四位同学进行一百米赛跑。赛后，甲、乙、丙三位同学说了以下几句话，丁没有说话。甲：丙第一名，我第三名；乙：我第一名，丁第四名；丙：丁第二名，我第三名。比赛成绩公布后，发现他们都只说对了一半，你能说出他们的名次是如何排列的吗？ 名次排列是_______________________________ 5. 小王、小张和小李原来是邻居，后来当了医生、 教师和战士。只知道：小李比战士年纪大，小王和教师比小张年龄小。请同学们想一想：谁是医生，谁是教师，谁是战士？ 6. 数学竞赛后，小明、小华和小强各获得一枚奖牌，其中一人得金牌，一人得银牌，一人得铜牌。老师猜测：“小明得金牌，小华不得金牌，小强不得铜牌。”结果老师只猜对了一个，那么谁得金牌，谁得银牌，谁得铜牌？ 金牌是________;银牌是________;铜牌是________。
7.三年级三个班级举行数学竞赛。小明猜想比赛的结果是：2班第一名，1班第二名，3班第三名；小华猜想的比赛名次是：1班，2班，3班。比赛结果只有小华猜的2班第二名是对的。 问比赛的名次如何排列？ 第一名是_________;第二名是_________;第三名是_________。 8.图中四个相同的正方体按相同的顺序在上面写数字1～6， 然后加图叠加，问1、2、3的对面分别是什么数字？ 1对面是_________;2对面是_________;3对面是_________ 9.甲、乙、丙、丁四人进行游泳比赛。赛前名次众说不一。 有的说：甲第二名，丁第三名。 有的说：甲第一名，丁第二名。 有的说：丙第二名，丁第四名。 实际上，上面三种说法各对了一半。问甲、乙、丙、丁各是第几名。 10.学校举行数学比赛，甲、乙、丙、丁、戊五位老师，对一贯刻苦学习的A 、B 、C 、D 、E 五位同学，事先就作了如下的估计：老师甲：B 第三名，C 第五名；老师乙：E 第四名，D 第五名；老师丙：A 第一名，E 第四名；老师丁：C 第一名，B 第二名；老师戊：A 第三名，D 第四名。比赛结束扣，这五名学生果然是前五名，且每一个名次，都有老师猜中了。试求各人的名次。 比赛名次：第一名是____;第二名是____;第三名是____第四名是____;第五名是____。 11.赵老师不在的时候，有一名同学把拾到的手表放在老师的办公桌上。大家都知道，这是冬冬、丹丹和菲菲三人中的一个人做的好事。教师找他们三人来问：“这是谁做的好事呢？” 冬冬说：“是丹丹干的。”丹丹说：“不是我干的。”菲菲也说：“不是我干的。” 如果他们三人中，有两人说的是假话，只有一个人说的是真话，你能判断出好事是谁干的吗？ _____和______的话是相互矛盾，所以他们两人的话必有一真。 那么______说的话一定是假话，所以做好事的是______。 12.有三个颜色分别是红、黄、蓝的盒子，每只盒子外面各有一句话（如下图所示），这三句话中只有一句是真的，你能判断出宝石放在哪个盒子里吗？ _____和______的盒子外面的一句话是相互矛盾，所以他们两人的话必有一真。 那么______的盒子外面的一句话一定是假话，所以宝石放是在______。 1 3 1 5 2 2 4 1 4
大学研究生学位课程论文论文题目：学习数理逻辑的意义
摘要：数理逻辑就是用数学方法研究思维形式的逻辑结构及其规律的科学。数理逻辑发展到今天，已经成熟为一门崭新的科学，具有强大的生命力和广泛的影响。学习数理逻辑可直接提高数理逻辑智能，如有利于学生思维能力的增强、思维效率的提高和创新能力的提升。数理逻辑在数学、计算机科学、语言研究、哲学等领域都已应用，数理逻辑学的任务在于探讨如何为整个数学建立严格的逻辑基础，其特点在于使用形式化的方法包括公理化的方法，因而比较抽象和艰深。本文介绍了数理逻辑的产生，数理逻辑主要贡献者的思想，数理逻辑的应用及学习数理逻辑学的意义。 关键词：数理逻辑；逻辑演算；应用 数理逻辑是一门新兴学科，至今有300年的历史。近百年来，它取得了长足发展。在现代的数学和计算机科学中以及在自然科学和社会科学的一些部门中都有广泛应用。在这样的背景下来研究数理逻辑的产生和发展，具有十分重要的意义。数理逻辑是用特制符号和数学方法来研究、处理演绎方法的逻辑学，包括各种逻辑演算（经典的和非经典的）和“四论”模型论、集合论、递归论和证明论。数理逻辑的定义:数理逻辑是用数学方法研究诸如推理的有效性、证明的真实性、数学的真理性和计算的可行性等这类问题中的逻辑问题的一门学问.当然，对此也可等价地这样说:数理逻辑是用数学方法研究各种推理中之逻辑问题的一门学问.其中主要包括推理的有效性、证明的真实性、数学的真理性、计算的能行性等这类问题中的逻辑问题.数理逻辑的研究对象:数理逻辑以推理本身作为自己的研究对象，其中主要包括演绎推理、形式推理、数学推理和各种近现代的非经典推理.数理逻辑的研究领域:作为数理逻辑之研究领域的历史性确认部分包括逻辑演算、集合论、模型论、递归论和证明论等五大块.但作为数理逻辑研究领域之近现代发展部分，还应包括诸如模态逻辑、多值逻辑、非单调逻辑、归纳逻辑、似然逻辑、不协调逻辑、信念修正、开放逻辑、中介逻辑和中介公理集合论等等各种各样的非经典逻辑分支.数理逻辑的学科归属:数理逻辑是逻辑和数学互相交织在一起的一门边缘性学科，或者说，数理逻辑既是一门逻辑化了的数学分科，又是一个数学化了的逻辑分支。 那么数理逻辑的的主要基础是什么？逻辑是研究推理的科学，分为形式逻辑和辨证逻辑。数理逻辑开始于用数学方法对形式逻辑中推理规律的研究，后来进一步发展到对数学中基础性问题及逻辑性问题的研究。现在数理逻辑是用数学方法研究形式逻辑的一门科学，也就是用数学方法研究推理的科学。所谓数学方法［1］，主要是指引进一套符号体系的方法，因此数理逻辑又叫符号逻辑。现代数理逻辑主要有四大分支：证明论、模型论、递归论和公
1 逻辑运算 逻辑运算又称布尔运算，它是用数学的方法解决或研究逻辑问题，即用离散的符号“1”和“0”表示逻辑中的“真”和“假”再加上一套与之相关的“与”、“或”、“非”为运算基础的逻辑运算规则解决实际逻辑问题的方法，从而实现复杂逻辑运算到简单的数值计算的转化。 尽管互联网的查询系统原理各不相同，但使用与（&）、或（||）、非（-）通配符的查词方法却是一致的，这便是逻辑运算的最好例子。下面我们就逻辑运算在电路设计中的运用加以探讨： 某公司王某欲搬入新房，搬迁前需要完成电路的设计安装，由于该房深处闹市，四周楼房林立，严重影响了客厅的采光，于是王某想设计一个电路，要求客厅四盏灯由一个开关控制，开关按下一次亮一盏灯，再按一下亮两盏，以此类推，直到按下第五次时所有灯熄灭。假设四个灯依次为A、B、C、D，灯亮为1，灯灭为0，开关有脉冲输入为1，否则为0，则根据题意可得真值表（如图１）： 设第ｎ号灯的上一状态为Nｎ，第ｎ＋１号灯现在在的状态为Nｎ＋１，脉冲输入状态为M，则有： Nｎ＋１=Nｎ∧M（N0与M的且运算） 其中Ｎｎ＝ＮＡ∧ＮＢ．．．∧Ｎｎ－１ 灯亮的条件为（A∧┐B∧┐C∧┐D）∨（A∧B∧┐C∧┐D）∨（A∧B∧C∧┐D）∨（A∧B ∧C∧D） 如Ｂ灯亮的条件是Ａ灯亮并且有脉冲输入，C灯亮的条件是ＡＢ都亮并且有脉冲输入。该电路功能由一个与门电路和一个计数触发器连接即可完成，当开关第5次输入后计数器输出信号置0，灯全部关闭，此时设备全部复位。如图２。 2 范式理论 范式是逻辑运算符号化表示的一种标准表达形式，根据这种方法，把同一类型中尽可能出现的命题变相以及具有完整功能的符号化内容通过合、析取的方式联合在一起，而不改变其逻辑功能。 甲、乙、丙、丁四个人有且只有两个人参加围棋比赛。关于谁参加比赛，下列四个判断都是正确的： (1)甲和乙只有一人参加比赛。 (2)丙参加，丁必参加。 (3)乙或丁至多参加一人。
第七讲简单的逻辑推理问题 年级（）姓名（）在日常生活中，有些问题不需要或很少需要用很多的数学知识和计算方法去解决，而是要求我们通过分析和推理，给出正确的估计。我们把这类问题叫做“逻辑推理”。在解决这类问题时，需要我们根据已知条件仔细分析，认真地推理。在解题时，我们往往需要找到解题的突破口，从突破口入手，用假设的方法来逐一验证，从而找到真正的结论。在这一节中，我们将对一些简单的情况进行推理分析。 例题精讲 例1、张明是张海的弟弟，张江是张河的哥哥，张江是张明的父亲，张河是张海的什么人？ 例2、三个小朋友，小芬、小丽和小壮在谈论谁的个子高。 小芬说“小丽比小壮高” 小丽说“小芬比小壮高” 小壮说“小芬比小丽矮” 这三位小朋友谁的个子最高？谁的个子最矮？ 例3、有A、B、C三个人，在这三个人中，一位是工人，一位是战士，一位是运动员，现知道C的年龄比战士大，A和运动员的年龄不同，运动员的年龄比B小，问这三个人各是什么人？
例4、第五组4个小朋友在交作业时少交了一个人的作业本，老师分别问了他们四人：甲说“没交作业的人在乙、丙、丁三人之中” 乙说“是丙没有交” 丙说“在甲和丁中有一个人没交作业” 丁说“乙说的是真的” 经过证实，四人中有两人说对了，两人说错了，你知道是谁没有交作业吗？ 小试牛刀： 1、刘刚、马辉、李强三个男孩各有一个妹妹，六个人进行乒乓球混合双打比赛．事先规定：兄妹二人不许搭伴．第一盘：刘刚和小丽对李强和小英；第二盘：李强和小红对刘刚和马辉的妹妹．问：三个男孩的妹妹分别是谁？ 2、王文、张贝、李丽分别是跳伞、田径、游泳运动员，现在知道：⑴张贝从未上过天；⑵跳伞运动员已得过两块金牌；⑶李丽还未得过第一名，她与田径运动员同年出生.请根据上述情况判断王文、张贝、李丽各是什么运动员？
第一讲引言 一、课程内容 ·数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。 ·集合论：数学的基础，对于学习程序设计、数据结构、编译原理等几乎所有计算机专业课程和数学课程都很有用处。熟练掌握有关集合、函数、关系等基本概念。 ·代数结构：对于抽象数据类型、形式语义的研究很有用处。培养数学思维，将以前学过的知识系统化、形式化和抽象化。熟练掌握有关代数系统的基本概念，以及群、环、域等代数结构的基本知识。 ·图论：对于解决许多实际问题很有用处，对于学习数据结构、编译原理课程也很有帮助。要求掌握有关图、树的基本概念，以及如何将图论用于实际问题的解决，并培养其使用数学工具建立模型的思维方式。 ·讲课时间为两个学期，第一学期讲授数理逻辑与集合论，第二学期讲授代数结构和图论。考试内容限于书中的内容和难度，但讲课内容不限于书中的内容和难度。 二、数理逻辑发展史 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)的模态逻辑，实质蕴涵怪论和严格蕴涵、
数理逻辑1-2章自测-填空题 填空题 1若且则称X是公式A的子公式. 答案：〔X是公式A的一部分；X本身也是公式〕 2写出下列表中各列所定义的命题联结词 P Q P Q P Q T T T F T F F T F T F T F F F T 答案：〔∧；↑〕 3P、Q为两个命题,当且仅当时,P∧Q的真值为T;当且仅当时, P∨Q的真值为F. 答案：〔P、Q的真值都为T； P、Q的真值都为F 〕 4由n个命题变元可组成不等值的命题公式. 答案：〔2（2）n〕 5两个重言式的析取是 ,一个重言式与一个矛盾式的析取是 . 答案：〔重言式；重言式〕 6给定命题公式A、B，若 ,则称A和B是逻辑等值的，记为A?B. 答案：〔给定A、B中原子变元P1……，P n任意一组赋值，A和B的真值相同〕 7A、B为两个命题公式，A?B当且仅当，A?B当且仅当 . 答案：〔A?B是重言式； A→B是重言式〕 8将P、Q为两个命题，德摩根律可表示为，吸收律可表示为 . 答案：〔┐(P∧Q)?┐P∨┐Q，┐(P∨Q)?┐P∧┐Q； P∧(P∨Q)?P, P∨(P∧Q)?P. 9公式(P∨Q)→R的只含联结词┐、∧的等值式为 . 答案：┐(┐(┐P∧┐Q) ∧┐R ) 10P、Q为两个命题，当且仅当时，P→Q的真值为F. 答案：〔P为T，Q为F 〕 11全体极大项的合取为式，全体极小项的析取式必为式. 答案：〔矛盾；重言〕 12公式┐P→Q的反换式为，逆反式为 . 答案：〔Q →┐P ；┐Q → P 〕 〕 13命题公式┐(P→Q)的主析取范式为，主合取范式的编码表示为 . 答案： P∧┐Q ； M00∧M01∧M11 14已知公式A(P，Q，R)的主合取范式为M0∧M3∧M5，它的主析取范式为(写成编码形式) . 答案：〔m001∨m010∨m100∨m110∨m111〕 15 命题公式┐(P?Q)的主析取范式为，主合取式的编码表示为 . 答案：〔 (P∧┐Q)∨(┐P∧Q)； M00∧M11〕
总复习 本章对高级数理逻辑所讲述的内容总结，并对已经学习的内容进行回顾。在对所讲述的内容回顾之前，首先对整个数理逻辑学科的组成进行回顾，从而使大家有更深刻的认识。 数理逻辑学科 学科发展 从数理逻辑学中衍生出来的学科有很多，如：递归论、可计算理论、模型论、机器证明、知识工程、布尔代数等。这些理论都是以数理逻辑学为基础的。针对数理逻辑本身，由于这些学科的需求产生了很多不同种类的逻辑系统。 数理逻辑的不同种类，基本上都是从经典的逻辑系统中扩展而来的。这种扩展通常有语法扩展和语义扩展。 ●语法扩展：在经典逻辑系统中，扩充一些符号，从而衍生出新的逻辑系统。如模态 逻辑，二阶谓词逻辑等。 ●语义扩展：对逻辑系统中语义的范围等进行扩展，如模糊逻辑等。 数理逻辑通常划分成以下不同种类的逻辑系统： 1、经典逻辑：传统的命题逻辑、一阶谓词逻辑等。认为世界是黑白的，对于一个命题 非真既假。 2、模态逻辑：认为世界上任何事情的真假是与时间有着密切的关系的。 3、多值逻辑：认为世界上的对与错是没有绝对的，命题的真假是可以是多个甚至连续 值的。 4、非单调逻辑：讨论如何将人类的常识加入到逻辑系统中去。经典逻辑是单调逻辑， 既事实越多，已有的结论不会消失；而单调逻辑中，可能随着事实的增加原有的结论被否定。 体系构成 在高级数理逻辑（计算逻辑）中，每一种逻辑都自成体系。逻辑的体系过程主要包括以下几个方面： 1、形式系统：用符号的方式来描述一个逻辑系统的构成。类似于形式语言系统。 2、语义系统：针对形式进行解释的一套体系，这套体系确定了符号的含义的解释方法 和规则。 3、元理论：对形式系统组成、语义系统特性和形式与语义之间关系进行研究。从而保 证了数理逻辑的初衷（利用数学演算的方法来研究人类思维过程）。 4、自动化推理：在形式系统的基础上，研究利用计算机自动进行推理的理论和方法。 以及自动推理的效率提高方法和自动推理完备性研究。
罗素的逻辑主义及其在数理逻辑史上的地位(下) 2010-02-26 19:43 罗素的逻辑主义及其在数理逻辑史上的 地位 【张家龙】 三、逻辑主义在数理逻辑史上的地位 以罗素为代表的逻辑主义在数理逻辑发展史上具有重要的历史地位。怀特海和罗素的巨著《数学原理》是数理逻辑发展史上的一个里程碑, 也是经典著作, 起了承先启后、继往开来的伟大作用。 可是, 逻辑主义者要从纯逻辑推出全部数学的计划, 遇到了极大的困难: 首先, 必须引进两条非逻辑公理———无穷公理和乘法公理(选择公理) 。无穷公理承认宇宙间个体的数量是无穷的, 没有这条公理, 连最简单的自然数也无法构成。乘法公理是与无穷有关的断定, 是与数量有关的假定, 即保证选择类存在的假定; 它不是逻辑的规律。罗素深知这一点, 他把这两条公理写在需要它们的各数学定理的条件里面, 作为假定。但是这种解决办法并不能真正解决问题。在数学中必须承认有无穷多个自然数, 而不是只承认条件语句“如果有无穷多个个体, 那么自然数存在”。如果一个系统推不出无穷公理, 推不出自然数的存在, 那么它肯定推不出数学。 其次, 《数学原理》系统是以分支类型论为基础的, 而在从逻辑推导数学的过程中, 已暴露出恶性循环原则、分支类型论和可化归性公理的缺陷。实际上, 数学不是建立在逻辑的基础之上, 而是建立在罗素的分支类型论的基础之上; 没有可化归性公理的分支类型论就不能推出全部数学。 虽然从纯逻辑推不出全部数学, 但罗素的逻辑主义在数理逻辑发展史上仍具有重要意义。 首先, 我们认为, 罗素的逻辑主义是一种科学假说。在逻辑和数学中提出假说或猜想, 是一种极其重要的方法论思想, 是促进逻辑和数学发展的有力手段。恩格斯说: “只要自然科学运用思维, 它的发展形式就是假说。一个新的事实一旦被观察到, 对同一类事实的以往的说明方式便不能再用了。从这一刻起, 需要使用新的说明方式———最初仅仅以有限数量的事实和观察为基础。进一步的观察材料会使这些假说纯化, 排除一些, 修正一些, 直到最后以纯粹的形态形成定律。如果要等待材料去纯化到足以形成定律为止, 那就是要在此以前使运用思维的研究停顿下来, 而定律因此也就永远不会出现。” (《马克思恩格斯选集》第4卷, 第336 - 337页) 罗素的逻辑主义就是这样的一种假说。数理逻辑的发展使它得到纯化和修正, 直到最后构成了关于逻辑与数学关系的科学理论。罗素是一位科学家, 以实事求是的精神对这一假说进行了探索。他从纯逻辑演算出发, 增加了两条非逻辑公理, 以分支类型论为基础, 推导出一般算术和集合论, 推导出代数和分析的主要概念。罗素的实践向我们表明, 逻辑与数学有紧密的联系。虽然从纯逻辑推不出全部数学, 但是数学要依赖逻辑: 在构成形式数学系统