一階邏輯等值演算與推理課件

第五章一階邏輯等值演算與推理主要內(nèi)容：重要的等值式①在有限個(gè)體域內(nèi)消去量詞等值式②量詞否定等值式③量詞轄域收縮與擴(kuò)張等值式④量詞分配等值式基本規(guī)則①置換規(guī)則②換名規(guī)則③代替規(guī)則前束范式與公式的前束范式自然推理系統(tǒng)F第五章一階邏輯等值演算與推理主要內(nèi)容：要求：深刻理解并記住重要等值式，并能熟練地應(yīng)用它們熟練地使用置換規(guī)則、換名規(guī)則、代替規(guī)則準(zhǔn)確地求出給定公式的前束范式正確地使用UI,UG,EG,EI規(guī)則，特別要注意它們之間的關(guān)系對(duì)給定的推理，正確地構(gòu)造出它的證明

要求：一、量詞否定等值式例：設(shè)P(x)：X今天去過操場(chǎng)（1）不是所有人今天去過操場(chǎng)存在一些人今天沒有去過操場(chǎng)（2）不存在一些人今天去過操場(chǎng)所有人今天都沒有去過操場(chǎng)。5.1一階邏輯等值式與置換規(guī)則一、量詞否定等值式例：設(shè)P(x)：X今天去過操場(chǎng)5.1一階證：設(shè)個(gè)體域中的客體變?cè)獮樽C：設(shè)個(gè)體域中的客體變?cè)獮槎⒘吭~轄域的擴(kuò)張與收縮等值式二、量詞轄域的擴(kuò)張與收縮等值式例：證明：證：例：證明：證：類似的可以推出：

例如類似的可以推出：例如三、量詞分配等值式例如聯(lián)歡會(huì)上所有人既唱歌又跳舞和所有人唱歌且所有人跳舞。這兩個(gè)語句意義相同。根據(jù)上式亦有：三、量詞分配等值式例如聯(lián)歡會(huì)上所有人既唱歌又跳舞和所有人唱四、多個(gè)量詞的使用對(duì)于甲村所有的人，乙村都有人和他同姓。存在一個(gè)乙村的人，甲村的人和他同姓。四、多個(gè)量詞的使用對(duì)于甲村所有的人，乙村都有人和他同姓。存在全稱量詞與存在量詞在公式中出現(xiàn)的次序，不能隨意更換。具有兩個(gè)量詞的謂詞公式，有如下一些蘊(yùn)含關(guān)系。存在一個(gè)甲村的人，乙村的人都和他同姓。對(duì)于乙村的人，甲村都有人和他同姓。全稱量詞與存在量詞在公式中出現(xiàn)的次序，不能隨意更換。具有兩個(gè)五、量詞分配中的一些推理關(guān)系式這些學(xué)生都聰明或這些學(xué)生都努力這些學(xué)生都聰明或努力。這些學(xué)生都聰明或努力這些學(xué)生都聰明或這些學(xué)生都努力。五、量詞分配中的一些推理關(guān)系式這些學(xué)生都聰明或這些學(xué)生都努力說明:以上五種單個(gè)量詞的謂詞演算式可類似推廣到多個(gè)量詞的情況。類似的有：說明:以上五種單個(gè)量詞的謂詞演算式可類似推類似的有：5.2一階邏輯前束范式前束范式：謂詞公式具有形式：則該公式叫前束范式。其中Ｑi是量詞或，A是不含量詞的謂詞公式。方法：利用換名規(guī)則及代替規(guī)則求前束范式5.2一階邏輯前束范式前束范式：謂詞公式具有形式：方法例:求下列公式的前束范式.１、原式例:求下列公式的前束范式.１、原式一階邏輯等值演算與推理課件４、４、１、全稱量詞消去規(guī)則（UＩ）5.3一階邏輯推理理論x是Ａ(x)中自由出現(xiàn)的個(gè)體變項(xiàng)；y為任意不在Ａ(x)中約束出現(xiàn)的個(gè)體變項(xiàng)；c為任意的個(gè)體常項(xiàng)。2、全稱量詞引入規(guī)則（UG）y在Ａ(y)中自由出現(xiàn)，且y取任何值時(shí)Ａ均為真；取代y的x不能在Ａ(y)中約束出現(xiàn)，否則會(huì)產(chǎn)生錯(cuò)誤。１、全稱量詞消去規(guī)則（UＩ）5.3一階邏輯推理理論x例：證明蘇格拉底的三段論（2）(1)ＵＩ（3）A（S）（4）M（S）證明：A(x):x是一個(gè)人M(x)：x是要死的S:蘇格拉底

