複製鏈接
請複製以下鏈接發送給好友

簡單合取式

鎖定
簡單合取式是一類合取式,它含有一個變元及其否定的合取式。
命題變項及其否定統稱作文字。僅有有限個文字構成的析取式稱作簡單析取式。僅有有限個文字構成的合取式稱作簡單合取式。
中文名
簡單合取式
外文名
simple conjunctive formula

目錄

簡單合取式定義

p,┐q等為一個文字構成簡單析取式,p∨┐p,┐p∨q等為2個文字構成的簡單析取式,┐p∨┐q∨r, p∨┐q∨r等為3個文字構成的簡單析取式。
┐p,q等為一個文字構成的簡單合取式,┐p∧p,p∧┐q等為2個文字構成的簡單合取式,p∧q∧┐r, ┐p∧p∧q等為3個文字構成的簡單合取式。
應該注意,一個文字既是簡單析取式,又是簡單合取式。為方便起見,有時用A1,A2,…,As表示s個簡單析取式或s個簡單合取式。
簡單合取式的重要特點是它的成真指派很容易找到,且它的永假性也容易判定一個簡單合取式是永假的,當且僅當它至少含一個變元及其否定 [1] 

簡單合取式定理與證明

(1)一個簡單析取式重言式當且僅當它同時含某個命題變項及它的否定式。
(2)一個簡單合取式是矛盾式當且僅當它同時含有某個命題變項及它的否定式。
證明:設Ai是含n個文字的簡單析取式,若Ai中既含有某個命題變項pj,又含有它的否定式┐pj,由交換律、排中律和零律可知,Ai為重言式。反之,若Ai為重言式,則它必同時含某個命題變項及它的否定式,否則,若將Ai中的不帶否定號的命題變項都取0,帶否定號的命題變項都取1,此賦值為Ai的成假賦值,這與Ai是重言式相矛盾。類似的討論可知,若Ai是含n個命題變項的簡單合取式,且Ai為矛盾式,則Ai中必同時含有某個命題變項及它的否定式,反之亦然。
如:p∨┐p,p∨┐p∨r都是重言式。 ┐p∨q,┐p∨┐q∨r都不是重言式 [1] 
參考資料
  • 1.    屈婉玲,耿素雲,張立昂.離散數學:高等教育出版社,2008