第一章-命题演算基础

醉雪—风随心动学时醉雪—风随心动逻辑学——研究推理的科学早期创始人•亚里士多德(公元前384—322)•柏拉图(公元前429—348),首先把逻辑学的思想方法引入几何学•苏格拉底（前470—前399年）醉雪—风随心动数理逻辑——数学化的逻辑学•德国G.W.Leibniz(1626-1716)把数学引入形式逻辑，明确提出用数学方法研究推理。•英国G.Boole(1815-1864)等创立了逻辑代数，1847年Boole实现了命题演算。•德国G.Frege(1848-1925)在1879年建立了第一个谓词演算系统。•英国B.Russell(1872-1970)等从逻辑学的基本法则建立了自然数理论、实数理论及解析几何学等。•奥地利K.Godel(1906-1978)在1931年提出Godel不完全性定理。•英国AlanM.Turing(1912-1954)在1936年提出一种抽象计算模型（数学逻辑机），引入图灵机——一种理想的计算机。醉雪—风随心动在计算机科学中的逻辑创建一种语言,使人们能够对计算机科学领域中所遇到的情境进行建模,并在这种方式下,对情境进行形式化推理。对情境进行推理意味着构造与其相关的论证，人们希望这个过程形式化，使这些论证经得起严格的推敲，或者能够在计算机上实现。醉雪—风随心动前提？结论？怎么推理?如果火车晚点，而且车站没有出租车，那么小王参加会议就会迟到。小王没有迟到，火车的确晚点了，因此，车站有出租车。P：火车晚点Q：车站有出租车R：小王参加会议会迟到如果P且非Q,那么R。非R，P，因此，Q。醉雪—风随心动前提？结论？怎么推理?如果下雨，小李没有带伞，就会被淋湿。而小李没有被淋湿，确实下雨了，因此，小李带伞了。P：下雨Q：小李带伞R：小李被淋湿如果P且非Q,那么R。非R，P，因此，Q。醉雪—风随心动数理逻辑的学习“我现在年纪大了，搞了这么多年的软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好好下点工夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻二十岁的话，我就去学逻辑。”——Edsger.W.Dijkstra1972年Turing奖获得者(1930-2002)带权图的最短通路算法醉雪—风随心动范式及其应用醉雪—风随心动(一)命题定义定义1：凡是可以判断真假的陈述句称为命题。命题的值真,用T(或1)表示假,用F(或0)表示醉雪—风随心动例：下列句子都是命题吗？①雪是白的。②雪是黑的。③好大的雪啊！④8大于12。⑤1+101=110。✔✔✔✔✘醉雪—风随心动例：下列句子都是命题吗？①上海世博会开幕时天晴②21世纪末，人类将住在月球③大于2的偶数可表示成两个素数之和④X0⑤如果x大于3，则x2大于9。✔✔✔✔✘醉雪—风随心动例：下列句子都是命题吗？①8大于12吗？②请勿吸烟。③姚明很帅。④南京很美。⑤我正在说谎。悖论✔✔✘✘✘醉雪—风随心动命题的真假问题在数理逻辑的学习中，不能去纠缠各种具体命题的真假问题，而是将命题当成数学概念来处理，看成一个抽象的形式化的概念，把命题定义成非真必假的陈述句．醉雪—风随心动带联结词的命题•今晚我看书。•今晚我玩网络游戏。•今晚我不看书。•今晚我不玩网络游戏。•今晚我不看书，我玩网络游戏。•今晚我看书，或者我玩网络游戏。否定并且或者醉雪—风随心动(二)原子命题和复合命题原子命题——不可剖开或分解为更简单命题的命题，也称为简单命题。本书约定用大写字母表示。复合命题——由原子命题利用联结词构成的命题醉雪—风随心动复合命题例子（1）雪不是白的（并非雪是白的）（2）今晚我看书或者去看电影。（3）如果天气好，那么我去接你。（4）偶数a是质数，当且仅当a=2（a是常数）。（5）2是偶数且3也是偶数。（6）你去了学校，我去了工厂。其中红字为逻辑联结词，（6）中省略了“且”醉雪—风随心动(三)命题变元定义2：如果当P表示任意命题时，P称为命题变元。字母P表示命题——具体的、特定的命题，有确定的真值命题变元——任意命题，没有确定的真值醉雪—风随心动范式及其应用醉雪—风随心动常用的联结词①否定词﹃②合取词∧③析取词∨④蕴含词⑤等价词醉雪—风随心动﹃P，“非P”设P是一个命题，﹃P是指如下命题：“P是不对的”PPTFFT日常语句中有：不，并非，……真值表醉雪—风随心动：上海是中国的城市。﹁P：上海不是中国的城市。例P：雪是黑色的。﹁P：雪不是黑色的。醉雪—风随心动否定联结词使用的原则将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。例P:这些都是学生。﹃P：这些不都是学生≠这些都不是学生醉雪—风随心动∧Q，“P合取Q”设P、Q是两个命题，P∧Q是指如下命题：“P并且Q”PQPQTTTTFFFTFFFF日常语句中有：且，与，……醉雪—风随心动合取词的例子P:2×2＝5Q：雪是白的。P∧Q：2×2＝5并且雪是白的。P:今天刮风。Q：今天下雨。P∧Q：今天刮风并且今天下雨。醉雪—风随心动∨Q，“P析取Q”设P、Q是两个命题，P∨Q是指如下命题：“P或者Q”PQPQTTTTFTFTTFFF日常语言中有：或，或者，……醉雪—风随心动析取词的例子P:2×2＝5Q：雪是白的。P∨Q：2×2＝5或者雪是白的。P:今天刮风。Q：今天下雨。P∨Q：今天刮风或者今天下雨。醉雪—风随心动可兼的“或”PQP∨QTTTTFTFTTFFF他会英语或法语。醉雪—风随心动不可兼的“或”PQP∨Q(P∧﹁Q)∨(﹁P∧Q)TTTFTFTTFTTTFFFF今天晚上我去看电影，或去看球赛。醉雪—风随心动→Q,“P蕴含Q”设P、Q是两个命题，P→Q是指如下命题：“如果P则Q”日常语言中有：如果…则…,只要…就…，……PQPQTTTTFFFTTFFT醉雪—风随心动蕴含词的例子•P：2×3＝6Q：(2×3)+1=6+2P→Q:如果2×3＝6，则（2×3）＋1＝6+2•P:天气不好Q：我去接你P→Q:如果天气不好，那么我去接你。醉雪—风随心动前件为假时，命题为真如果蕴含前件P是假命题，那么不管Q是什么命题，命题P→Q在逻辑中都被认为是真命题。例：如果1=2，那太阳从西边升起。醉雪—风随心动前件、后件可以毫不相关在日常语言中“如果……则……”所联结的句子之间表现的是一种因果关系，但在数理逻辑中，尽管说前件蕴涵后件，但两个命题可以是毫不相关的。例：P：2×3＝5Q：雪是黑色的P→Q：如果2×3＝5，则雪是黑色的醉雪—风随心动：天下雨。q：我回家。试表示下列命题：（1）只要天下雨，我就回家。（2）只有天下雨，我才回家。（3）除非天下雨，否则我不回家。（4）仅当天下雨，我才回家。p→qq→pq→pq→p或﹃p→﹃q醉雪—风随心动例.将下列命题符号化:（1）只要星期六天气好，我就去公园玩。（2）只有星期六天气好，我才去公园玩。（3）除非星期六天气好，否则我不去公园玩。要特别注意蕴涵联结的应用，要弄清三个问题：①p→q的逻辑关系②p→q的真值③p→q的灵活的叙述方法醉雪—风随心动Q，“P等价于Q”设P、Q是两个命题，PQ是指如下命题：“P当且仅当Q”PQPQTTTTFFFTFFFT日常语言中有：当且仅当，……醉雪—风随心动等价词的例子•P:2×2＝4Q：雪是白色的。PQ：2×2＝4当且仅当雪是白色的。•P:2×2＝5Q：雪是黑色的。PQ：2×2＝5当且仅当雪是黑色。醉雪—风随心动等价词的例子•P:2×2＝5Q：雪是白色的。PQ：2×2＝5当且仅当雪是白色的。•P:2×2＝4Q：雪是黑色的。PQ：2×2＝4当且仅当雪是黑色。醉雪—风随心动是否复合命题？例1Tom和John是兄弟。例2如果x0，则x20。例3a=0当且仅当|a|=0。✘✘✘醉雪—风随心动真值函项的定义以真假为定义域并以真假为值域的函数{T,F}{(T,T),(T,F),(F,T),(F,F)}{T,F}一元真值函项二元真值函项醉雪—风随心动，可取“T”和“F”两种值。可定义四个一元真值函项f0，f1，f2，f3。Pf0(P)f1(P)f2(P)f3(P)TTTFFFTFTF永真恒等否定P永假醉雪—风随心动为析取f2为蕴含f8为等价f11为合取醉雪—风随心动三元联结词共有多少个？f0f1f2…………f?(0,0,0)010…………1(0,0,1)001…………1(0,1,0)000…………1(0,1,1)000…………1(1,0,0)000…………1(1,0,1)000…………1(1,1,0)000…………1(1,1,1)000…………128醉雪—风随心动范式及其应用醉雪—风随心动合式公式(Wellformedformulae)合式公式为如下定义的式子，简称为公式：①任何命题变元均是公式；②如果P为公式，则P为公式；③如果P，Q为公式，则PQ,PQ,PQ,PQ为公式；④当且仅当经过有限次使用①、②、③所组成的符号串才是公式，否则不为公式。醉雪—风随心动元公式若公式中有n个不同的命题变元，就说为n元公式。3元公式的例子：（（PQ）R）（PQ）（PQR）（PQ）✔✘醉雪—风随心动优先级约定•非﹃比其它联结词有更高的优先级•括号（）内的运算优先本书未约定•∧和∨比有更高的优先级•是右结合的醉雪—风