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

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