命题逻辑基本概念

主要内容

1.命题与真值(或真假值)。 
2.简单命题与复合命题。 
3.联结词:否定联结词┐,合取联结词∧,析取联结词∨,蕴涵联结词→,等价联结词《命题逻辑基本概念》。 
4.命题公式(简称公式)。 
5.命题公式的层次和公式的赋值。
6.真值表。
7.公式的类型(重言式(或永真式),矛盾式(或永假式),可满足式)。

学习要求

1.在5种联结词中,要特别注意蕴涵联结的应用,要弄清三个问题: 
 ① p→q的逻辑关系
② p→q的真值
③ p→q的灵活的叙述方法 
2.写真值表要特别仔细认真,否则会出错误。 
3.深刻理解各联结词的逻辑含义。 
4.熟练地将复合命题符号化。 
6.会用真值表求公式的成真赋值和成假赋值。

===========================================

命题与联结词

命题的概念

作为命题的陈述句所表达的判断结果称为命题的真值,真值只取两个值:真或假。真值为真的命题称为真命题,真值为假的命题称为假命题。真命题表达的判断正确,假命题表达的判断错误。任何命题的真值都是唯一的

判断给定句子是否为命题,应该分两步:

  • 首先判定它是否为陈述句,
  • 其次判断它是否有唯一的真值。 

例1.1 判断下列句子是否为命题。

  • (1) 4是素数。
  • (2) 《命题逻辑基本概念》 是无理数。
  • (3) x大于y。 
  • (4) 月球上有冰。 
  • (5) 2100年元旦是晴天。 
  • (6) π大于《命题逻辑基本概念》吗? 
  • (7) 请不要吸烟!
  • (8) 这朵花真美丽啊! 
  • (9) 我正在说假话。

        解: 本题的(9)个句子中,(6)是疑问句,(7)是祈使句,(8)是感叹句,因而这3个句子都不是命题。剩下的6个句子都是陈述句,但(3)无确定的真值,根据x,y的不同取值情况它可真可假,即无唯一的真值,因而不是命题。若(9)的真值为真,即“我正在说假话”为真,也就是“我正在说真话”,则又推出(9)的真值应为假;反之,若(9)的真值为假,即“我正在说假话”为假,也就是“我正在说假话”,则又推出(9)的真值应为真。于是(9)既不为真又不为假,因此它不是命题。像(9)这样由真推出假,又由假推出真的陈述句称为悖论。凡是悖论都不是命题。本例中,只有(1),(2),(4),(5)是命题。(1)为假命题,(2)为真命题。虽然今天我们不知道(4),(5)的真值,但它们的真值客观存在,而且是唯一的,将来总会知道(4)的真值,到2100年元旦(5)的真值就真相大白了。


复合命题与联结词

各种论述和推理中,出现的命题多数比例1.1中的命题更加复杂。


例1.2 《命题逻辑基本概念》是有理数是不对的; 2是偶素数; 2或4是素数; 如果2是素数,则3也是素数; 2是素数当且仅当3也是素数。 全是命题

上述命题都是通过诸如“或”,“如果……,则……”等连词联结而成,这样命题,称为复合命题。相对地,构成复合命题的命题称为简单命题

数理逻辑中,通常通过下列“联结词”来构成复合命题。

  • 方式一例1.2中“《命题逻辑基本概念》是有理数是不对的”是“《命题逻辑基本概念》是有理数”的否定。

定义1.1 设p为命题,复合命题“非p”(或“p的否定”)称为p的否定式,记作┐p,符号┐称作否定联结词。并规定┐p为真当且仅当p为假

  • 方式二例1.2中“2是偶素数”是“2是偶数”且“2是素数”的复合。

定义1.2: 设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式,记作p∧q,∧称作合取联结词。并规定p∧q为真当且仅当p与q同时为真 

 问题:“既……又……”、“不但……而且……”、“虽然……但是……”、“一面……一面……”等联结而成地复合命题是否仍为合取式?还有哪些“合取词”?


