Posts

本文及其系列文章用于离散数学（1）科目的期末考试复习 基本的推理公式 $(\forall x)P(x)\lor(\forall x)Q(x)\Rightarrow(\forall x)(P(x)\lor Q(x))$⭐️ $(\exists x)(P(x)\land Q(x))\Rightarrow (\exists x)P(x)\land (\exists x)Q(x)$⭐️ $(\forall x)(P(x)\rightarrow Q(x))\Rightarrow (\forall x)P(x)\rightarrow (\forall x)Q(x)$ $(\forall x)(P(x)\rightarrow Q(x))\Rightarrow (\exists x)P(x)\rightarrow (\exists x)Q(x)$ $(\forall x)(P(x)\leftrightarrow Q(x))\Rightarrow (\forall x)P(x)\leftrightarrow (\forall x)Q(x)$ $(\forall x)(P(x)\leftrightarrow Q(x))\Rightarrow (\exists x)P(x)\leftrightarrow (\exists x)Q(x)$ $(\forall x)(P(x)\rightarrow Q(x))\land (\forall x)(Q(x)\rightarrow R(x))\Rightarrow (\forall x)(P(x)\rightarrow R(x))$⭐ $(\forall x)(P(x)\rightarrow Q(x))\land P(a)\Rightarrow Q(a)$⭐ $(\forall x)(\forall y)P(x,y)\Rightarrow (\exists x)(\forall y)P(x,y)$ $(\exists x)(\forall y)P(x,y)\Rightarrow (\forall y)(\exists x)P(x,y)$ 这些推理公式的逆一般是不成立的，所以记住和理解顺序很重要。 推理演算 注意，本节按照老师上课讲义的符号和规则来描述，不同的规定和不同的讲述方式可能导致本节内容在一定程度上不是普适性的。本节适配内容为T大软件学院离散数学（1）的课程及考试内容。 ...

本文及其系列文章用于离散数学（1）科目的期末考试复习 由命题公式得来的等值公式 这部分我们把谓词逻辑看做命题逻辑中的命题变元，命题逻辑中正确的公式也是谓词逻辑中正确的公式。 例如，命题逻辑中，$\neg\neg p=p$是重言式，那么对于谓词逻辑$\neg\neg (\forall x)P(x)=(\forall x)P(x)$是一个有效式。 这部分是谓词逻辑的一个重要基石，因为谓词逻辑中很多细节性的、不涉及量词变换的等值公式都是由此得来的。 否定型等值式⭐⭐ 这部分是最最重要的基础。 $\neg(\forall x)P(x)=(\exists x)\neg P(x)$ $\neg(\exists x)P(x)=(\forall x)\neg P(x)$ 可以这样直观的理解和解释： 并不是对于所有的$x,P(x)$都成立，那么肯定存在一个$x,P(x)$不成立，即$\neg P(x)$成立。 不存在一个$x$让$P(x)$成立，那么对于所有的$x,P(x)$都不成立，即$\neg P(x)$成立。 谓词公式和命题变项的分配律 有关$\land$和$\lor$的分配律⭐ $(\forall x)(P(x)\land q)=(\forall x)P(x)\land q$ $(\forall x)(P(x)\lor q)=(\forall x)P(x)\lor q$ $(\exists x)(P(x)\land q)=(\exists x)P(x)\land q$ $(\exists x)(P(x)\lor q)=(\exists x)P(x)\lor q$ 这部分是比较好理解的，也是非常基础性的定律。 有关$\rightarrow$的分配律 $(\forall x)(P(x)\rightarrow q)=(\exists x)P(x)\rightarrow q$ $(\exists x)(P(x)\rightarrow q)=(\forall x)P(x)\rightarrow q$ $(\forall x)(q\rightarrow P(x))=q \rightarrow (\forall x)P(x)$ $(\exists x)(q\rightarrow P(x))=q \rightarrow (\exists x)P(x)$ ...