（1）前提引入前提引入（2)(3)假言推理例：證明蘇格拉底的三段論（2）(1)ＵＩ（3）A（S）（（3）存在量詞引入規(guī)則（ＥＧ）（4）存在量詞消去規(guī)則（EＩ）c是特定的個(gè)體常項(xiàng)；取代c的x不能已在Ａ(c)中出現(xiàn)過。c是使Ａ為真的特定的個(gè)體常項(xiàng)；c不曾在Ａ(x)中出現(xiàn)過；Ａ(x)中除x外還有其他自由出現(xiàn)的個(gè)體變項(xiàng)時(shí),不能用此規(guī)則。（3）存在量詞引入規(guī)則（ＥＧ）（4）存在量詞消去規(guī)則（EＩ）證明：(2)EI(3)化簡(jiǎn)(1)UI(4)(5)假言推理(7)(8)合取引入(9)EG例：證明前提引入前提引入(3)化簡(jiǎn)(6)化簡(jiǎn)證明：(2)EI(3)化簡(jiǎn)(1)UI(4)(5)假言推理(7例證明證明：用反證法：設(shè)為附加前提（1）P（2）T（1）E（3）T（2）I（4）T（3）E（5）T（2）I（6）T（5）E（7）ES（4）（8）US（6）（9）T（7）（8）I例證明證明：用反證法：設(shè)為附加前提（1）P（2）T（1（10）（11）（12）（13）T（9）EPUST（10）（12）I矛盾原命題成立（10）（11）（12）（13）T（9）EPUST（1證法2：用CP規(guī)則

（2）T（1）E（3）ES（2）證法2：用CP規(guī)則（2）T（1）E（3）ES（2）下列推理是否嚴(yán)密？例：任何人違反交通規(guī)則，則要受到罰款，因此，如果沒有罰款，則沒有人違反交通規(guī)則。下列推理是否嚴(yán)密？例：任何人違反交通規(guī)則，則要受到罰款，因此一階邏輯等值演算與推理課件分析帶量詞的謂詞公式，在進(jìn)行邏輯推證時(shí)，必須正確使用US,UG,ES,EG這幾個(gè)消去量詞和擴(kuò)張量詞的規(guī)則。在推理過程中，謂詞公式只能應(yīng)用表2-1所列的蘊(yùn)含式和等價(jià)式，除表中所列的代量詞公式外，一般的不能在量詞后面的轄域內(nèi)進(jìn)行蘊(yùn)含推導(dǎo)或等價(jià)變換。如：但在推理中不能作為公式引用，因?yàn)樗戳腥牍酵评肀碇?。根?jù)以上分析：分析帶量詞的謂詞公式，在進(jìn)行邏輯推證時(shí)，必須正確使用US,一階邏輯等值演算與推理課件一階邏輯等值演算與推理課件第五章一階邏輯等值演算與推理主要內(nèi)容：重要的等值式①在有限個(gè)體域內(nèi)消去量詞等值式②量詞否定等值式③量詞轄域收縮與擴(kuò)張等值式④量詞分配等值式基本規(guī)則①置換規(guī)則②換名規(guī)則③代替規(guī)則前束范式與公式的前束范式自然推理系統(tǒng)F第五章一階邏輯等值演算與推理主要內(nèi)容：要求：深刻理解并記住重要等值式，并能熟練地應(yīng)用它們熟練地使用置換規(guī)則、換名規(guī)則、代替規(guī)則準(zhǔn)確地求出給定公式的前束范式正確地使用UI,UG,EG,EI規(guī)則，特別要注意它們之間的關(guān)系對(duì)給定的推理，正確地構(gòu)造出它的證明

要求：一、量詞否定等值式例：設(shè)P(x)：X今天去過操場(chǎng)（1）不是所有人今天去過操場(chǎng)存在一些人今天沒有去過操場(chǎng)（2）不存在一些人今天去過操場(chǎng)所有人今天都沒有去過操場(chǎng)。5.1一階邏輯等值式與置換規(guī)則一、量詞否定等值式例：設(shè)P(x)：X今天去過操場(chǎng)5.1一階證：設(shè)個(gè)體域中的客體變?cè)獮樽C：設(shè)個(gè)體域中的客體變?cè)獮槎?、量詞轄域的擴(kuò)張與收縮等值式二、量詞轄域的擴(kuò)張與收縮等值式例：證明：證：例：證明：證：類似的可以推出：

