（1）逻辑和证明

本系列是离散数学及其应用第七版与北京交通大学的离散数学课程的个人笔记，章节顺序以书为准

本章内容完全从数学定义上学习，建议看之前读一下王路的逻辑基础做铺垫，深入可以看数理逻辑

1.命题逻辑

命题是一个陈述语句，它或真或假，但不能同时成立，使用一个字母代表命题变元，其值为true或false

image.png

image.png

命题联结词

image.png

事实上，有多种记法：

image.png

合取：命题p和q，当两者同真时才为真，即p且q，记作p∧q（当初记忆时为了和∨区别 合字 上面的的人正好和∧相似 这样就很容易记住了）

image.png

析取：命题p和q，有一者为真即为真，即p或q，记作p∨q
image.png

非：命题p的否命题记作¬p，或~p
image.png

异或：命题p和q，两者相反即为真，相同为假，即p异或q，记作p\oplus q，也称为不可兼或

条件语句

命题p和q，条件语句p\to q或p\Rightarrow q表示命题“如果p，则q”。当p为真而q为假时，条件语句p\to q为假，其余情况都为真。在条件语句中，p称为假设或前提，q称为结论。其真值表如下

image.png

条件语句p\to q可以理解为如下等价的语句

image.png

等价形式中，值得注意的是以下两种：

  1. p仅当q可以理解为当q不为真时，p一定为假，也就是说当q为假，p为真时，q仅当p这条语句为假。p为假时，q可以为真也可以为假。

  2. q除非¬p可以理解为如果¬p是假的，即p是真的，则q必然是真的

自然语言与符号的对照


image.png

几种特殊情况


image.png

符号化的通用原则

image.png

下面是一些例子

image.png

条件语句的逆命题，否命题，逆否命题
对p\to q来说，其逆命题为q\to p，否命题为¬p\to ¬q，逆否命题为¬q\to ¬p
对于任意命题，其原命题和逆否命题是等价的，否命题与逆命题也是等价的，但上述两种情况却不是等价的

双条件语句
对命题p和q，p\leftrightarrow q或p\Leftrightarrow q表示p当且仅当q。也就是说p和q具有相同的真值时，双条件语句为真，否则为假。可以理解为如下等价的语句：

  • p是q的充分必要条件
  • 如果p那么q，反之亦然

即p\leftrightarrow q等价于(p\to q)∧(q\to p)

双条件与条件语句的区别：
如果下雨 ，主队就能获胜 ；（除了下雨之外可能还有别的办法也可以获胜）
主队能获胜当且仅当下雨；（除了下雨，没有其他办法获胜了）

综合A\to B,B\to A,A\leftrightarrow B三种情况

image.png

也就能够理解对应A仅当B，对应A当B，对应A当且仅当B的含义了

逻辑运算符的优先级

image.png

由上向下递减

2. 命题逻辑的应用

语句翻译
大体遵循以下原则

image.png

命题的符号化遵循以下规则


image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

复杂命题的示例：

image.png

image.png

命题公式
格式要求：对命题公式形如p,q,r...来说，¬p,¬(p),(p∧q),(p∨q),(p\to q),(p\leftrightarrow q)的组合嵌套使用都是命题，其中使用了n个命题变元，就属于n元命题公式
在括号的书写上，只有满足以下要求

image.png

的情况，可以省略括号（同优先级的情况括号不能省略）

对于n元命题公式A，其含有p_1,p_2...p_n命题变元，则这组命题变元的一组确定真值称为该命题公式的一个真值指派（表示为一串长度为n的01序列），若这组真值指派使得A为真，则称为成真指派，若这组真值指派使得A为假，则称为成假指派。可以通过真值表直观的理解复杂命题。

对于n元命题公式A，若其所有2^n个真值指派都是成真指派，则称A为永真式或重言式，若其所有2^n个真值指派都是成假指派，则称A为永假式或矛盾式，若其至少存在一个成真指派，则称A为可满足式，若A至少存在一个成真指派与成假指派，则称A为非重言的可满足式

任意两个重言式的析取或合取仍然是重言式，任意两个矛盾式的析取或合取依然是矛盾式

真值表的使用规则


image.png

image.png

image.png

image.png

命题等价式

如果对于命题公式A与B，有A\leftrightarrow B是永真式，则命题A与B是逻辑等价的，记作A\equiv B

  1. 注意这并不是一个命题，恒等也不是一个逻辑联结词
  2. 如果p_1,p_2,...,p_n是A,B中出现的全部命题变项，则A与B是逻辑等价的当且仅当任意一组命题变项的真值指派，对A，B的产生的结果是相同的

等值演算是指由已知的等值式推演出新的等值式的过程

判断两个命题公式等值的办法


image.png

下面是真值表法的示例


image.png

显然当命题变项过多时，列写真值表是很麻烦的一件事，此时使用等值演算，基于一些基本的逻辑等价式，对复杂的逻辑式应用代入规则和替换规则化简后比较


image.png

image.png

image.png

在此之上还有一些常用的

  • p∨q≡\sim p\to q
  • p∧q≡\sim (p\to \sim q)
  • (p\to q)∧(p\to r)≡p\to(q∧r)
  • (p\to r)∧(q\to r)≡(p∨q)\to r
  • (p\to q)∨(p\to r)≡p\to(q∨r)
  • (p\to r)∨(q\to r)≡(p∧q)\to r≡p\to(q\to r)≡q\to(p\to r)
  • p\leftrightarrow q≡(p∧q)∨(\sim p\ ∧\sim q)
  • \sim(p\leftrightarrow q)≡p\leftrightarrow \sim q
  • p \oplus q ≡\sim(p\leftrightarrow q)≡(p\leftrightarrow \sim q)≡(\sim p\leftrightarrow - q)

