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

格 格的定义,最大元,最小元,有界格,有补格 冷子格(是格不一定是子格 给定 Hasse图,判断是否分配格,布尔格 给定 Hasse图,判断某个子集是否为子格 给定格的子集,验证是否为子格。 ☆分配不等式证明分配格等价定理证明 利用性质和上下界的概念证明等式成立。 令格的同态映射,同构映射,保序映射 布尔格,布尔代数 注意分配格不一定是布尔格 布尔环:a2=a,2a=0

❖ 一、格 ❖ 格的定义，最大元，最小元，有界格，有补格 ❖ 子格(是格不一定是子格), ❖ 给定Hasse图，判断是否分配格，布尔格 ❖ 给定Hasse图，判断某个子集是否为子格 ❖ 给定格的子集，验证是否为子格。 ❖ 分配不等式证明,分配格等价定理证明 ❖ 利用性质和上下界的概念证明等式成立。 ❖ 格的同态映射，同构映射，保序映射 ❖ 布尔格，布尔代数 ❖ 注意分配格不一定是布尔格 ❖ 布尔环：a 2=a,2a=0

在布尔代数上定义的环是有单位元的可交换 环,即布尔环; 而有单位元满足幂等律的环布尔环 泛代数 自由T代数 引理17.1定理171,证明方法, 唯一性 存在性构造性证明过程实质上就是后面逻 辑的模型构造方法 给定谓词逻辑公式,化为自由T代数元素中 的形式,并且知道属于哪个Gn

❖ 在布尔代数上定义的环是有单位元的可交换 环,即布尔环; ❖ 而有单位元满足幂等律的环,布尔环 ❖ 二、泛代数 ❖ 自由T-代数 ❖ 引理17.1,定理17.1,证明方法, ❖ 唯一性 ❖ 存在性:构造性证明过程实质上就是后面逻 辑的模型构造方法 ❖ 给定谓词逻辑公式，化为自由T-代数元素中 的形式,并且知道属于哪个Gn

令三、命题逻辑 令设X是可列集,X上的自由T代数称为X 上关干命题演算的命题代数,记为PX), 并称X为命题变量,X中的元素称为 命题变元,P(X)中的每个元素称为命题 演算的合式公式,简记为w,仅由 个命题变元符组成的合式公式称为原子 公式,所有原子公式全体称为原子公式 集

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

对P(X)如何解释 冷设P(X)是X上关于命题演算的命题代数, 称P(X)→Z2的同态映射v为P(X)的赋值。 对于任意的p∈P(X),若v(p)=1则称p按 值为真,若v(p)=0则称p按败值v为 。 真值函数,真值表 ☆标准析取范式,标准合取范式

❖ 对P(X)如何解释 ❖ 设P(X)是X上关于命题演算的命题代数， 称P(X)→Z2的同态映射v为P(X)的赋值。 对于任意的pP(X)，若v(p)=1则称p按 赋值v为真，若v(p)=0则称p按赋值v为 假。 ❖ 真值函数，真值表 ❖ 标准析取范式，标准合取范式

冷设AcP(X),q∈P(X),若对所有使得 v(p)=1(对一切p∈A)的赋值v,都有 v(q)=1,则称q是假设集A的后件,或称 A义蕴含q,记为AFq,用comA表示 的后件全体 conA={p∈P(XAFp 形式证明,给定公理集,MP规则,演绎 定理 命题符号化 分析,问题的化解。 掌握可靠性定理,可满足性定理,完备 性定理的方法

❖ 设 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}。 ❖ 形式证明，给定公理集，MP规则，演绎 定理 ❖ 命题符号化 ❖ 分析，问题的化解。 ❖ 掌握可靠性定理，可满足性定理，完备 性定理的方法

令四、谓词逻辑 个体变元集X个体常元集C 项集l是XUc自由T1)代数 冷Rnt1t是P上的n元关系,为原子关系 原子关系全体Y 冷Y上的自由F,→,xx∈X}-代数P(Y) 给定谓词逻辑公式,化为自由T-代数元素中的 形式,并且知道属于哪个Gn 谓词合式公式,辖域,自由变元,约束变元, 项t对自由变元x自由,能够判断 习题19.6,19.7,19.8 冷求p),d(p)

