2010秋季学期-离散数学-范式 [兼容模式].pdfVIP

离离 散散 数数 学学 Instructor: 李劲 Email: ljatynu@ School of Software Technology YunNan University 2010.9 ~ 2011.1 1.4 范 式—— 问题的提出 Σ为n-元命题公式集合。按 ⇔关系, 将 Σ划分为互不相 交的子集 Σ ,Σ ,...,Σ ,使得 1 2 l ∀P ∈Σ,∀Q ∈Σ ,若 i ≠j ,则P ⇔Q i j ∀P ∈Σ,∀Q ∈Σ ,则 P ⇔Q i i 问题1 ：可将 划分为 个互不相交的子集？ Σ 问题2 ：对于相互等价的命题, 能否找到唯一的等价命题 标准形式（范式）？ 2010-10-11 云南大学软件学院 2 1.4 范 式—— 问题1 2 22 种不同真值列？ ________ P Q 1 1 0 0 1 1 0 0 0 1 … … … 0 1 0 0 1 0 0 0 1 1 P ⇔Q iff P ,Q 对应的真值列相同 含含n个命题变元的公式集个命题变元的公式集 ,, 按按 ⇔ 关系关系,, 可划可划 ΣΣ 分为22n 个互不相交的公式子集, 且同一公式子 集内的任意两个命题公式等价。 2010-10-11 云南大学软件学院 3 1.4 范 式—— 析,合取范式 术语 •• 文字文字 ：：命题常元命题常元 （（TT,FF））,命题变元及其否定命题变元及其否定。 析取子句：文字或若干文字的析取。 P , P ∨¬Q , P Q R • ¬ ∨¬ ∨ •• 合取子句合取子句 ：：文字或若干文字的合取文字或若干文字的合取。 ¬PP ,PP ∧∧¬QQ , PP ∧∧¬QQ ∧∧RR 公式 P ′称为公式 P 的析取范式（dnf）, 如果 • P ′′⇔P • P ′为一合取子句或若干合取子句的析取。 dnfdnf ((PP →→QQ)) :: ¬PP ∨∨QQ dnfdnf ((((((PP →→QQ)) ∧∧¬PP)) ∨∨¬QQ)) :: ¬PP ∨∨((¬PP ∧∧QQ )) ∨∨¬QQ 公式 P ′称为公式 P 的合取范式（cnf）, 如果 • PP ′′⇔PP • P ′为一析取子句或若干析取子句的合取。 cnfcnf ((PP →→QQ)) :: ¬PP ∨∨QQ cnfcnf ((((