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

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

的成真赋值。记为

alphaleft(Aright)=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的主析取范式。

代码语言：javascript复制

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

主合取范式：

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

代码语言：javascript复制

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

极大项，极小项:

alpha 变量 对象 计算机

0 人点赞