命題公式分類及等值演算

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

第三頁，共二十九頁，2022年，8月28日關(guān)于合式公式的說明(┐A)、(A∧B)等公式單獨(dú)出現(xiàn)時，外層括號可以省去，寫成┐A、A∧B等。公式中不影響運(yùn)算次序的括號可以省去，

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

(p→q)∧(qr)

(p∧q)∧┐r

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

pq→r

(p→(r→q)

第四頁，共二十九頁，2022年，8月28日定義1.7公式層次

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

(2)稱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，則稱A是k層公式。例如：(┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)

分別為3層和4層公式第五頁，共二十九頁，2022年，8月28日公式的解釋在命題公式中，由于有命題符號的出現(xiàn)，因而真值是不確定的。當(dāng)將公式中出現(xiàn)的全部命題符號都解釋成具體的命題之后，公式就成了真值確定的命題了。例如：(p∨q)→r若p：2是素數(shù)，q：3是偶數(shù)，r：π是無理數(shù)，則p與r被解釋成真命題，q被解釋成假命題，此時公式(p∨q)→r被解釋成：若2是素數(shù)或3是偶數(shù)，則π是無理數(shù)。（真命題）r被解釋為：π是有理數(shù)，則(p∨q)→r被解釋成：若2是素數(shù)或3是偶數(shù)，則π是有理數(shù)。（假命題）第六頁，共二十九頁，2022年，8月28日定義1.8賦值或解釋設(shè)p1,p2,…,pn是出現(xiàn)在公式A中的全部命題變項(xiàng)，給p1,p2,…,pn各指定一個真值，稱為對A的一個賦值或解釋。若指定的一組值使A的真值為1，則稱這組值為A的成真賦值；若使A的真值為0，則稱這組值為A的成假賦值。對含n個命題變項(xiàng)的公式A的賦值情況做如下規(guī)定：

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

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

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

第七頁，共二十九頁，2022年，8月28日賦值舉例在公式(┐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)個命題變項(xiàng)的公式共有2n個不同的賦值。

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

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

說明第九頁，共二十九頁，2022年，8月28日例

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

第十頁，共二十九頁，2022年，8月28日定義1.9重言式、永真式、可滿足式設(shè)A為任一命題公式(1)若A在它的各種賦值下取值均為真,則稱A是重言式或永真式。(2)若A在它的各種賦值下取值均為假,則稱A是矛盾式或永假式。(3)若A不是矛盾式,則稱A是可滿足式。

第十一頁，共二十九頁，2022年，8月28日定義1.9的進(jìn)一步說明A是可滿足式的等價定義是：A至少存在一個成真賦值。重言式一定是可滿足式，但反之不真。因而，若公式A是可滿足式，且它至少存在一個成假賦值，則稱A為非重言式的可滿足式。真值表可用來判斷公式的類型:若真值表最后一列全為1，則公式為重言式。若真值表最后一列全為0，則公式為矛盾式。若真值表最后一列中至少有一個1，則公式為可滿足式。第十二頁，共二十九頁，2022年，8月28日例題例下列各公式均含兩個命題變項(xiàng)p與q，它們中哪些具有相同的真值表?

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

(2)pq (5)┐q∨p

(3)┐(p∧┐q)

第十三頁，共二十九頁，2022年，8月28日例題例下列公式中,哪些具有相同的真值表?

(1)p→q

(2)┐q∨r

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

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

第十四頁，共二十九頁，2022年，8月28日兩公式什么時候代表了同一個命題呢？抽象地看，它們的真假取值完全相同時即代表了相同的命題。設(shè)公式A,B共同含有n個命題變項(xiàng)，若A與B有相同的真值表，則說明在2n個賦值的每個賦值下，A與B的真值都相同。于是等價式AB應(yīng)為重言式。

第十五頁，共二十九頁，2022年，8月28日等值的定義及說明定義1.10設(shè)A,B是兩個命題公式，若A,B構(gòu)成的等價式AB為重言式，則稱A與B是等值的，記作AB。

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

p→q(┐p∨q)∨(┐r∧r)用真值表可以驗(yàn)證兩個公式是否等值。第十六頁，共二十九頁，2022年，8月28日例題例判斷下面兩個公式是否等值

┐(p∨q)與┐p∧┐q解答說明在用真值表法判斷AB是否為重言式時，真值表的最后一列可以省略。等值第十七頁，共二十九頁，2022年，8月28日例題例判斷下列各組公式是否等值

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

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

解答等值不等值第十八頁，共二十九頁，2022年，8月28日常用的等值式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)

（∨對∧的分配律）

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

（∧對∨的分配律）6.德·摩根律

┐(A∨B)┐A∧┐B

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

A∨(A∧B)A，

A∧(A∨B)A

第十九頁，共二十九頁，2022年，8月28日

8.零律

A∨11,A∧009.同一律

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

A∨┐A111.矛盾律

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

A→B┐A∨B13.等價等值式

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

A→B┐B→┐A15.等價否定等值式

AB┐A┐B16.歸謬論

(A→B)∧(A→┐B)┐A第二十頁，共二十九頁，2022年，8月28日等值演算與置換規(guī)則每個等值式模式都給出了無窮多個同類型的具體的等值式。

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

取A=p，B=q時，得等值式p→q┐p∨q

取A=p∨q∨r，B=p∧q時，得等值式

(p∨q∨r)→(p∧q)┐(p∨q∨r)∨(p∧q)第二十一頁，共二十九頁，2022年，8月28日這些具體的等值式都被稱為原來的等值式模式的代入實(shí)例。由已知的等值式推演出另外一些等值式的過程為等值演算。置換規(guī)則設(shè)Φ(A)是含公式A的命題公式，Φ(B)是用公式B置換了Φ(A)中所有的A后得到的命題公式，若BA，則Φ(B)Φ(A)。第二十二頁，共二十九頁，2022年，8月28日關(guān)于等值演算的說明等值演算的基礎(chǔ)等值關(guān)系的性質(zhì)：

自反性：AA。

對稱性：若AB，則BA。

傳遞性：若AB且BC，則AC?；镜牡戎凳街脫Q規(guī)則等值演算的應(yīng)用證明兩個公式等值判斷公式類型解判定問題第二十三頁，共二十九頁，2022年，8月28日等值演算的應(yīng)用舉例證明兩個公式等值

(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ī)則）說明也可以從右邊開始演算因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫出熟練后，基本等值式也可以不寫出通常不用等值演算直接證明兩個公式不等值解答第二十四頁，共二十九頁，2022年，8月28日例用等值演算法驗(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)含等值式)解答第二十五頁，共二十九頁，2022年，8月28日例

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

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

方法三、通過等值演算化成容易觀察真值的情況，再進(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的成真賦值。