重言式的判定-chi.ppt

1、重言式的判定、熊明(篇)、目錄、重言式用真值表來(lái)判定重言式的歸謬代入法，判定重言式、重言式、重言式和矛盾式，一個(gè)式與其中的命題變量取什么真值表無(wú)關(guān)，如果該式本身是真的，就把該式作為重言式(tautology )或一個(gè)式子在其中的命題變量取任何真值，但該式子本身是假的情況下，將該式子稱為矛盾式或恒假式。 例如，重語(yǔ)式： p p (p p )矛盾式： p(pp )、常見(jiàn)的重語(yǔ)式、(pq ) pq (pq ) PPP、常見(jiàn)的重語(yǔ)式、(p q ) pq (p q ) (p q ) (p q )、用真值表來(lái)判定重語(yǔ)式、真值表的作用真值表的結(jié)構(gòu)以式(pq)(pq )為例，決定(1)式中的所有命題變量，并依

2、次列在真值表的第一行。 按照一定的秩序列舉這些命題變量的所有可能的真值情況。 (2)對(duì)于每個(gè)命題變量的真值，從簡(jiǎn)單到復(fù)雜地決定式中的各子式的真值，最后決定原來(lái)的式的真值。f、f、t、t、t、f、t、t、t、t、t、t、t、(3)真值表中，僅列舉命題變量和原來(lái)的式的真值的情況，其他子式的真值的情況可以省略。 使用真值表來(lái)判定重言式的方法：畫(huà)出應(yīng)該判定的公式的真值表。 從表中直接讀取那個(gè)是否是重言式。 /判定(pq)(pq )是重言式嗎？ 畫(huà)(pq)(pq )的真值表：從上表可以判定(pq)(pq )是重言式。 真值表判定的優(yōu)點(diǎn)和缺點(diǎn)，優(yōu)點(diǎn)：缺點(diǎn)：在要判定的公式中命題變量多的情況下，比較麻煩，例如

3、：判定(pqr)(qpr )是否是重言式，歸謬代入法判定重言式、歸謬代入法的思想，真值表判定法在直接“去看”式取命題變量的各種值的情況下，原公式的真理反過(guò)來(lái)說(shuō)，可以尋找有命題變量的取值，使原來(lái)的公式在這個(gè)取值的情況下為假。 實(shí)際上找到命題變量的這個(gè)取值，原來(lái)的公式不是重言式。 如果能證明命題變量的這個(gè)取值不存在，原來(lái)的公式是重言式。 這就是謬誤代入法的思想。 歸謬代入法的思想例子，式的主接續(xù)詞，式的主接續(xù)詞：式形成過(guò)程中使用的最后的接續(xù)詞。 例如，式(pq)(pq )的主連接詞從左數(shù)第一個(gè)式(pq r ) (p r) q的主連接詞是從右數(shù)第一個(gè)，錯(cuò)誤代入法的實(shí)施以(pq)(pq )的判定為例，

4、假設(shè)(pq)(pq )為假，該式的主連接詞的下標(biāo)f表示此情況：(pq ) (p ) 在pq的主連接詞之下標(biāo)記為t，pq的主連接詞之下標(biāo)記為f，表明上述的估計(jì)：(pq)(pq)tf為(pq)(pq )、f、t、f、t、f、f、f，因此，當(dāng)p為t、q為f時(shí)，原式的取法為f 遞歸錯(cuò)誤代入法的實(shí)施，以(pq)(pq )的判定為例，假設(shè)(pq)(pq )為假，在該式的主連接詞的后綴f中，有表示此情況的：(ptq)(ptq)f，由此可知，原式的前件pq為真，后件pq為假。在pq的主連接詞之下標(biāo)記為t，pq的主連接詞之下標(biāo)記為f，表示上述的估計(jì)：(pq)(pq)tf是pq)(pq )、f、t、f、t、t、t

5、、f、f、f，以上的導(dǎo)出，如果假定有p、q的值，則p、q的原始式為假定因此，如果沒(méi)有p、q的取法，就會(huì)假原來(lái)的公式，所以原來(lái)的公式一定是重言式。 從原來(lái)的式子，如果它是假的話，用下面的意義規(guī)則，依次推定原來(lái)的式子式的真值。、歸謬代入法的施行過(guò)程，優(yōu)先使用的語(yǔ)義規(guī)則：AB、f、t、f、AB、t、t、a、t、f、a、f、t，盡可能不使用的語(yǔ)義規(guī)則：AB、t、AB、t、AB、f、f、找出命題變量的真值，假設(shè)原來(lái)的式子如果能證明不存在將原來(lái)的式作為假命題變量的真值表，就可以判定原來(lái)的式不是重言式。 如何證明不存在假原來(lái)的式子的命題變量的真值：假原來(lái)的式子的命題變量的各種真值的情況下，一定有的子式是真的

6、還是假的。 /判定(p qr)(pr)(qr )是重言式嗎？ (p qr)(pr)(qr )、f、t、f，以下，必須按情況分別進(jìn)行研究。 在第一種情況下，子表達(dá)式的qr可以是t或f。 在第二種情況下，子表達(dá)式p qr既可以是t，也可以是f .在第二種情況下，子表達(dá)式p qr可以是t。 如上所述，無(wú)論在哪種情況下，子式都是t和f兩者。 可以判定原來(lái)的公式是重言式。 /判定(pqr)(pq)(pr )是重言式嗎？ 若假定(pqr)(pq)(pr )、f、t、f、式(pqr)(pq)(pr )是假的，則可知其中子式pq是假的，還是其中子式pr是假的。 第一種情況下，根據(jù)以上的分析，設(shè)p為t，q為f，r為t時(shí)，原來(lái)的公