- 非真即假的陳述句稱為命題
- 不能被分解的命題稱為簡(jiǎn)單命題或原子命題，由簡(jiǎn)單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的命題稱為復(fù)合命題
- 將命題變項(xiàng)用聯(lián)結(jié)詞和圓括號(hào)按一定的邏輯關(guān)系聯(lián)結(jié)起來的符號(hào)串稱為合式公式，也稱為命題公式
- 設(shè)A為任一命題公式
- 若A在它的各種賦值下取值均為真，則稱A為永真式或重言式
- 若A在它的各種賦值下取值均為假，則稱A為永假式或矛盾式
- 若A不是矛盾式，則稱A是可滿足式（A至少存在一個(gè)成真賦值，重言式一定是可滿足式）
- 命題變項(xiàng)及其否定統(tǒng)稱為文字。
僅由有限個(gè)文字構(gòu)成的析取式稱作簡(jiǎn)單析取式
僅由有限個(gè)文字構(gòu)成的合取式稱作簡(jiǎn)單合取式
一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變項(xiàng)及其否定式
一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變項(xiàng)及其否定式 - 范式
由有限個(gè)簡(jiǎn)單合取式的析取構(gòu)成的命題公式稱為析取范式
由有限個(gè)簡(jiǎn)單析取式的合取構(gòu)成的命題公式稱為合取范式
析取范式和合取范式統(tǒng)稱為范式 - 范式存在定理
任一命題公式都存在與之等值的析取范式和合取范式 - 極小項(xiàng)和極大項(xiàng)
在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式（簡(jiǎn)單析取式）中，若每個(gè)命題變項(xiàng)和它的否定式恰好出現(xiàn)一個(gè)且僅出現(xiàn)一次，而且命題變項(xiàng)或它的否定式按下標(biāo)從小到大或按字典順序排列，稱這樣的簡(jiǎn)單合取式（簡(jiǎn)單析取式）為極小項(xiàng)（極大項(xiàng)） - 主析取范式
所有簡(jiǎn)單合取式（簡(jiǎn)單析取式）都是極小項(xiàng)（極大項(xiàng)）的析取范式（合取范式）稱為主析取范式（主合取范式）
任何命題公式都存在與之等值的主析取范式和主合取范式，并且是唯一的 - 判斷推理正確與否
- 真值表法
- 等值演算法
- 主析取范式法
- 形式系統(tǒng)
- 自然推理系統(tǒng)：從任意給定的前提出發(fā)，應(yīng)用系統(tǒng)中的推理規(guī)則進(jìn)行推理演算，最后得到的命題公式是推理的結(jié)論（它是有效的結(jié)論，可能是重言式，也可能不是重言式）
- 公理推理系統(tǒng)：只能從若干條給定的公理出發(fā)，應(yīng)用系統(tǒng)中的推理規(guī)則進(jìn)行推理演算，得到的結(jié)論是系統(tǒng)中的重言式，稱為系統(tǒng)中的定理。
- 一階邏輯（一階謂詞邏輯或謂詞邏輯）
在命題邏輯中不能很好的描述“凡偶數(shù)都能被2整除”中的“凡”字，為了克服命題邏輯的局限性，需要引入量詞，以期達(dá)到表達(dá)出個(gè)體與總體之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系，這就是一階邏輯研究的內(nèi)容 - 閉式
設(shè)A是任意公式，若A中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則稱A為封閉的公式，簡(jiǎn)稱閉式 - 前束范式
具有如下形式Q1x1Q2x2...QkxkB的一階邏輯公式稱為前束范式，其中Q為量詞存在或任意，B不含量詞的公式。
前束范式存在定理：一階邏輯中的任何公式都存在等值的前述范式 - 集合之間的關(guān)系和初級(jí)運(yùn)算可以用文恩圖（Venn Diagram）給予形象的描述。
-
包含排斥原理（容斥原理）
在計(jì)數(shù)時(shí)，必須沒有重復(fù)和遺漏?？梢韵炔豢紤]重疊的情況，把包含于某內(nèi)容中的所有對(duì)象的數(shù)目先計(jì)算出來，然后再把計(jì)數(shù)時(shí)重復(fù)的數(shù)目排斥出去，使得計(jì)算結(jié)果既無遺漏有無重復(fù)，這種計(jì)數(shù)方法稱為容斥原理。
image.png - 笛卡爾積
設(shè)A，B為集合，用A中的元素作為第一元素，B中的元素作為第二元素構(gòu)成有序?qū)?，所有這樣的有序?qū)M成的集合叫做A和B的笛卡爾積，記作AxB. - 二元關(guān)系
如果一個(gè)集合滿足以下條件之一，則稱該集合為一個(gè)二元關(guān)系。
- 集合非空，且它的元素都是有序?qū)?/li>
- 集合是空集
- 設(shè)A，B為集合，AxB的任何子集所定義的二元關(guān)系叫做從A到B的二元關(guān)系，當(dāng)B=A時(shí)叫做A上的二元關(guān)系
集合A的全體子集構(gòu)成的集合叫做A的冪集，記作P(A). -
等價(jià)關(guān)系
設(shè)R為非空集合A上的關(guān)系，如果R是自反的、對(duì)稱的、傳遞的，則稱R為A上的等價(jià)關(guān)系。
image.png
image.png
image.png
以R的所有等價(jià)類作為元素的集合稱為A關(guān)于R的商集，記作A/R.
商集就是A上的一個(gè)劃分，并且不同的商集將對(duì)應(yīng)于不同的劃分。A上的等價(jià)關(guān)系和A的劃分是一一對(duì)應(yīng)的。 - 偏序關(guān)系
- 設(shè)R是非空集合A上的關(guān)系，若R是自反的、反對(duì)稱的、傳遞的，則稱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)系，因?yàn)槿魏蝺蓚€(gè)數(shù)都可比大??；而集合{1,2,3}上的整除關(guān)系就不是全序關(guān)系，因?yàn)?和3不可比。
- 集合A和A上的偏序關(guān)系一起構(gòu)成偏序集
- 偏序集中極小元和最小元不同，最小元是集合中最小的元素，它與集合中的其它元素都可比；而極小元不一定和集合中的元素都可比，只是沒有比它小的元素。極小元一定存在，并且可能有多個(gè)；最小元不一定存在，若存在也是唯一的。
- 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ì)
集合的勢(shì)就是量度集合所含元素多少的量。集合的勢(shì)越大，所含的元素就越多。
設(shè)A，B是集合，如果存在從A到B的雙射函數(shù)，就稱A和B是等勢(shì)的。
設(shè)A，B是集合，如果存在從A到B的單射函數(shù)，就稱B優(yōu)勢(shì)于A。
一個(gè)集合是有窮的當(dāng)且僅當(dāng)它與某個(gè)自然數(shù)等勢(shì)；如果一個(gè)集合不是有窮的，就稱為無窮集。如{a, b, c}=3
任何有窮集只與唯一的自然數(shù)等勢(shì)。
對(duì)于有窮集合A，稱與A等勢(shì)的那個(gè)唯一的自然數(shù)為A的基數(shù)，記作cardA或|A|.
自然數(shù)集合N的基數(shù)記作阿列夫零，實(shí)數(shù)集R的基數(shù)記作阿列夫。
設(shè)A為集合，若cardA小于等于阿列夫零，則稱A是可數(shù)集或可列集。
