定义18.2:设X是可列集，X上的自由T-代数称为X上关于命题演算的命题代数，记为P(X)，并称X为命题变量集，X中的元素称为命题变元，P(X)中的每个元素称为命题演算的合式公式，简记为wff，仅由一个命题变元符组成的合式公式称为原子公式，所有原子公式全体称为原子公式集。

Presentation on theme: "定义18.2:设X是可列集，X上的自由T-代数称为X上关于命题演算的命题代数，记为P(X)，并称X为命题变量集，X中的元素称为命题变元，P(X)中的每个元素称为命题演算的合式公式，简记为wff，仅由一个命题变元符组成的合式公式称为原子公式，所有原子公式全体称为原子公式集。"— Presentation transcript:

1 定义18.2:设X是可列集，X上的自由T-代数称为X上关于命题演算的命题代数，记为P(X)，并称X为命题变量集，X中的元素称为命题变元，P(X)中的每个元素称为命题演算的合式公式，简记为wff，仅由一个命题变元符组成的合式公式称为原子公式，所有原子公式全体称为原子公式集。

2 在任何命题代数中，可利用F和→定义一元运算和其它二元运算,,，定义为：

3 (p)(q)可简写为pq。 运算的优先次序排列为：  >  >  > → >  在相同优先级的运算之间，先左后右。

4 §2 命题演算的语义 一、P(X)的赋值 定义18.3:设P(X)是X上关于命题演算的命题代数，称P(X)→Z2的同态映射v为P(X)的赋值。对于任意的pP(X)，若v(p)=1则称p按赋值v为真，若v(p)=0则称p按赋值v为假。 定理18.1:设A为命题代数，v0为X→A的映射，则v0可唯一扩张为P(X)→A的同态映射v。

5 定义18.4:设v0为X→Z2的映射，称v0为命题变元的一个指派。
v(p→q)=v(p)→v(q)=1+v(p)(1+v(q)) =1+v(p)+v(p)v(q)； v(p)=v(p→F)=v(p)→v(F)=1+v(p)(1+v(F)) =1+v(p)(1+0)=1+v(p)； v(pq)=v(p→q)=v(p)→v(q) =1+(1+v(p))(1+v(q)) =v(p)+v(q)+v(p)v(q)； v(pq)=v((pq))=1+v(pq) =v(p)v(q); v(pq)=v((p→q)(q→p)) =1+v(p)+v(q)

6 二、P(X)中元素的解释和真值表 把P(X)中的每个元素(即命题演算的合式公式)解释为可判断真假的语句 原子公式集中的每个原子公式(命题变元x)表示任意的简单命题(即原子命题) P(X)中的其它元素表示复合命题。 对任意pP(X)和给定的赋值v:P(X)→Z2，若v(p)=1，则说p 所表示的命题为真，简称p为真；若v(p)=0，则说p所表示的命题为假，简称p为假。

7 在P(X)上所定义的一元和二元运算,,, →,,可分别解释为命题联结词“非”，“合取”，“析取”，“蕴含”和“等价”。
列出下述表格(在表中p表示v(p))： 通过对P(X)的解释,命题代数P(X)所建立的形式系统就可以表示我们所熟悉的命题.

8 对任意的v1,v2,vnZ2,将v1,v2,vn分别指派给x1,x2,xn
由定理18.1知此指派可唯一扩张为赋值v:P(Xn)→Z2, 此时对任意pP(Xn),都有确定的真值v(p)Z2 由此定义n元真值函数fp:Z2n→Z2,使得fp(v1,v2,vn)=v(p). 定义18.5:函数f: Z2n→Z2称为n元真值函数

9 定义18.6:设pP(X)，定义p的n元真值函数fp:Z2n→Z2为：fp=v(p)，称fp为p的真值函数。由p的真值函数所建立的函数值表称为p的真值表。
例:写出合式公式(x1x2)→(x3→x1)真值表

10 以后可简写为:

11 三、语言蕴含 定义18.7：设AP(X),qP(X)，若对所有使得v(p)=1(对一切pA)的赋值v，都有v(q)=1，则称q是假设集A的后件，或称A语义蕴含q，记为A╞q，用Con(A)表示A的后件全体，即Con(A)={pP(X)|A╞p}。 注意：A是P(X)的子集，但A本身不是命题公式。 由定义知，对于A中的任意元素p，对所有使得A中元素的赋值为1的赋值v，都有v(p)=1，因此ACon(A).

12 又因为不存在赋值v使得v(F){1}，所以对任意的pP(X)总有pCon(F)。
即对任意qP(X)，有{F}╞q。 定义18.8:设pP(X)，若对P(X)的任意赋值v都有v(p)=1，则称p是有效的，也称为重言式。若对P(X)的任意赋值v都有v(p)=0，则称p是永假式。 因此若╞p，则p就是重言式，简记为╞p 注意A╞p是命题逻辑元语言中的陈述句，但它本身不是P(X)中的元素。

13 例：{p}╞p→q 例：{x1→(x2→x3),x2}╞x1→x3

14 引理18.1:Con 有如下性质： (i)ACon(A) (ii)若A1A2，则Con(A1) Con(A2) (iii)Con(Con(A))=Con(A) 定义18.9：设p,qP(X)，若对P(X)的任意赋值v有v(p)=v(q)，则称p,q等值。

15 定理18.2:下述结论是等价的。 (1)p,q等值。 (2)╞pq。 (3)p,q有相同的真值函数和真值表。 定理18.3:对任意p,q,rP(X)有下述结论： (1)╞pp； (2)╞(pq)pq； (3)╞(pq)pq； (4)╞(p1p2…pn)p1p2…pn (5)╞(p1p2…pn)p1p2…pn

16 四、析取范式和合取范式 定义18.10:形式为 的合式公式称为 析取范式，形式为 的合式公式称 为合取范式，这里yij为某个命题变元xk或其否定xk。 例：(x1x2)(x1x2)(x1x2x3)是析取范式，而 (x1x2)  (x1 x3)是合取范式。

17 定理18.4:任何命题合式公式(即P(X)中的元素)都有只含命题变元及,,这三种运算的合式公式与该命题合式公式等值
证明:对任意p=p(x1,x2,…xn)P(Xn) 1.对P(Xn)中任一赋值v恒有v(p(x1,x2,…xn)) =0 2.存在P(Xn)中的赋值v使得v(p(x1,x2,…xn)) =1 构造与该指派所对应的合式公式y1y2… yn, 使得: 目标是v(yi)=1

18 定义18.11:一个合式公式若不是永假式，则用定理18.4的证明方法得到的等值析取范式称为该合式公式的标准析取范式。
推论18.1:每个非重言式必等值于一个合取范式。 定义18.12:一个合式公式若不是重言式，则用推论18.1的证明方法得到的等值合取范式称为该合式公式的标准合取范式。

19 例：求与(x1→x2)→(x3)等值的标准析取范式和标准合取范式。

20 作业: P ,6,7