胡广.top

the ready for discrete mathmatics

离散数学

第一章

命题逻辑

重要术语

  • 非：\huge \neg
  • 合取\huge \bigwedge
  • 析取\huge \bigvee
  • 蕴含\huge \to
  • 等价\huge \leftrightarrow

等值演算

  • 等值式：如果\huge A\leftrightarrow B是重言式，则称A与B等值，记作\huge A\Leftrightarrow B
  • 分配律： \huge A\bigwedge(B\bigvee C)\Leftrightarrow (A\bigwedge B)\bigvee(A\bigwedge C)
  • 德摩根率：\huge \neg(A\bigwedge B)\Leftrightarrow \neg A \bigvee \neg B
  • 蕴含等值式：\huge A\to B \Leftrightarrow \neg A\bigvee B
  • 等价等值式：\huge A\leftrightarrow B\Leftrightarrow(A\to B)\bigwedge(B\to A)
  • 假言易位：\huge A\to B\Leftrightarrow \neg B\to \neg A
  • 等价否定等值式：\huge A\leftrightarrow B\Leftrightarrow \neg A\leftrightarrow \neg B

术语

  • 命题常项：用p、q、r等等确定的简单命题，真值是确定不变的
  • 命题变项：用p、q、r等等表示真值不确定的简单陈述句
  • 变量：上面提到的p、q、r等等就是变量，它们的取值为0或1
  • 合式公式：由有限个命题变项或者命题常项组成的公式
  • 极小项：设有n个命题变项，若在简单合取式中每个命题变项以文字的形式出现且仅出现一次，则称这样的简单合取式为极小项
  • 真值表：设公式A含有n个命题变项，将A在2^n种赋值下的情况列成表，称为A的真值表
  • 赋值或解释：设A为一个公式，\huge p_1,p_2,p_3,\cdots,p_n是出现在A中的全部命题变项，给\huge p_1,p_2,p_3,\cdots,p_n各指定一个真值称为对A的一个赋值或者解释。
  • 成真赋值：赋值或解释使A真值为1
  • 成假赋值：赋值或解释使A真值为0

公式的分类

  • 设A是一个公式
  • 若A无成假赋值，那么称A为重言式或者永真式
  • 若A无成真赋值，那么称A为矛盾式或者永假式
  • 若A至少有一个成真赋值，那么A称为可满足式
  • 若A至少有一个成真赋值，又至少有一个成假赋值，那么A称为非重言式的可满足式

公式的层次

  • 设A是单个的命题变项，则称A为0层公式
  • 称A是n+1层公式是指以下的请情况
  1. $\huge A=\neg B$,B为n层公式
  2. $\huge A=B\bigwedge C$或者$\huge A=B\bigvee C$或者$\huge A=B\to C$或者$\huge A=B\leftrightarrow C$，其中B、C分别为i，j层公式，其中n=max(i,j)
  3. 若A的层次为k，那么称A为k层公式

范式

  • 文字：命题变项及其否定统称为文字
  • 简单析取式：由有限个文字组成的析取式
  • 简单合取式：由有限个文字组成的合取式
  • 极小项：设有n个命题变项，若在简单合取式中每一个变项以文字的形式出现且仅出现一次，则称这样的简单合取式为极小项。n个命题变项共可产生2^n个不同的极小项，分别记为m_0 , m_1 ,\cdots,m_{2^n-1}，其中i (0\leq i\leq 2^n-1)的二进制表示即为m_i的成真赋值
  • 极大项：设有n个命题变项，若在简单析取式中每一个变项以文字的形式出现且仅出现一次，则称这样的简单合取式为极大项。n个命题变项共可产生2^n个不同的极大项，分别记为M_0,M_1,\cdots,M_{2^n-1}，其中i (0\leq i\leq 2^n-1)的二进制表示即为M_i的成假赋值
  • 在极小项和极大项中，文字通常按照下角标或字典顺序排列
  • 析取范式：由有限个简单合取式组成的析取式
  • 主析取范式：由有限个极小项组成的析取范式
  • 合取范式：由有限个简单析取范式组成的合取范式
  • 主合取范式：由有限个极大项组成的合取范式

