离散数学数理逻辑部分【1】

小咪咪 2024-03-30 11:48 71阅读 0赞

## 前言 ##

*  本文创作的起因是，经历了离散数学的学习，深感学习离散之艰辛。所以产生了写一些内容帮助大家期末复习。
 *  虽然在csdn发表本文，有些不太合适，但是还是相信本文的质量和内容，可以给正在学习离散数学的大学生提供一些帮助。
 *  由于作者水平有限，不足之处，还请海涵。

![在这里插入图片描述][2e08616696b54d7b90aedbfc0cd162dc.jpeg_pic_center]

#### 文章目录 ####

*  前言
 *  命题逻辑
 *   *  一 命题及真值的判定
     *  命题联结词
     *   *  练习题
     *  合式公式（合适公式）
     *  综合练习题
     *  公式的分类和等价
     *  基本等价公式：设A、B、C为任意公式【重点】

## 命题逻辑 ##

### 一 命题及真值的判定 ###

*  命题的定义
    
     *  定义：***一个具有真假意义的陈述句被称为一个命题。***
 *  解题技巧
    
     *  所有非陈述句都不是命题（感叹句，疑问句，祈使句，命令句）
     *  有歧义的句子也不是命题，如，悖论
     *  命题不需要要知道真值是什么，而是知道具有唯一真值
     *  带有 x , y , z x,y,z x,y,z等变量的句子，则需要认真区分
 *  命题的真值
    
     *  真命题: 真值为真的命题
     *  假命题: 真值为假的命题
 *  原子命题&符合命题：
    
     *  ***一个命题不能再分解为更简单的命题，这个命题称为原子命题*** 如：2是素数
     *  ***复合命题 + 命题可进一步分解***  如：王红学过英语或法语：（王红学过英语） ⋁ （王红学过法语） 如：王红学过英语或法语：（王红学过英语）\\bigvee（王红学过法语） 如：王红学过英语或法语：（王红学过英语）⋁（王红学过法语）  
        ![在这里插入图片描述][8655fcd1f91e4f0b8cf49ae2f83e3278.png]

### 命题联结词 ###

*  命题联结词
    
     *  否定 ¬ \\neg ¬：表示否定
     *  合取 ⋀ \\bigwedge ⋀:两个事件同时成立
     *  析取 ⋁ \\bigvee ⋁ ：表示两件事中至少有一个成立
     *  蕴涵 → \\rightarrow →：表示两舰事之间有条件因果关系
     *  等价 ↔ \\leftrightarrow ↔：表示两件事是等价的

<table> 
 <thead> 
 <tr> 
 <th>P Q</th> 
 <th> P ⋀ Q P\bigwedge Q P⋀Q</th> 
 <th> P ⋁ Q P\bigvee Q P⋁Q</th> 
 <th> P ⟶ Q P\longrightarrow Q P⟶Q</th> 
 <th> P ⟷ Q P\longleftrightarrow Q P⟷Q</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>0 0</td> 
 <td>0</td> 
 <td>0</td> 
 <td>1</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td>0 1</td> 
 <td>0</td> 
 <td>1</td> 
 <td>1</td> 
 <td>0</td> 
 </tr> 
 <tr> 
 <td>1 0</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>0</td> 
 </tr> 
 <tr> 
 <td>1 1</td> 
 <td>1</td> 
 <td>1</td> 
 <td>1</td> 
 <td>1</td> 
 </tr> 
 </tbody> 
</table>

*  关于 ⋀ \\bigwedge ⋀的常考关键词
    
     *  虽然……但是……
     *  既……又……
     *  不仅……而且……
     *  ……并且……
     *  ……和……
     *  ……与……
 *  关于 ⋁ \\bigvee ⋁的两类情况：排斥或（不可兼容或）、相容或（可兼容或）
    
     *  排斥或：p、q不可同时为真  ( p ⋀ ¬ q ) ⋀ ( ¬ p ⋀ q ) (p \\bigwedge \\neg q) \\bigwedge (\\neg p \\bigwedge q) (p⋀¬q)⋀(¬p⋀q)
     *  相容或：p、q不可同时为真  p ⋁ q p \\bigvee q p⋁q
     *  选小王或小李中的一个人当班长
        
         *  p：小王当班长 q：小李当班长
         *   ( p ⋀ ¬ q ) ⋀ ( ¬ p ⋀ q ) (p \\bigwedge \\neg q) \\bigwedge (\\neg p \\bigwedge q) (p⋀¬q)⋀(¬p⋀q)
     *  李明在教室，张强是个好教练
     *  p：李明在教室 q:张强是个好教练
     *   p ⋁ q p \\bigvee q p⋁q
 *  关于蕴涵 ⟶ \\longrightarrow ⟶的提示词
    
     *  蕴涵 ⟶ \\longrightarrow ⟶ 的条件(前件)、结论(后件)
     *  ***条件在前，结论在后***
        
         *  如果……则……
         *  因为……所以……
         *  只要……就……
         *  ……仅当……
     *  特殊的倒装情况：
        
         *  ***只要结论，才条件***
         *  ***除非结论，否则 ¬ \\neg ¬条件***
         *  ***除非结论，才条件***
 *  等价的 ⟷ \\longleftrightarrow ⟷的关键词
    
     *  ……等价……
     *  ……当且仅当……
     *  若……才能……
     *  除非……，否则……
 *  联结词的优先级
 *   ( ) > ¬ > ⋀ > ⋁ > ⟶ > ⟷ () > \\neg > \\bigwedge >\\bigvee > \\longrightarrow > \\longleftrightarrow ()>¬>⋀>⋁>⟶>⟷

