- 非真即假的陳述句稱為命題
- 不能被分解的命題稱為簡單命題或原子命題裂逐，由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的命題稱為復(fù)合命題
- 將命題變項用聯(lián)結(jié)詞和圓括號按一定的邏輯關(guān)系聯(lián)結(jié)起來的符號串稱為合式公式错妖，也稱為命題公式
- 設(shè)A為任一命題公式
- 若A在它的各種賦值下取值均為真戈锻，則稱A為永真式或重言式
- 若A在它的各種賦值下取值均為假，則稱A為永假式或矛盾式
- 若A不是矛盾式桐经，則稱A是可滿足式（A至少存在一個成真賦值几缭，重言式一定是可滿足式）
- 命題變項及其否定統(tǒng)稱為文字。
僅由有限個文字構(gòu)成的析取式稱作簡單析取式
僅由有限個文字構(gòu)成的合取式稱作簡單合取式
一個簡單析取式是重言式當且僅當它同時含有某個命題變項及其否定式
一個簡單合取式是矛盾式當且僅當它同時含有某個命題變項及其否定式 - 范式
由有限個簡單合取式的析取構(gòu)成的命題公式稱為析取范式
由有限個簡單析取式的合取構(gòu)成的命題公式稱為合取范式
析取范式和合取范式統(tǒng)稱為范式 - 范式存在定理
任一命題公式都存在與之等值的析取范式和合取范式 - 極小項和極大項
在含有n個命題變項的簡單合取式（簡單析取式）中留美，若每個命題變項和它的否定式恰好出現(xiàn)一個且僅出現(xiàn)一次彰檬，而且命題變項或它的否定式按下標從小到大或按字典順序排列伸刃，稱這樣的簡單合取式（簡單析取式）為極小項（極大項） - 主析取范式
所有簡單合取式（簡單析取式）都是極小項（極大項）的析取范式（合取范式）稱為主析取范式（主合取范式）
任何命題公式都存在與之等值的主析取范式和主合取范式，并且是唯一的 - 判斷推理正確與否
- 真值表法
- 等值演算法
- 主析取范式法
- 形式系統(tǒng)
- 自然推理系統(tǒng)：從任意給定的前提出發(fā)逢倍，應(yīng)用系統(tǒng)中的推理規(guī)則進行推理演算捧颅，最后得到的命題公式是推理的結(jié)論（它是有效的結(jié)論，可能是重言式较雕，也可能不是重言式）
- 公理推理系統(tǒng)：只能從若干條給定的公理出發(fā)碉哑，應(yīng)用系統(tǒng)中的推理規(guī)則進行推理演算，得到的結(jié)論是系統(tǒng)中的重言式亮蒋，稱為系統(tǒng)中的定理扣典。
- 一階邏輯（一階謂詞邏輯或謂詞邏輯）
在命題邏輯中不能很好的描述“凡偶數(shù)都能被2整除”中的“凡”字，為了克服命題邏輯的局限性慎玖，需要引入量詞贮尖，以期達到表達出個體與總體之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系，這就是一階邏輯研究的內(nèi)容 - 閉式
設(shè)A是任意公式趁怔，若A中不含自由出現(xiàn)的個體變項湿硝，則稱A為封閉的公式，簡稱閉式 - 前束范式
具有如下形式Q1x1Q2x2...QkxkB的一階邏輯公式稱為前束范式润努，其中Q為量詞存在或任意关斜，B不含量詞的公式。
前束范式存在定理：一階邏輯中的任何公式都存在等值的前述范式 - 集合之間的關(guān)系和初級運算可以用文恩圖（Venn Diagram）給予形象的描述铺浇。
-
包含排斥原理（容斥原理）
在計數(shù)時痢畜，必須沒有重復(fù)和遺漏△⒙拢可以先不考慮重疊的情況丁稀，把包含于某內(nèi)容中的所有對象的數(shù)目先計算出來，然后再把計數(shù)時重復(fù)的數(shù)目排斥出去倚聚，使得計算結(jié)果既無遺漏有無重復(fù)二驰，這種計數(shù)方法稱為容斥原理。
image.png - 笛卡爾積
設(shè)A秉沼，B為集合，用A中的元素作為第一元素矿酵，B中的元素作為第二元素構(gòu)成有序?qū)８矗羞@樣的有序?qū)M成的集合叫做A和B的笛卡爾積，記作AxB. - 二元關(guān)系
如果一個集合滿足以下條件之一全肮，則稱該集合為一個二元關(guān)系敞咧。
- 集合非空，且它的元素都是有序?qū)?/li>
- 集合是空集
- 設(shè)A辜腺，B為集合休建，AxB的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系乍恐，當B=A時叫做A上的二元關(guān)系
集合A的全體子集構(gòu)成的集合叫做A的冪集，記作P(A). -
等價關(guān)系
設(shè)R為非空集合A上的關(guān)系测砂，如果R是自反的茵烈、對稱的、傳遞的砌些，則稱R為A上的等價關(guān)系呜投。
image.png
image.png
image.png
以R的所有等價類作為元素的集合稱為A關(guān)于R的商集，記作A/R.
商集就是A上的一個劃分存璃，并且不同的商集將對應(yīng)于不同的劃分仑荐。A上的等價關(guān)系和A的劃分是一一對應(yīng)的。 - 偏序關(guān)系
- 設(shè)R是非空集合A上的關(guān)系纵东，若R是自反的粘招、反對稱的、傳遞的偎球，則稱R為A上的偏序關(guān)系洒扎。記作‘小于等于’，表示在偏序關(guān)系中的順序性甜橱，排在前面或相同逊笆。
- 設(shè)R是非空集合A上的偏序關(guān)系，如果任意x岂傲，y屬于A难裆，x與y都是可比的的，則稱R為A上的全序關(guān)系镊掖。如數(shù)集上的小于等于關(guān)系是全序關(guān)系乃戈，因為任何兩個數(shù)都可比大小亩进；而集合{1,2,3}上的整除關(guān)系就不是全序關(guān)系症虑，因為2和3不可比。
- 集合A和A上的偏序關(guān)系一起構(gòu)成偏序集
- 偏序集中極小元和最小元不同归薛，最小元是集合中最小的元素谍憔，它與集合中的其它元素都可比；而極小元不一定和集合中的元素都可比主籍，只是沒有比它小的元素习贫。極小元一定存在，并且可能有多個千元；最小元不一定存在苫昌，若存在也是唯一的。
- f: A->B
- 若ranf=B幸海，則稱f: A->B是滿射的
- 若任意y屬于ranf祟身，都存在唯一的x屬于A使得f(x)=y奥务，則稱f: A->B是單射的（函數(shù)要單調(diào)）
- 若f: A->B既是滿射又是單射的，則稱f: A->B是雙射的（一一映射）
- 集合的勢
集合的勢就是量度集合所含元素多少的量。集合的勢越大，所含的元素就越多浪南。
設(shè)A，B是集合溢谤，如果存在從A到B的雙射函數(shù)，就稱A和B是等勢的憨攒。
設(shè)A世杀，B是集合，如果存在從A到B的單射函數(shù)肝集，就稱B優(yōu)勢于A瞻坝。
一個集合是有窮的當且僅當它與某個自然數(shù)等勢；如果一個集合不是有窮的杏瞻，就稱為無窮集所刀。如{a, b, c}=3
任何有窮集只與唯一的自然數(shù)等勢。
對于有窮集合A捞挥，稱與A等勢的那個唯一的自然數(shù)為A的基數(shù)浮创，記作cardA或|A|.
自然數(shù)集合N的基數(shù)記作阿列夫零，實數(shù)集R的基數(shù)記作阿列夫砌函。
設(shè)A為集合斩披，若cardA小于等于阿列夫零，則稱A是可數(shù)集或可列集讹俊。
