命題公式分類(lèi)及等值演算

命題公式分類(lèi)及等值演算第1頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月1.2命題公式及其賦值簡(jiǎn)單命題是真值唯一確定的命題邏輯中最基本的研究單位，所以也稱(chēng)簡(jiǎn)單命題為命題常項(xiàng)或命題常元。用p,q,r,…等小寫(xiě)字母表示命題常項(xiàng)。稱(chēng)真值可以變化的陳述句為命題變項(xiàng)或命題變?cè)?。也用p,q,r,…表示命題變項(xiàng)。當(dāng)p,q,r,…表示命題變項(xiàng)時(shí)，它們就成了取值0或1的變項(xiàng)，因而命題變項(xiàng)已不是命題。這樣一來(lái)，p,q,r,…既可以表示命題常項(xiàng)，也可以表示命題變項(xiàng)。在使用中，需要由上下文確定它們表示的是常項(xiàng)還是變項(xiàng)。將命題常項(xiàng)或命題變項(xiàng)用聯(lián)結(jié)詞和圓括號(hào)按一定的邏輯關(guān)系聯(lián)結(jié)起來(lái)的符號(hào)串稱(chēng)為合式公式或命題公式。第2頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月定義1.6合式公式(1)單個(gè)命題常項(xiàng)或命題變項(xiàng)是合式公式，并稱(chēng)為原子命題公式。(2)若A是合式公式，則(┐A)也是合式公式。(3)若A，B是合式公式，則(A∧B)，(A∨B)，(A→B)，(AB)也是合式公式。(4)只有有限次地應(yīng)用(1)～(3)組成的符號(hào)串才是合式公式。合式公式也稱(chēng)為命題公式或命題形式，并簡(jiǎn)稱(chēng)為公式。設(shè)A為合式公式，B為A中一部分，若B也是合式公式，則稱(chēng)B為A的子公式。

第3頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月關(guān)于合式公式的說(shuō)明(┐A)、(A∧B)等公式單獨(dú)出現(xiàn)時(shí)，外層括號(hào)可以省去，寫(xiě)成┐A、A∧B等。公式中不影響運(yùn)算次序的括號(hào)可以省去，

如公式(p∨q)∨(┐r)可以寫(xiě)成p∨q∨┐r。合式公式的例子：

(p→q)∧(qr)

(p∧q)∧┐r

p∧(q∧┐r)不是合式公式的例子

pq→r

(p→(r→q)

第4頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月定義1.7公式層次

(1)若公式A是單個(gè)命題（常項(xiàng)或變項(xiàng)），則稱(chēng)A為0層合式。

(2)稱(chēng)A是n+1(n≥0)層公式是指下面情況之一：

(a)A＝┐B，B是n層公式；

(b)A＝B∧C，其中B,C分別為i層和j層公式，且n=max(i,j)；

(c)A＝B∨C，其中B,C的層次及n同(b)；

(d)A＝B→C，其中B,C的層次及n同(b)；

(e)A＝BC，其中B,C的層次及n同(b)。

(3)若公式A的層次為k，則稱(chēng)A是k層公式。例如：(┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)

分別為3層和4層公式第5頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月公式的解釋在命題公式中，由于有命題符號(hào)的出現(xiàn)，因而真值是不確定的。當(dāng)將公式中出現(xiàn)的全部命題符號(hào)都解釋成具體的命題之后，公式就成了真值確定的命題了。例如：(p∨q)→r若p：2是素?cái)?shù)，q：3是偶數(shù)，r：π是無(wú)理數(shù)，則p與r被解釋成真命題，q被解釋成假命題，此時(shí)公式(p∨q)→r被解釋成：若2是素?cái)?shù)或3是偶數(shù)，則π是無(wú)理數(shù)。（真命題）r被解釋為：π是有理數(shù)，則(p∨q)→r被解釋成：若2是素?cái)?shù)或3是偶數(shù)，則π是有理數(shù)。（假命題）第6頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月定義1.8賦值或解釋設(shè)p1,p2,…,pn是出現(xiàn)在公式A中的全部命題變項(xiàng)，給p1,p2,…,pn各指定一個(gè)真值，稱(chēng)為對(duì)A的一個(gè)賦值或解釋。若指定的一組值使A的真值為1，則稱(chēng)這組值為A的成真賦值；若使A的真值為0，則稱(chēng)這組值為A的成假賦值。對(duì)含n個(gè)命題變項(xiàng)的公式A的賦值情況做如下規(guī)定：

(1)若A中出現(xiàn)的命題符號(hào)為p1,p2,…,pn，給定A的賦值α1α2,…,αn