复合命题真假值

 通常用1表示真,用0表示假,复合命题的真假值如表1.1。

表1.1 基本复合命题的真值
《命题逻辑基本概念》

联结词可以嵌套使用,在嵌套使用时,规定如下优先顺序: ( ),┐,∧,∨,→,《命题逻辑基本概念》,对于同一优先级的联结词,先出现者先运算。


例1.7 令 p:北京比天津人口多。
                q:2+2=4.

                r:乌鸦是白色的。

    求下列复合命题的真值:

     (1) ((┐p∧q)∨(p∧┐q))→r
     (2) (q∨r)→(p→┐r)
     (3) (┐p∨r)《命题逻辑基本概念》(p∧┐r)

p,q,r的真值分别为1,1,0,容易算出(1),(2),(3)的真值分别为1,1,0。

命题公式及其赋值

命题公式的定义

上节说明了命题可以表示为符号串,那么符号串是否都代表命题呢?显然不是,如“PV”,“PP→”。哪些符号串代表命题呢?

由于简单命题是真值唯一确定的命题逻辑中最基本的研究单位,所以也称简单命题为命题常项命题常元。从本节开始对命题进一步抽象,首先称真值可以变化的陈述句为命题变项命题变元,也用p,q,r,…表示命题变项。当p,q,r,…表示命题变项时,它们就成了取值0或1的变项,因而命题变项已不是命题。这样一来,p,q,r,…既可以表示命题常项,也可以表示命题变项。在使用中,需要由上下文确定它们表示的是常项还是变项。

定义1.6

  • (1)单个命题变项是合式公式,并称为原子命题公式。 
  • (2)若A是合式公式,则(┐A)也是合式公式。 
  • (3)若A,B是合式公式,则(A∧B),(A∨B),(A→B),(A《命题逻辑基本概念》B)也是合式公式。 
  • (4)只有有限次地应用(1)~(3)形式的符号串才是合式公式。

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

如:(p→q)∧(q《命题逻辑基本概念》r),(p∧q)∧┐r,p∧(q∧┐r)等都是合式公式,而pq→r,(p→(r→q)等不是合式公式。

注意定义1.6给出的合式公式的定义方式称为归纳定义方式,下文中还将多次出现这种定义方式。


公式的层次

为描述公式构造的复杂性,引入下列“层次”定义。

定义1.7

  • (1)若公式A是单个的命题变项,则称A为0层合式
  • (2)称A是n+1(n≥0)层公式是指下面情况之一:
  • (a) A=┐B,B是n层公式;
    • (b) A=B∧C,其中B,C分别为i层和j层公式,且n=max(i,j);
    • (c) A=B∨C,其中B,C的层次及n同(b);
    • (d) A=B→C,其中B,C的层次及n同(b);
    • (e) A=B《命题逻辑基本概念》C,其中B,C的层次及n同(b);
  • (3)若公式A的层次为k,则称A是k层公式

易知,(┐p∧q)→r,(┐(p→┐q))∧((r∨s)《命题逻辑基本概念》┐p)分别为3层和4层公式。


公式的赋值

公式就代表命题,但代表的命题是真还是假呢?

在命题公式中,由于有命题符号的出现,因而真值是不确定的。当将公式中出现的全部命题符号都解释成具体的命题之后,公式就成了真值确定的命题了。

例如,在公式(p∨q)→r中,若将p解释成:2是素数,q解释成:3是偶数,r解释成:《命题逻辑基本概念》是无理数,则p与r被解释成真命题,q被解释成假命题了,此时公式(p∨q)→r被解释成:若2是素数或3是偶数,则《命题逻辑基本概念》是无理数。这是一个真命题。若p,q的解释不变,r被解释为:《命题逻辑基本概念》是有理数,则(p∨q)→r被解释成:若2是素数或3是偶数,则《命题逻辑基本概念》是有理数。这是个假命题。其实,将命题符号p解释成真命题,相当于指定p的真值为1,解释成假命题,相当于指定p的真值为0。下面的问题是,指定p,q,r的真值为何值时,(p∨q)→r的真值为1;指定p,q,r的真值为何值时,(p∨q)→r的真值为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)∨(p1∧p2)中,000(p1=0,p2=0,p3=0),110(p1=1,p2=1,p3=0)都是成真赋值,而001(p1=0,p2=0,p3=1),011(p1=0,p2=1,p3=1)都是成假赋值。在(p∧┐q)→r中,011(p1=0,p2=1,p3=1)为成真赋值,100(p1=1,p2=0,p3=0)为成假赋值。 

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


