| 离散数学 | 您所在的位置：网站首页 › 离散数学异或真值表 › 离散数学 |
离散数学
|
目录 命题逻辑 命题 联结词与复合命题 复合命题（合式公式） 等值式 等值公式定义 拿来即用的等价公式 重言式与矛盾式 重言蕴含式 范式 谓词逻辑 逻辑：研究人的思维的科学 思维过程： 概念-->判断-->推理 推理方法： 类比推理：由个别事实推出个别结论归纳推理：由若干个别事实推出一般结论演绎推理：由一般规律、个别事实推出个别结论 命题逻辑 命题概念：命题是一个非真即假的陈述句 命题为真：所作的判断与客观一致，记做T（True） 命题为假：所作的判断与客观不一致，记做F（False） 注意： 1.感叹句、祈使句、疑问句不是命题 2.未知结果的命题为命题，但无法判断真假 3.悖论都不是命题 原子命题：由最简单的陈述句构成的命题 复合命题：由若干个原子命题构成的命题 联结词与复合命题复合命题的构成：连接词 + 原子命题 六种联结词：
否定（┐） 表示：“。。。不成立”，“” 用于：表示对一个命题的否定，写成┐p 🌰： p:2是素数 ┐p：2不是素数 否定真值表 p┐pFTTF合取（∧） 表示：且关系 🌰： p:小王能踢球 q：小王能唱歌 p∧q：小王既能踢球又能唱歌 合取真值表 pqp∧qFFFTFFFTFTTT析取（∨） 表示：或者关系 🌰： p:灯泡坏了 q:线路有故障 p∨q:灯泡坏了或者线路有故障 析取真值表 pqp∨qFFFFTTTFTTTT异或（⊻） 表示：两个命题不能同时都成立 例子： p:第一节上数学 q:第一节上英语 p⊻q:第一节上数学或者上英语 异或真值表 p qp⊻q FFFFTTTFTTTF蕴涵（→） 表示：表示如果。。。则。。。 🌰： p:缺少水分 q:植物会死亡 p→q:如果确实缺少水分，植物会死亡 蕴涵真值表 p(小王发达了)q（送大家房子）p→q(如果小王发达了，送大家房子)FFT(因为小王没有发达，所以无法判断q是否会发生，所有命题为真)F TTTFFTTT等价（↔） 表示：当且仅当，互为充要条件 🌰： p:三角形A是等边三角形 q:三角形A是等腰三角形 p↔q：三角形A即是等边三角形，又是等腰三角形 等价真值表 pqp↔qFFTFTFTFFTTT完整的真值表 pqp∧qp∨qp⊻q p→qp↔qFFFFFTTFTFTTTFTFFTTFFTTTTFTT 复合命题（合式公式）定义： a.单个命题变元是合式公式 b.若A是合式公式，则┐A是合式公式。 c.若A和B是合式公式，则p∧q、p∨q、p→q、p↔q都是合式公式 d.当且仅当有限次的应用a、b、c所得到的含有命题变元、联结词和括号的符号串是合式公式 运算顺序约定： 运算顺序优先级：┐、∧、∨、→、↔，相同的运算符按从左到右依次序计算，优先计算括号里的内容 公式(┐p→q)∨q的真值表如下 pq┐p┐p→q(┐p→q)∨qFFTFFFTTTTTFFTTTTFTT永真命题：公式中的命题变量无论如何代入，公式对应的真值恒为T 永假命题：公式中的命题变量无论如何代入，公式对应的真值恒为F 一般命题公式：既不是永真命题也不是永假命题 等值式 等值公式定义定义：给定两个命题A和B，设p1,p2,p3...pn为所有出现在A、B中的原子命题，那么给p1,p2,p3...pn任一组真值指派，A和B的真值都相同，则称A和B等价，记做A=B 拿来即用的等价公式
判断命题逻辑等价的方法： 真值表（考试力荐）命题公式的演算：a.基本等值定理 b.公式的代入不变性 c.等值关系的传递性等值公式的性质
例子： p┐pVp(永真)┐p^p(永假)FTFTTF置换式：A(p1...pn)是命题公式，如果用合式公式X替换某个Pi，其余变元不变，替换后得到的新的公式B，则称B是A(p1...pn)的置换式 永真式的性质： 如果A是永真式，则┐A是永假式如果A、B是永真式，则p∧q、 p∨q、p⊻q、p→q、p↔q也都是永真式如果A是永真式，则A的置换式也都是永真式 重言蕴含式定义：如果p→q是重言式，则称A永真蕴涵B，记作A=>B 解释：当A为真时，B也为真 p∧q=>pp∧q为真的条件是p和q都为真，所以得出p为真p∧q=>p同理p=>p∨qp为真时，p析取任何命题都为真q=>p∨q同理┐p=>p→q┐p为真代表p为假，假命题的所有蕴涵式都为真┐q=>p→q同理┐(p→q)=>pp→q为假，当且仅当p位真┐(p→q)=>┐q同理p,q=>p∧qp、q都为真，合取为真┐p∧（p∨q）=>qp假q真p∧（p→q）=>qq为真┐q∧（p→q）=>pq为真p为假（p→q）∧（q→r）=>p→r1.p真，q真，r真 2.p假， （p∨q）∧（p→r）∧(q→r）=>r1.p真，r真 2.p假，q真，r真 p→q=>（p∨c）→（q∨c）1.p真，q真 2.p假，c真 3.p假，c假 p→q=>（p∧c）→（q∧c）同理 范式范式就是命题公式形式的规范形式。这里约定范式中只含联结词 简单合取式：用∧联结命题变元或变元的否定构成的式子 简单析取式：用∨联结命题变元或变元的否定构成的式子 析取范式：如果公式写成A1∨A2∨...∨An其中每个Ai是合取式，称之为A的析取范式 合取范式：如果公式写成A1∧A2∧...∧An其中每个Ai是析取式，称之为A的合取范式 范式定理：任一命题公式都存在与之等值的析取范式和合取范式 范式求法
小项：在一个又n个命题变元的合取式中，每个变元或该变元的否定仅出现一次，称这个合取式是个小项 主析取范式：析取范式A1∨A2∨...∨An其中每个Ai都是小项，称之为主析取范式 大项：在一个又n个命题变元的析取式中，每个变元或该变元的否定仅出现一次，称这个析取式是个小项 主合取范式：合取范式A1∧A2∧...∧An其中每个Ai都是大项，称之为主合取范式 谓词逻辑个体词：指研究对象中可以独立存在的具体或抽象的客体。 谓词的定义：命题去掉主语，剩余部分叫做谓词 量词：个体变项之间的数量关系 分类 全称量词 ∀（All-A倒写）、存在量词∃（Exist-E反写） 基本两次等值定律 个体域有限 D= {a1,a2,a3....an} ∀xA(x)A（a1）∧A（a2）∧A（a3）...∧A（an） ∃xA(x)A（a1）∨A（a2）∨A（a3）...∨A（an） 量词否定等值式 ┐∀xA(x)∃x┐A（x） ┐∃xA(x)∀┐A（x） 量词分配律 ∀x（A(x)∧B(x)）∀xA(x)∧∀xB(x) ∃x（A(x)∨B(x)）∃xA(x)∨∃xB(x) 量词扩张/收缩律 ∀x（A∨B(x)）A∨∀xB(x) ∀x（A∧B(x)）A∧∀xB(x) ∃x（A∨B(x)）A∨∃xB(x) ∃x（A∧B(x)）A∧∃xB(x) |
【本文地址】