离散数学第一章命题演算基础-命题和联结词.ppt

南京师范大学－孔子像 子曰：学而不思则罔，思而不学则殆 ????孔子说：只重学习而不注重思考，就有可能遭到蒙蔽而陷于迷惑；只重思考而不注重学习，就有可能因误入歧途而招致疲乏及危险。 数学化的逻辑学，是用数学方法研究推理的科学，其历史只有300年。 图灵机（英语：Turing Machine，又称确定型图灵机）是英国数学家阿兰·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。 英国科学家艾伦·图灵1937年发表著名的《论应用于解决问题的可计算数字》一文。文中提出思考原理计算机——图灵机的概念，推进了计算机理论的发展。1945年图灵到英国国家物理研究所工作，并开始设计自动计算机。1950年，图灵发表题为《计算机能思考吗？》的论文，设计了著名的图灵测验，通过问答来测试计算机是否具有同人类相等的智力。图灵提出了一种抽象计算模型，用来精确定义可计算函数。图灵机由一个控制器、一条可无限伸延的带子和一个在带子上左右移动的读写头组成。这个在概念上如此简单的机器，理论上却可以计算任何直观可计算的函数。图灵机作为计算机的理论模型，在有关计算机和计算复杂性的研究方面得到广泛应用。 　　计算机是人类制造出来的信息加工工具。如果说人类制造的其他工具是人类双手的延伸，那么计算机作为代替人脑进行信息加工的工具，则可以说是人类大脑的延伸。最初真正制造出来的计算机是用来解决数值计算问题的。二次大战后期，当时为军事目的进行的一系列破译密码和弹道计算工作，越来越复杂。大量的数据、复杂的计算公式，即使使用电动机械计算器也要耗费相当的人力和时间。在这种背景下，人们开始研制电子计算机。　　世界上第一台计算机“科洛萨斯”诞生于英国，“科洛萨斯”计算机是1943年3月开始研制的，当时研制“科洛萨斯”计算机的主要目的是破译经德国“洛伦茨”加密机加密过的密码。使用其他手段破译这种密码需要6至8个星期，而使用‘科洛萨斯’计算机则仅需6至8小时。1944年1月10日，“科洛萨斯”计算机开始运行。自它投入使用后，德军大量高级军事机密很快被破译，盟军如虎添翼。“科洛萨斯”比美国的ＥＮＩＡＣ计算机问世早两年多，在二战期间破译了大量德军机密，战争结束后，它被秘密销毁了，故不为人所了解。　　尽管第一台电子计算机诞生于英国，但英国没有抓住由计算机引发的技术和产业革命的机遇。相比之下，美国抓住了这一历史机遇，鼓励发展计算机技术和产业，从而崛起了一大批计算机产业巨头，大大促进了美国综合国力的发展。1944年美国国防部门组织了有莫奇利和埃克脱领导的ＥＮＩＡＣ计算机的研究小组，当时在普林斯顿大学工作的现代计算机的奠基者美籍匈牙利数学家冯·诺依曼也参加了者像研究工作。1946年研究工作获得成功，制成了世界上第一台电子数字计算机ＥＮＩＡＣ。这台用18000只电子管组成的计算机，尽管体积庞大，耗电量惊人，功能有限，但是确实起了节约人力节省时间的作用，而且开辟了一个计算机科学技术的新纪元。这也许连制造它的科学家们也是始料不及的。　　最早的计算机尽管功能有限，和现代计算机有很大的差别，但是它已具备了现代计算机的基本部分，那就是运算器、控制器和存储器。　　运算器就象算盘，用来进行数值运算和逻辑运算，并获得计算结果。而控制器就象机算机的司令部，指挥着计算机各个部分的工作，它的指挥是靠发出一系列控制信号完成的。　　计算机的程序、数据、以及在运算中产生的中间结果以及最后结果都要有个存储的地方，这就是计算机的第三个部件——存储器。　　计算机是自动进行计算的，自动计算的根据就是存储于计算机中的程序。现代的计算机都是存储程序计算机，又叫冯·诺依曼机，这是因为存储程序的概念是冯·诺依曼提出的。人们按照要解决的问题的数学描述，用计算机能接受的“语言”编制成程序，输入并存储于计算机，计算机就能按人的意图，自动地高速地完成运算并输出结果。程序要为计算机提供要运算的数据、运算的顺序、进行何种运算等等。 带权图的最短通路算法 命题为真——这个陈述句所表达的内容正确、符合客观实际 古典逻辑认为，命题或真或假，但不兼而有之，这就是逻辑学的一个基本假设——排中律。 命题为真——这个陈述句所表达的内容正确、符合客观实际 古典逻辑认为，命题或真或假，但不兼而有之，这就是逻辑学的一个基本假设——排中律。 （4）表示了一个错误的判断，故为假，又是一个陈述句，故为命题。 （5）这是一个数学表达式，相当于一个陈述句，可以叙述为1加101等110，这个句子所表达的内容在十进制范围中真值为假，而在二进制范围中真值为真。可见这个命题的真值还与所讨论问题的范围有关。 （1）是命题，虽然它的真值未必在现在或将来可以得知，但它们所作判断是否符