#### 练习题 ####

*  除非他以书面形式或口头形式通知我，否则我不会参加明天的会议
    
     *  p：他书面形式同时我，q：他口头形式通知我，r：我参加明天的会议
     *   r ⟶ p ⋁ q r \\longrightarrow p \\bigvee q r⟶p⋁q
 *  虽然你努力了，但还是失败了。
    
     *  p：你努力了，q：你失败了
     *   p ⋀ q p \\bigwedge q p⋀q
 *  占据空间的，有质量的而且不断运动的叫做物质
    
     *  P：它占据空间 ，Q：它没有质量，R：它不断运动，S：它叫做物质。
     *   ( P ⋀ ¬ Q ⋀ R ) ⟶ S (P \\bigwedge \\neg Q \\bigwedge R) \\longrightarrow S (P⋀¬Q⋀R)⟶S

### 合式公式（合适公式） ###

*  括号要匹配
 *  联结词使用是否合适
 *  除变元外，是否存在非联结词符号
 *  判断合适公式
    
     *   ( P ⋀ ¬ Q ⋁ ⋀ R ) (P\\bigwedge \\neg Q \\bigvee \\bigwedge R) (P⋀¬Q⋁⋀R)(×)
     *   P ⋀ ¬ Q ⇒ P P \\bigwedge \\neg Q \\Rightarrow P P⋀¬Q⇒P(×) 无 ⇒ \\Rightarrow ⇒联结词
     *   ( ( P → Q ) → ( R ∧ S ) ((P \\rightarrow Q)\\rightarrow (R \\wedge S ) ((P→Q)→(R∧S)(×)括号不匹配
 *  公式中每个变元有两种取值 0 、 1 0、1 0、1，所有 n n n个命题变原会有 2 n 2^n 2n种可能的取值。
 *  使公式成真的叫成真赋值，为假的交成假赋值。

### 综合练习题 ###

*  有ABC三个猜测甲乙丙三个球队中的冠军，个人的猜测如下：  
    A：冠军不是甲，也不是乙  
    B：冠军不是甲，而是丙  
    C：冠军不是丙，而是甲  
    已知其中有一个人说的完全正确，一个人说的都不对，而另外一个人恰有一半说对了，据此推算，冠军应该是（）  
    A.甲 B.乙 C.丙 D.不确定
 *  设P：甲是冠军 Q：乙是冠军 R：丙是冠军。则ABC三人的说法可分别描述为：
    
     *   ¬ P ∧ ¬ Q \\neg P \\wedge \\neg Q ¬P∧¬Q  ¬ P ∧ R \\neg P \\wedge R ¬P∧R  P ∧ ¬ R P \\wedge \\neg R P∧¬R由于P、Q、R中只能有一个为真，可列真值表如下：

<table> 
 <thead> 
 <tr> 
 <th> P Q R P Q R PQR</th> 
 <th> ¬ P ∧ ¬ Q \neg P \wedge \neg Q ¬P∧¬Q</th> 
 <th> ¬ P ∧ R \neg P \wedge R ¬P∧R</th> 
 <th> P ∧ ¬ R P \wedge \neg R P∧¬R</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>1 0 0</td> 
 <td> 0 ∧ 1 0 \wedge 1 0∧1</td> 
 <td> 0 ∧ 0 0 \wedge 0 0∧0</td> 
 <td> 1 ∧ 1 1 \wedge 1 1∧1</td> 
 </tr> 
 <tr> 
 <td>0 1 0</td> 
 <td> 1 ∧ 0 1 \wedge 0 1∧0</td> 
 <td> 1 ∧ 0 1 \wedge 0 1∧0</td> 
 <td> 0 ∧ 1 0 \wedge 1 0∧1</td> 
 </tr> 
 <tr> 
 <td>0 0 1</td> 
 <td> 1 ∧ 1 1 \wedge 1 1∧1</td> 
 <td> 1 ∧ 1 1 \wedge 1 1∧1</td> 
 <td> 0 ∧ 0 0 \wedge 0 0∧0</td> 
 </tr> 
 </tbody> 
</table>

*  只有当PQR为1 0 0 时符合题目要求，所以冠军应该是甲

### 公式的分类和等价 ###

*  公式类型有三种：
    
    1.  永真式(重言式):公式在所有可能的解释下都为真
    2.  永假式(矛盾式):公式在所有可能的解释下都为假
    3.  可满足式:至少有一种解释使得公式为真
    
     *  永真式(重言式)的否定为永假式(矛盾式)
     *  永假式(矛盾式)的否定为永真式(重言式)
     *  永真式(重言式)是一种特殊的可满足式
 *  两个公式等价( ⟺ \\Longleftrightarrow ⟺): 2个公式在所有解释下真值相同。

### 基本等价公式：设A、B、C为任意公式【重点】 ###

*  双重否定律： ¬ ¬ A = A \\lnot \\lnot A=A ¬¬A=A
 *  幂等律：
    
     *   A ∨ A ⇔ A A \\vee A\\Leftrightarrow A A∨A⇔A
     *   A ∧ A ⇔ A A\\wedge A\\Leftrightarrow A A∧A⇔A
 *  交换律：
    
     *   A ∨ B ⇔ B ∨ A A \\vee B \\Leftrightarrow B\\vee A A∨B⇔B∨A
     *   A ∧ B ⇔ B ∧ A A\\wedge B\\Leftrightarrow B\\wedge A A∧B⇔B∧A
 *  结合律：
    
     *   ( A ∨ B ) ∨ C ⇔ A ∨ ( B ∨ C ) (A \\vee B)\\vee C\\Leftrightarrow A\\vee (B\\vee C) (A∨B)∨C⇔A∨(B∨C)
     *   ( A ∧ B ) ∧ C ⇔ A ∧ ( B ∧ C ) (A\\wedge B)\\wedge C\\Leftrightarrow A\\wedge (B \\wedge C) (A∧B)∧C⇔A∧(B∧C)
 *  分配律：
    
     *   A ∨ ( B ∧ C ) ⇔ ( A ∨ B ) ∧ ( A ∨ C ) A \\vee (B \\wedge C)\\Leftrightarrow(A \\vee B)\\wedge(A \\vee C) A∨(B∧C)⇔(A∨B)∧(A∨C)
     *   A ∧ ( B ∨ C ) ⇔ ( A ∧ B ) ∨ ( A ∧ C ) A \\wedge (B \\vee C)\\Leftrightarrow(A \\wedge B)\\vee(A \\wedge C) A∧(B∨C)⇔(A∧B)∨(A∧C)
 *  德·摩根律：
    
     *   ¬ ( A ∨ B ) ⇔ ¬ A ∧ ¬ B \\lnot (A \\vee B)\\Leftrightarrow \\neg A\\wedge \\lnot B ¬(A∨B)⇔¬A∧¬B
     *   ¬ ( A ∧ B ) ⇔ ¬ A ∨ ¬ B \\lnot(A\\land B) \\Leftrightarrow \\lnot A \\vee \\lnot B ¬(A∧B)⇔¬A∨¬B
 *  吸收律：
    
     *   A ∨ ( A ∧ B ) ⇔ A A\\lor(A\\land B)\\Leftrightarrow A A∨(A∧B)⇔A
     *   A ∧ ( A ∨ B ) ⇔ A A\\land (A\\lor B)\\Leftrightarrow A A∧(A∨B)⇔A
 *  零律：
    
     *   A ∨ 1 ⇔ 1 A\\lor 1\\Leftrightarrow1 A∨1⇔1
     *   A ∧ 0 ⇔ 0 A \\land 0\\Leftrightarrow 0 A∧0⇔0
 *  同一律：
    
     *   A ∨ 0 ⇔ A A \\lor 0\\Leftrightarrow A A∨0⇔A
     *   A ∧ 1 ⇔ A A \\land 1\\Leftrightarrow A A∧1⇔A
 *  排中律：
    
     *   A ∨ ¬ A ⇔ 1 A \\lor \\neg A\\Leftrightarrow 1 A∨¬A⇔1
 *  矛盾律：
    
     *   A ∧ ¬ A ⇔ 0 A \\land \\neg A\\Leftrightarrow 0 A∧¬A⇔0
 *  蕴涵等值式：
    
     *   A → B ⇔ ¬ A ∨ B A \\rightarrow B\\Leftrightarrow \\lnot A \\lor B A→B⇔¬A∨B
 *  等价等值式：
    
     *   A ↔ B ⇔ ( A → B ) ∧ ( B → A ) A \\leftrightarrow B \\Leftrightarrow (A \\rightarrow B)\\land (B\\rightarrow A) A↔B⇔(A→B)∧(B→A)
 *  假言易位：
    
     *   A → B ⇔ ¬ B → ¬ A A\\rightarrow B \\Leftrightarrow \\lnot B \\rightarrow \\lnot A A→B⇔¬B→¬A
 *  等价否定等值式：
    
     *   A ⇔ B → ¬ A ⇔ ¬ B A \\Leftrightarrow B\\rightarrow\\lnot A\\Leftrightarrow \\lnot B A⇔B→¬A⇔¬B

[2e08616696b54d7b90aedbfc0cd162dc.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/51bbe021912c4cdd84c48088e03424ed.jpeg
[8655fcd1f91e4f0b8cf49ae2f83e3278.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a80217ab327a414a9a77ec1c9a9c1ee8.png