真值表

为看清公式在赋值下的取值,通常构造下面的“真值表”。

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

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

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

例1.8 求下列公式的真值表,并求成真赋值和成假赋值。

    (1)(┐p∧q)→┐r
    (2)(p∧┐p)《命题逻辑基本概念》(q∧┐q)

    (3) ┐(p→q)∧q∧r

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

表1.2 (┐p∧q)→┐r的真值表
《命题逻辑基本概念》

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

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

表1.3 (p∧┐p)《命题逻辑基本概念》(q∧┐q)的真值表
《命题逻辑基本概念》


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

表1.4 ┐(p→q)∧q∧r的真值表
《命题逻辑基本概念》

表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∧q)→┐r为非重言式的可满足式,公式(2)(p∧┐p)《命题逻辑基本概念》(q∧┐q)为重言式,而公式(3)┐(p→q)∧q∧r为矛盾式。

:关于n个命题变元P1,P2,…,Pn,可以构造多少个真值表呢? n个命题变元共产生2n个不同赋值,在每个赋值下,公式的值只有0和1两个值。于是n个命题变元的真值表共有《命题逻辑基本概念》种不同情况。

习题

1.将下列命题符号化。
  (1)刘月跑得快,跳得高。

  (2)老王是山东人或河北人。

  (3)因为天气冷,所以我穿了羽绒服。

  (4)王欢与李乐组成一个小组。

  (5)李辛与李末是兄弟。

  (6)王强与刘威都学过法语。

  (7)他一面吃饭,一面听音乐。

  (8)如果天下大雨,他就乘班车上班。

  (9)只有天下大雨,他才乘班车上班。

  (10)除非天下大雨,他才乘班车上班。

  (11)下雪路滑,他迟到了。

  (12)2与4都是素数,这是不对的。

  (13)“2或4是素数,这是不对的”是不对的。

2.将下列命题符号化,并给出各命题的真值:

  (1)若3+2=4,则地球是静止不动的。

  (2)若3+2=4,则地球是运动不止的。

  (3)若地球上没有树木,则人类不能生存。

  (4)若地球上没有水,则《命题逻辑基本概念》是无理数。

3.将下列命题符号化,并给出各命题的真值:

  (1)2+2=4当且仅当3+3=6。

  (2)2+2=4的充要条件是3+3≠6。

  (3)2+2≠4与3+3=6互为充要条件。

  (4)若2+2≠4,则3+3≠6,反之亦然。

4.设p:2+3=5。
       q:大熊猫产在中国。
       r:复旦大学在广州。

求下列复合命题的真值:
  (1)(p《命题逻辑基本概念》q)→r
  (2)(r→(p∧q))《命题逻辑基本概念》┐p
  (3)┐r→(┐p∨┐q∨r)
  (4)(p∧q∧┐r)《命题逻辑基本概念》((┐p∨┐q)→r)
5.用真值表判断下列公式的类型:
  (1)p→(p∨q∨r)
  (2)(p→┐q)→┐q
  (3)┐(q→r)∧r
  (4)(p→q)→(┐q→┐p)
  (5)(p∧r)《命题逻辑基本概念》(┐p∧┐q)
  (6)((p→q)∧(q→r))→(p→r)
  (7)(p→q)《命题逻辑基本概念》(r《命题逻辑基本概念》s)

关于Discrete Mathematics更多讨论与交流,敬请关注本博客和新浪微博songzi_tea.

    原文作者:松子茶
    原文地址: https://blog.csdn.net/utimes/article/details/45032849
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