离散数学笔记(2)——命题逻辑(2)

离散数学笔记(2)——命题逻辑(2)

Contents

命题逻辑

重言蕴涵式

重要的重言蕴涵式

$P \land Q \Rightarrow P,P \land Q \Rightarrow Q$

$P,Q \Rightarrow P \land Q$

$\lnot P \land (P \lor Q) \Rightarrow Q$

$P \land (P \rightarrow Q) \Rightarrow Q$

$\lnot Q \land (P \rightarrow Q) \Rightarrow \lnot P$

$(P \rightarrow Q) \land (Q \rightarrow R) \Rightarrow P \rightarrow R$

性质

自反性、传递性、反对称性等

其他联结词

与非:$P \uparrow Q = \lnot (P \land Q)$

或非:$P \downarrow Q = \lnot(P \lor Q)$

条件否定:$P \mathop{\rightarrow}\limits^c Q = \lnot(P \rightarrow Q)$

等价公式的对偶性

对偶式

在一个只含联结词 $\lnot,\lor,\land$ 的公式 $A$ 中(之后两条默认成立),将 $\lor,\land$ 互换,$T,F$ 互换,其他不变,得到 $A^ *$,称 $A$ 和 $A^ *$ 互为对偶式。

用对偶式求公式的否定

$\lnot A(P_1,\cdots,P_n) = A^*(\lnot P_1,\cdots,\lnot P_n)$

对偶原理

如果 $A(P_1,\cdots,P_n) = B(P_1,\cdots,P_n)$,则 $A^*(P_1,\cdots,P_n) = B^*(P_1,\cdots,P_n)$

推论:若 $A$ 是重言式,则 $A$ 必为矛盾式。

范式

只含有 $\lnot,\lor,\land$。

合取式与析取式

合取式:用 $\land$ 联结命题变元或变元的否定构成的式子。

析取式:用 $\lor$ 联结命题变元或变元的否定构成的式子。

$P,\lnot P$ 两者均可看成。

析取范式与合取范式

析取范式:公式 $A$ 如果写为如下形式:$A_1 \lor A_2 \lor \cdots \lor A_n(n \ge 1)$ 其中每个 $A_i$ 是合取式,称之为 $A$ 的析取范式。

合取范式:公式 $A$ 如果写为如下形式:$A_1 \land A_2 \land \cdots \land A_n(n \ge 1)$ 其中每个 $A_i$ 是析取式,称之为 $A$ 的合取范式。

$P \lor Q \lor R$ 两者均可看成。

析取范式与合取范式的求法

范式定理:任一命题公式都存在与之等值的析取范式和合取范式。

求法:

  1. 先用相应公式去掉 $\rightarrow$ 和 $\leftrightarrow$
  2. 用德-摩根定律将 $\lnot$ 后移到命题变元之前
  3. 用分配律、结合律、幂等律等公式进行整理,使之成为所要求的形式。

主析取范式

小项:在一个有 $n$ 个命题变元的合取式中,每个变元或该变元的否定必出现且仅出现一次,称这个合取式为小项。

每一组指派有且只有一个小项为 $T$。

析取范式 $A_1 \lor A_2 \lor \cdots \lor A_n$ 其中每个 $A_i$ 均为小项,称之为主析取范式。

主合取范式

大项:在一个有 $n$ 个命题变元的析取式中,每个变元或该变元的否定必出现且仅出现一次,称这个析取式为大项。

每一组指派有且只有一个大项为 $F$。

合取范式 $A_1 \land A_2 \land \cdots \land A_n$ 其中每个 $A_i$ 均为大项,称之为主合取范式。

求法

  1. 列真值表
    1. 定理:在真值表中,一个公式的真值为 $T$ 的指派所对应的小项的析取,即为此公式的主析取范式。
    2. 定理:在真值表中,一个公式的真值为 $F$ 的指派所对应的大项的合取,即为此公式的主合取范式。
  2. 公式的等价变换
    1. 先写出对应的析(合)取范式
    2. 补全缺少的变元,用永真(假)式联结
    3. 用分配律等公式加以整理

命题逻辑推理

推理

根据一个或几个已知的判断得出一个新的判断的思维过程。称已知的判断为前提。得到的新的判断为前提的有效结论。

令 $H_1,H_2,\cdots,H_n$ 是已知的命题公式,若有 $H_1 \land H_2 \land \cdots \land H_n \Rightarrow C$,则称 $C$ 是 $H_1,H_2,\cdots,H_n$ 的有效结论,简称结论。

规则

规则 P(引入前提规则)

在推理过程中,可以随时引入前提。

规则 T(引入结论规则)

在推理过程中,如果前面有一个或几个公式永真蕴涵公式 $S$,则可将 $S$ 纳入推理过程中。

规则 CP

如果 $H_1 \land H_2 \land \cdots \land H_n \land R \Rightarrow S$,则 $H_1 \land H_2 \land \cdots \land H_n \Rightarrow R \rightarrow S$

1568692889400

三种推理方法

直接推理、条件论证及反证法

直接推理

格式中包含步骤号,给定前提或得出的结论,推理时所用规则,此结论是从哪几步得到的以及所用公式。

1568691629400

1568691720354

($I$:蕴涵式,$E$:等价式)

条件论证

1568692470771

反证法

主要思想:假设结论不成立,可以推出矛盾的结论(矛盾式)。

定义:设 $H_1,H_2,\cdots,H_n$ 为命题公式,$P_1,P_2,\cdots,P_m$ 是公式中的命题变元,如果对所有命题变元至少有一种指派,使得 $H_1 \land H_2 \land \cdots \land H_n$ 的真值为 $T$,则称公式集合 ${H_1,H_2,\cdots,H_n}$ 是相容的(也称是一致的);如果对所有命题变元每一种指派,都使得 $H_1 \land H_2 \land \cdots \land H_n$ 的真值为 $F$,则称公式集合 ${H_1,H_2,\cdots,H_n}$ 是不相容的(也称是不一致的)。

定理:若要证明相容的公式集合 ${H_1,H_2,\cdots,H_n}$ 可以推出公式 $C$,只要证明 $H_1 \land H_2 \land \cdots \land H_n \land \lnot C$ 是个矛盾式即可。

1568693091264

1568693168515

证明推理不正确:取合适真值使得条件为真,结论为假。

 

点赞 1

No Comments

Add your comment