代入规则


image.png

image.png

替换规则


image.png

image.png
image.png

几个例子

image.png

image.png

image.png

image.png

image.png

image.png

image.png


即可知，p,r为假，q,s为真

对偶

定义：在仅含有连接词~，∧，∨的命题公式A中，将∧∨相互取代，T和F也这么做，所得命题称为A的对偶式，记作A^*，显然(A^*)^*=A

性质1：在仅含有连接词~，∧，∨的命题公式A中，p_1,p_2...p_n是其命题变项，则有
\sim A(p_1,p_2...p_n)\equiv A^*(\sim p_1,\sim p_2...\sim p_n)
推论：在仅含有连接词~，∧，∨的命题公式A中，若A为重言式，则A^*为矛盾式

性质2：在仅含有连接词~，∧，∨的命题公式A与B中，若A\equiv B，则A^*\equiv B^*

范式

image.png

image.png

image.png

显然，析取式是重言式当且仅当其中出现互补对，合取式是矛盾式当且仅当其中出现互补对

image.png

image.png

性质：


image.png

image.png

求范式的步骤：


image.png

示例：


image.png

image.png

极小项与极大项

极小项


image.png
image.png

image.png

极大项


image.png

image.png

image.png

比较


image.png

image.png

image.png

主范式

提出主范式的原因


image.png

主析取范式


image.png

image.png

image.png

image.png

image.png

而实际上，将2,4,5,6,7转化为二进制数，再化为命题变元的表示，也就是所有原命题的成真指派

主合取范式


image.png

image.png

image.png

而实际上，将0,1,3转化为二进制数，再化为命题变元的表示（跟析取相反），也就是所有原命题的成真指派

两种范式的转换


image.png

image.png

image.png

主范式的意义

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

联结词的完备集
我们已经知道了很多联结词，有一元的比如取反，剩下的都是二元的，但对任意一个有n个命题变项的命题公式A，我们使用多少个联结词就能通过与命题变项的组合把A完整的表述出来呢？

定义：设C是一个联结词的集合，如果任何由n个命题变项组成的命题公式都存在仅使用C中的联结词构成的等值公式，则称C是完备的联结词集合，或联结词的完备集。同时当 C是一个联结词的完备集时，C中某个联结词可以通过其他联结词表达出来，这个联结词叫冗余联结词。不含有冗余联结词的联结词的完备集叫极小完备集。

定理1：如果对联结词完备集A来说，其中所有联结词都可以通过联结词集合B中的联结词表达出来，那么B也是联结词的完备集

定理2：以下常见联结词集合都是完备集

  • {~,∧,∨} 显然这不是一个极小完备集，∧,∨都是冗余联结词（两者只有一个即可）
  • {~,∧}
  • {~,∨}
  • {~,\to}

其证明如下

  1. 有上节内容，根据命题公式的主析取范式的唯一性，而主析取范式由这三种联结词构成，所以是完备集
  2. p∨q\equiv \sim\sim(p∨q)\equiv\sim(\sim p\ ∧\sim q)，且1是完备集，故2也是完备集
  3. p∧q\equiv \sim\sim(p∧q)\equiv\sim(\sim p\ ∨\sim q)，且1是完备集，故3也是完备集
  4. p∨q\equiv \sim(\sim p)∨q\equiv\sim p\to q，且3是完备集，故4也是完备集

再给出两个二元联结词

与非：对命题p,q，p与非q，记作p\uparrow q，表示仅当p,q均为真时，p与非q为假，等值表示为p\uparrow q\equiv\sim (p∧q)

或非：对命题p,q，p或非q，记作p\downarrow q，表示仅当p,q均为假时，p或非q为真，等值表示为p\downarrow q\equiv\sim (p∨q)

下面证明这两个联结词是完备集
与非：\sim p\equiv\sim(p∧p)\equiv p\uparrow p,p∧q\equiv \sim\sim(p∧q)\equiv \sim( p\uparrow q)

上面的完备集中，至少需要两个联结词，而与非，或非本身已经是完备集，这也解答了为什么逻辑电路中，选用或非门或者与非门的一种，就可以构造出全部的逻辑电路（而现实中也的确是这么做的）

命题的逻辑推理

基于国内外教材顺序的不同，本小节内容建议先阅读离散数学及其应用1.6节至1.8节内容后再来学习


image.png

image.png

image.png

这里补充一下，之前我们用p\to q表示p蕴含q，在推理证明部分我们用p\Rightarrow q式表示蕴含式p\to q为永真式，即

image.png

image.png

image.png

也就是说我们只关注p为真时，q也为真，而不在意p为假时，q的真假（而p蕴含q则包括这一情况）

image.png

其实使用演绎法会发现最后是~p与~q间的关系，这是无论如何也无法用符号联结的

image.png

演绎法


image.png

image.png
  • 前后件附加
    (A\Rightarrow B)\Rightarrow ((A∨C)\Rightarrow(B∨C))
    (A\Rightarrow B)\Rightarrow ((A∧C)\Rightarrow(B∧C))
    (A\Rightarrow B)\Rightarrow ((C\Rightarrow A)\Rightarrow(C\Rightarrow B))
  • 对偶 (A\Rightarrow B)\Rightarrow(B^*\Rightarrow A^*)
image.png

名词初看比较唬人，下面写一些自己的理解：

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png

image.png
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,185评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,445评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 157,684评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,564评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,681评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,874评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,025评论 3赞 408
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,761评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,217评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,545评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,694评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,351评论 4赞 332
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,988评论 3赞 315
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,778评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,007评论 1赞 266
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,427评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,580评论 2赞 349

推荐阅读更多精彩内容