本文及其系列文章用于离散数学（1）科目的期末考试复习 一些定义和名称 个体词就是命题逻辑里面的主词。包括了个体常项和个体变项。将个体变化的范围成为个体域或者论域$D$。 谓词指的是用来刻画对象性质和关系的符号，一般用大写字母$P,Q,R$表示，可以理解为语法上的谓语的作用。把在谓词的定义中涉及到的个体词的个数称为该谓词的元数。如$P(x,y)$表示$x=y$就是一个二元谓词；命题逻辑中的命题就是一个零元谓词。注意，谓词的值域是$\{T,F\}$ 函数指的是一些从$D$到$D$的映射。他们与谓词的区别在于值域。例如，$f(x)$表示“$x$的父亲”是一个函数，而$P(x)$表示“$x$是父亲”就是一个谓词。 项是用于表示论语中对象的符号表达式。个体词和函数都是项。 量词是对个体数量加以约束和限制的词。量词分为全称量词和存在量词。全称量词就是$\forall$，存在量词就是$\exists$，具体内涵就是我们高中就熟知的。量词的辖域指的就是某个量词所约束的范围。一般而言，我们可以认为如果量词后不加括号，那辖域就是后一个谓词符号；如果量词后有括号，那就是括号里的内容。 一些实例 在这里给出一些自然语言形式化变成一阶谓词逻辑的结果，便于理解。注意，这些结果中有些是特别需要注意的。 所有的有理数都是实数 取$P(x)$表示$x$是有理数，$R(x)$表示$x$是实数。则原句可以形式化为$(\forall x)(P(x)\rightarrow R(x))$ 注意，“所有的……都是……”这样类型的语句只能用$\rightarrow$ 有的实数是有理数 取$P(x)$表示$x$是有理数，$R(x)$表示$x$是实数。则原句可以形式化为$(\exists x)(R(x)\land P(x))$ 注意，“有的……是……”这样类型的语句一般用$\land$ 有的实数不是有理数 取$P(x)$表示$x$是有理数，$R(x)$表示$x$是实数。则原句可以形式化为$(\exists x)(R(x)\land \neg P(x))$ 没有无理数是有理数 取$P(x)$表示$x$是有理数，$Q(x)$表示$x$是无理数数。则原句可以形式化为$\neg(\exists x)(Q(x)\land P(x))$ 至少有一个偶数是素数 取$A(x)$表示$x$为偶数，$B(x)$表示$x$为素数。则原句可以形式化为$(\exists x)(A(x)\land B(x))$ 至少有一个偶数并且至少有一个素数 取$A(x)$表示$x$为偶数，$B(x)$表示$x$为素数。则原句可以形式化为$(\exists x)A(x)\land(\exists x) B(x)$ 函数$f(x)$在$[a,b]$上的点$x_0$处连续 根据微积分的知识，可以形式化为$(\forall \epsilon)(\epsilon >0\rightarrow (\exists \delta)(\delta>0\land (\forall x)(|x-x_0|<\delta\rightarrow|f(x)-f(x_0)|<\epsilon)))$ 自然数集合的形式描述 即，论域是自然数集，我们要形式化下列语句（自然数集合建立公理）：$\\(1)$对于每个数，有且仅有一个相继后元$\\(2)$没有一个数的相继后元是0 $\\(3)$ 对于除0以外的数，有且仅有一个相继前元。 设谓词$P(x,y)$表示$x=y$，函数$f(x)=x+1$，函数$g(x)=x-1$。则原句可以形式化为：$\\(1)(\forall x)(\exists y)(P(y,f(x))\land(\forall z)(P(z,f(x))\rightarrow P(y,z)) )\\(2)\neg(\exists x)P(0,f(x))\\(3)(\forall x)(\neg P(0,x)\rightarrow (\exists y)(P(y,g(x))\land(\forall z)(P(z,g(x))\rightarrow P(y,z))))$ ...

本文及其系列文章用于离散数学（1）科目的期末考试复习 一般公理系统的结构 通常而言，一个公理系统一般包括如下几部分： 初始符号：公理所允许出现的全体符号的集合。 形成规则：由出事符号可以组成各种符号序列。 公理：选出几个最基本的重言式作为推演其他所有重言式的依据。 变形规则：变形规则就是公理系统所规定的推理规则。 建立定理：这是公理系统内做演算的主要内容，应该包括所有的重言式和对它们的证明。 罗素系统 初始符号 $A,B,C……$，大写英文字母（表示命题） $\neg , \lor$表示联结词 （ ），表示圆括号 $\vdash$，写在一个公式之前表示其为重言式 形成规则 符号形成规则的符号序列成为合式公式。 符号$\pi$是合式公式（$\pi$取值为$A,B……$） 如果$A,B$是合式公式，那么$A\lor B$也是合式公式 如果$A$是合式公式，那么$\neg A$也是合式公式 只有符合1,2,3的符号序列才是合适公式 定义 除了由形成规则构成的合式公式之外，还可以通过定义来引入新的合式公式，这样引入的合式公式有着缩写和简化表达的作用。 定义1 $A\rightarrow B$定义为$\neg A\lor B$ 定义2 $A\land B$定义为$\neg(\neg A\lor\neg B)$ 定义3 $A\leftrightarrow B$定义为$(A\rightarrow B)\land(B\rightarrow A)$ 或者换句话说，罗素公理系统中只有“非”和“或”两种逻辑，其余逻辑都要求用“非”和“或”来表示。并且注意，上述定义中的顺序关系是严格的。 公理⭐️ 公理1 $\vdash (P\lor P)\rightarrow P$ 公理2 $\vdash P\rightarrow (P\lor Q)$ 公理3 $\vdash (P\lor Q)\rightarrow (Q\lor P)$ 公理4 $\vdash (Q\rightarrow R)\rightarrow((P\lor Q)\rightarrow (P\lor R))$ 注意，只有这些公理才能够直接运用在罗素公理系统的推导过程中！我们其余所知道的所有公式定理都不能够直接在罗素公理系统中用，包括交换律、结合律、互反律、摩根律等等等等。 变形规则⭐️ 代入规则：将合式公式$A$中出现的某一个符号$\pi$到处都带一某一个合适的公式$B$，从而得到合式公式$A\frac{\pi}{B}$叫代入。带入规则说，如果$\vdash A$,则$\vdash A\frac{\pi}{B}$ ...

