吉林大學(xué)2021年9月考試《離散數(shù)學(xué)》作業(yè)考核

1、吉林大學(xué)網(wǎng)絡(luò)教育學(xué)院2020-2021 學(xué)年第二學(xué)期期末考試《離散數(shù)學(xué)》大作業(yè) 學(xué)年第二學(xué)期期末考試《離散數(shù)學(xué)》大作業(yè)學(xué) 生 姓 名 專(zhuān) 業(yè) 層 次 年 級(jí) 學(xué) 號(hào) 學(xué) 習(xí) 中 心 成 績(jī) 年 月 日2) 任意設(shè)公式 H 是 S 的一個(gè)邏輯結(jié)果，H 是一些極大項(xiàng)的合取?，F(xiàn)在要證組成 H 的極

2、大項(xiàng)都在 G 的主合取范式 G”中。反證法：若不然，假設(shè) H 中有一個(gè)極大項(xiàng) mk 不在 G 的主合取范式中。則取使 mk 為0 的解釋 I，可有解釋 I 使 H 取 0 值。而 I 使所有不等于 mk 的極大項(xiàng)都為 1，則可有G 的主合取范式 G’’在 I 下取 1 值，即 G 在 I 下取 1 值，這與 G=>H 矛盾。二 證明題 證明題 (共 1 題 ，總分值 ，總分值 10 10 分 )2. 設(shè) G 是有向圖，其中含一有向

3、路(e1，…，en)，其中 fin(en)=init(e1)，證明：G 不是有向樹(shù)。 （10 分）三 問(wèn)答題 問(wèn)答題 (共 10 10 題 ，總分值 ，總分值 80 80 分 )3. 什么是謂詞邏輯公式？ （8 分）答：由原子公式、聯(lián)結(jié)詞和量詞可構(gòu)成謂詞公式. 命題的符號(hào)化結(jié)果都是謂詞公式.例如“x(F(x)G(x))，$x(F(x)G(x))，“x“y(F(x)F(y)L(x,y)H(x,y))等都是謂詞公式.h 變?cè)c轄域，在謂詞公