Posts

本文及其系列文章用于离散数学（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$ ...