命题演算基础课件.ppt

《命题演算基础课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数理逻辑第一章命题演算基础第二章命题演算的推理理论第三章谓词演算基础第四章谓词演算的推理理论第五章递归函数论数理逻辑集合论图论代数24学时17学时19学时12学时逻辑学——研究推理的科学早期创始人亚里士多德(公元前384—322)柏拉图(公元前429—348),首先把逻辑学的思想方法引入几何学苏格拉底（前470—前399年）数理逻辑——数学化的逻辑学德国G.W.Leibniz(1626-1716)把数学引入形式逻辑，明确提出用数学方法研究推理。英国G.Boole(1815-1864)等创立了逻辑代数

2、，1847年Boole实现了命题演算。德国G.Frege(1848-1925)在1879年建立了第一个谓词演算系统。英国B.Russell(1872-1970)等从逻辑学的基本法则建立了自然数理论、实数理论及解析几何学等。奥地利K.Godel(1906-1978)在1931年提出Godel不完全性定理。英国AlanM.Turing(1912-1954)在1936年提出一种抽象计算模型（数学逻辑机），引入图灵机——一种理想的计算机。在计算机科学中的逻辑创建一种语言,使人们能够对计算机科学领域中所遇到的

3、情境进行建模,并在这种方式下,对情境进行形式化推理。对情境进行推理意味着构造与其相关的论证，人们希望这个过程形式化，使这些论证经得起严格的推敲，或者能够在计算机上实现。例1前提？结论？怎么推理?如果火车晚点，而且车站没有出租车，那么小王参加会议就会迟到。小王没有迟到，火车的确晚点了，因此，车站有出租车。P：火车晚点Q：车站有出租车R：小王参加会议会迟到如果P且非Q,那么R。非R，P，因此，Q。例2前提？结论？怎么推理?如果下雨，小李没有带伞，就会被淋湿。而小李没有被淋湿，确实下雨了，因此，小李带伞了

4、。P：下雨Q：小李带伞R：小李被淋湿如果P且非Q,那么R。非R，P，因此，Q。数理逻辑的学习“我现在年纪大了，搞了这么多年的软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好好下点工夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻二十岁的话，我就去学逻辑。”——Edsger.W.Dijkstra1972年Turing奖获得者(1930-2002)带权图的最短通路算法第一章命题演算基础1.1命题和联结词1.1.1命题1.1.2联结词1.1.3合式公

5、式1.2真假性1.3范式及其应用(一)命题定义定义1：凡是可以判断真假的陈述句称为命题。命题的值真,用T(或1)表示假,用F(或0)表示例：下列句子都是命题吗？雪是白的。雪是黑的。好大的雪啊！8大于12。1+101=110。✔✔✔✔✘例：下列句子都是命题吗？上海世博会开幕时天晴21世纪末，人类将住在月球大于2的偶数可表示成两个素数之和X<0如果x大于3，则x2大于9。✔✔✔✔✘例：下列句子都是命题吗？8大于12吗？请勿吸烟。姚明很帅。南京很美。我正在说谎。悖论✔✔✘✘✘命题的真假问题在数理逻辑的学习

6、中，不能去纠缠各种具体命题的真假问题，而是将命题当成数学概念来处理，看成一个抽象的形式化的概念，把命题定义成非真必假的陈述句．带联结词的命题今晚我看书。今晚我玩网络游戏。今晚我不看书。今晚我不玩网络游戏。今晚我不看书，我玩网络游戏。今晚我看书，或者我玩网络游戏。否定并且或者(二)原子命题和复合命题原子命题——不可剖开或分解为更简单命题的命题，也称为简单命题。本书约定用大写字母表示。复合命题——由原子命题利用联结词构成的命题复合命题例子（1）雪不是白的（并非雪是白的）（2）今晚我看书或者去看电影。（3

7、）如果天气好，那么我去接你。（4）偶数a是质数，当且仅当a=2（a是常数）。（5）2是偶数且3也是偶数。（6）你去了学校，我去了工厂。其中红字为逻辑联结词，（6）中省略了“且”(三)命题变元定义2：如果当P表示任意命题时，P称为命题变元。字母P表示命题——具体的、特定的命题，有确定的真值命题变元——任意命题，没有确定的真值第一章命题演算基础1.1命题和联结词1.1.1命题1.1.2联结词1.1.3合式公式1.2真假性1.3范式及其应用常用的联结词否定词﹃合取词∧析取词∨蕴含词等价词﹃P，“非P”

8、设P是一个命题，﹃P是指如下命题：“P是不对的”PPTFFT日常语句中有：不，并非，……真值表否定词的例子例P：上海是中国的城市。﹁P：上海不是中国的城市。例P：雪是黑色的。﹁P：雪不是黑色的。否定联结词使用的原则将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。例P:这些都是学生。﹃P：这些不都是学生≠这些都不是学生P∧Q，“P合取Q”设P、Q是两个命题，P∧Q是指如下命题：“P并且Q”PQPQTTTTFFFTFFFF日常语句中有：