离散数学-命题逻辑

《离散数学-命题逻辑》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、什么是数理逻辑？用数学方法来研究推理的规律称为数理逻辑。这里所指的数学方法，就是引进一套符号体系的方法，所以数理逻辑又称为符号逻辑，它是从量的侧面来研究思维规律的学科。命题逻辑谓词逻辑第一章数理逻辑一命题逻辑命题及其表示法联结词命题公式与翻译真值表与等价式重言式与蕴含式对偶与范式推理理论二谓词逻辑谓词的概念与表示命题函数与量词谓词公式与翻译变元的约束谓词演算的等价式与蕴含式前束范式谓词演算的推理理论本章作业关于命题逻辑问题：传说中有一个住在边远小镇上的剃头匠,这个剃头匠只能给那些不自己剃须的人刮胡子,他能给自己剃须吗?问题:边远村庄的每个人要么总说真话,那么总说谎.对旅游者的问题,村民要么回答

2、“是”,要么回答“否”.假定你在这一地区旅游,走到一个岔路口,一条岔路通向你想去的遗址,一条岔路通向丛林深处,此时恰好有一村民站在岔路口,问村民什么样的一个问题就能决定走哪条路?>>>关于命题逻辑问题：甲、乙、丙、丁四人参加拳击比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜；如果甲不获胜，则丁不失败。能否推出结论：如果丙获胜，则丁不失败问题：设计一个控制客厅照明的电路，使得分别装在卧室和客厅的两只开关都能控制照明。判断：通过概念对事物是否具有某种属性进行肯定或否定的回答。一、命题及其表示1、命题的定义命题：指能表达判断的陈述句。一个命题，总是具有一个“值”，称为真值。真值只有“真”和“假”

3、两种，记作True（真）和False（假），分别用符号T和F表示。只有具有确定真值的陈述句才是命题，一切没有判断内容的句子，无所谓是非的句子，如感叹句，疑问句，祈使句等都不能作为命题。2、命题类型命题有两种类型：原子命题：不能分解为更简单的陈述语句的命题。复合命题：由联结词，标点符号和原子命题复合构成的命题。所有这些命题，都应具有确定的真值。联结词的例子，如：“并且”、“或者”、“如果…则…”等。例：判断下面的句子是否为命题。（1）中国人民是伟大的。（2）雪是黑的。（3）1+101=110（4）别的星球上有生物。（5）全体立正。（6）明天是否开大会？（7）天气多好啊！（8）我正在说谎。（9）我

4、学英语，或者我学日语。3、命题的表示在本课程中，我们将使用大写字母A、B、…、P、Q、…，或带下标的大写字母，或方括号括起来的数字。来表示命题。如：P：太阳从西边出来。[12]：太阳从西边出来。即命题既可用字母也可用数字来表示命题标识符表示命题的符号。命题常量一个具体的命题。命题变元命题标识符只表示任意命题的位置。注：命题变元不是命题。指派当命题变元P用一个特定的命题取代时，P才能确定真值，称对P进行指派。命题逻辑与程序语言的对应关系命题标识符程序语言标识符。命题常量逻辑常量。命题变元逻辑变量。指派给逻辑变量赋值。二、命题联结词在自然语言中，常常使用“或者”，“并且”，“不是”等一些联结词，对

5、于这种联结词的使用，一般没有很严格的定义。在数理逻辑中，复合命题是由原子命题与联结词组合而成，联结词不仅是复合命题中的重要组成部分，而且起到了运算符的作用。为了便于书写和进行推理演算，必须对联结词作出明确规定并符号化。下面介绍各个联结词。1）否定定义：设P为一命题，P的否定是一个新的命题，记作：ךP。若P为T，ךP为F；若P为F，ךP为T。“ך”是一元运算。其运算规则表如下：TFFTךPP例：P：太阳从东边出来ךP：ךP：太阳不从东边出来注意：“ך”表示命题的否定。2）合取定义：两个命题P和Q的合取是一个复合命题，记作P∧Q。当且仅当P、Q同时为T时，P∧Q为T，其他情况下P∧Q的真值都是F。

6、“合取”是一个二元运算，称为“与”运算。其运算法则表如下：联结词“∧”的运算法则：FFFTP∧QFFTFFTTTQP注：合取的概念与自然语言中的“并且”意义相似。例：P：北京是中国的首都。Q：北京是一个故都。P∧Q：P∧Q：北京是中国的首都并且是一个故都。3）析取定义：两个命题P和Q的析取是一个复合命题，记作P∨Q。当且仅当P、Q同时为F时，P٧Q的真值为F，否则P∨Q的真值为T。注：从析取的定义可以看到，联结词٧与汉语中的“或者”的意义类似。“析取”也是二元运算，称为“或”运算，其运算法则表如下：联词“∨”的运算法则：注意：“∨”为可兼或FTTTP∨QFFTFFTTTQP例：P：成都是中国的

7、首都。Q：成都是一个故都。P∨Q：P∨Q：成都是中国的首都或者是一个故都。4）条件定义：给定两个命题P和Q，其条件命题是一个复合命题，记作P→Q,读作：“如果P，那么Q”或“若P则Q”。当且仅当P的真值为T，Q的真值为F时，P→Q的真值为F，否则P→Q的真值为T。我们称P为前件，Q为后件。联给词“→”的运算法则：TTFTP→QFFTFFTTTQP例：P：x>yQ：x-y>0P→Q：P→Q：如果x>