主要定理

  • 任何一个公式都存在与其等值的析取范式和合取范式
  • 任何一个公式都存在唯一与其等值的主析取范式和主合取范式

联结词全功能集

  • 真值函数：记\huge {\lbrace 0,1 \rbrace}^n= \lbrace 0\cdots 00,0 \cdots 01,\cdots ,1 \cdots 11 \rbrace，即所有长为n的0、1的符号串的集合，称定义域为\huge {\lbrace 0,1 \rbrace }^n，值域为\huge \lbrace 0,1 \rbrace的函数为n元真值函数，有\huge 2^{2^n}个不同的n元真值函数
  • 联结词全功能集：设S为一个联结词集合，若任意真值函数都可以用仅含S中的联结词的公式表示，则称S为联结词的全功能集
    • $\huge \lbrace \neg,\bigwedge,\bigvee,\to,\leftrightarrow \rbrace , \lbrace \neg,\bigvee,\bigwedge \rbrace , \lbrace \neg,\bigvee \rbrace , \lbrace \neg,\bigwedge \rbrace , \lbrace \uparrow \rbrace , \lbrace \downarrow \rbrace , \lbrace \neg,\to \rbrace$这些都是联结词的全功能集
  • 与非式：设p、q为两命题，复合命题“p与q的否定”称为p与q的与非式，记作\huge p\uparrow q
    • $\huge p\uparrow q=\neg(p\bigwedge q)$，其中的$\huge \uparrow$称为与非联结词
    • $\huge p\uparrow q$为假当且仅当$\huge p、q$都为真
  • 或非式：设\huge p、q为两命题复合命题“p或q的否定”称为p或q的或非式，记作\huge p\downarrow q
    • $\huge p\downarrow q=\neg(p\bigvee q)$，其中的$\huge \downarrow$称为或非联结词
    • $\huge p\downarrow q$为真当且仅当$\huge p、q$同时为假

组合电路

设计组合电路的一般步骤：
1. 写出问题的输入~输出表，也就是写出问题的真值函数
2. 根据真值函数写出它的主析取范式
3. 将主析取范式化简展开式，可采用奎因·莫克拉斯基方法化简

推理理论

  • 推理的形式结构
    • 设\huge A_1,A_2,\cdots,A_k,B为命题公式称\huge (A_1\bigwedge A_2\bigwedge\cdots\bigwedge A_k)\to B为推理的形式结构
    • $\huge A_1,A_2,\cdots,A_k$为推理的前提，$\huge B$为推理的结论，如果$\huge (A_1,A_2,\cdots,A_k)\to B$为重言式，那么称为推理正确,这个时候称B是$\huge A_1,A_2,\cdots,A_k$的逻辑结论或有效结论，记为$\huge (A_1\bigwedge A_2\bigwedge \cdots\bigwedge A_k)\Rightarrow B$