本文及其系列文章用于离散数学（1）科目的期末考试复习 推理形式 我们将用自然语句描述的推理关系引入符号，抽象化并以条件式表现出来，就得到了一种推理形式。 比如： 如果$P$，则$Q$。非$Q$，所以非$P$ 形式化之后就得到了 ： $((P\rightarrow Q)\land\neg Q)\rightarrow \neg P$ 当然，也有一些推理形式是错误的，比如$((P\rightarrow Q)\land\neg P)\rightarrow \neg Q$。这种推理形式我们不太关心。我们关心的是那些前提真则结论必真的推理形式，我们叫它正确的推理形式。 即，给定两个命题公式$A,B$，如果$A$取值为真，那么$B$取值也必为真，那么说$A\rightarrow B$就是一个正确的推理形式。这时候，我们称$A$重言蕴含$B$，或者称$B$为$A$的逻辑推论，并用符号$A\Rightarrow B$表示。 $\Rightarrow$可以理解为我们之前在初高中常见的“推导出”的符号。 基本的推理公式 常用公式 $P\land(P\rightarrow Q)\Rightarrow Q$⭐️⭐️ 假言推理，或者说叫分离规则，最常用的公式 $(P\rightarrow Q)\land(Q\rightarrow R) \Rightarrow P\rightarrow R$⭐️⭐️ 三段论 $P\land Q\Rightarrow P$⭐️ 最基础的公式，常用于分离合取的不同公式 $P\Rightarrow P\lor Q$⭐️ 常用于增加条件，方便三段论规范性 其余常见公式 这里的公式都可以由常用公式推导出。 $\neg(P\rightarrow Q)\Rightarrow P$ $\neg(P\rightarrow Q)\Rightarrow \neg Q$ $\neg P\Rightarrow P\rightarrow Q$ $Q\Rightarrow P\rightarrow Q$ $\neg P\land(P \lor Q)\Rightarrow Q$ $\neg Q\land(P\rightarrow Q)\Rightarrow\neg P$ ...

