計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)5

1、第二章 謂詞邏輯蘇格拉底三段論：凡人要死，蘇格拉底是人，所以蘇格拉底要死， P：凡人要死 Q：蘇格拉底是人 R：蘇格拉底要死 此三段論表示為（PQ）R蘇格拉底三段論是正確的，但PQR卻不是重言式，這就是命題邏輯的局限性。2.1 謂詞邏輯的基本概念一、 謂詞1.個(gè)體域： 命題邏輯中將命題（句子）繼續(xù)細(xì)分。命題是由主語(yǔ)和謂語(yǔ)兩部分組成。主語(yǔ)是名詞，稱之為個(gè)體詞。是獨(dú)立存在的客體，可以是具體事物也可以是抽象概念。 在謂語(yǔ)中含有賓語(yǔ)，它也是名詞，它也是個(gè)體詞。個(gè)體域：客體（個(gè)體）的取值范圍。例如：吳華是大學(xué)生，用P表示， 李明是大學(xué)生，用Q表示。 在命題邏輯中就沒(méi)辦法表示出兩句的聯(lián)系。“是大學(xué)生”用A

2、（X）表示，x是大學(xué)生，命題符號(hào)含有個(gè)體詞變量。a表示吳華，A（a）表示吳華是大學(xué)生。b表示李明，A（b）表示李明是大學(xué)生。 相當(dāng)于“是大學(xué)生”，用A（）來(lái)表示，這就是謂詞。例：張三比李四高， 用H（x,y）表示x比y高。a:張三b:李四 H（a,b）：張三比李四高H（b,a）：李四比張三高x,y,a,b表示客體，H（,）是謂詞這個(gè)謂詞涉及了兩個(gè)客體，是二元謂詞。2.謂詞： 只涉及一個(gè)客體的謂詞稱為一元謂詞，涉及兩個(gè)客體的謂詞稱為二元謂詞，涉及n個(gè)客體的謂詞稱為n元謂詞。 一般，如A表示謂詞符號(hào)，用Xi表示第i個(gè)客體變項(xiàng)，則n元謂詞表示為A（x1,xn）,如a1,a2,an是個(gè)體域中的客體名詞

3、，則A（a1,a2,an）是個(gè)命題。不含客體變項(xiàng)的謂詞稱零元謂詞，零元謂詞本身就是命題。注意：（1） n元謂詞中，客體變項(xiàng)的次序很重要 。 例：F（x,y）表示x是y的父親，a:張三，b:張小明。 F（a,b）表示張三是張小明的父親。 F（b,a）表示張小明是張三的父親。 兩個(gè)命題至多一個(gè)是真（2） 在討論一個(gè)問(wèn)題是必須先確定好個(gè)體域D。如不作限制，表示宇宙一切事物組成的個(gè)體，成為全總個(gè)體域。（3） 同一個(gè)n元謂詞，取不同的客觀，真假會(huì)不同。A（x）：x是大學(xué)生。 A（a） 真值可能為真，而A（b）真值可能為假。（4） 對(duì)于同一謂詞，個(gè)體域D不同，真值可能也不同。 例：對(duì)于A（x），x是大學(xué)生

4、。 如D=大學(xué)生全體，A（x）是重言式。 如D=學(xué)生全體，A（x）是僅可滿足式。 如D=計(jì)算機(jī)全體，A（x）是永假式。3.命題函數(shù) 對(duì)于謂詞B（x），B（x,y），H（x,y,z）等，本身不是命題。 只有命題變項(xiàng)在D中取出個(gè)體名稱時(shí)才成為一個(gè)確定的命題。 故謂詞也稱為命題函數(shù)或簡(jiǎn)單命題函數(shù)。 有限個(gè)簡(jiǎn)單命題函數(shù)用聯(lián)結(jié)詞，進(jìn)行聯(lián)結(jié)而成，成為復(fù)合命題函數(shù)。二、 量詞：1. 全稱量詞：“所有的”，“任何一個(gè)”，“每一個(gè)”，“凡是”，“一切”表示個(gè)體域中每一個(gè)，用符號(hào)“”表示，稱為全稱量詞。 例1：將下列命題符號(hào)化（1） 所有人都要呼吸（2） 每個(gè)人都是要死的解: （1）設(shè)M（x）：x是人，M（x）：

5、x是要呼吸。 命題符號(hào)化為： x（M（x）H（x）。（3） 設(shè)M（x）：x是人，D（x）：x是要死的。 命題符號(hào)化為： x（M（x）D（x）。2.存在量詞：“有些”，“存在”，“至少有一個(gè)”，表示個(gè)體域D中存在個(gè)體，用符號(hào)“$”表示。例2：將下列命題符號(hào)化（1） 有些人是聰明和美麗的。（2） 有人早飯吃面包。解: （1）設(shè)M（x）：x是人，Q（x）：x是聰明的， R（x）：x是美麗的。 命題符號(hào)化為：$x（M（x）Q（x）R（x）。（3） 設(shè)M（x）：x是人，E（x）：x是早飯時(shí)吃面包， 命題符號(hào)化為：$x（M（x）E（x）說(shuō)明：命題符號(hào)化之前，必須明確個(gè)體域的范圍，以上兩例子均為 全總個(gè)體域

6、。 如果將個(gè)體域改為D=人類，則特性謂詞M（x）就不需要 了。 例1：（1） xH（x），（2） xD（x） 例2：（1）$x（Q（x）R（x） （2）$xE（x）3.含量詞的謂詞的真值規(guī)定 說(shuō)明：不含量詞的謂詞公式G（x） ，它不是命題，而是命題函 數(shù)，其真值依賴于x從個(gè)體域中取的個(gè)體名詞的不同而不 同。例：D表示某班全體學(xué)生，G（x）表示x是男生。 則G（李剛）是真，而G（王芳）是假。 而 xG（x）與$xG（x）是命題了，x僅是一個(gè)“指導(dǎo)變量” xG（x）與 xG（y）意義完全相同。 xG（x）：全班每個(gè)人均是男生。$xG（x）：全班存在一個(gè)人是男生。 含量詞的謂詞公式的真值不再依賴于x的選取了。 （1） xG（x）的真值規(guī)定 xG（x）的命題是“對(duì)任意xD，均有G（x）” xG（x）的真值為1，當(dāng)且僅當(dāng)，對(duì)一切xD，G（x）真 值 均為1， xG（x）的真值為0，當(dāng)且僅當(dāng)，對(duì)一切x0D， G（x0）真 值為0。（2） $xG（x）的真值規(guī)定$xG（x）的命題是“存在一個(gè)x0D，使得G（x0）成立”$xG（x）的真值為1，當(dāng)且僅當(dāng)存在x0D， G（x0）的真值為1。$xG（x）的真值為0， 當(dāng)且僅當(dāng)，對(duì)一切xD， G（x）的真值為0