二、命题逻辑的等值演算

一、等值式

常见的等值式：

20200517195132685.jpg

例一：判断公式类型

$p \wedge r \wedge \neg(q \rightarrow p)$

$\iff p\wedge r\wedge \neg(\neg q\vee p)$

$\iff p\wedge r\wedge( q\wedge\neg p)$

$\iff p\wedge \neg p\wedge r\wedge q$

所以，公式为矛盾式

$(\neg P \wedge Q) \rightarrow\neg R$

$\iff \neg(\neg P\wedge Q)\vee \neg R$

$\iff P\vee \neg Q\vee \neg R$
  明显地，存在一个成真赋值：111

  存在一个成假赋值：011

  所以，公式为可满足式
例二：证明 $q \rightarrow(p \rightarrow r) \Leftrightarrow(p \wedge q) \rightarrow r$

$q \rightarrow(p \rightarrow r)$

$\iff \neg q\vee \neg(p\rightarrow r)$

$\iff \neg q\vee (\neg p\vee \neg r)$

$\iff (\neg q\vee\neg p) \vee r$

$\iff \neg(q\wedge p) \vee r$

$\iff (p \wedge q) \rightarrow r$

二、析取范式、合取范式

p为任意命题变量，则p和 $\neg p$ 称为文字。
有限个文字的析取称为析取式。

有限个文字的和取称为合取式。
有限个合取式的析取称为析取范式。

有限个析取式的合取称为合取范式。

三、主析取范式、主合取范式

主析取范式
- 含有n个命题变元的合取式G（ $p_1,p_2,...p_n$ ），若每个 $p_i$ 和 $\neg p_i$ 出现且仅出现一次，而且出现的次序与 $p_1,p_2,...p_n$ 的次序保持一致，称该G（ $p_1,p_2,...p_n$ ）为一个小项（极小项）。
- 对析取范式 $A_1\vee A_2\vee ...\vee A_n$ ，若其中每个合取式 $A_i(i=1,2,..,n)$ 都是小项，则称该析取范式为主析取范式。
主合取范式
- 含有n个命题变元的析取式G（ $p_1,p_2,...p_n$ ），若每个 $p_i$ 和 $\neg p_i$ 出现且仅出现一次，而且出现的次序与 $p_1,p_2,...p_n$ 的次序保持一致，称该G（ $p_1,p_2,...p_n$ ）为一个大项（极大项）。
- 对合取范式 $A_1\wedge A_2\wedge ...\wedge A_n$ ，若其中每个析取式 $A_i(i=1,2,..,n)$ 都是大项，则称该析取范式为主析取范式。

最后编辑于：2020.10.08 15:48:16

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

二、命题逻辑的等值演算

一、等值式

二、析取范式、合取范式

三、主析取范式、主合取范式

友情链接更多精彩内容