離散數(shù)學(xué)(數(shù)學(xué)教育)知識(shí)點(diǎn)

蘊(yùn)涵（）：設(shè)P,Q是兩個(gè)命題，，命題“若P，則Q”稱為P蘊(yùn)涵Q，記作.規(guī)定：是假的當(dāng)且僅當(dāng)P是真的而Q是假的.二、1．設(shè)A是非空集合，R是A上的二元關(guān)系，R的自反閉包（對(duì)稱閉包、傳遞閉包）滿足如下條件：（1）是自反的（對(duì)稱的，傳遞的）；（2）；（3）對(duì)A上任意包含R的自反的（對(duì)稱的，傳遞的）關(guān)系，都有.2．R的自反閉包、對(duì)稱閉包和傳遞閉包分別記為，他們分別是包含R的最?。ㄊ侵冈貍€(gè)數(shù)最?。┑淖苑搓P(guān)系、對(duì)稱關(guān)系和傳遞關(guān)系.3．定理1.2.5：設(shè)R是集合A上的關(guān)系，則（1）；（2）；（3）.三．五個(gè)特殊關(guān)系：集合A上的關(guān)系R稱為自反的（反身的），如果對(duì)于每個(gè)，都有對(duì)于自反性，有3個(gè)命題是等價(jià)的：（1）R是自反的；（2）;（3）是自反的.集合A上的關(guān)系R稱為對(duì)稱的，如果xRy，則有yRx，其中.對(duì)于對(duì)稱性，有2個(gè)命題是等價(jià)的：（1）R是對(duì)稱的；（2）.集合A上的關(guān)系R稱為傳遞的，如果xRy，yRz，則有xRz，其中.集合A上的關(guān)系R稱為反對(duì)稱的，如果xRy，yRx，則必有x=y,其中.對(duì)于反對(duì)稱性，有2個(gè)命題是等價(jià)的：（1）R是反對(duì)稱的；（2）.（注意這里若，也有，即若，也稱R是反對(duì)稱的）.集合A上的關(guān)系R稱為反自反的，如果對(duì)于每個(gè)，均不成立.對(duì)于反自反性，有2個(gè)命題是等價(jià)的：（1）R是反自反的；（2）.注：逆關(guān)系：設(shè)R是集合A上的一個(gè)關(guān)系，令，稱關(guān)系為關(guān)系R的逆關(guān)系.四．基本的等價(jià)式和蘊(yùn)涵式基本的等價(jià)式如下：（1）；（2）；（3）；（等冪律）（4）；（交換律）（5）；（結(jié)合律）（6）；（吸收律）（7）；（分配律）（8）；（同一律）（9）；（零一律）（10）.（DeMorgan律）2．基本蘊(yùn)涵式：（1）；（2）；（3）；（因?yàn)椋?）；（因?yàn)?3．注1：的充要條件是公式是恒真的.五．1．等價(jià)關(guān)系：設(shè)R是非空集合A上的一個(gè)關(guān)系，若R具有自反性、對(duì)稱性和傳遞性，則稱R是一個(gè)等價(jià)關(guān)系.例子：設(shè)A={a,b,c}，R={(a,a),(b,b),(c,c),(a,b),(b,a)}是A上的等價(jià)關(guān)系.等價(jià)類：設(shè)A是一個(gè)非空集合，是A上的一個(gè)等價(jià)關(guān)系.A的一個(gè)非空集合M叫做一個(gè)等價(jià)類，如果若，則；若，則.（即a,b屬于同一個(gè)等價(jià)類當(dāng)且僅當(dāng)）商集：設(shè)R是非空集合A上的一個(gè)等價(jià)關(guān)系，以R的所有不同的等價(jià)類為元素作成的集合稱為A關(guān)于R的商集，簡(jiǎn)稱A的商集，記作.劃分：當(dāng)A的子集簇C滿足如下條件時(shí)，稱C為A的劃分：若，則；（2）；（3）對(duì)任意的，且，則.定理：設(shè)R是非空集合A上的一個(gè)等價(jià)關(guān)系，則A的商集構(gòu)成A的一個(gè)劃分；反之，若C是集合A的一個(gè)劃分，令，則是A的一個(gè)等價(jià)關(guān)系.六．冪集的定義：設(shè)A是集合，A中所有子集為元素構(gòu)成的集合稱為A的冪集。七．主析取范式設(shè)是n個(gè)不同的原子，一個(gè)短語如果恰好包含所有這n個(gè)原子或其否定，且其排列順序與的順序一致，則稱此短語為關(guān)于的一個(gè)極小項(xiàng).共有個(gè)不同的極小項(xiàng).例子：有3個(gè)不同的原子P,Q,R，則是極小項(xiàng).書本定義2.4.5：主析取范式的定義定理2.4.2：對(duì)于命題公式G，都存在等價(jià)于它的主析取范式.主析取范式的求法及應(yīng)用例子：求下列公式的主析取范式：．知識(shí)回顧：若G在一組解釋下為真，則對(duì)應(yīng)主析取范式中的一個(gè)極小項(xiàng)，具體的作法如下：在此解釋中原子的真值是1時(shí)，極小項(xiàng)取它自身；在此解釋中原子的真值是0時(shí)，極小項(xiàng)取它的否定.解：應(yīng)用真值表法求其主析取范式.的真值表如下：PQ00101011011000011111由上表可知G的主析取范式為：.是可滿足的.八．群，單位元，逆元九．完全圖：若G中任兩點(diǎn)之間恰有一條邊，則稱G為完全圖.n個(gè)頂點(diǎn)的完全圖恰有條邊.十．設(shè)R,S是集合A上的兩個(gè)關(guān)系，令，或則稱為關(guān)系R與S的乘積或合成.十一.設(shè)是有個(gè)頂點(diǎn)條邊的簡(jiǎn)單連通圖，那么.十二.1．例子：設(shè)，，則下列公式中，（）的真值為1.ABCD例子：對(duì)公式，給出如下的解釋I：D={2,3}；；于是，