推理理论

  • 称重言蕴含式为推理定律，主要的推理定理：
    • 附加：\huge A\Rightarrow (A\bigvee B)
    • 化简：\huge (A\bigwedge B)\Rightarrow A
    • 假言推理：\huge ((A\to B)\bigwedge A)\Rightarrow B
    • 拒取式：\huge ((A\to B)\bigwedge \neg B\Rightarrow \neg A
    • 析取三段论：\huge ((A\bigvee B)\bigwedge \neg A)\Rightarrow B
    • 假言三段论：\huge ((A\to B)\bigwedge(B\to C))\Rightarrow (A\to C)
    • 等价三段论：\huge ((A\leftrightarrow B)\bigwedge(B\leftrightarrow C))\Rightarrow(A\leftrightarrow B)
    • 构造性二难：\huge (A\to B)\bigwedge (C\to D)\bigwedge (A\bigvee C)\Rightarrow(B\bigvee D)

判断推理是否正确

  • 即判断推理的形式结构是否为重言式，主要方法：
  1. 真值表法
  2. 等值演算法
  3. 主析取、主合取范式法

推理规则

  1. 前提引入规则
  2. 结论引入规则
  3. 置换规则
    > 接下来的部分上面是前提，下面是结论
  4. 假言推理规则：

\huge A\to B

\huge \qquad A

\huge \overline{\therefore B\qquad \qquad }

  1. 附加规则：

\huge \qquad A

\huge \overline{\therefore A\bigvee B}

  1. 化简规则

\huge A\bigwedge B

\huge \overline{\therefore A\qquad}

  1. 拒取式规则：

\huge A\to B

\huge \qquad \neg B

\huge \overline{\therefore \qquad\neg A}

  1. 假言三段论规则：

\huge A\to B

\huge B\to C

\huge \overline{\therefore A\to C}

  1. 析取三段论规则：

\huge A\bigvee B

\huge \neg A

\huge \overline{\therefore B\qquad}

  1. 合取引入规则

\huge A

\huge B

\huge \overline {\therefore A\bigwedge B}

  1. 构造性二难规则

\huge A\to B

\huge C\to D

\huge A\bigvee C

\huge \overline{\therefore B\bigvee D}

其他的一些证明方法

  1. 构造证明法
    • 证明是一个描述推理过程的命题公式序列，其中的每个命题公式或者为已知的前提，或者是由前面的公式应用推理规则得到的结论（中间结论）
  2. 附加前提证明法
    • 设推理的结论是蕴含式\huge A\to B,把结论中的前件A作为前提，称为附加前提，证明结论中的后件B为有效结论
  3. 归谬法
    • 把推理的结论B的否定\huge \neg B作为前提，推出矛盾，即证明0为有效结论

第一章节小结

  • 命题都是陈述句，但是陈述句不都是命题。只有当陈述句所表达的判断结果是唯一的时候（正确或者错误的），它才是命题
  • 基本等值式一共有24个

第二章

一阶逻辑

基本概念

  • 个体词
    • 在一阶逻辑中，简单命题被分解成主语和谓语两个部分，表示主语的词称为个体词
    • 具体或者特定的词称为个体常项，抽象或者泛指的词称为个体变项，个体变项的取值范围称为个体域。
    • 宇宙中一切事物组成的个体域称为全总个体域
  • 谓词
    • 用于刻画个体词的性质或者描述个体词之间的关系
    • 谓词分为个体常项和个体变项
    • 为了讨论个体域中有共同性质的个体的其他性质，首先要引进表示其共同性质的谓词，这叫做特性谓词
  • 量词
    • 表示数量的词。表示存在的量词称为存在量词，符号为\exist。表示所有的量词称为全称量词,符号为\forall

一阶逻辑的公式及其解释

  • 字母表
    • 个体常项：a,b,c,···,a_i
    • 个体变项：x，y，z，···，x_i
    • 函数符号：f,g,h,···,f_i
    • 谓词符号：F,G,H,···
    • 量词符号：\exist \forall
    • 联结词：上一章讲到的
    • 括号与逗号
  • 项
    • 个体常项和个体变项都是项
    • 由有限个项组成的项也是项
  • 原子公式
    • 由谓词连接项
  • 合式公式
    • 原子公式和由联结词构成的公式是合式公式
  • 指导变元，辖域
    • 在公式\forall xA和\exist xA中，称x为指导变元，称A为相应量词的辖域。当x为指导变元时，A中x的所有出现都称为是约束出现，A中不是约束出现的个体变项称为自由出现。若在\forall xA和\exist xA中，无自由出现的个体变项，则称它们为闭式。

第三章

集合的基本概念和运算

第四章

二元关系和函数

你的登录窗口呢

,