例如類似的可以推出：例如三、量詞分配等值式例如聯(lián)歡會(huì)上所有人既唱歌又跳舞和所有人唱歌且所有人跳舞。這兩個(gè)語句意義相同。根據(jù)上式亦有：三、量詞分配等值式例如聯(lián)歡會(huì)上所有人既唱歌又跳舞和所有人唱四、多個(gè)量詞的使用對(duì)于甲村所有的人，乙村都有人和他同姓。存在一個(gè)乙村的人，甲村的人和他同姓。四、多個(gè)量詞的使用對(duì)于甲村所有的人，乙村都有人和他同姓。存在全稱量詞與存在量詞在公式中出現(xiàn)的次序，不能隨意更換。具有兩個(gè)量詞的謂詞公式，有如下一些蘊(yùn)含關(guān)系。存在一個(gè)甲村的人，乙村的人都和他同姓。對(duì)于乙村的人，甲村都有人和他同姓。全稱量詞與存在量詞在公式中出現(xiàn)的次序，不能隨意更換。具有兩個(gè)五、量詞分配中的一些推理關(guān)系式這些學(xué)生都聰明或這些學(xué)生都努力這些學(xué)生都聰明或努力。這些學(xué)生都聰明或努力這些學(xué)生都聰明或這些學(xué)生都努力。五、量詞分配中的一些推理關(guān)系式這些學(xué)生都聰明或這些學(xué)生都努力說明:以上五種單個(gè)量詞的謂詞演算式可類似推廣到多個(gè)量詞的情況。類似的有：說明:以上五種單個(gè)量詞的謂詞演算式可類似推類似的有：5.2一階邏輯前束范式前束范式：謂詞公式具有形式：則該公式叫前束范式。其中Ｑi是量詞或，A是不含量詞的謂詞公式。方法：利用換名規(guī)則及代替規(guī)則求前束范式5.2一階邏輯前束范式前束范式：謂詞公式具有形式：方法例:求下列公式的前束范式.１、原式例:求下列公式的前束范式.１、原式一階邏輯等值演算與推理課件４、４、１、全稱量詞消去規(guī)則（UＩ）5.3一階邏輯推理理論x是Ａ(x)中自由出現(xiàn)的個(gè)體變項(xiàng)；y為任意不在Ａ(x)中約束出現(xiàn)的個(gè)體變項(xiàng)；c為任意的個(gè)體常項(xiàng)。2、全稱量詞引入規(guī)則（UG）y在Ａ(y)中自由出現(xiàn)，且y取任何值時(shí)Ａ均為真；取代y的x不能在Ａ(y)中約束出現(xiàn)，否則會(huì)產(chǎn)生錯(cuò)誤。１、全稱量詞消去規(guī)則（UＩ）5.3一階邏輯推理理論x例：證明蘇格拉底的三段論（2）(1)ＵＩ（3）A（S）（4）M（S）證明：A(x):x是一個(gè)人M(x)：x是要死的S:蘇格拉底

（1）前提引入前提引入（2)(3)假言推理例：證明蘇格拉底的三段論（2）(1)ＵＩ（3）A（S）（（3）存在量詞引入規(guī)則（ＥＧ）（4）存在量詞消去規(guī)則（EＩ）c是特定的個(gè)體常項(xiàng)；取代c的x不能已在Ａ(c)中出現(xiàn)過。c是使Ａ為真的特定的個(gè)體常項(xiàng)；c不曾在Ａ(x)中出現(xiàn)過；Ａ(x)中除x外還有其他自由出現(xiàn)的個(gè)體變項(xiàng)時(shí),不能用此規(guī)則。（3）存在量詞引入規(guī)則（ＥＧ）（4）存在量詞消去規(guī)則（EＩ）證明：(2)EI(3)化簡(jiǎn)(1)UI(4)(5)假言推理(7)(8)合取引入(9)EG例：證明前提引入前提引入(3)化簡(jiǎn)(6)化簡(jiǎn)證明：(2)EI(3)化簡(jiǎn)(1)UI(4)(5)假言推理(7例證明證明：用反證法：設(shè)為附加前提（1）P（2）T（1）E（3）T（2）I（4）T（3）E（5）T（2）I（6）T（5）E（7）ES（4）（8）US（6）（9）T（7）（8）I例證明證明：用反證法：設(shè)為附加前提（1）P（2）T（1（10）（11）（12）（13）T（9）EPUST（10）（12）I矛盾原命題成立（10）（11）（12）（13）T（9）EPUST（1證法2：用CP規(guī)則

（2）T（1）E（3）ES（2）證法2：用CP規(guī)則（2）T（1）E（3）ES（2）下列推理是否嚴(yán)密？例：任何人違反交通規(guī)則，則要受到罰款，因此，如果沒有罰款，則沒有人違反交通規(guī)則。下列推理是否嚴(yán)密？例：任何人