離散數(shù)學之數(shù)理邏輯(習題課)

1、離散數(shù)學之數(shù)理邏輯（習題課）上海交通大學軟件學院吳剛2009年春內容n內容復習n習題講解n復習作業(yè)內容復習n數(shù)理邏輯：用數(shù)學方法研究形式邏輯中推理（演繹）規(guī)律的一門學科n特制的符號語言體系n公理化與形式化方法內容復習n命題邏輯n命題的概念與判斷n命題聯(lián)結詞n真值表內容復習n命題的公式化n準確判斷原子命題；n析取和異或的關系；n指派n成真指派、成假指派n重言式、矛盾、可滿足公式內容復習n等價重言式（等式）n含義n基本等式n對偶定理n蘊涵重言式n含義n基本蘊涵重言式內容復習n等式證明與蘊涵重言式證明n利用基本等式/基本蘊涵重言式n真值表n范式n命題邏輯推理n“前提1,前提2,前提n 結論”有效的充

2、要條件是命題公式“(前提1 前提2 前提n) 結論”是重言式n推理規(guī)則內容復習n范式n析取范式n合取范式n特異析取范式n特異合取范式n矛盾/重言式與范式的關系n最小項與最大項n與指派的對應關系內容復習n聯(lián)結詞化歸n聯(lián)結詞的完全集內容復習n謂詞邏輯n謂詞與個體n量詞n個體域的表達與量詞約束n函數(shù)：個體之間的關系內容復習n謂詞邏輯n公式構成n項n原子公式n公式n量詞的轄域、自由變元與約束變元n改名規(guī)則內容復習n謂詞邏輯n命題的謂詞邏輯公式化n謂詞邏輯公式的解釋n個體變元、個體常量、n元函數(shù)f、謂詞Fn解釋給定后，若無自由變元則公式真值確定n解釋給定后，若有自由變元，則賦值后公式真值確定n謂詞邏輯公

3、式的永真、永假、可滿足內容復習n謂詞邏輯n等價永真公式（含義同命題邏輯永真公式）n蘊涵永真公式（含義同命題邏輯永真公式）n基本等價永真公式和蘊涵永真公式n但謂詞邏輯永真公式不易證明n利用基本公式n范式內容復習n謂詞邏輯n前束范式n斯柯林范式n一個謂詞公式的永真/永假性和可滿足性與其斯柯林范式相同，但一般并不等價數(shù)理邏輯公理化n形式化公理系統(tǒng)的組成n語法部分n基本符號n公式的構成規(guī)則n推理部分n公理n推理規(guī)則n推理方法n定理形式化公理系統(tǒng)的性質n系統(tǒng)的一致性（不矛盾性）、完備性、獨立性n相對完備性、絕對完備性n并不追求獨立性命題邏輯公理系統(tǒng)（N系統(tǒng)）n命題邏輯永真公式的公理系統(tǒng)n語法部分n基本符號：原子命題、聯(lián)結詞、括弧n公式構成：n := P | ( ) | ( ) | ( ) |( ) | ( )， 其中P代表原子命題，、是公式命題邏輯公理系統(tǒng)n推理部分n公理（P.212共15條，并不獨立）n規(guī)則nPQ, P Q 分離規(guī)則n證明方法n給出一個公式序列：P1，P2，PnnPn是證明出來的定理nPi（i=1,2,n）要么是公理，要么由Pj、Pk經(jīng)過規(guī)則生成（j,k0或=0習題講解n11.2n第2題麻煩點n11.3n注意改名n11.4n注意存在量詞的處理習題講解n12.1n簡單n12.2n注意額外變元n第