命題邏輯聯(lián)結(jié)詞完全性證明
——數(shù)學(xué)歸納法的應(yīng)用

曹發(fā)生

（貴州民族大學(xué)民族文化邏輯與認(rèn)知研究中心，貴州 貴陽(yáng) 550025）

1 兩種數(shù)學(xué)歸納法的比較

第一，數(shù)學(xué)歸納法的步驟。

(1)基礎(chǔ)步驟當(dāng)n=1時(shí)，這個(gè)命題為真。(2)歸納步驟假設(shè)當(dāng)n=k時(shí)，這個(gè)命題為真，那么當(dāng)n=k+1時(shí)，這個(gè)命題也為真。

第二，數(shù)學(xué)歸納法的步驟。

(1)基礎(chǔ)步驟當(dāng)n=1時(shí)，這個(gè)命題為真。(2)歸納步驟假設(shè)當(dāng)n=1，…，k時(shí)，這個(gè)命題為真，那么當(dāng)n=k+1時(shí)，這個(gè)命題也為真。

數(shù)學(xué)歸納法的兩個(gè)步驟缺一不可。前一步驟是基礎(chǔ)，后一步驟是核心。歸納步驟中要能表明由前一步得到后一步，環(huán)環(huán)相扣，以至對(duì)每一個(gè)自然數(shù)都能成立。

將第一數(shù)學(xué)歸納法基礎(chǔ)步驟中的“當(dāng)n=1時(shí)，這個(gè)命題為真”，推廣為“當(dāng)n=1時(shí)，這個(gè)命題為真；當(dāng)n=2時(shí)，這個(gè)命題都為真”。此時(shí)歸納步驟中假設(shè)當(dāng)n=k時(shí)，這個(gè)命題都為真，來(lái)證明當(dāng)n=k+1時(shí)，這個(gè)命題也為真。

這就是我們對(duì)第一數(shù)學(xué)歸納法的推廣。下文將說(shuō)明在有些時(shí)候這個(gè)推廣是必要的。

第一，數(shù)學(xué)歸納法基礎(chǔ)步驟中的“當(dāng)n=1時(shí)，這個(gè)命題為真”是要證明的，歸納步驟中假設(shè)當(dāng)n=k時(shí)，這個(gè)命題也為真，來(lái)證明當(dāng)n=k+1時(shí)，這個(gè)命題也為真。而第二數(shù)學(xué)歸納法基礎(chǔ)步驟中的“當(dāng)n=1時(shí)，這個(gè)命題為真”是要證明的。歸納步驟中假設(shè)當(dāng)n=2，…，k時(shí)，這個(gè)命題都為真，來(lái)證明當(dāng)n=k+1時(shí)，這個(gè)命題也為真。

它們之間的區(qū)別在于第一數(shù)學(xué)歸納法假設(shè)步驟中僅僅是“假設(shè)當(dāng)n=k時(shí)，這個(gè)命題為真”。而第二數(shù)學(xué)歸納法假設(shè)步驟中是“假設(shè)當(dāng)n=2，…，k時(shí)，這個(gè)命題都為真”。

2 命題邏輯聯(lián)結(jié)詞的完全性證明

聯(lián)結(jié)詞組是完全的定義為：這組聯(lián)結(jié)詞能夠定義其他所有的邏輯聯(lián)結(jié)詞[5]。

命題集合的歸納定義方式[5]，基礎(chǔ)部分：原子命題屬于命題集合；歸納部分：假設(shè)屬于命題集合，則屬于命題集合。

下面先利用推廣后的第一數(shù)學(xué)歸納法對(duì)聯(lián)結(jié)詞函數(shù)的元的個(gè)數(shù)進(jìn)行歸納證明。

下面再利用第二數(shù)學(xué)歸納法對(duì)聯(lián)結(jié)詞函數(shù)的元的個(gè)數(shù)進(jìn)行歸納證明。

注：用第二數(shù)學(xué)歸納法的歸納步驟中含有“假設(shè)當(dāng)n=2，…，k時(shí)，這個(gè)命題都為真”，而“當(dāng)n=2時(shí)，這個(gè)命題都為真”就是假設(shè)有的條件，這與上面的推廣的第一數(shù)學(xué)歸納法不同，那里是直接證明“當(dāng)n=2時(shí)，這個(gè)命題為真”。所以我們對(duì)第一數(shù)學(xué)歸納法中基礎(chǔ)步驟的推廣是有意義的，因?yàn)橛玫谝粩?shù)學(xué)歸納法又沒(méi)有要求證明“當(dāng)n=2時(shí)，這個(gè)命題為真”，而在證明歸納步驟時(shí)候又需要“當(dāng)n=2時(shí)，這個(gè)命題為真”。

數(shù)學(xué)歸納法可以證明與自然數(shù)n有關(guān)的命題，可是要證明的命題有時(shí)候很難聯(lián)想到與自然數(shù)n有關(guān)。要證明當(dāng)n=2時(shí)命題為真時(shí)，利用其前一步“當(dāng)n=1時(shí)，這個(gè)命題為真”沒(méi)辦法證得，于是可以在數(shù)學(xué)歸納法的基礎(chǔ)步驟中增加當(dāng)n=2時(shí)命題成立具體的證明；本文對(duì)命題邏輯聯(lián)結(jié)詞的完全性用推廣的第一數(shù)學(xué)歸納法和第二數(shù)學(xué)歸納法兩種方法給出證明。