离散数学-命题逻辑.pptVIP

什么是数理逻辑？ 第一章 数理逻辑 一 命题逻辑 命题及其表示法 联结词 命题公式与翻译 真值表与等价式 重言式与蕴含式 对偶与范式 推理理论 二 谓词逻辑 谓词的概念与表示 命题函数与量词 谓词公式与翻译 变元的约束 谓词演算的等价式与蕴含式 前束范式 谓词演算的推理理论 本章作业 关于命题逻辑 关于命题逻辑 二、命题联结词 命题公式与翻译 关于命题逻辑--答案 定义:命题演算的合式公式（wff），规定为： （1）单个命题变元本身是一个合式公式。 （2）如果A是合式公式，那么?A是合式公式。 （3）如果A和B是合式公式，那么A∧ B ， A∨B，A→ B和A ? B都是合式公式。 （4）当且仅当能够有限次地应用1、2、3、所得到的包含命题变元，联结词和括号的符号串是合式公式。 * 用数学方法来研究推理的规律称为数理逻辑。这里所指的数学方法，就是引进一套符号体系的方法，所以数理逻辑又称为符号逻辑，它是从量的侧面来研究思维规律的学科。 命题逻辑 谓词逻辑 问题：传说中有一个住在边远小镇上的剃头匠,这个剃头匠只能给那些不自己剃须的人刮胡子,他能给自己剃须吗? 问题:边远村庄的每个人要么总说真话,那么总说谎.对旅游者的问题,村民要么回答“是”,要么回答“否”.假定你在这一地区旅游,走到一个岔路口,一条岔路通向你想去的遗址,一条岔路通向丛林深处,此时恰好有一村民站在岔路口,问村民什么样的一个问题就能决定走哪条路? 问题：甲、乙、丙、丁四人参加拳击比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜；如果甲不获胜，则丁不失败。 能否推出结论：如果丙获胜，则丁不失败 问题：设计一个控制客厅照明的电路，使得分别装在卧室和客厅的两只开关都能控制照明。 判断：通过概念对事物是否具有某种属性进 行肯定或否定的回答。 一、命题及其表示 1、命题的定义 命题：指能表达判断的陈述句。 一个命题，总是具有一个“值”，称为真值。 真值只有“真”和“假”两种，记作True（真） 和False（假），分别用符号T和F表示。只有 具有确定真值的陈述句才是命题，一切没有 判断内容的句子，无所谓是非的句子，如感 叹句，疑问句，祈使句等都不能作为命题。 2、命题类型 命题有两种类型： 原子命题：不能分解为更简单的陈述语句的命题。 复合命题：由联结词，标点符号和原子命题复合构成的命题。 所有这些命题，都应具有确定的真值。 联结词的例子，如：“并且”、“或者”、“如果…则…”等。 例：判断下面的句子是否为命题。 （1）中国人民是伟大的。 （2）雪是黑的。 （3）1+101=110 （4）别的星球上有生物。 （5）全体立正。 （6）明天是否开大会？ （7）天气多好啊！ （8）我正在说谎。 （9）我学英语，或者我学日语。 3、命题的表示 在本课程中，我们将使用大写字母A、B、…、P、Q、…，或带下标的大写字母，或方括号括起来的数字。来表示命题。 如： P：太阳从西边出来。 [12]：太阳从西边出来。 即命题既可用字母也可用数字来表示 命题标识符 表示命题的符号。 命题常量 一个具体的命题。 命题变元 命题标识符只表示任意命题的位置。 注：命题变元不是命题。 指 派 当命题变元P用一个特定的命题取代时，P才能确 定真值，称对P进行指派。 命题逻辑与程序语言的对应关系 命题标识符 程序语言标识符。 命题常量 逻辑常量。 命题变元 逻辑变量。 指 派 给逻辑变量赋值。 在自然语言中，常常使用“或者”，“并且”，“不是”等一些联结词，对于这种联结词的使用，一般没有很严格的定义。在数理逻辑中，复合命题是由原子命题与联结词组合而成，联结词不仅是复合命题中的重要组成部分，而且起到了运算符的作用。为了便于书写和进行推理演算，必须对联结词作出明确规定并符号化。下面介绍各个联结词。 1）否定 定义：设P为一命题，P的否定是一个新的命题，记作：?P。若P为T， ?P为F；若P为F， ?P为T。 “?” 是一元运算。 其运算规则表如下： T F F T ?P P 例： P：太阳从东边出来 ?P： ?P：太阳不从东边出来 注意： “?”表