邏輯與集合相關(guān)基礎(chǔ)知識講義第一章邏輯基礎(chǔ)1.1命題邏輯1.1.1命題與真值命題是具有唯一真值（真/假，記為\(T/1\)或\(F/0\)）的陳述句。例如：原子命題：“2是素數(shù)”（真值為\(1\)）、“三角形內(nèi)角和為\(180^\circ\)”（歐氏幾何中為\(1\)）。復(fù)合命題：“2是素數(shù)且3是奇數(shù)”（由原子命題通過邏輯連接詞組合而成）。注意：疑問句、祈使句、悖論（如“這句話是假的”）不構(gòu)成命題。1.1.2邏輯連接詞常用連接詞及真值表（\(P,Q\)為命題，\(1\)表真，\(0\)表假）：否定（\(\neg\)）：對\(P\)取反，\(\negP\)真值為\(1-P\)。例：\(P\)：“今天下雨”，則\(\negP\)：“今天不下雨”。合?。╘(\land\)）：“\(P\)且\(Q\)”，\(P\landQ\)為\(1\)當(dāng)且僅當(dāng)\(P,Q\)均為\(1\)。例：“2是偶數(shù)\(\land\)3是奇數(shù)”為\(1\)。析?。╘(\lor\)）：“\(P\)或\(Q\)”（相容或，至少一個為真），\(P\lorQ\)為\(1\)當(dāng)且僅當(dāng)\(P,Q\)至少一個為\(1\)。例：“2是偶數(shù)\(\lor\)3是偶數(shù)”為\(1\)（因前者為真）。蘊含（\(\rightarrow\)）：“若\(P\)則\(Q\)”，僅當(dāng)\(P=1\)且\(Q=0\)時，\(P\rightarrowQ=0\)，其余為\(1\)。例：“若\(1+1=3\)，則太陽從西邊升起”為\(1\)（前件為假，蘊含式恒真）。等價（\(\leftrightarrow\)）：“\(P\)當(dāng)且僅當(dāng)\(Q\)”，\(P\leftrightarrowQ\)為\(1\)當(dāng)且僅當(dāng)\(P,Q\)真值相同。1.1.3命題公式與分類由命題變元（如\(p,q,r\)）和連接詞構(gòu)成的式子稱為命題公式（合式公式），如\(\negp\)、\(p\landq\)、\((p\rightarrowq)\land(q\rightarrowp)\)（等價于\(p\leftrightarrowq\)）。根據(jù)真值情況分類：永真式（重言式）：所有賦值下真值為\(1\)，如\(p\lor\negp\)（排中律）、\((p\rightarrowq)\leftrightarrow(\negq\rightarrow\negp)\)（逆否命題等價）。永假式（矛盾式）：所有賦值下真值為\(0\)，如\(p\land\negp\)（矛盾律）。可滿足式：至少存在一種賦值使真值為\(1\)（永真式是特殊的可滿足式）。1.1.4命題邏輯的推理規(guī)則推理有效當(dāng)且僅當(dāng)前提的合取蘊含結(jié)論（即\(\alpha_1\land\alpha_2\land\dots\land\alpha_n\rightarrow\beta\)為永真式）。常用規(guī)則：假言推理：由\(p\rightarrowq\)和\(p\)，推出\(q\)（肯定前件）。拒取式：由\(p\rightarrowq\)和\(\negq\)，推出\(\negp\)（否定后件）。析取三段論：由\(p\lorq\)和\(\negp\)，推出\(q\)。假言三段論：由\(p\rightarrowq\)和\(q\rightarrowr\)，推出\(p\rightarrowr\)（傳遞性）。例：前提“若今天下雨（\(p\)），則地面濕（\(q\)）”（\(p\rightarrowq\)）且“今天下雨”（\(p\)），推出“地面濕”（\(q\)）（假言推理）。1.2謂詞邏輯（一階邏輯）命題邏輯無法處理“所有”“存在”等量化關(guān)系（如“所有素數(shù)大于1”），需用謂詞邏輯。1.2.1個體詞與謂詞個體詞：研究對象（如“2”“素數(shù)”“人”），分個體常項（特定對象，如2）和個體變項（泛指對象，如\(x\)表示任意數(shù)）。謂詞：描述個體的性質(zhì)/關(guān)系，如“…是素數(shù)”（一元謂詞，記為\(P(x)\)）、“…大于…”（二元謂詞，記為\(Q(x,y)\)）。1.2.2量詞全稱量詞（\(\forall\)）：“所有”，\(\forallxP(x)\)表“對所有\(zhòng)(x\)，\(P(x)\)成立”。例：\(\forallx(x\text{是實數(shù)}\rightarrowx^2\geq0)\)。存在量詞（\(\exists\)）：“存在”，\(\existsxP(x)\)表“存在\(x\)使\(P(x)\)成立”。例：\(\existsx(x\text{是素數(shù)}\landx\text{是偶數(shù)})\)（即2）。1.2.3謂詞公式與解釋謂詞公式由個體詞、謂詞、量詞、連接詞構(gòu)成（如\(\forallx(P(x)\rightarrow\existsyQ(x,y))\)）。解釋：為公式指定論域（個體域，如實數(shù)集）、謂詞的具體含義、個體常項的對象。例：對\(\forallx(P(x)\rightarrowQ(x,2))\)，論域為自然數(shù)，\(P(x)\)解釋為“\(x\)是偶數(shù)”，\(Q(x,y)\)解釋為“\(x\geqy\)”，則公式意為“所有偶數(shù)都\(\geq2\)”（真值為\(1\)）。第二章集合論基礎(chǔ)2.1集合的基本概念2.1.1集合的定義與表示集合是確定、互異的對象的全體（對象稱為元素）。表示方法：列舉法：\(\{a,b,c\}\)、\(\mathbb{N}=\{0,1,2,\dots\}\)（自然數(shù)集）。描述法：\(E=\{x\midx\in\mathbb{N}\text{且}x\text{是偶數(shù)}\}\)（偶數(shù)集）。注意：“高個子的人”不構(gòu)成集合（“高”無明確標(biāo)準，違反確定性）；集合元素互異（如\(\{a,a,b\}=\{a,b\}\)）。2.1.2元素與集合的關(guān)系元素\(a\)屬于集合\(A\)，記為\(a\inA\)；否則\(a\notinA\)。例：\(3\in\mathbb{N}\)，\(\sqrt{2}\notin\mathbb{N}\)。集合可作為元素（如\(B=\{\{1,2\},3\}\)，則\(\{1,2\}\inB\)，但\(1\notinB\)）。2.1.3特殊集合空集（\(\emptyset\)）：不含任何元素，\(\emptyset\subseteqA\)對任意集合\(A\)成立。全集（\(U\)）：包含所有相關(guān)對象的集合（語境依賴，如討論數(shù)時\(U\)可為\(\mathbb{R}\)）。2.2集合的關(guān)系與運算2.2.1集合的包含與相等子集：\(A\subseteqB\)當(dāng)且僅當(dāng)\(A\)的元素都屬于\(B\)（如\(\{1,2\}\subseteq\{1,2,3\}\)，\(\emptyset\subseteq\)任意集合）。真子集：\(A\subsetB\)當(dāng)且僅當(dāng)\(A\subseteqB\)且\(A\neqB\)。相等：\(A=B\)當(dāng)且僅當(dāng)\(A\subseteqB\)且\(B\subseteqA\)（如\(\{1,2\}=\{x\midx^2-3x+2=0\}\)）。2.2.2集合的基本運算（\(A,B\subseteqU\)）并集：\(A\cupB=\{x\midx\inA\text{或}x\inB\}\)（如\(\{1,2\}\cup\{2,3\}=\{1,2,3\}\)）。交集：\(A\capB=\{x\midx\inA\text{且}x\inB\}\)（如\(\{1,2\}\cap\{2,3\}=\{2\}\)；\(A\capB=\emptyset\)時稱\(A,B\)不相交）。補集：\(\overline{A}=U\setminusA=\{x\midx\inU\text{且}x\notinA\}\)（如\(U=\mathbb{N}\)時，\(\overline{\{x\midx\geq5\}}=\{0,1,2,3,4\}\)）。差集：\(A\setminusB=\{x\midx\inA\text{且}x\notinB\}\)（如\(\{1,2,3\}\setminus\{2,4\}=\{1,3\}\)）。對稱差：\(A\triangleB=(A\setminusB)\cup(B\setminusA)\)（如\(\{1,2,3\}\triangle\{2,3,4\}=\{1,4\}\)）。2.2.3運算律（\(A,B,C\subseteqU\)）交換律：\(A\cupB=B\cupA\)；\(A\capB=B\capA\)。結(jié)合律：\((A\cupB)\cupC=A\cup(B\cupC)\)；\((A\capB)\capC=A\cap(B\capC)\)。分配律：\(A\cup(B\capC)=(A\cupB)\cap(A\cupC)\)；\(A\cap(B\cupC)=(A\capB)\cup(A\capC)\)。德摩根律：\(\overline{A\cupB}=\overline{A}\cap\overline{B}\)；\(\overline{A\capB}=\overline{A}\cup\overline{B}\)。2.3集合的進階概念2.3.1冪集集合\(A\)的所有子集構(gòu)成的集合，記為\(\mathcal{P}(A)\)（或\(2^A\)）。例：\(A=\{a,b\}\)，則\(\mathcal{P}(A)=\{\emptyset,\{a\},\{b\},\{a,b\}\}\)，元素個數(shù)為\(2^{|A|}\)（\(|A|\)為\(A\)的基數(shù)）。2.3.2笛卡爾積\(A\timesB=\{\langlex,y\rangle\midx\inA,y\inB\}\)（\(\langlex,y\rangle\)為有序?qū)Γ琝(x\neqy\)時\(\langlex,y\rangle\neq\langley,x\rangle\)）。例：\(A=\{1,2\},B=\{a,b\}\)，則\(A\timesB=\{\langle1,a\rangle,\langle1,b\rangle,\langle2,a\rangle,\langle2,b\rangle\}\)，\(|A\timesB|=|A|\times|B|\)。2.4集合的關(guān)系（等價與偏序）2.4.1二元關(guān)系集合\(A\)到\(B\)的二元關(guān)系\(R\)是\(A\timesB\)的子集（\(R\subseteqA\timesB\)）。若\(A=B\)，則\(R\)是\(A\)上的關(guān)系（如\(A=\{1,2,3\}\)，\(R=\{\langle1,2\rangle,\langle2,3\rangle\}\)表“小于”）。2.4.2等價關(guān)系滿足自反（\(\forallx,\langlex,x\rangle\inR\)）、對稱（\(\langlex,y\rangle\inR\Rightarrow\langley,x\rangle\inR\)）、傳遞（\(\langlex,y\rangle,\langley,z\rangle\inR\Rightarrow\langlex,z\rangle\inR\)）的關(guān)系。例：“模2同余”（\(x\equivy\pmod{2}\)）是整數(shù)集上的等價關(guān)系，將\(\mathbb{Z}\)劃分為偶數(shù)類\([0]\)和奇數(shù)類\([1]\)（等價類互不相交且并為\(\mathbb{Z}\)）。2.4.3偏序關(guān)系滿足自反、反對稱（\(\langlex,y\rangle,\langley,x\rangle\inR\Rightarrowx=y\)）、傳遞的關(guān)系（記為\(\leq\)）。例：集合的包含關(guān)系\(\subseteq\)是冪集\(\mathcal{P}(A)\)上的偏序。若任意元素可比（\(x\leqy\)或\(y\leqx\)），則\(\leq\)為全序（如\(\mathbb{R}\)上的\(\leq\)）。第三章邏輯與集合的關(guān)聯(lián)3