离散数学PPT课件-15命题公式及命题符号.ppt

1-3 命题公式及命题符号化一.常值命题与命题变元常值命题：即是我们前面所说的命题。它是有具体含义(真值)的。例如：“3是素数。”就是常值命题。命题变元：用大写的英字母如P、Q等表示任何命题。称这些字母为命题变元。对命题变元作指派(给命题变元一个解释)：将一个常值命题赋予命题变元的过程，或者是直接赋给命题变元真值“T”或“F”的过程。注意：命题变元本身不是命题，只有给它一个解释，才变成命题。二.合式公式(wff)(well formed formulas)1.定义：单个命题变元是个合式公式。若A是合式公式，则A是合式公式。若A和B是合式公式，则(AB)，(AB)，(AB)和(AB)都是合式公式.当且仅当有限次地应用，所得到的含有命题变元、联结词和括号的符号串是合式公式。注意这个定义是递归的。(1)是递归的基础，由(1)开始，使用(2)(3)规则，可以得到任意的合式公式。这里所谓的合式公式可以解释为合法的命题公式之意，也称之为命题公式，有时也简称公式。下面的式子不是合式公式：PQ，PR，PQR下面的式子才是合式公式：(PQ)，(PR)，(PQ)R)按照合式公式定义最外层括号必须写。约定约定：为方便，最外层括号可以不写，上面的合式公式可以写成：PQ，PR，(PQ)R2.命题公式的真值表 一个命题公式不是命题，所以它没有真值，但是给其中的所有命题变元作指派以后它就有了真值。可以以表的形式反应它的真值情况，例如命题 公式(PQ)Q 的真值表如下所示：P Q P PQ (PQ)Q F F T F F F T T T T T F F T T T T F T T由于对每个命题变元可以有两个真值(T,F)被指派，所以有n个命题变元的命题公式 A(P1,P2,Pn)的真值表有2n行。为了有序地列出公式的真值表，在对命题变元做指派时，可以按照二进制数的次序列表。补充：关于“二进制数”见下页。关于二进制数简介：关于二进制数简介：由于计算机的硬件是由二个状态的逻辑元件组由于计算机的硬件是由二个状态的逻辑元件组成的，所以它只处理二进制的信息成的，所以它只处理二进制的信息.二进制数：只有两个基本符号二进制数：只有两个基本符号0和和1，计算时，计算时，逢二进一逢二进一，如，如 0+1=1，1+1=10，10+1=11，11+1=100 0 1 10 11 +1 +1 +1 [phone]十进制数十进制数 0 1 2 3 4 5 6 7 8 9二进制数二进制数 0 1 10 11 100 101 110 111 1000 1001注注:有效数字前加有效数字前加0不影响数值，如不影响数值，如000=0，001=1，010=10，011=11、为了有序地列出A(P1,P2,Pn)的真值表，可以将F看成0，将T看成1，按照二进制数000,0001,00010,1110,111(即十进制的0,1,2,.,2n-1)的次序进行指派列真值表。如A(P,Q)的真值表可按照如下次序指派：00(F,F)，01(F,T)，10(T,F)，11(T,T)如A(P,Q,R)的真值表可按照如下次序指派：000(F,F,F),001(F,F,T),010(F,T,F),011(F,T,T)100(T,F,F),101(T,F,T),110(T,T,F),111(T,T,T)例如列出例如列出P(QR)的真值表的真值表 P Q R QR P(QR)000 F F F T T001 F F T T T010 F T F F T011 F T T T T100 T F F T T101 T F T T T110 T T F F F111 T T T T T三.命题符号化 所谓命题符号化，就是用命题公式的符号串来表示给定的命题。命题符号化的方法 1.首先要明确给定命题的含义。2.对于复合命题，找联结词，用联结词 断句，分解出各个原子命题。3.设原子命题符号，并用逻辑联结词联 结原子命题符号，构成给定命题的符 号表达式。例1.说离散数学无用且枯燥无味是不对的。P：离散数学是有用的。Q：离散数学是枯燥无味的。该命题可写成：(PQ)例2.如果小张与小王都不去，则小李去。P：小张去。Q：小王去。R：小李去。该命题可写成：(PQ)R例3.如果小张与小王不都去，则小李去。该命题可写成：(PQ)R 也可以写成：(PQ)R例4.仅当天不下雨且我有时间，才上街。P：天下雨。Q：我有时间。R：我上街。分析：由于“仅当”是表示“必要条件”的，既“天不下雨且我有时间”，是“我上街”的必要条件。所以 该命题可写成：R(PQ)例5.人不犯我，我不犯人；人若犯我，我必犯人。P：人犯我。Q：我犯人。该命题可写成：(PQ)(PQ)或写成：PQP是Q的充分条件P是Q的必要条件P是Q的充分且必要条件例例6.若天不下雨，我就上街；否则在家。若天不下雨，我就上街；否则在家。P：天下雨。天下雨。Q：我上街。我上街。R：我在家。：我在家。该命题可写成：该命题可写成：(PQ)(P R).注意注意：中间的联结词一定是：中间的联结词一定是“”，而不是，而不是“”，也，也不是不是“”。因为原命题表示：因为原命题表示：“天不下雨时我做什么天不下雨时我做什么，天天下雨我又下雨我又做什么做什么”的的两种作法，两种作法，其中有一种作法是假的，则我说其中有一种作法是假的，则我说的就是假话，所以中间的联结词一定是的就是假话，所以中间的联结词一定是“”。如果写成如果写成(PQ)(P R)，就表明，就表明两种作法两种作法都是假的都是假的时候，我说的才是假话。这显然不对时候，我说的才是假话。这显然不对。若写成若写成(PQ)(P R)时，当时，当P为为F，Q为为F时，即天没时，即天没下雨而我没上街，此时我说的是假话，但是表达式下雨而我没上街，此时我说的是假话，但是表达式 (PQ)(P R)的真值却是的真值却是“T”，因为此时，因为此时(P R)的的真值真值是是“T”。所以这个表达式也不对。所以这个表达式也不对。作业：P33 1.2,1.4,1.5