离散数学-考纲版-01-命题逻辑

用户2225445

发布于 2023-10-16 17:56:00

4410

发布于 2023-10-16 17:56:00

文章被收录于专栏：IT从业者张某某

1. 命题逻辑的等值演算与推理演算

参考

离散数学知识点总结（5）：蕴含式；命题的推理理论；逻辑推演的方法；推理的有效性证明

1.1 命题

命题：我们对确定对象做出的陈述句称为命题（propositions and statements 命题或陈述）。当判断为真时，该命题为真，否则为假。

今天下雨是命题 √ 你在干什么啊非陈述句 X 我只给所有不给自己理发的人理发悖论 X

原子命题:通常把不含有逻辑联结词的命题称为原子命题或原子(atoms) 复合命题:把由原子命题和逻辑联结词共同组成的命题称为复合命题(compositive propositions or compound statements 综合命题或复合命题)。

1.2 常用联结词

否定：符号

\neg

称作否定联结词 合取：符号

\wedge

称作合取联结词 析取：符号

\vee

称作析取联结词 . 蕴含或条件：符号

\to

称作蕴含或条件联结词 . 双向蕴含或等价：符号

\leftrightarrow

称作双向蕴含或等价联结词 .

联结词优先级

()

>

\neg

>

\wedge

>

\vee

>

\to

>

\leftrightarrow

1.3 命题公式

命题常元：代表特定的简单命题 命题变元：代表任意命题，取值为真或假的变量 命题公式：含有命题变元的表达式。即

P \vee Q

便是一个命题公式

公式的赋值 定义：若命题公式

A

含有的全部命题变元为

p_1,p_2,p_3,p_4…p_n

,给

p_1,p_2,p_3,p_4…p_n

指定一组真值，称为

A

的一个解释或赋值。使

A

的真值为真的赋值称为成真赋值，使A的真值为假的赋值为成假赋值。

指派或赋值:用

\alpha,\beta

等表示当

A

对取值状况

\alpha

为真时，称指派

\alpha

成真

A

，或是

\alpha

是

A

的成真赋值。记为

\alpha\left(A\right)=1

对一切可能的指派，公式

A

的取值可用下表描述，真值表

真值表：命题公式在所有可能的赋值下的取值的列表含n个变形的公式有2的n次方个赋值。

命题公式的分类-重言式-矛盾式-可满足式

若A在它的各种情况下赋值的取值均为真，则称A为重言式或永真式若A在它的各种情况下赋值的取值均为假，则称A为矛盾式或永假式若至少存在一种赋值能使A的真值为真，则称A为可满足式

等价关系式-逻辑等价 logically equivalent

逻辑等价：当命题公式

A \leftrightarrow B

为重言式时，称

A

逻辑等价于

B

，记为

A \Leftrightarrow B

注意:

A \leftrightarrow B

和

A \Leftrightarrow B

是有区别的，符号

A \leftrightarrow B

是逻辑联结词，是运算符。而

A \Leftrightarrow B

是关系符，表示A 和 B的逻辑等价关系。

1.4 命题的等值演算与推理

基本等价式

（1）双重否定律

\neg \neg \Leftrightarrow A

（2）幂等律

A \wedge A \Leftrightarrow A,A \vee A \Leftrightarrow A

（3）交换律

A \wedge B \Leftrightarrow B \wedge A, A \vee B \Leftrightarrow B \vee A

（4）结合律

A \wedge (B \wedge C )\Leftrightarrow (A \wedge B) \wedge C

,

A \vee (B \vee C )\Leftrightarrow (A \vee B) \vee C

A \leftrightarrow (B \leftrightarrow C )\Leftrightarrow (A \leftrightarrow B) \leftrightarrow C

（5）分配律

A \wedge (B \vee C )\Leftrightarrow (A \wedge B) \vee (A \wedge C)

A \vee (B \wedge C )\Leftrightarrow (A \vee B) \wedge (A \vee C)

A \rightarrow (B \rightarrow C) \Leftrightarrow (A \rightarrow B) \rightarrow (A \rightarrow C)

（6）德摩根律

\neg (A \wedge B) \Leftrightarrow \neg A \vee \neg B , \neg (A \vee B) \Leftrightarrow \neg A \wedge \neg B

（7）吸收律

A \wedge (A \vee B )\Leftrightarrow A , A \vee (A \wedge B ) \Leftrightarrow A

（8）零律

A \vee 1 \Leftrightarrow 1 , A \wedge 0 \Leftrightarrow 0

（9）同一律

A \wedge 1 \Leftrightarrow A , A \vee 0 \Leftrightarrow A

（10）排中律

A \vee \neg A \Leftrightarrow 1

（11）矛盾律

A \wedge \neg A \Leftrightarrow 0

（12）蕴涵等值式

A \to B \Leftrightarrow \neg A \vee B

（13）等价等值式

A \leftrightarrow B \Leftrightarrow (A \to B) \wedge (B \to A)

A \leftrightarrow B \Leftrightarrow (\neg A \vee B) \wedge (\neg B \vee A)

A \leftrightarrow B \Leftrightarrow (A \wedge B) \vee (\neg A \wedge \neg B)

（14）假言易位

A \to B \Leftrightarrow \neg B \to \neg A

（15）等价否定等值式

A \leftrightarrow B \Leftrightarrow \neg A \leftrightarrow \neg B

（16）归谬论

(A \to B)\wedge (A \to \neg B) \Leftrightarrow \neg A

逻辑蕴涵重言式 logically implication

当命题公式

A \to B

为重言式，称

A

逻辑蕴涵

B

，记为

A \Rightarrow B

，需要注意重言蕴含

\Rightarrow

与普通蕴含

\rightarrow

的关系。

重言蕴涵推到

\Rightarrow

是命题公式

A

和命题公式

B

的推理关系，

\rightarrow

是两个原子命题的联结关系。

归结法

归结法是计算机进行推理的方法

1.5 命题公式与真值表的关系

对任一依赖于命题变元

p_1,p_2,p_3,p_4…p_n

的命题公式

A

来说，可由

p_1,p_2,p_3,p_4…p_n

的真值根据命题公式

A

给出

A

的真值，从而建立起从

p_1,p_2,p_3,p_4…p_n

到

A

的真值表。反之，若给定了由

p_1,p_2,p_3,p_4…p_n

到

A

的真值表，可以由下述方法，写出命题公式

A

对

p_1,p_2,p_3,p_4…p_n

的逻辑表达式。

由T列来写

由F列来写

1.6 联结词的完备集

参考：【离散数学】数理逻辑第一章命题逻辑(4) 联结词的完备集

完备集

对偶式基本概念

1.7 范式

范式定义与生成步骤

主析取及主合取范式

主析取范式：

设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。

  若干个极小项的析取（并集）。

主合取范式：

设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。

若干个极大项的合取（交集）。

极大项，极小项:

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-04-24，如有侵权请联系 cloudcommunity@tencent.com 删除

alpha

变量

对象

计算机

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度