命題邏輯(數(shù)據(jù)庫(kù))

時(shí)間：2022-11-01 20:30:01 | 來(lái)源：信息時(shí)代

時(shí)間：2022-11-01 20:30:01 來(lái)源：信息時(shí)代

    命題邏輯 : 以命題為研究對(duì)象,研究基于命題的符號(hào),邏輯體系及推理規(guī)律。命題邏輯是數(shù)理邏輯中研究最早也是最成熟的一門學(xué)科,對(duì)它的研究始于19世紀(jì),而至20世紀(jì)初已趨成熟,它是數(shù)理邏輯的基礎(chǔ),它的成果廣泛應(yīng)用于計(jì)算機(jī)及數(shù)據(jù)庫(kù)領(lǐng)域中。
1. 命題
命題邏輯的基礎(chǔ)是命題。凡能分辨真假的語(yǔ)句稱命題。它可用P、Q、R等表示,而其中真假分別可用T、F表示。
2. 原子命題
凡不能進(jìn)一步分解成更簡(jiǎn)單的命題稱原子命題。
3.命題聯(lián)結(jié)詞
命題間可用命題聯(lián)結(jié)詞相連,常用的有五個(gè)聯(lián)系詞, 它們是:⌝(否定)、 ∧(并且、合取)、 ∨(或者、析取)、→(蘊(yùn)涵)及↔(等價(jià)), 它們可用表1和表2中的真值表示。

表1 命題聯(lián)結(jié)詞否定的真值表

P	P
T F	F T

表2 命題聯(lián)結(jié)詞并且、或者、蘊(yùn)涵及等價(jià)的真值表

P	Q	P∧Q	P∨Q	P→Q	P↔Q
T T F F	T F T F	T F F F	T T T F	T F T T	T F F T

4. 公式
由命題及命題聯(lián)結(jié)詞可組成公式,公式組成規(guī)則如下:
(1)原子命題是公式。
(2)如P、 Q為公式, 則P、(P∧Q)、(P∨Q)、(P→Q)、(P↔Q)為公式。
(3)公式由且僅由有限次使用(1)、(2)而得。
5. 范式
由于命題邏輯公式結(jié)構(gòu)混亂不易實(shí)際使用,因此一般采用具統(tǒng)一結(jié)構(gòu)的范式,它們是:
(1)特異析取范式: 是一種析取式,其每個(gè)析取項(xiàng)是一個(gè)合取式,在合取式中公式的所有命題變?cè)霈F(xiàn),它或以命題變?cè)蛞云浞穸ㄐ问匠霈F(xiàn)且僅出現(xiàn)一次。
(2)特異合取范式: 是一種合取式,其每個(gè)合取項(xiàng)是一個(gè)析取式,在析取式中公式的所有命題變?cè)霈F(xiàn),它或以命題變?cè)蛞云浞穸ㄐ问匠霈F(xiàn)且僅出現(xiàn)一次。
6. 重言式
一公式對(duì)其所有指派均取值為真則稱該公式為重言式。
7.命題演算
命題邏輯的形式系統(tǒng)稱命題演算,有關(guān)形式系統(tǒng)的介紹可見參考文獻(xiàn)[1]。
8. 公理系統(tǒng)
在命題演算中取一些重言式為公理,并規(guī)定一些推理規(guī)則組成一個(gè)公理系統(tǒng),它可以推出所有的重言式,命題邏輯中常用的推理規(guī)則有分離規(guī)則:P→Q, P⊦Q, 該規(guī)則表示如P→Q, P為重言式必可推出Q為重言式。
9.一個(gè)典型的公理系統(tǒng)
命題演算中可以有很多個(gè)公理系統(tǒng),現(xiàn)介紹一個(gè)典型的公理系統(tǒng)。
(1)系統(tǒng)的組成部分:
基本符號(hào):①命題: P,Q,R,…;②聯(lián)結(jié)詞:, ∧, ∨,→,↔;③括號(hào): (, )。
公式: ①命題是公式; ②如P、Q是公式,則(P)、(P∨Q)、(P∧Q)、(P→Q)、(P↔Q)是公式;③公式由且僅由有限次使用前面的①、②而得。
(2)系統(tǒng)的推理部分:
公理: 如P、Q、R為公式,則有下述的公理:
P→P;
(P→(Q→R))→(Q→(P→R));
(P→Q)→((Q→R)→(P→R));
(P→(P→Q))→(P→Q);
(P↔Q)→(P→Q);
(P↔Q)→(Q→P);
(P→Q)∧(Q→P)→(P↔Q));
P∧Q→Q;
P∧Q→P;
P→(Q→P∧Q);
P→P∨Q;
Q→P∨Q;
(Q→P)→((R→P)→(Q∨R→P));
(P→Q)→(Q→P);
P→P。
推理規(guī)則: 分離規(guī)則:P→Q, P⊦Q。
證明(過(guò)程)與定理:證明(過(guò)程)給出了公理系統(tǒng)中定理生成的過(guò)程,它是一個(gè)公式序列“P₁,P₂,…,P_n”,其中,每個(gè)P_i(i=1,2,…,n)必須滿足下列條件之一:①P_i是公理;②P_i是由P_k、P_r、(k,r<i)施行分離規(guī)則而得; ③P_n＝Q即為定理。
可以證明該公理系統(tǒng)是不矛盾的、完全的,但是是不獨(dú)立的。