复旦大学：《离散数学——代数结构与数理逻辑》PPT课件_22/29

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

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

在任何命题代数中,可利用F和→定义 元运算一和其它二元运算,,,定义为: def p=p→>F pVq=(-p)→>q p入q=-(p)(q)) p<>q=(p>q)∧(q→p)

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

(p)y(q)可简写为p∨-q 运算的优先次序排列为: >∧>V>>4 在相同优先级的运算之间,先左后右

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

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

§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

定义18.4:设v为X→Z2的映射,称v为命 题变元的一个指派。 v(p→>q)=v(p)→v(q)=1+v(p)(1+v(q) 1+v(p)+v(pv(g); v(p)=v(p→F)=v(p)→→v(F)=1+v(p)(1+v(F) =1+v(p)(1+0)=1+v(p); v(pq)=v(→p→q)=v(p)-v(q) =1+(1+v(p)(1+v(q)=v(p)+v(q)+v(p)yv(q); v(pAg=v((pv-1g)=1+vepv-1g) -V(pv(q; v(p>q)=v(p→q)(q→p)) 1+v(p+v(g

定义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)

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

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

在P(X)上所定义的一元和二元运算一,八,V,→,),可 分别解释为命题联结词“非”,“合取 析 取”,“蕴含”和“等价”。 列出下述表格(在表中p表示v(p) V(p v(p)v(a)v(pvg) 0 010 0 0 01 p∧q v001 v(p)v(a)v(p<>g) v0101 v0001 0 通过对P(X)的解释, 0 001 命题代数P(X)所建 10 立的形式系统就可 以表示我们所熟悉 的命题

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

对任意的v12n∈Z2将v12V2vn分别 指派给x12x2.xn 由定理18.1知此指派可唯一扩张为赋值 v:P(Xn)→Z 29 此时对任意p∈P(X)都有确定的真值 v(p)∈Z2 由此定义n元真值函数f:Z2n→Z2,使得 p(v1,v2s.vn=v(p) 定义18.5:函数:Z2nZ2称为n元瘪信函 数

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

定义18.6:设p∈P(X),定义p的n元真值函数 Z2Z2为:f=v(p),称为p的度值西数 由p的真值函数所建立的函数值表称为的 真值表。 例:写出合式公式(x1yx2)→(x3→x1)真值表 2 (v1Vv2)→>(-V3>V v000011 0 0 V01010101 0

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

以后可简写为 (XX)→(x→X 000 1000 000 01 0100 0000 00 0111 101 1011

以后可简写为: (x1  x2 ) → (  x3 → x1) 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1