是指p1＝α1，p2＝α2,…，pn＝αn。

(2)若A中出現(xiàn)的命題符號(hào)為p,q,r...,給定A的賦值α1,α2,…,αn是指p＝α1，q＝α2,…，最后一個(gè)字母賦值αn。上述αi取值為0或1，i＝1,2,…,n。

第7頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月賦值舉例在公式(┐p1∧┐p2∧┐p3)∨(p1∧p2)中，

000(p1＝0，p2＝0，p3＝0)，

110(p1＝1，p2＝1，p3＝0)都是成真賦值，

001(p1＝0，p2＝0，p3＝1)，

011(p1＝0，p2＝1，p3＝1)都是成假賦值。在(p∧┐q)→r中，

011(p1＝0，p2＝1，p3＝1)為成真賦值，

100(p1＝1，p2＝0，p3＝0)為成假賦值。重要結(jié)論：

含n(n≥1)個(gè)命題變項(xiàng)的公式共有2n個(gè)不同的賦值。

第8頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月真值表將命題公式A在所有賦值下取值情況列成表，稱(chēng)作A的真值表。構(gòu)造真值表的具體步驟如下：(1)找出公式中所含的全體命題變項(xiàng)p1,p2,…,pn(若無(wú)下角標(biāo)就按字典順序排列)，列出2n個(gè)賦值。本書(shū)規(guī)定，賦值從00…0開(kāi)始，然后按二進(jìn)制加法依次寫(xiě)出各賦值，直到11…1為止。(2)按從低到高的順序?qū)懗龉降母鱾€(gè)層次。(3)對(duì)應(yīng)各個(gè)賦值計(jì)算出各層次的真值，直到最后計(jì)算出公式的真值。

公式A與B具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考慮構(gòu)造真值表的中間過(guò)程。

說(shuō)明第9頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月例

求下列公式的真值表，并求成真賦值和成假賦值。(1)(┐p∧q)→┐r(2)(p∧┐p)(q∧┐q)(3)┐(p→q)∧q∧r

第10頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月定義1.9重言式、永真式、可滿(mǎn)足式設(shè)A為任一命題公式(1)若A在它的各種賦值下取值均為真,則稱(chēng)A是重言式或永真式。(2)若A在它的各種賦值下取值均為假,則稱(chēng)A是矛盾式或永假式。(3)若A不是矛盾式,則稱(chēng)A是可滿(mǎn)足式。

第11頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月定義1.9的進(jìn)一步說(shuō)明A是可滿(mǎn)足式的等價(jià)定義是：A至少存在一個(gè)成真賦值。重言式一定是可滿(mǎn)足式，但反之不真。因而，若公式A是可滿(mǎn)足式，且它至少存在一個(gè)成假賦值，則稱(chēng)A為非重言式的可滿(mǎn)足式。真值表可用來(lái)判斷公式的類(lèi)型:若真值表最后一列全為1，則公式為重言式。若真值表最后一列全為0，則公式為矛盾式。若真值表最后一列中至少有一個(gè)1，則公式為可滿(mǎn)足式。第12頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月例題例下列各公式均含兩個(gè)命題變項(xiàng)p與q，它們中哪些具有相同的真值表?

(1)p→q (4)(p→q)∧(q→p)

(2)pq (5)┐q∨p

(3)┐(p∧┐q)

第13頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月例題例下列公式中,哪些具有相同的真值表?

(1)p→q

(2)┐q∨r

(3)(┐p∨q)∧((p∧r)→p)

(4)(q→r)∧(p→p)

第14頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月兩公式什么時(shí)候代表了同一個(gè)命題呢？抽象地看，它們的真假取值完全相同時(shí)即代表了相同的命題。設(shè)公式A,B共同含有n個(gè)命題變項(xiàng)，若A與B有相同的真值表，則說(shuō)明在2n個(gè)賦值的每個(gè)賦值下，A與B的真值都相同。于是等價(jià)式AB應(yīng)為重言式。第15頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月等值的定義及說(shuō)明定義1.10設(shè)A,B是兩個(gè)命題公式，若A,B構(gòu)成的等價(jià)式AB為重言式，則稱(chēng)A與B是等值的，記作AB。

說(shuō)明在A(yíng)或B中命題變項(xiàng)可能不同。

p→q(┐p∨q)∨(┐r∧r)用真值表可以驗(yàn)證兩個(gè)公式是否等值。第16頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月例題例判斷下面兩個(gè)公式是否等值

┐(p∨q)與┐p∧┐q解答說(shuō)明在用真值表法判斷AB是否為重言式時(shí)，真值表的最后一列可以省略。等值第17頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月例題例判斷下列各組公式是否等值

