《離散數(shù)學(xué)定義(必須背).doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、命題邏輯§(論域)定義：論域是一個數(shù)學(xué)系統(tǒng)，記為D。它由三部分組成：?(1)一個非空對象集合S，每個對象也稱為個體；?(2)一個關(guān)于D的函數(shù)集合F；?(3)一個關(guān)于D的關(guān)系集合R?！欤ㄟ壿嬤B接詞）定義?設(shè)n>0,稱為{0,1}n到{0,1}的函數(shù)為n元函數(shù)，真值函數(shù)也稱為聯(lián)結(jié)詞。?若n=0，則稱為0元函數(shù)?！欤}合式公式）定義：?(1).常元0和1是合式公式；?(2).命題變元是合式公式；?(3).若Q,R是合式公式，則(?Q)、(QùR)、(QúR)、(Q?R)、(Q?R)、(Q?R)是合式公式；?(4).只有有限次應(yīng)用(1)—(3)構(gòu)成的公式是合式公式

2、?！欤ㄉ晒剑┒x1.5設(shè)S是聯(lián)結(jié)詞的集合。由S生成的公式定義如下：?⑴若c是S中的0元聯(lián)結(jié)詞，則c是由S生成的公式。?⑵原子公式是由S生成的公式。?⑶若n≥1，F(xiàn)是S中的n元聯(lián)結(jié)詞，A1,…,An是由S生成的公式，則FA1…An是由S生成的公式。§（復(fù)雜度）公式A的復(fù)雜度表示為FC(A)?常元復(fù)雜度為0。?命題變元復(fù)雜度為0，如果P是命題變元，則FC(P)=0。?如果公式A=?B，則FC(A)=FC(B)+1。?如果公式A=B1ùB2，或A=B1úB2，或A=B1?B2，或A=B1?B2，或A=B1?B2，或則FC(A)=max{FC(B1),FC(B2

3、)}+1?！烀}合式公式語義?論域：研究對象的集合。?解釋：用論域的對象對應(yīng)變元。?結(jié)構(gòu)：論域和解釋稱為結(jié)構(gòu)。?語義：符號指稱的對象。公式所指稱對象。合式公式的語義是其對應(yīng)的邏輯真值?！欤ê鲜焦秸Z義）設(shè)S是聯(lián)結(jié)詞的集合是{?，ù，ú，?，?，?}。由S生成的合式公式Q在真值賦值v下的真值指派v(Q)定義如下：?⑴v(0)=0,v(1)=1。?⑵若Q是命題變元p，則v(A)=pv。?⑶若Q1,Q2是合式公式§若Q=?Q1，則v(Q)=?v(Q1)§若Q=Q1ùQ2，則v(Q)=v(Q1)ùv(Q2)§若Q=Q1∨Q2，則v(Q)=v(Q1)∨v(Q2)§若Q

4、=Q1?Q2，則v(Q)=v(Q1)?v(Q2)§若Q=Q1?Q2，則v(Q)=v(Q1)?v(Q2)§若Q=Q1?Q2，則v(Q)=v(Q1)?v(Q2)§（真值賦值）由S生成的公式Q在真值賦值v下的真值v(Q)定義如下：?⑴若Q是S中的0元聯(lián)結(jié)詞c，則v(Q)=c。?⑵若Q是命題變元p，則v(Q)=pv。?⑶若Q是FQ1…,Qn，其中n≥1，F(xiàn)是S中的n元聯(lián)結(jié)詞，Qi是公式，則v(Q)=v(FQ1…Qn)=Fv(Q1)…v(Qn)?！欤蓾M足與有效）定義1.7設(shè)Q是公式。?⑴如果真值賦值v使得v(Q)=1，則稱v滿足Q。?⑵如果每個真值賦值都滿足Q，則稱

5、Q為有效式，或稱為永真式，也稱為重言式。?⑶如果每個真值賦值都不滿足Q，則稱Q為永假式，也稱為矛盾式，不可滿足式。?⑷如果至少有一個真值賦值滿足Q，則稱Q為可滿足式?！於ɡ?.5（對偶定理）?設(shè)A,B是由{0,1,?,∨,∧}生成的公式，A*與A互為對偶式，B*與B互為對偶式。如果A?B，則A*?B*?！欤ㄍ耆┒x：?定義1.12設(shè)F是n元聯(lián)結(jié)詞，p1,p2,…,pn是不同的命題變元。如果公式A中不出現(xiàn)除p1,p2,…,pn之外的命題變元，并且A?Fp1,p2,…,pn，則稱A定義F。?設(shè)S是聯(lián)結(jié)詞集合。如果每個n(n>0)元的聯(lián)結(jié)詞都可由S定義，則稱S

6、為完全集。?如果完全集S1中的每個聯(lián)結(jié)詞都可由聯(lián)結(jié)詞集合S2定義，則S2也是完全集。?如果從完全集S中去掉任何一個聯(lián)結(jié)詞就成為不完全的了，就稱S為極小完全集?！?范式)定義：?原子公式和原子公式的否定統(tǒng)稱為文字。如果一個文字恰為另一個文字的否定，則稱它們?yōu)橄喾次淖帧?設(shè)n是正整數(shù)，A1,……,An都是文字，稱A1∨…∨An為簡單析取式，稱A1∧…∧An為簡單合取式。?定義⒈１６設(shè)n是正整數(shù)。若B1,……,Bn都是簡單合取式，則稱B1∨…∨Bn為析取范式。若B1,……,Bn都是簡單析取式，則稱B1∧…∧Bn為合取范式?！欤ㄟ壿嬐普摚┒x：?若真值賦值v滿足公式

7、集合Γ中的每個公式，則稱v滿足Γ。若有真值賦值滿足Γ，則稱Γ是可滿足的，否則稱Γ是不可滿足的。?設(shè)Γ是公式的集合，A是公式。如果每個滿足Γ的真值賦值都滿足A，則稱A是Γ的邏輯推論，記為Γ

8、=A。若Γ

9、=A不成立，記為Γ

10、≠A。謂詞邏輯§（論域）定義：論域是一個數(shù)學(xué)系統(tǒng)，記為D。它由三部分組成：?(1)一個非空對象集合D；?(2)一個關(guān)于D的函數(shù)集合,也稱運算；?(3)一個關(guān)于D的關(guān)系集合?！欤ㄒ浑A謂詞邏輯語言）簡稱一階邏輯語言?邏輯符號：包括變元、聯(lián)接詞、量詞；?非邏輯符號：包括常元、函詞、謂詞；?僅有個體變元；?按形成規(guī)則構(gòu)成的合式公式集合?（字符集）定義

11、：§邏輯符號，包括變元、聯(lián)接詞、量詞、逗號以及括號等