命题逻辑等值演算

前言:第二章!

0X00 等值式

设公式 A、B 共同含有 n 个命题变项,若 A 与 B 有相同的真值表,则说明在 2^{n} 个赋值下,A 和 B 的真值相同

因此:

A \leftrightarrow B 恒为真,是「重言式」。此时称 A 与 B 是「等值式」记做 A \Leftrightarrow B

例题:判断下面两个公式是否等值

\neg(p \vee q)\neg(p \wedge q)

由于真值表完全相同!所以这两个公式等值

为了接下来的「等值演算」,我们必须学会一些等值式定律。

例:证明 p \rightarrow (q \rightarrow r) \Leftrightarrow (p \wedge q) \rightarrow r

0X01 析取范式和合取范式

基本概念

  • 文字

命题变项及其否定的统称

比如 q 可以叫做文字,\neg q 也可以叫做一个文字

  • 简单析取式

有限个「文字」构成的析取式

比如:

p, \neg q, p \vee q....

  • 简单合取式

有限个「文字」构成的合取式

比如:

p, \neg q, p \wedge q....

  • 范式

「析取范式」和「合取范式」的总称

  • 析取范式

有限个「简单合取式」组成的「析取式」

比如:

p, \neg q, p \wedge q, p \vee \neg q, (p \wedge q) \vee (p \wedge \neg q) ....

注意前四个,这都是「简单合取式」数目为 1 的「析取范式」

  • 合取范式

有限个「简单析取式」组成的「合取式」

p, \neg q, p \wedge q, p \vee \neg q, (p \vee q) \wedge (p \vee \neg q) ....

注意前四个,这都是「简单析取式」数目为 1 的「合取范式」

「极小项」以及「极大项」

先感性地认识「极小项」以及「极大项」首先我们拿两个「命题变相」形成「极小项」和「极大项」

同样也可以用三个命题变项,形成「极小项」和「极大项」

为了方便记忆,我是这么理解的:合取范围变小,所以是「极小项」、析取范围变大,所以是「极大项」

「主合取范式」和「主析取范式」

之前说了「合取范式」:有限个「简单析取式」组成的「合取式」

如果「简单析取式」是「极大项」那么这个范式就是「主合取范式」

相反如果,「析取范式」中的「简单合取式」是「极小项」的话这个范式就是「主析取范式」

在后面我会举一个求「主合取范式的例子」

0X02 联结词的完备集

假设 S 是一个联结词集合,如果任何 n(n>0)元真值函数都可以由仅含 S 中的联结词构成的公式表示,则 S 是「联结词的完备集」

我们有一个最基本的完备集:

\{\neg, \wedge, \vee\}

也就是说所有的真值函数都能用这三个联结词表示!

0X03 用等值演算法得到「主析取范式」和「主合取范式」

举个例子,求:p \vee q \vee r 的「主析取范式」和「主合取范式」

在这里不写出完整过程,只是将 p 转换成「极小项」的方法记录下来

p

\Leftrightarrow (p \wedge q \wedge r) \vee (p \wedge \neg q \wedge r) \vee (p \wedge \neg q \wedge \neg r) \vee (p \wedge q \wedge \neg r)

这一步可以直接写,缺啥补啥

\Leftrightarrow m_{7} \vee m_{6} \vee m_{4} \vee m_{5}

最后!「极小项」还可以和「极大项」互相转换

\Leftrightarrow M_{0} \wedge M_{1} \wedge M_{2} \wedge M_{3}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,793评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,567评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,342评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,825评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,814评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,680评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,033评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,687评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 42,175评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,668评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,775评论 1 332
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,419评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,020评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,978评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,206评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,092评论 2 351
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,510评论 2 343

推荐阅读更多精彩内容

  • 非真即假的陈述句称为命题 不能被分解的命题称为简单命题或原子命题,由简单命题通过联结词联结而成的命题称为复合命题 ...
    乘瓠散人阅读 3,139评论 0 1
  • 一.五个联结词 否定 合取 析取 蕴含 等价 1.文氏图分析 2.对于蕴含关系,只需要记住,只有前件为真后件为假,...
    Flashpoint阅读 2,526评论 0 0
  • 第四部分的主题是再论演绎推理。由第11章到第14章组成。 第11章-复合命题 引出检验有效性的一种方法,即通过真值...
    yannit阅读 2,389评论 1 2
  • 演讲是一种技能,任何技能的提升,必须通过学和练的结合,二者缺一不可,可能你会说我每天听龙兄师的分享就是学,可我没地...
    极致践行者上贝阅读 163评论 0 0
  • 一 、阅读<<首席增长官>> 我一直觉得很多销售最后卖的不是商品而是自己 二、书写 001 今天早上正常5:45起...
    思远同学阅读 102评论 0 0