(1)p→(q→r)與(p∧q)→r

(2)(p→q)→r與(p∧q)→r

解答等值不等值第18頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月常用的等值式1.雙重否定律 A┐┐A2.冪等律 AA∨A, AA∧A3.交換律 A∨BB∨A， A∧BB∧A4.結(jié)合律 (A∨B)∨CA∨(B∨C)

(A∧B)∧CA∧(B∧C)5.分配律

A∨(B∧C)(A∨B)∧(A∨C)

（∨對(duì)∧的分配律）

A∧(B∨C)(A∧B)∨(A∧C)

（∧對(duì)∨的分配律）6.德·摩根律

┐(A∨B)┐A∧┐B

┐(A∧B)┐A∨┐B7.吸收律

A∨(A∧B)A，

A∧(A∨B)A

第19頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月

8.零律

A∨11,A∧009.同一律

A∨0A，A∧1A10.排中律

A∨┐A111.矛盾律

A∧┐A012.蘊(yùn)涵等值式

A→B┐A∨B13.等價(jià)等值式

AB(A→B)∧(B→A)14.假言易位

A→B┐B→┐A15.等價(jià)否定等值式

AB┐A┐B16.歸謬論

(A→B)∧(A→┐B)┐A第20頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月等值演算與置換規(guī)則每個(gè)等值式模式都給出了無(wú)窮多個(gè)同類(lèi)型的具體的等值式。

例：在蘊(yùn)涵等值式A→B┐A∨B中，其中A,B,C可以代表任意的公式，例如

取A=p，B=q時(shí)，得等值式p→q┐p∨q

取A=p∨q∨r，B=p∧q時(shí)，得等值式

(p∨q∨r)→(p∧q)┐(p∨q∨r)∨(p∧q)第21頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月這些具體的等值式都被稱(chēng)為原來(lái)的等值式模式的代入實(shí)例。由已知的等值式推演出另外一些等值式的過(guò)程為等值演算。置換規(guī)則設(shè)Φ(A)是含公式A的命題公式，Φ(B)是用公式B置換了Φ(A)中所有的A后得到的命題公式，若BA，則Φ(B)Φ(A)。第22頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月關(guān)于等值演算的說(shuō)明等值演算的基礎(chǔ)等值關(guān)系的性質(zhì)：

自反性：AA。

對(duì)稱(chēng)性：若AB，則BA。

傳遞性：若AB且BC，則AC?；镜牡戎凳街脫Q規(guī)則等值演算的應(yīng)用證明兩個(gè)公式等值判斷公式類(lèi)型解判定問(wèn)題第23頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月等值演算的應(yīng)用舉例證明兩個(gè)公式等值

(p→q)→r(p∨r)∧(┐q∨r)(p→q)→r(┐p∨q)→r

（蘊(yùn)含等值式、置換規(guī)則）

┐(┐p∨q)∨r （蘊(yùn)含等值式、置換規(guī)則）(p∧┐q)∨r

（德摩根律、置換規(guī)則）(p∨r)∧(┐q∨r) （分配律、置換規(guī)則）說(shuō)明也可以從右邊開(kāi)始演算因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫(xiě)出熟練后，基本等值式也可以不寫(xiě)出通常不用等值演算直接證明兩個(gè)公式不等值解答第24頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月例用等值演算法驗(yàn)證等值式

(p∨q)→r(p→r)∧(q→r)(p→r)∧(q→r)

(┐p∨r)∧(┐q∨r) (蘊(yùn)含等值式)(┐p∧┐q)∨r (分配律) ┐(p∨q)∨r (德摩根律) (p∨q)→r (蘊(yùn)含等值式)解答第25頁(yè)，課件共29頁(yè)，創(chuàng)作于2023年2月例

證明：(p→q)→r與p→(q→r)不等值方法一、真值表法。

方法二、觀(guān)察法。易知，010是(p→q)→r的成假賦值，而010是p→(q→r)的成真賦值，所以原不等值式成立。

方法三、通過(guò)等值演算化成容易觀(guān)察真值的情況，再進(jìn)行判斷。

A=(p→q)→r(┐p∨q)→r

（蘊(yùn)涵等值式）

┐(┐p∨q)∨r （蘊(yùn)涵等值式）

(p∧┐q)∨r

（德摩根律）

B=p→(q→r)┐p∨(┐q∨r)

（蘊(yùn)涵等值式） ┐p∨┐q∨r

（結(jié)合律）

000，010是A的成假賦值，而它們是B的成真賦值