資源描述：
《離散數(shù)學(xué)定義(必須背)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、命題邏輯§(論域)定義：論域是一個(gè)數(shù)學(xué)系統(tǒng)，記為D。它由三部分組成：?(1)一個(gè)非空對(duì)象集合S，每個(gè)對(duì)象也稱為個(gè)體；?(2)一個(gè)關(guān)于D的函數(shù)集合F；?(3)一個(gè)關(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).命題變?cè)呛鲜焦剑?(3).若Q,R是合式公式，則(?Q)、(QùR)、(QúR)、(Q?R)、(Q?R)、(Q?R)是合式公式；?(4).只有有限次應(yīng)
2、用(1)—(3)構(gòu)成的公式是合式公式?！欤ㄉ晒剑┒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。?命題變?cè)獜?fù)雜度為0，如果P是命題變?cè)瑒tFC(P)=0。?如果公式A=?B，則FC(A)=FC(B)+1。?如果公式A=B1ùB2，或A=B1úB2，或A=B1?B2，或A=B1?
3、B2，或A=B1?B2，或則FC(A)=max{FC(B1),FC(B2)}+1?！烀}合式公式語(yǔ)義?論域：研究對(duì)象的集合。?解釋：用論域的對(duì)象對(duì)應(yīng)變?cè)?結(jié)構(gòu)：論域和解釋稱為結(jié)構(gòu)。?語(yǔ)義：符號(hào)指稱的對(duì)象。公式所指稱對(duì)象。合式公式的語(yǔ)義是其對(duì)應(yīng)的邏輯真值?！欤ê鲜焦秸Z(yǔ)義）設(shè)S是聯(lián)結(jié)詞的集合是{?，ù，ú，?，?，?}。由S生成的合式公式Q在真值賦值v下的真值指派v(Q)定義如下：?⑴v(0)=0,v(1)=1。?⑵若Q是命題變?cè)猵，則v(A)=pv。?⑶若Q1,Q2是合式公式§若Q=?Q1，則v(Q)=?v(Q1)§若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)§若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是命題變?cè)猵，則v(Q)=pv。?⑶若Q是FQ1…,Qn，其中n≥1，F(xiàn)是S中的n元聯(lián)結(jié)詞，Qi是公式，則v(Q)=v(FQ1…Qn)=Fv(
5、Q1)…v(Qn)?！欤蓾M足與有效）定義1.7設(shè)Q是公式。?⑴如果真值賦值v使得v(Q)=1，則稱v滿足Q。?⑵如果每個(gè)真值賦值都滿足Q，則稱Q為有效式，或稱為永真式，也稱為重言式。?⑶如果每個(gè)真值賦值都不滿足Q，則稱Q為永假式，也稱為矛盾式，不可滿足式。?⑷如果至少有一個(gè)真值賦值滿足Q，則稱Q為可滿足式?！於ɡ?.5（對(duì)偶定理）?設(shè)A,B是由{0,1,?,∨,∧}生成的公式，A*與A互為對(duì)偶式，B*與B互為對(duì)偶式。如果A?B，則A*?B*。§（完全集）定義：?定義1.12設(shè)F是n元聯(lián)結(jié)詞，p1,p2,…,pn是不同的命
6、題變?cè)?。如果公式A中不出現(xiàn)除p1,p2,…,pn之外的命題變?cè)?，并且A?Fp1,p2,…,pn，則稱A定義F。?設(shè)S是聯(lián)結(jié)詞集合。如果每個(gè)n(n>0)元的聯(lián)結(jié)詞都可由S定義，則稱S為完全集。?如果完全集S1中的每個(gè)聯(lián)結(jié)詞都可由聯(lián)結(jié)詞集合S2定義，則S2也是完全集。?如果從完全集S中去掉任何一個(gè)聯(lián)結(jié)詞就成為不完全的了，就稱S為極小完全集?！?范式)定義：?原子公式和原子公式的否定統(tǒng)稱為文字。如果一個(gè)文字恰為另一個(gè)文字的否定，則稱它們?yōu)橄喾次淖帧?設(shè)n是正整數(shù)，A1,……,An都是文字，稱A1∨…∨An為簡(jiǎn)單析取式，稱A1∧…
7、∧An為簡(jiǎn)單合取式。?定義⒈１６設(shè)n是正整數(shù)。若B1,……,Bn都是簡(jiǎn)單合取式，則稱B1∨…∨Bn為析取范式。若B1,……,Bn都是簡(jiǎn)單析取式，則稱B1∧…∧Bn為合取范式?！欤ㄟ壿嬐普摚┒x：?若真值賦值v滿足公式集合Γ中的每個(gè)公式，則稱v滿足Γ。若有真值賦值滿足Γ，則稱Γ是可滿足的，否則稱Γ是不可滿足的。?設(shè)Γ是公式的集合，A是公式。如果每個(gè)滿足Γ的真值賦值都滿足A，則稱A是Γ的邏輯推論，記為Γ
8、=A。若Γ
9、=A不成立，記為Γ
10、≠A。謂詞邏輯§（論域）定義：論域是一個(gè)數(shù)學(xué)系統(tǒng)，記為D。它由三部分組成：?(1)一個(gè)非空對(duì)
11、象集合D；?(2)一個(gè)關(guān)于D的函數(shù)集合,也稱運(yùn)算；?(3)一個(gè)關(guān)于D的關(guān)系集合?！欤ㄒ浑A謂詞邏輯語(yǔ)言）簡(jiǎn)稱一階邏輯語(yǔ)言?邏輯符號(hào)：包括變?cè)?、?lián)接詞、量詞；?非邏輯符號(hào)：包括常元、函詞、謂詞；?僅有個(gè)體變?cè)?按形成規(guī)則構(gòu)成的合式公式集合?（字符集）定義：§邏輯符號(hào)，包括變?cè)?、?lián)接詞、量詞、逗號(hào)以及括號(hào)等