本文及其系列文章用于离散数学（1）科目的期末考试复习 命题公式的真值表 对于一个含有$n$个命题变元$P_1,P_2,……,P_n$的命题公式$A$来说，可以根据$P_1,P_2,……,P_n$的真值给出$A$的真值，从而建立起了一个命题公式的真值表。 一般我们认为，从真值表出发写命题公式可以从列表中值为$T$或者值为$F$来写。 比如，如果真值表为 $$\begin{array}{|cc|c|}P&Q&{A}\\0&0&0\\0&1&1\\1&0&0\\1&1&1\end{array}$$ 那么，从取到$T$的那几行来看，$A=(\neg P\land Q)\lor(P\land Q)$。即，A在取$T$的时候，$P,Q$的取值应该让$A$的表达式中某个括号的真值为1。 从取到$F$的那几行来看，$A=(\neg P \lor\neg Q)\land(P\lor\neg Q)$。即，A在取到$F$的时候，$P,Q$的取值应该让$A$的表达式中某个括号的真值为0。 联结词的完备集 除了常见的5个联结词外，我们还可以定义更多的联结词。以下是三个较为常见的联结词。 异或$\overline\lor$ $$\begin{array}{|cc|c|}P&Q&{P\overline\lor Q}\\0&0&0\\0&1&1\\1&0&1\\1&1&0\end{array}$$ 与非$\uparrow$ $$\begin{array}{|cc|c|}P&Q&{P\uparrow Q}\\0&0&1\\0&1&1\\1&0&1\\1&1&0\end{array}$$ 或非$\downarrow$ $$\begin{array}{|cc|c|}P&Q&{P\downarrow Q}\\0&0&1\\0&1&0\\1&0&0\\1&1&0\end{array}$$ 理论上，其他的联结词都是存在的，但是因为使用甚少，所以常常不予讨论。 还有一个问题是，对于$n$个命题变项而言，我们可以定义出多少个联结词。容易知道，答案是$2^{2^n}$个。这由归纳法或者直接构造即可得证。 对偶式和补公式 将$A$中所有出现的$\land,\lor,T,F$分别以$\lor,\land,F,T$替换，得到公式$A^$，则称，$A^$是$A$的对偶式。或者说，$A$和$A^*$互为对偶式。 设$A=A(P_1,P_2,……,P_n)$，令$A^-=A(\neg P_1,\neg P_2,……,\neg P_n)$，则称$A^-$为A的补公式 那么，我们由如下定理： $\neg(A^* )=(\neg A)^* ,\neg(A^-)=(\neg A)^-$ $(A^* )^* =A=(A^-)^-$ $\neg A=(A^* )^-$ 其中，性质2.非常显然，性质1.和3.可以通过对式子中联结词个数进行归纳来证明。实际上，3.是摩根律的推广形式。 以下是对偶式、补公式有关真值性的的一些性质。 如果$A=B$，那么$A^* =B^*$ 如果$A\rightarrow B$永真，那么$B^* \rightarrow A^*$永真 若$A$永真，那么$A^-$永真。反之亦然 若$\neg A$永真，那么$A^*$永真。反之亦然。 范式 一些定义 为了描述方便，先定义几个术语。 简单命题$P$和$\neg P$被称为文字 一些文字的合取被称为合取式 一些文字的析取被称为析取式 ...

本文及其系列文章用于离散数学（1）科目的期末考试复习 等值的定义 给定两个命题公式$A,B$，以及在$A,B$中出现的所有命题变相$P_1,P_2,……,P_n$，那么公式$A,B$一共有$2^n$种解释。如果在所有的解释下有$A$和$B$的真值都相等，那么称$A$和$B$等值,记做$A=B$ 等值定理指的是，$A=B$的充要条件是$A\leftrightarrow B$是重言式 等值公式 这部分极其重要。 转换公式 $P\rightarrow Q=\neg P\lor Q$ ⭐️⭐️ $P\leftrightarrow Q=(P\land Q)\lor(\neg P\land\neg Q)=(P\lor\neg Q)\land(\neg P\lor Q)$ ⭐️ 一般认为，在进行公式的转化和计算的时候，我们会把所有的蕴含和双蕴含转化为我们熟悉的与或非，这样计算会比较简单。 双重否定律 $\neg\neg P=P$ 结合律 $(P\lor Q)\lor R=P\lor(Q\lor R)$ $(P\land Q)\land R=P\land(Q\land R)$ $(P\leftrightarrow Q)\leftrightarrow R=P\leftrightarrow(Q\leftrightarrow R)$ $(P\rightarrow Q)\rightarrow R\not=P\rightarrow(Q\rightarrow R)$ ⚠️ 交换律 $P\lor Q=Q\lor P$ $P\land Q=Q\land P$ $P\leftrightarrow Q=Q\leftrightarrow P$ $P\rightarrow Q\not =Q\rightarrow P$ ⚠️ 分配律 $P\lor(Q\land R)=(P\lor Q)\land(P\lor R)$⭐️ $P\land(Q\lor R)=(P\land Q)\lor(P\land R)$⭐️ $P\rightarrow(Q\rightarrow R)=(P\rightarrow Q)\rightarrow(P\rightarrow R)$ $P\leftrightarrow(Q\leftrightarrow R)\not=(P\leftrightarrow Q)\leftrightarrow(P\leftrightarrow R)$ ⚠️ 摩根律 $\neg(P\lor Q)=\neg P\land\neg Q$ ⭐️⭐️ $\neg(P\land Q)=\neg P\lor\neg Q$ ⭐️⭐️ 其他常用公式 $\neg P\rightarrow Q=\neg Q\rightarrow P$ ⭐️ $P\rightarrow(Q\rightarrow R)=(P\land Q)\rightarrow R$ $(P\rightarrow R)\land(Q\rightarrow R)=(P\lor Q)\rightarrow R$ 置换和置换规则 对于公式$A$的子公式，用与之等值的公式代换称之为置换。 ...

