離散數(shù)學定義(必須背)

《離散數(shù)學定義(必須背)》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、命題邏輯§(論域)定義：論域是一個數(shù)學系統(tǒng)，記為D。它由三部分組成：?(1)一個非空對象集合S，每個對象也稱為個體；?(2)一個關于D的函數(shù)集合F；?(3)一個關于D的關系集合R?！欤ㄟ壿嬤B接詞）定義?設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).只有有限次應

2、用(1)—(3)構成的公式是合式公式。§（生成公式）定義1.5設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生成的公式。§（復雜度）公式A的復雜度表示為FC(A)?常元復雜度為0。?命題變元復雜度為0，如果P是命題變元，則FC(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?！烀}合式公式語義?論域：研究對象的集合。?解釋：用論域的對象對應變元。?結(jié)構：論域和解釋稱為結(jié)構。?語義：符號指稱的對象。公式所指稱對象。合式公式的語義是其對應的邏輯真值。§（合式公式語義）設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

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是命題變元p，則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設Q是公式。?⑴如果真值賦值v使得v(Q)=1，則稱v滿足Q。?⑵如果每個真值賦值都滿足Q，則稱Q為有效式，或稱為永真式，也稱為重言式。?⑶如果每個真值賦值都不滿足Q，則稱Q為永假式，也稱為矛盾式，不可滿足式。?⑷如果至少有一個真值賦值滿足Q，則稱Q為可滿足式。§定理1.5（對偶定理）?設A,B是由{0,1,?,∨,∧}生成的公式，A*與A互為對偶式，B*與B互為對偶式。如果A?B，則A*?B*?！欤ㄍ耆┒x：?定義1.12設F是n元聯(lián)結(jié)詞，p1,p2,…,pn是不同的命

6、題變元。如果公式A中不出現(xiàn)除p1,p2,…,pn之外的命題變元，并且A?Fp1,p2,…,pn，則稱A定義F。?設S是聯(lián)結(jié)詞集合。如果每個n(n>0)元的聯(lián)結(jié)詞都可由S定義，則稱S為完全集。?如果完全集S1中的每個聯(lián)結(jié)詞都可由聯(lián)結(jié)詞集合S2定義，則S2也是完全集。?如果從完全集S中去掉任何一個聯(lián)結(jié)詞就成為不完全的了，就稱S為極小完全集?！?范式)定義：?原子公式和原子公式的否定統(tǒng)稱為文字。如果一個文字恰為另一個文字的否定，則稱它們?yōu)橄喾次淖帧?設n是正整數(shù)，A1,……,An都是文字，稱A1∨…∨An為簡單析取式，稱A1∧…

7、∧An為簡單合取式。?定義⒈１６設n是正整數(shù)。若B1,……,Bn都是簡單合取式，則稱B1∨…∨Bn為析取范式。若B1,……,Bn都是簡單析取式，則稱B1∧…∧Bn為合取范式?！欤ㄟ壿嬐普摚┒x：?若真值賦值v滿足公式集合Γ中的每個公式，則稱v滿足Γ。若有真值賦值滿足Γ，則稱Γ是可滿足的，否則稱Γ是不可滿足的。?設Γ是公式的集合，A是公式。如果每個滿足Γ的真值賦值都滿足A，則稱A是Γ的邏輯推論，記為Γ

8、=A。若Γ

9、=A不成立，記為Γ

10、≠A。謂詞邏輯§（論域）定義：論域是一個數(shù)學系統(tǒng)，記為D。它由三部分組成：?(1)一個非空對

11、象集合D；?(2)一個關于D的函數(shù)集合,也稱運算；?(3)一個關于D的關系集合?！欤ㄒ浑A謂詞邏輯語言）簡稱一階邏輯語言?邏輯符號：包括變元、聯(lián)接詞、量詞；?非邏輯符號：包括常元、函詞、謂詞；?僅有個體變元；?按形成規(guī)則構成的合式公式集合?（字符集）定義：§邏輯符號，包括變元、聯(lián)接詞、量詞、逗號以及括號等