数学

本文及其系列文章用于离散数学（1）科目的期末考试复习 命题 命题是一个陈述句，并且可以判断真或假 命题常元，就是$True$和$False$ 命题变项(变元) 一般用大写字母表示,如$P、Q$等 简单命题（原子命题) 指的是不包含任何联结词的命题，不可再分割 符合命题 指的是简单命题用联结词构成的新命题 联结词 否定词$\neg$，即not。 $$\begin{array}{|c|c|}P&{\neg P}\\0&1\\1&0\end{array}$$ 合取词$\land$，即and $$\begin{array}{|cc|c|}P&Q&{P\land Q}\\0&0&0\\0&1&0\\1&0&0\\1&1&1\end{array}$$ 析取词$\lor$，即or $$\begin{array}{|cc|c|}P&Q&{P\lor Q}\\0&0&0\\0&1&1\\1&0&1\\1&1&1\end{array}$$ 蕴含词$\rightarrow$，可以理解为“推导出” $$\begin{array}{|cc|c|}P&Q&{P\rightarrow Q}\\0&0&1\\0&1&1\\1&0&0\\1&1&1\end{array}$$ 双条件词$\leftrightarrow$，可以理解为“当且仅当” $$\begin{array}{|cc|c|}P&Q&{P\leftrightarrow Q}\\0&0&1\\0&1&0\\1&0&0\\1&1&1\end{array}$$ 一般认为，联结词的运算优先级排列为$\neg ，\land ， \lor ，\rightarrow ，\leftrightarrow$ 合式公式定义 这是一个递归定义。 简单命题是合式公式 如果$A$是合式公式，那么$\neg A$也是合式公式 如果$A,B$是合式公式，那么$A\land B,A\lor B,A\rightarrow B,A\leftrightarrow B$是合式公式 当且仅当经过有限次使用$1,2,3$所组成的符号串才是合式公式 公式分类 对于某个命题公式$X$ 如果$X$在任何的解释$I$下都为真， 那么称之为重言式(永真式) 如果$X$在任何的解释$I$下都为假，那么称之为永假式。 如果存在一种解释$I_0$使得$X$为真，那么称之为可满足式。 代入规则 对于某个公式$X$，如果打算用公式$Q$来替换$X$中的$P$，那么这时候我可以记做$\frac{P}{Q}$ 比如，在公式$((R\lor S)\land((R\lor S)\rightarrow (P\lor Q)))\rightarrow (P\lor Q)$中，我们需要用$A,B$来代换$(R\lor S),(P \lor Q)$，这个时候我们会记$\frac{A}{(R\lor S)},\frac{B}{(P \lor Q)}$，用来确保过程用于规范。 ...