❖ 四、谓词逻辑 ❖ 个体变元集X,个体常元集C ❖ 项集I是X∪C自由T(1)-代数 ❖ Rn i (t1 ,,tn )是I n上的n元关系,为原子关系 ❖ 原子关系全体Y ❖ Y上的自由{F,→,x|xX}-代数P(Y) ❖ 给定谓词逻辑公式，化为自由T-代数元素中的 形式,并且知道属于哪个Gn ❖ 谓词合式公式，辖域，自由变元，约束变元， 项t对自由变元x自由,能够判断 ❖ 习题19.6, 19.7, 19.8 ❖ 求l(p),d(p)

解释域,项解释,赋值,语义藴涵 冷习题19.12,19.13,19.14,19.15,1922 19.23 ☆形式证明,要求同命题逻辑注意有时可 能规定只能用公理集和演绎定理 注意问题的化解 冷习题18,21 命题符号化 ☆求前束析取范式习题27 Skolen范式

❖ 解释域，项解释，赋值，语义蕴涵 ❖ 习题19.12, 19.13, 19.14, 19.15, 19.22, ❖ 19.23 ❖ 形式证明，要求同命题逻辑,注意有时可 能规定只能用公理集和演绎定理 ❖ 注意问题的化解 ❖ 习题18,21 ❖ 命题符号化 ❖ 求前束析取范式 习题27. ❖ Skolem范式

集合是协调的概念,证明集合是协调的。 掌握演绎定理,完备性定理,协调性定理 掌握可满足性定理(谓词逻辑系统)证明的 基本思路, 掌握演绎定理的证明方法

❖ 集合是协调的概念，证明集合是协调的。 ❖ 掌握演绎定理,完备性定理,协调性定理， 掌握可满足性定理(谓词逻辑系统)证明的 基本思路, ❖ 掌握演绎定理的证明方法

(7)-(pAq)→q 冷证明:即证-(-p-q)→>q 冷由演绎定理即证{(p→-q)-q 令p1=-(7p→7q)=(-p→(q→+F)→F(A) 令p2=(77p→(q→F)→F)→(q→F)→(77p→(q→F) F)(A1) 令p3=(q→F)→(77p→(qF)→F)(p1,p2MP) P4=(q.)F)(-p→(qF)→F)→((4qF)→(7-p (q→F)→(q→F)→F))(A 冷p5=(qF)→(p→(q→F)→(q→F)→F) (p3, p4MP 冷p6=(qF)→(-p→(q→F)(A1) p7=(q→F)→F=77q(p6,p5MP) 冷P8==q→q (A3) 令P9=q (p7, p8MP) 冷可简单,利用-q→(--p→-q)

❖ (7) |-(pq) →q ❖ 证明:即证|-¬(¬¬p→¬q)→q ❖ 由演绎定理即证{¬(¬¬p→¬q)}|-q ❖ p1= ¬(¬ ¬ p → ¬q)=(¬¬p →(q→F)) →F (A) ❖ p2= ((¬¬p →(q→F)) →F) →((q→F) →((¬¬p →(q→F)) →F)) (A1) ❖ p3= (q→F) →((¬¬p →(q→F)) →F) (p1,p2MP) ❖ P4=((q→F) →((¬¬p →(q→F)) →F)) →((((q→F) → (¬¬p →(q→F)))→((q→F) →F))) (A2) ❖ p5= ((q→F) → (¬¬p →(q→F)))→((q→F) →F) (p3,p4MP) ❖ p6= (q→F) → (¬¬p →(q→F)) (A1) ❖ p7= (q→F) →F= ¬¬q (p6,p5MP) ❖ P8= ¬ ¬q →q (A3) ❖ P9=q (p7,p8MP) ❖ 可简单，利用 ¬q → (¬ ¬ p → ¬q)

p1=q(p-→7q) A1 P2=(q→(-p→q)-(- p→>-q))-q)已证 P3=-(p→-q)77q p1, p2MP 冷P4=-(7p→7q) 冷P5=7=q p4, p3MP P6=7q一q (A3) % P7Eq p5, p6MP

❖ p1=¬q→(¬ ¬ p→¬q) A1. ❖ P2=(¬q→(¬ ¬ p→¬q))→(¬(¬ ¬p→¬q)→¬ ¬q) 已证 ❖ P3=¬(¬¬p→¬q)→¬ ¬q p1,p2MP ❖ P4=¬(¬ ¬ p→¬q) A ❖ P5=¬ ¬q p4,p3MP ❖ P6= ¬ ¬q →q (A3) ❖ P7=q p5,p6MP