本文及其系列文章用于离散数学（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)}$，用来确保过程用于规范。 ...

1.定理的描述 定义：$v_p(x)$表示素数$p$整除$x$的最高次幂。记$v_p(x)=\alpha$也即有$p^{\alpha}||x$ 引理：$n\in \mathbb{Z}^+, x,y\in \mathbb{Z}, \forall p\in\mathbb{P},(p,n)=1,p|x-y,p\nmid x,p\nmid y$，有 $v_p(x^n-y^n)=v_p(x-y),v_p(x^n+y^n)=v_p(x+y)$ 定理1：$n\in \mathbb{Z}^+, x,y\in \mathbb{Z}, \forall p\in\mathbb{P},p|x-y,p\nmid x,p\nmid y$，有$v_p(x^n-y^n)=v_p(x-y)+v_p(n),v_p(x^n+y^n)=v_p(x+y)+v_p(n)$ 定理2（LTE中 $n=2$情形1）：$n\in \mathbb{Z}^+, 4|x-y,2\nmid x,2\nmid y$，有$v_2(x^n-y^n)=v_2(x-y)+v_2(n)$ 定理3（LTE中 $n=2$情形2）：$n\in \mathbb{Z}^+, 2|n,2\nmid x,2\nmid y$，有$v_2(x^n-y^n)=v_2(x-y)+v_2(x+y)+v_2(n)-1$ 证明：不会，我菜。参考这里 2.基本性质和用法 $v_p(x)+v_p(y)=v_p(xy)$ $v_p(x)-v_p(y)=v_p(\frac{x}{y})$（此时需要$y|x$) 是不是很像$\log$函数 我们可以知道，$x|y \Leftrightarrow\forall p|x,p\in\mathbb{P},v_p(x)\leqslant v_p(y)$ $eg1.$求证$2^{m+3}|3^{2^{m+2}}-1$ 应用引理，有$v_2(3^{2^{m+2}}=v_2(3-1)+v_2(3+1)+v_2(2^{m+2})-1=m+4 > v_2(2^{m+3})=m+3$知其成立 $eg2.$已知$a,b,n\in\mathbb{N}^+$,满足$n|a^n-b^n$，求证$n|\frac{a^n-b^n}{a-b}$ 考虑n的一个素因子$p$ 若 $(p,a-b)=1$，有$v_p(\frac{a^n-b^n}{a-b})=v_p(a^n+b^n)\geqslant v_p(n)$ 若$p|a,p|a$，有$p^{v_p(\frac{a^n-b^n}{a-b})}\geqslant p^{n-1}\geqslant n\geqslant p^{v_p(n)}$ 若$p|a-b,(p,ab)=1$,有$v_p(\frac{a^n-b^n}{a-b})=v_p(n)$ 3.具体做题 利用LTE引理在各种数论题目里乱搞 $eg1.;$求$x^{2022}+y^{2022}=337^z$的全部正整数解 由费马小定理$337|(x^{2022}+y^{2022})-(x+y)$，故$337|x+y$ 故$v_{337}(x^{2022}+y^{2022})=v_{337}(2022)+v_{337}(x+y)=v_{337}(337(x+y))$ 因此$x^{2022}+y^{2022}\leqslant 337^{v_{337}(x^{2022}+y^{2022})}=337^{v_{337}(337(x+y))}\leqslant 337(x+y)$ （显然$p^{v_p(x)}≤x$） 而不等式$x^{2022}+y^{2022}\leqslant 337(x+y)$在$x,y$不全等于1时显然不成立 而且$x=y=1$也不成立 因此原方程无正整数解 $eg2.;m\in\mathbb{Z},p\in\mathbb{P},$令$a_1=8p^m,a_n=(n+1)^{\frac{a_{n-1}}{n}}$，求所有素数$p$使得对于一切$n\in\mathbb{N}^+$，均有$a_n\prod\limits_{i=1}^n(1-\frac{1}{a_i})\in\mathbb{Z}$ 由于对一切n成立，不妨设$n=2$，此时$a_n\prod\limits_{i=1}^n(1-\frac{1}{a_i})=\frac{(a_1-1)(a_2-1)}{a_1}\in\mathbb{Z}$ $\Rightarrow a_1|a_2-1\Leftrightarrow 8p^m|3^{4p^m}-1\Rightarrow p|3^{4p^m}-1$ ...