精华内容
下载资源
问答
  • 1.2命题公式及其赋值

    千次阅读 2019-08-14 10:52:00
    上节讨论了简单命题(原子命题)和复合命题以及它们的符号化形式简单命题命题逻辑中最基本的研究单位,其真值是确定的,又称作命题常项或命题常元,命题常项相当于初中的常数。初等数学中还有变量,对应地这里有命题变项...

    上节讨论了简单命题(原子命题)和复合命题以及它们的符号化形式简单命题是命题逻辑中最基本的研究单位,其真值是确定的,又称作命题常项或命题常元,命题常项相当于初中的常数。初等数学中还有变量,对应地这里有命题变项。取值1(真)或0(假)的变元称作命题变项或命题变元可以用命题变项表示真值可以变化的陈述句.命题变项不是命题,命题变项与命题常项的关系如同初等数学中变量与常量的关系今后也用p,q,r,…表示命题变项这样来,P,q,r,…既可以表示命题常项,又可以表示命题变项,通常可以由上下文确定。

    将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为合式公式,当使用联结词集{┓,A,V,→,<->}时,合式公式定义如下.

    定义1.6 (1)单个命题变项和命题常项是合式公式,并称为原子命题公式.

    1. 若A是合式公式,则(┓A)是合式公式
    2. 若A,B是合式公式,则(A∧B),(AVB),(A→B),(A<->B)是合式公式
    3. 有限次地应用(1)~(3)形成的符号串是合式公式

    合式公式也称为命题公式命题形式,简称为公式.

    设A为合式公式,B为A中一部分,若B也是合式公式,则称B为A的子公式.

    对于定义1.6,要做以下说明:

    1. 定义1.6给出的合式公式的定义方式称为归纳定义或递归定义方式,下文中还将多次出现这种定义方式
    2. 定义中引进了A,B等符号,用它们表示任意的合式公式,称作元语言符号.而某个具体的公式,如p,P∧q,(P∧q)→r等称作对象语言符号.所谓对象语言是指用来描述研究对象的语言,而元语言是指用来描述对象语言的语言,这两种语言是不同层次的语言.做一个不完全恰当的类比,中国人学英语,常用汉语描述英语,英语是对象语言,而汉语就成了元语言。
    3. 为方便起见,(┓A),(A∧B)等公式单独出现时,外层括号可以省去,写成┓A,A∧B等,另外,公式中不影响运算次序的括号也可以省去,如公式(pVq)V(┓r)可以写成pVgV┓r

    由定义可知,(p→q)∧(q<->r),(P∧q)∧┓r,p∧(q∧┓r)等都是合式公式,而pq->r,p->(r->q等不是合式公式。

    下面给出公式层次的定义

    定义1.7(1)若公式A是单个的命题变项,则称A为0层公式

    1. 称是n+1(n≥0)层公式是指下面情况之一:
    1. A=┓B,B是n层公式
    2. A=BAC,其中B,C分别为i层和j层公式,且n=max(i,j)
    3. A=BVC,其中B,C的层次及n同(b)
    4. A=B→C,其中B,C的层次及n同(b)
    5. A=B<->C,其中B,C的层次及n同(b)
    1. 若公式A的层次为k.则称A是k层公式

    例如,(┓p∧q)→r,((p→┓q))∧((rVs)<->┓p)分别为3层和4层公式

    在命题公式中.由于有命题变项的出现,因而真值是不确定的,用命题常项替换公式中的命题变项称作解释.当将公式中出现的全部命题变项都解释成具体的命题常项之后,公式就成了真值确定的命题.例如,在公式(pVq)→r中,若将p解释成:2是素数,q解释成:3是偶数,r解释成:√2是无理数,则公式(pVq)→r被解释成:若2是素数或3是偶数,则2是无理数.这是一个真命题.若p,q的解释不变,r被解释为:2是有理数,则(pVq)→r被解释成:若2是素数或3是偶数,则√2是有理数.这是一个假命题,还可以给出这个公式各种不同的解释,其结果不是得到真命题就是得到假命题.其实,将命题变项p解释成真命题,相当于指定p的真值为1,解释成假命题,相当于指定p的真值为0

    定义1.8设p1,P2,…,Pn是出现在公式A中的全部命题变项,给p1,P2,…,Pn各指定一个真值,称为对A的一个赋值或解释.若指定的一组值使A为1,则称这组值为A的成真赋值;若使A为0,则称这组值为A的成假赋值

    在本书中,对含n个命题变项的公式A的赋值采用下述记法

    1.若A中出现的命题变项为p1,P2,…,Pn。,A的赋值α1α2…αn,是指p1=α1,p2=α2,…,pn=αn

    2.若A中出现的命题变项(按字母顺序)为p,q,r,…,A的赋值α1α2…αn是指p=α1,q=α2,…,最后字母赋值αn其中αi,为0或1,i=1,2,...,n

    例如,在公式(┓P1∧┓P2∧p3)V(P1∧P2)中,000(P1=0,P2=0,P3=0),110(P1=1,P1=1,P3=0)都是成真赋值,而001(P1=0,P2=0,P3=1),011(P1=0,P2=1,p3=1)都是成假赋值.在(pA┓q)→r中,011(p=0,q=1,r=1)为成真赋值,100(p=1,q=0,r=0)为成假赋值.

    不难看出,含n(n≥1)个命题变项的公式共有2"个不同的赋值

    定义1.9将命题公式A在所有赋值下取值情况列成表,称作A的真值表

    构造真值表的具体步骤如下

    1. 找出公式中所含的全体命题变项P1,P2,...,pn(若无下角标就按字母顺序排列),列出2n个赋值.赋值从00…0开始,然后按二进制加法依次写出每个赋值,直到11…1为止
    2. 按从低到高的顺序写出公式的各个层次
    3. 对应各个斌值计算出各层次的真值,直到最后计算出公式的真值

    如果两个公式A与B的真值表对所有赋值最后一列都相同,即最后结果都相同,则称这两个真值表相同,而不考虑构造真值表的中间过程

    例1.8写出下列公式的真值表,并求它们的成真赋值和成假赋值:

    1. (┓p∧q)-->┓r
    2. (p^┓q)<->(q^┓q)
    3. ┓(p->p)^q^r

    解:公式(1)是含3个命题变项的3层合式公式。它的真值表如表1.2所示:

     

     

    从表1.2可知公式(1)的成假赋值为011,其余7个赋值都是成真赋值

    公式(2)是含2个命题变项的3层合式公式,它的真值表如表1.3所示.从表1.3看出该公式的4个赋值全是成真赋值,即无成假赋值。

     

    公式(3)是含3个命题变项的4层合式公式,它的真值表如表1.4所示。不难看出,该公式的8个赋值全是成假赋值,无成真赋值。

     

    表1.2~表1.4都是按构造真值表的步骤一步一步地构造出来的,这样构造真值表不易出错.如果构造的思路比较淸楚,有些层次可以省略

    根据公式在各种赋值下的取值情况,可按下述定义将命题公式进行分类

    定义1.10设A为任一命题公式

    1. 若A在它的各种赋值下取值均为真,则称A是重言式或永真式
    2. 若A在它的各种赋值下取值均为假,则称A是矛盾式或永假式
    3. 若A不是矛盾式A是可满足式

    从定义不难看出以下几点

    1. A是可满足式的等价定义是:A至少存在一个成真赋值
    2. 重言式一定是可满足式,但反之不真.若公式A是可满足式,且它至少存在一个成假赋值则称A为非重言式的可满足式
    3. 真值表可用来判断公式的类型
    1. 若真值表最后一列全为1,则公式为重言式
    2. 若真值表最后一列全为0,则公式为矛盾式
    3. 若真值表最后一列中至少有一个1,则公式为可满足式

    从表1.2~表1.4可知,例1.8中,公式(1)(┓p^g)→┓r为非重言式的可满足式,公式(2)(p^┓p)<->(q^┓q)为重言式,而公式(3)┓(P->q)^q^r为矛盾式

    从以上的讨论可知,真值表不但能准确地给出公式的成真赋值和成假赋值,而且能判断公式的类型

    给定n个命题变项,按合式公式的形成规则,自然可以形成无穷多种形式各异的公式,现在要问:这些公式的真值表是否也有无穷多种不同的情况呢?答案是否定的.n个命题变项共产生2“个不同的赋值,而任何公式在每种赋值下只能取两个值,0或1,于是含n个命题变项的公式的真值表只有2种不同的情况,因而必有无穷多个公式具有相同的真值表

    例1.9下列各公式均含两个命题变项p与q,它们中哪些具有相同的真值表?

    1. (p→q)
    2. P<->q
    3. ┓(p^┓q)
    4. (p->q)^(q->p)
    5. ┓qvp

     构造过程略去不写,表1.5给出了5个公式的真值表,从表中可看出,(1),(3)具有相同的真值表,(2),(4)具有相同的真值表

     

    设公式A,B中共含有命题变项P1,P2,...,pn而A或B不全含这些命题变项,比如A中不含pi,pi+1,...,pn,i>=2,称这些命题变项为A的哑元,A的取值与哑元无关,因而在讨论A与B是有相同的真值表时,可将A,B都看成含P1,P2,…,Pn的命题公式

    例1.10 下列公式中,哪些具有相同的真值表

    (1) p->q

    (2) ┓qvr

    (3) (┓pvq)^((p^r)->p)

    (4) (q->r)^(p->p)

     本例中给出的4个公式,总共有3个命题变项P,q和r,r是公式(1)的哑元,P是公式(2)的哑元,讨论它们是否有相同的真值表时,均按3个命题变项写出它们的真值表.表1.6列出4个公式的真值表,中间过程省略了.从表中看出,(1)与(3)有相同的真值表,(2)与(4)有相同的真值表.

     

     

    展开全文
  • 本资料为原书第2版PDF转为WORD形式而成,仅供学习参考!
  • 由联结词和多个命题常项可以组成复合命题,若是有联结词和多个命题变项则可以组成命题公式。更具体的说,命题公式是由命题常项、命题变项、联结词、括号组成的特殊符号串,通常用大写字母表示。 命题公式的严格定义...

    由联结词和多个命题常项可以组成复合命题,若是有联结词和多个命题变项则可以组成命题公式。更具体的说,命题公式是由命题常项、命题变项、联结词、括号组成的特殊符号串,通常用大写字母表示。

    命题公式的严格定义
    1. 单个命题变项 p , q , r , . . . p,q,r,... p,q,r,...是命题公式
    2. 多个命题公式通过联结词有限次的组合而成的符号串是命题公式

    在命题逻辑中命题公式又称合式公式,简称为公式。

    命题公式的层次

    命题公式的层次是命题公式的重要概念之一,有利于描述命题公式的求解过程。

    定义:

    1. 若命题公式 A A A是单个命题常项或命题变项,则称 A A A是0层公式
    2. 若命题公式 A A A是有其他命题公式通过联结词组合而成的。设组成 A A A的所以命题公式中层次最高命题公式的层次为 n n n,则称 A A A的层次为 n + 1 n+1 n+1
    命题公式的赋值(解释)及真值表

    定义:
    A A A为一个命题公式 p 1 , p 2 , . . . , p n p_1,p_2,...,p_n p1,p2,...,pn A A A中出现的所有命题变项,则给 p 1 , p 2 , . . . , p n p_1,p_2,...,p_n p1,p2,...,pn指定一组真值的行为,称为对 A A A赋值(解释)。若指定的一组值使 A A A的值为真,则称这组值为 A A A成真赋值;若使 A A A的值为假,则称这组值为 A A A成假赋值

    一个含有命题变项的命题公式的真值是不确定的,只有对它的每个命题变项都用指定的命题常项代替后,其真值才唯一确定,命题公式也才能被称为一个命题。

    含有 n n n个命题变项的命题公式共有 2 n 2^n 2n组赋值。
    将命题公式 A A A在所有赋值之下的取值情况列成表,则称该表为 A A A的真值表。构造真值表的步骤如下:

    1. 将命题公式中的所有命题变项按从左到右的出现顺序列出(有脚标则按脚标顺序)
    2. 将所有可能赋值赋给命题变项,从00…0开始,每次加1,直到11…1为止(即以二进制渐增的方式赋值)
    3. 对应的每个赋值公式都计算出其命题公式各层次的值

    举例:
    列出命题公式 ¬ ( p → q ) ∧ q \lnot (p\to q)\land q ¬(pq)q的真值表

    p p p q q q p → q p\to q pq ¬ ( p → q ) \lnot (p\to q) ¬(pq) ¬ ( p → q ) ∧ q \lnot (p\to q)\land q ¬(pq)q
    00100
    01100
    10010
    11100
    命题公式的分类

    定义:
    A A A为一个命题公式

    1. A A A在所有赋值下取值均为真,则称 A A A重言式(永真式)
    2. A A A在所有赋值下取值均为假,则称 A A A矛盾式(永假式)
    3. A A A至少存在一组成真赋值,则称 A A A可满足式

    根据在各种赋值下的取值情况,所有的命题公式都可以分为以上三类。并且根据定义我们可以知道,重言式一定是可满足式,反之不真。

    举例:
    求命题公式 ( p ∧ ( p → q ) ) → q (p\land (p\to q))\to q (p(pq))q是哪种类型的命题公式。
    解:画出真值表

    p p p q q q p → q p\to q pq p ∧ ( p → q ) p\land(p\to q) p(pq) ( p ∧ ( p → q ) ) → q (p\land (p\to q))\to q (p(pq))q
    00101
    01101
    10001
    11111

    由真值表可知命题公式 ( p ∧ ( p → q ) ) → q (p\land (p\to q))\to q (p(pq))q为一个重言式

    真值函数

    定义:
    一个 n ( n ⩾ 1 ) n(n\geqslant 1) n(n1)阶笛卡尔积 { 0 , 1 } n \{0,1\}^n {0,1}n { 0 , 1 } \{0,1\} {0,1}的函数称为一个 n n n元真值函数, n n n元真值函数 F F F记为 F : { 0 , 1 } n → { 0 , 1 } F:\{0,1\}^n\to \{0,1\} F:{0,1}n{0,1}

    n n n个命题变项的真值表实际上是给出 { 0 , 1 } n \{0,1\}^n {0,1}n { 0 , 1 } \{0,1\} {0,1}的一个对应关系,这就是真值函数。 n n n个命题变项,共有 2 n 2^n 2n个可能的赋值。对于每个赋值,真值函数的函数值非0即1。于是 n n n个命题变项共可以组成 2 2 n 2^{2^{n}} 22n个不同的真值函数。其中每一个真值函数都对应一个真值表,同时也对应着无穷个命题公式,这些公式彼此都是等值的,它们中的每一个都是这个真值函数的一个表达式。

    例如,含有两个命题变项 p , q p,q p,q的真值函数共有16个函数值。

    p p p q q q F 1 F_1 F1 F 2 F_2 F2 F 3 F_3 F3 F 4 F_4 F4 F 5 F_5 F5 F 6 F_6 F6 F 7 F_7 F7 F 8 F_8 F8
    0000000000
    0100001111
    1000110011
    1101010101
    p p p q q q F 9 F_9 F9 F 1 0 F_10 F10 F 1 1 F_11 F11 F 1 2 F_12 F12 F 1 3 F_13 F13 F 1 4 F_14 F14 F 1 5 F_15 F15 F 1 6 F_16 F16
    001111111
    0100001111
    1000110011
    1101010101
    展开全文
  • 为观察命题公式在不同赋值下的真值情况,将命题公式 A ( P 1 , P 2 , … , P n ) A(P_1, P_2, \dots, P_n) A(P1​,P2​,…,Pn​) 的所有可能赋值和对应真值形成的各种情况列举出来,就是命题公式的真值表。...

    本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动,欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外,在本系列学习文章中,为了透彻理解数学知识,本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录,在后续学习中还会逐渐补充:

    • 国外经典教材)离散数学及其应用 第七版 Discrete Mathematics and Its Applications 7th ,作者是 Kenneth H.Rosen ,袁崇义译,机械工业出版社
    • 离散数学 第二版,武波等编著,西安电子科技大学出版社,2006年
    • 离散数学 第三版,方世昌等编著,西安电子科技大学出版社,2013年
    • (经典参考书及其题解)离散数学/离散数学——理论•分析•题解,左孝凌、李为鉴、刘永才编著,上海科学技术文献出版社
    • 离散数学习题集:数理逻辑与集合论分册,耿素云;图论分册,耿素云;抽象代数分册, 张立昂。北京大学出版社


    2. 命题公式

    2.1 命题公式及其符号化(难点)

    命题常元 Propositional constant ,表示一个确定命题(真值不是 T T T 就是 F F F)的标识符,一般为 T T T F F F命题变元 Propositional variable ,表示一个不确定或可泛指任意命题的、以“真,假”为其变域的标识符,即真值未确定(但真值唯一)的命题的标识符,表示为 A ,   B ,   C A,\ B,\ C A, B, C 。在此基础上,原子公式指的是单个命题变元命题常元

    命题公式的递归定义如下:

    • (1)基础:单个原子公式是命题公式
    • (2)归纳:如果 A A A B B B 是命题公式,则 ( ¬ A ) ,   ( A ∧ B ) ,   ( A ∨ B ) ,   ( A → B ) ,   ( A ⇔ B ) (¬ A),\ (A∧B),\ (A∨B),\ (A→B),\ (A \Leftrightarrow B) (¬A), (AB), (AB), (AB), (AB) 是命题公式。
    • (3)极小性:只有有限步应用条款(1)和(2)生成的长度有限的符号串才是命题公式。

    这种定义叫归纳定义递归定义。由这种定义产生的公式叫命题公式合式公式 Well formed formula 。若 B B B 是命题公式 A A A 的一个连续段,并且 B B B 也是命题公式,则称 B B B A A A 的一个子公式

    例1:(a) 说明 ( P → ( P ∨ Q ) ) (P→(P∨Q)) (P(PQ)) 是命题公式。
    解:

    • (i) P是命题公式,根据条款(1)
    • (ii) Q是命题公式,根据条款(2)
    • (iii) ( P ∨ Q ) (P∨Q) (PQ) 是命题公式,根据(i)(ii)和条款(2)
    • (iv) ( P → ( P ∨ Q ) ) (P→(P∨Q)) (P(PQ)) 是命题公式,根据(i)(iii)和条款(2)

    (b) ∧ Q ∧Q Q ( P → Q (P→ Q (PQ P → ∧ Q P→∧Q PQ ( ( P Q ) ∧ R ) ((PQ)∧R) ((PQ)R) 都不是命题公式, 因为它们不能由形成规则得出。

    注意,并非由命题常元/变元、联结词和一些括号组成的字符串都能成为命题公式

    例2. 符号化下列命题:
    ① 若天不下雨也不下雪,则我去学校。
    解: P P P:天下雨; Q Q Q:天下雪; R R R:我去学校。于是命题公式是, ( ¬ P ∧ ¬ Q ) → R (\lnot P \wedge \lnot Q) \to R (¬P¬Q)R

    翻译时约定:运算符结合力的强弱顺序为 : ¬ ¬ ¬ ∧ ∧ ∨ ∨ → → ⇔ \Leftrightarrow 凡符合此顺序的,括号均可省去。相同的运算符,按从左至右次序计算时,括号可省去。最外层的圆括号可以省去。

    ② 林芬和林芳是姐妹。
    解: P P P:林芬和林芳是姐妹。这是一个原子命题。

    ③ 除非你掌握情况,否则你不能作出科学判断。
    解: P P P:你掌握情况; Q Q Q:作出科学判断。于是命题公式为, ¬ P → ¬ Q \lnot P \to \lnot Q ¬P¬Q 或其逆否命题 Q → P Q \to P QP

    ④ 说离散数学枯燥无味或毫无价值,那是不对的。
    解: P P P:离散数学是枯燥无味的; Q Q Q:离散数学是毫无价值的。于是命题公式为, ¬ ( P ∨ Q ) ¬(P\vee Q) ¬(PQ)

    2.2 命题公式的赋值 assign

    命题公式的真值往往取决于所含命题变元的真值。设 p 1 , p 2 , … , p n p_1, p_2, \dots, p_n p1,p2,,pn 是命题公式 A A A 中出现的所有命题变元,如果给 p 1 , p 2 , … , p n p_1, p_2, \dots, p_n p1,p2,,pn 指定一组真值,则称为对命题公式 A A A 赋值/指派/解释。

    显而易见,对于含有 n n n 个命题变元的命题公式 A ( P 1 , P 2 , … , P n ) A(P_1, P_2, \dots, P_n) A(P1,P2,,Pn) ,由于每个命题变元可以有 T , F T, F T,F 两个不同赋值,因此共有 2 n 2^n 2n 种不同的赋值。

    为观察命题公式在不同赋值下的真值情况,将命题公式 A ( P 1 , P 2 , … , P n ) A(P_1, P_2, \dots, P_n) A(P1,P2,,Pn)所有可能赋值对应真值形成的各种情况列举出来,就是命题公式的真值表。不过真值表有以下约定:

    • 将公式中出现的 n n n 个命题变元,按照字典升序或降序排列;
    • 对于 2 n 2^n 2n 个不同赋值,按照对应的 n n n 位二进制数从小到大或从大到小的顺序排列;
    • 若公式较复杂,可从里到外先列出各个子公式的真值,最后列出所求公式的真值。

    在这里插入图片描述

    从真值表的各种情况发现,可以将命题公式分为三类:重言式、矛盾式、偶然式:

    • 给定一个命题公式,如果在任何赋值下,它的真值都为 T T T ,则称该命题公式为重言式 tautology永真式;如 ¬ P ∨ P \lnot P\vee P ¬PP
    • 给定一个命题公式,如果在任何赋值下,它的真值都为 F F F ,则称该命题公式为矛盾式 contradiction永假式;如 ¬ P ∧ P \lnot P\wedge P ¬PP
    • 给定一个命题公式,如果它既不是永真式,也不是永假式,则称该命题公式为偶然式 contingency ;如 P ∨ Q P\vee Q PQ
    • 对一个命题公式 A A A ,如果至少存在一种赋值,使得 A A A 的真值为 T T T ,则称 A A A可满足的 satisfiable
    • 对一个命题公式 A A A ,如果至少存在一种赋值,使得 A A A 的真值为 F F F ,则称 A A A非永真

    从而有以下推论:

    • 重言式和偶然式都是可满足式;如果一个命题不是可满足式,则它是矛盾式。
    • 如果命题公式 A A A 为重言式,则 ¬ A \lnot A ¬A 为矛盾式。反之亦然。
    • 如果命题公式 A , B A, B A,B 均为重言式,则 ( A ∧ B ) (A\wedge B) (AB) ( A ∨ B ) (A\vee B) (AB) ( A → B ) (A\to B) (AB) ( A ↔ B ) (A \leftrightarrow B) (AB) 都是重言式。

    关于可满足式,还有一个有趣的问题:SAT,即判断一个命题公式是否为一个可满足式。关于SAT问题的介绍和2-SAT问题的解法,见[这篇文章]。

    展开全文
  • 1.2命题公式及其分类 基础定义: 命题常元:代表特定简单命题 命题变元:代表任意命题,取值为1或0的变量 二者定义可类比我们常数,与未知数。 命题公式的定义: 每一个命题常元或命题变元都是命题公式 ...

    1.2命题公式及其分类

    基础定义:

    • 命题常元:代表特定简单命题
    • 命题变元:代表任意命题,取值为1或0的变量(注意命题变元不是命题)

    二者定义可类比我们常数,与未知数。

    命题公式的定义:

    1. 每一个命题常元或命题变元都是命题公式
    2. 若A是命题公式,则(¬A)是命题公式
    3. 若A和B都是命题公式,则(A∧B),(A∨B),(A→B),(A↔B)都是命题公式
    4. 一个由命题常元或命题变元,联结词和括号所组成的符号串是命题公式,当且仅当这个符号串是有限次应用上面的步骤得到的。

    不难理解,一个含有命题变元的命题公式的真值是不确定的(就像X+1的值我们不知道)。只有当公式中的所有命题变元被指定成特定命题时,命题公式才成为命题。

    对命题公式A内所有命题变元赋值后,使A的真值为真的赋值称为成真赋值,使A的真值为假的赋值称为成假赋值

    若命题公式中有n个变项,则命题公式有 2 n 2^n 2n个赋值。(因为每个变量都有且只有0,1两种状态)

    可用画真值表的方法判断命题公式的真值,例如:

    1. (¬p∧q)→q

    真值表

    1. ¬(p→ q)↔ ¬(p ∧ ¬q)

    真值表

    1. (p→q)∧ ¬r

    真值表

    • 若一个命题公式A像情况1一样,在它的各种赋值下取值为真,则称A为永真式重言式
    • 若一个命题公式A像情况2一样,在它的各种赋值下取值为假,则称A为永假式矛盾式
    • 若一个命题公式A像情况3一样,至少有一种赋值使A的真值为真,则称A为可满足式

    所有,易得:

    1. 公式A不是可满足式,则一定是永假式
    2. 公式A不是永假式,则一定是可满足式
    3. 公式A是永真式,则¬A一定是永假式

    练习:

    1.设p:2是素数 ,q:3是素数 ,r: 2 \sqrt 2 2 是有理数,下列命题公式中哪个是假命题?

    • (p∨q)→ r ✔
    • r → ( p∨q )
    • ( p∧q ) → p
    • ( r∨q ) ↔ p

    2.命题公式 (¬p → q)→ ( ¬q ∨ p )中,成真赋值的个数为?

    • 0
    • 1
    • 2
    • 3 ✔

    3.下列命题公式不是永真式的是?

    • (p → q)→ p ✔
    • p → ( q → p )
    • ¬p ∨ ( q → p )
    • (p → q ) ∨ p

    4.下列式子为矛盾式的是 ?

    • p ∨ ( p ∧ q )
    • p ∨ ¬p
    • p ∧ ¬p ✔
    • ¬( p∨ q ) → ¬p ∧ ¬q
    展开全文
  • 命题公式及分类

    千次阅读 2020-03-09 13:41:46
    命题公式及分类 0x00 前言 本篇文章参考教材为:屈婉婷《离散数学(第五版)》——第一章 命题逻辑 一切以此书为准,本文为学习总结所用如有偏差,是本人才疏学浅,望指正???? 0x10 命题公式 抽象的说,命题公式是由...
  • 命题公式的主范式

    千次阅读 2020-11-26 19:43:57
    命题公式的主范式题目信息输入输出解答想法 题目信息 输入命题公式的合式公式,求出公式的真值表,并输出该公式的主合取范式和主析取范式。 输入 命题公式的合式公式 输出 公式的主析取范式和主析取范式,输出形式...
  • C语言 命题公式真值表

    千次阅读 2020-11-21 00:49:36
    输入任意命题公式,要求用数据存储命题公式的所有赋值及对应真值,并输出该公式真值表 此题,难度稍大,对命题公式的表示的方式不一样,实现过程略有不同,可查找相关资料。 3.实验过程(主要思想、核心算法、...
  • 第一章 命题和命题公式 学习目标 1、理解命题的概念,能够正确的判别什么是命题,并能够给出命题的真值 ①具有唯一真值的陈述句称作命题。真值为真的命题称为真命题,真值为假的称为假命题。 ②由原子命题通过联结词...
  • 命题常元:表示确定的命题{T,F}。...3)若A、B是命题公式,则(AΛB)、(A∨B)、(A→B)、(A↔B)均为命题公式 4)当且仅当有限次使用 (1)(2)(3)所生成的公式才是命题公式。 例如:(¬(P ∨.
  •  先分析一下思路,总体上讲,在我能力范围内的表达式求值方法通常是利用栈来实现(在此之外还有二叉树),命题公式的求值同样如此,因为有不同的赋值情况,所以我们要利用一个数组通过下标识别的方法来进行赋值。...
  • [离散] 编程求命题公式真值表

    万次阅读 多人点赞 2017-03-18 09:41:19
    [离散] 编程求命题公式真值表概述 真值表是离散数学中的一个重要概念,由真值表我们能求得任意命题公式的主析取范式和主合取范式。本文将用C语言编写一个求任意命题公式真值表的程序
  • 命题公式
  • 已知命题公式(¬p→q)→(¬q∨p)(\lnot p\rightarrow q)\rightarrow(\lnot q \lor p)(¬p→q)→(¬q∨p) 构造真值表 p,q (¬p→q)(\lnot p\rightarrow q)(¬p→q) (¬q∨p)(\lnot q \lor p)(¬q∨p) (¬p→q)→...
  • “离散数学”实验报告(求给定命题公式的真值表一.实验目的3二.实验内容……………………………………………………………………….3求任意一个命题公式的真值表3三.实验环境3四. 实验原理和实现过程(算法描述)31.实验...
  • A-Z + is OR * is AND _ is → # is⊕(圆圈里加个bai+) @ is ⊙$ is ↑ 命题的"与非" 运算du( "与非门zhi" )% is ↓ 命题的"或非"运算( "或非门" )Input the source formula:A*!S+RNORMALc: (!A*!B*!R)+(A*!B*!R)+(!...
  • 命题公式的真值表计算

    千次阅读 2020-04-16 09:17:48
    1.包括了如何得到后缀式 还有后缀式的计算 2.关于去重问题 用set存储命题中的字母 起...5.关于命题变元的真假值赋值 可以参考子集得到方法 i&(1<<j) /* //草稿图 */ #include<iostream> #include&l...
  • 命题公式A在所有赋值下取值情况列成表,称作A的真值表。 构造真值表的具体步骤如下: (1) 找出公式中所含的全体命题变项p1,p2,…,pn (若无下角标就按字典顺序排列),列出2n个赋值。本课程规定,赋值从00…0开始,...
  • 给定多个合法的命题公式,编写一个程序,提取所有命题公式中的以单个小写字母(‘a’~‘z’)表示的命题变元,并按命题变元字母的升序顺序,输出命题变元字典。 【输入】 本题只有一组测试数据,测试数据为表示多个...
  • 2.1 谓词逻辑的合式公式(谓词公式) 与命题公式类似,不存在逻辑联结词和量词的单个谓词,如 P ( x 1 , x 2 , … , x n ) ( n ≥ 0 ) P(x_1, x_2, \dots, x_n)\ (n \ge 0) P(x1​,x2​,…,xn​) (n≥0) 称为谓词...
  • http://www.cnblogs.com/6DAN_HUST/archive/2011/12/14/2287671.html 来源:中科院研究生课程 主讲人:高随祥
  • 离散数学命题公式求值及真值表题目要求算法思想代码总结 题目要求 给定任意一个命题公式的真值表,并根据真值表求主范式。 算法思想 将逻辑表达式转换为后缀表达式,然后套用逆波兰表达式的求值方法 利用位运算,找...
  • 通过此课题,熟练掌握命题公式的计算机表示、命题等价常见算法的实现,实现一个简单的命题逻辑应用系统。2 需要实现的功能或函数(1)计算显示任一个命题公式的真值表;(2)计算命题公式的主析取范式;(3)计算命题公式...
  • 给定一个合法的命题公式,编写一个程序,提取命题公式中的所有以单个小写字母(‘a’~‘z’)表示的命题变元,并按命题变元字母的升序顺序,输出命题变元字典。 【输入】 本题单组测试数据,测试数据为单独占一行的...
  • 的主析取范式与主合取范式,并求公式的成真赋值和成假赋值。 a1 = [0,0,0,0,1,1,1,1]; a2 = [0,0,1,1,0,0,1,1]; a3 = [0,1,0,1,0,1,0,1]; a4 = [1,1,0,0,1,1,0,0]; fprintf('在本题中用!代表非,&代表合取,-&...
  • 赋值

    2021-07-16 03:40:27
    将某一数值赋给某个变量的过程,称为赋值。将确定的数值赋给变量的语句叫做赋值语句。各程序设计语言有自己的赋值语句,赋值语句也有不同的类型。所赋“值”可以是数字,也可以是字符串和表达式。中文名赋值领域...
  • 离散数学基础(命题的合式公式

    万次阅读 2016-04-17 15:17:01
    所有符合定义的合式公式构成合式公式空间,它可被视为命题逻辑的符号化语言。语言的结构包括符号表、语法规则(即合适公式定义)和语义(也即真值)。 • 定义:符号化语言 Lp 的符号表包括 − 小写英文字母:p, q

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,236
精华内容 494
关键字:

命题公式的赋值