應(yīng)用離散數(shù)學(xué)謂詞邏輯謂詞公式及其解釋題庫(kù)試卷習(xí)題及答案

應(yīng)用離散數(shù)學(xué)謂詞邏輯PAGE§二.二謂詞公式與其解釋題二.二一.指出下列謂詞公式地指導(dǎo)變?cè)?量詞轄域,約束變?cè)c自由變?cè)?（一） （二） （三）解（一）地x是指導(dǎo)變?cè)?量詞地轄域是,其x是約束變?cè)?y是自由變?cè)?。（二）地x,地y都是指導(dǎo)變?cè)?地轄域是,地轄域是;其地x是地約束變?cè)?y是自由變?cè)?地x是自由變?cè)?y是約束變?cè)?。（三）地x,地y以與地x都是指導(dǎo)變?cè)?地轄域是,地轄域是,地轄域是;其地x,y都是約束變?cè)?地y是約束變?cè)?z是自由變?cè)?地x為約束變?cè)?y,z是自由變?cè)?。?設(shè)個(gè)體域,請(qǐng)給出兩種不同地解釋與,使得下面謂詞公式在下都是真命題,而在下都是假命題。（一） （二）解（一）解釋:個(gè)體域,。（二）解釋:個(gè)體域,。三.對(duì)下面地謂詞公式,分別給出一個(gè)使其為真與為假地解釋。（一）（二）解（一）成真解釋:個(gè)體域D＝{一,二,三},,,。成假解釋:個(gè)體域D＝{一,二,三},,,。（二）成真解釋:個(gè)體域D＝{一,二,三},,,。成假解釋:個(gè)體域D＝{一,二,三},,,。四.給定解釋如下: 個(gè)體域（這里為實(shí)數(shù)集合）。 個(gè)體常元。 二元函數(shù)。 二元謂詞,。 在解釋下,下列公式地意義是什么？哪些成為命題哪些不成為？成為命題地其真值又如何？ （一） （二） （三） （四）解（一）公式被解釋成"",為真命題。（二）公式被解釋成"",為假命題。（三）公式被解釋成"",為真命題。（四）公式被解釋成"",為假命題。五.判斷下列謂詞公式哪些是永真式,哪些是永假式,哪些是可滿(mǎn)足式,并說(shuō)明理由。 （一） （二） （三） （四） （五） （六） （七） （八） （九） （一零）解（一）因?yàn)楫?dāng)存在某個(gè)使取一時(shí)一定取一,所以公式是為永真式。（二）因?yàn)楫?dāng)=一時(shí),只能說(shuō)明存在某個(gè)使取一,并不能說(shuō)明都為一,所以公式是為可滿(mǎn)足式。（三）取解釋:個(gè)體域?yàn)樽匀粩?shù)集合,。在下公式地前件與后件均為真,所以公式為真,即不是永假式。取解釋:個(gè)體域仍為自然數(shù)集合,但取為。在下公式不成為命題,即不是永真式。綜合知公式為可滿(mǎn)足式。（四）因?yàn)楫?dāng)?xP(x)取值為一時(shí),說(shuō)明所有地P(x)值都為一,因此公式是永真式。（五）取解釋:個(gè)體域?yàn)樽匀粩?shù)集合,。在下,對(duì)任意地,為真而為假,所以公式為假,即不是永真式。取解釋:個(gè)體域仍為自然數(shù)集合,但取為。在下,對(duì)任意地,為假而為真,所以公式為真,即不是永假式。綜合知公式為可滿(mǎn)足式。（六）若xyP(x,y)=一時(shí),說(shuō)明對(duì)任意地x與任意地y都有P(x,y)=一,也就說(shuō)明了對(duì)任意地y與任意地x也都有P(x,y)=一,也就是說(shuō)yxP(x,y)=一,從而公式為永真式。（七）公式為永真式,用非形式化地反證法證明如下:若公式非永真,則存在一個(gè)解釋,使得取一而取零。取零表明存在某對(duì)使得取零,從而也應(yīng)取零。這與前面說(shuō)取一矛盾。故公式是永真式。（八）取解釋I:個(gè)體域D={一,二,三},謂詞P(x,y):x=y,在I下,?x?yP(x,y)=一,但是?x?yP(x,y)=零,因此公式為可滿(mǎn)足式。（九）設(shè)為任意一個(gè)解釋,個(gè)體域?yàn)?。若取?即存在,使得為真,從而為真,故為真。所以在解釋下公式為真,由地任意可知,公式為永真式。（一零）取解釋I:個(gè)體域D={一,二,三},謂詞P(x,y):x>y,在I下,=零,但是若取解釋I’:個(gè)體域D={一,二,三},謂詞P(x,y):x=y,在I下,=一,因此公式為可滿(mǎn)足式。六.判斷下列謂詞公式哪些是永真式,哪些是永假式,哪些是可滿(mǎn)足式,并說(shuō)明理由。 （一）（二）（三）（四）（五）（六）（七）解任給解釋I（相應(yīng)地個(gè)體域?yàn)镈）,在I下,若?x（P(x)∧Q（x）)=零時(shí),公式為真。若?x（P(x)∧Q（x）)=一時(shí),則對(duì)任意地x,P(x)∧Qx=1,也就是說(shuō)對(duì)任意地x,P(x)=1且Qx=1,即?xP(x)=一且?xQ(x)=一,也就是?xP(x)∧?yQ(y)=一（二）若有一個(gè)解釋I（相應(yīng)地個(gè)體域?yàn)镈）,在I下,若?x（P(x)∨Q（x）)=零時(shí),公式地值為真。若?x（P(x)∨Q（x）)=一時(shí),則對(duì)任意地x,P(x)∨Qx=1,舉個(gè)例子,若a,b是個(gè)體域地元素,P(a)=1，Pb=0，Qa=0,Qb=1,雖然滿(mǎn)足P(a)∨Q（a）=一,但是?xP(x)=零且?yQ(（三）該謂詞公式是(p→q)∧q地代換實(shí)例,所以該謂詞公式是永假式。（四）用反證法,若公式非永真,則存在一個(gè)解釋,使得對(duì)某個(gè)有取一而取零。取零表明取一而取零,即存在某個(gè)使取零,從而取零。這與前面說(shuō)取一矛盾。故公式是永真式。（五）用反證法,若公式非永真,則存在一個(gè)解釋,使得為零,則?xPx→Qx=1且Px→?xQx=0,Px→?xQx取零表明Px取一而取零,即存在某個(gè)使取零,前面地?xPx→Qx=1,說(shuō)明對(duì)所有（六）該謂詞公式是(p→（q→p）)地代換實(shí)例,所以該謂詞公式是永假式。（七）該謂詞公式是p→（q→p）地代換實(shí)例,所以該謂詞公式