目錄

• 集合論
• 數(shù)理邏輯
• • 命題邏輯
  • 謂詞邏輯

集合論

集合： 由指定范圍內(nèi)的滿足給定條件的所有對象聚集在一起構(gòu)成，每個對象成為集合的元素
常用集合： 自然數(shù)集合N，整數(shù)集合Z，有理數(shù)集合Q，實數(shù)集合R
集合表示方法： 枚舉法，敘述法，文氏圖法
基數(shù)： 集合中元素的數(shù)量，若基數(shù)是有限的，稱為有限集，否則稱為無限集
全集： 針對特定的研究范圍，所有對象的集合
【注】 集合中的元素是無序的，不同的
外延性定理： 兩個集合相等，當且僅當它們的元素完全相同
子集： 如果B中的每個元素都是A中的元素，則稱B是A的子集，若A≠B，則稱B是A的真子集
集合相等證明： A包含于B且B包含于A
冪集： A的所有子集構(gòu)成的集合叫做A的冪集。記做P(A)={x|x∈A}
等勢： 若A，B之間存在一種一一對應(yīng)的關(guān)系，則稱A和B等勢，記做A∽B
可數(shù)集合： A與自然數(shù)集合N等勢，稱為可數(shù)集合，記做阿列夫零
不可數(shù)集合： 開區(qū)間(0,1)稱為不可數(shù)集合，凡與開區(qū)間(0,1)等勢的集合稱為不可數(shù)集合，記為阿列夫

數(shù)理邏輯

命題邏輯

概念： 用數(shù)學的方法研究邏輯推理的規(guī)律
命題： 具有確切真值的陳述句
【注】 推理的前提和結(jié)論都是命題，命題是推理的基本單位
復合命題： 可以分解為簡單命題的命題
聯(lián)結(jié)詞： 否定，合取，析取，蘊含，等價
命題變量（命題變元）： 一個任意的沒有賦予具體內(nèi)容的原子命題是一個變量命題
命題公式： ① 命題變元本身是公式
②若G是公式，則非G也是公式
③若G，H是公式，則包含聯(lián)結(jié)詞的G，H也是公式
僅有有限步使用以上規(guī)則后得到的包含命題變元，聯(lián)結(jié)詞和括號的符號串才是命題公式
解釋： 指定公式中所有命題變元的真值
永真公式： 公式G在所有解釋下真值都為真，又稱為重言式
永假公式： 公式G在所有解釋下真值都為假，又稱矛盾式
可滿足式： 不是永假式的公式
等價公式： 設(shè)A和B是兩個命題公式，設(shè)P1，P2，…，Pn是所有出現(xiàn)于A和B中的原子變元，若給定P1，P2，…，Pn任一組真值指派，A和B的真值都相同，則稱A和B是等值的或者等價的，記為A<=>B
等價置換： 將公式A替換為等價的公式B
蘊含式： 設(shè)A和B是命題公式，若A->B是永真式，則稱A蘊含B
聯(lián)結(jié)詞完備集： 設(shè)S是一個聯(lián)結(jié)詞集，如果任何n(n≥1)個變元組成的公式，都可以由S中的聯(lián)結(jié)詞來表示，則稱S是聯(lián)結(jié)詞完備集
文字： 命題變元或者命題變元的否定
子句： 有限個文字的析取
短語： 有限個文字的合取
析取范式： 有限個短語的析取式
合取范式： 有限個子句的合取式
范式存在定理： 對于任意命題公式，都存在與其等價的析取范式和合取范式
極小項： 含n個命題變元的短語中，若每個命題變元與其否定不同時存在，但二者之一恰好出現(xiàn)一次，并且出現(xiàn)的次序與P1，P2，…，Pn一致
極大項： 含n個命題變元的子句中，若。。。
【注】 極小項只有一組成真賦值，極大項只有一組成假賦值
主析取范式： 給定的析取范式中，每個短語都是極小項，且按編碼從小到大的順序排列
主合取范式： 給定的合取范式中，每個子句都是極大項，且按照編碼從小到大的順序排列
【注】 任何一個公式都有與之等價的主析取范式和主合取范式
永真公式： 主析取范式包含所有的極小項
永假公式： 主合取范式包含所有的極大項
推理： 從一組前提合乎邏輯的推出結(jié)論的思維過程
規(guī)則P： 在推導過程中，可隨時引入前提集合中的任意一個前提
規(guī)則T： 在推導的過程中，可以隨時引入公式S，該公式S是由其前的一個或多個公式推導出來的邏輯結(jié)果
規(guī)則CP： 如果能從給定的前提集合F與公式P推導出S，則能從此前提集合F推導出P->S
演繹： 從前提集合F推出結(jié)論H的一個演繹是構(gòu)造命題公式的一個有限序列H1，H2，…,Hn-1,Hn
其中，Hi或者是F中的某個前提，或者是前面某些Hj的有效結(jié)論，并且Hn就是H，而稱公式H為該演繹的有效結(jié)論，或者稱從前提F能夠演繹出結(jié)論H來
演繹方法： 直接證明法，規(guī)則CP證明法，間接證明法(反證法，歸謬法)

謂詞邏輯

概念： 為了研究簡單命題句子內(nèi)部的邏輯關(guān)系，我們需要對簡單命題進行分解，利用個體詞，謂詞和量詞來描述它們，并研究個體和總體的內(nèi)在聯(lián)系和數(shù)量關(guān)系。
個體詞： 在原子命題中，可以獨立存在的客體
謂詞： 用以刻畫客體的性質(zhì)或客體之間的關(guān)系
n元謂詞： 設(shè)D為非空的個體域，定義在Dn上取值{0,1}的n元函數(shù)，記為P(x1,x2,…,xn)
0元謂詞： 一般將沒有任何個體變量的謂詞稱為0元謂詞
全稱量詞： 所有的，一切
存在量詞： 存在
項： ①任意的常量符號或者變量符號是項
② 若f(x1,x2,…,xn)是n元函數(shù)符號，t1,t2,…,tn是項，則f(t1,t2,…,tn)是項
僅由有限次使用以上兩個規(guī)則產(chǎn)生的符號串才是項
原子公式： 若P(x1,x2,…,xn)是n元謂詞，t1,t2,…,tn是項，則P(t1,t2,…,tn)是原子謂詞公式
合式公式： ①原子公式是合式公式
②若G，H是合式公式，則包含聯(lián)結(jié)詞的G，H是合式公式
③若G是合式公式，x是個體變量，則包含量詞的公式G是合式公式
由有限次使用以上三個規(guī)則產(chǎn)生的表達式才是合式公式
約束變元： 給定一個合式公式G，若變元x出現(xiàn)在使用變元的量詞的轄域之內(nèi)，則稱變元x的出現(xiàn)為約束出現(xiàn)
自由變元： 若x的出現(xiàn)不是約束出現(xiàn)，則稱它是自由出現(xiàn)
閉式： 設(shè)G是任意一個公式，若G中無自由變元，則稱G是封閉的合式公式，閉式是一個命題
前束范式： 如果G中的一切量詞都位于該公式的最前端(不含否定詞)，且這些量詞的轄域都延伸到公式的末端

總結(jié)

以上是生活随笔為你收集整理的离散数学集合论与数理逻辑基本概念的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。