测试1 您的名字 在您的复习练习讲师上刻一个圈 Ishan Christos Grant 影可以使用一张在两面都由影自已写的笔记的85×11”的纸，是不能有其他的信 息源。 计算器是不允许使用的。 您可以假设所有的结果来自博座、笔记，问题集以及复习练习。 在提供的空格处写出您的解答。如果需要更多的空可。连问题一起写在的抵的背围。 保持整洁和写作清晰，能不仅会根据您的答案给分，也根据能表达它们的清晰程度给分。 考试在下午9刘结桌. ·祝您好运！ 问题 分值 得分 计分者 1 20 2 13 3 20 4 15 15 6 15 总分 100 F文件使用"pdfFactory Pro”试用版本创建，fineprint,cn
测试 1 您的名字:_________________________________________ 在您的复习练习讲师上划一个圈 Ishan Christos Grant l 您可以使用一张在两面都由您自己写的笔记的 8.5 × 11’’ 的纸，但是不能有其他的信 息源。 l 计算器是不允许使用的。 l 您可以假设所有的结果来自讲座、笔记、问题集以及复习练习。 l 在提供的空格处写出您的解答。如果需要更多的空间，连问题一起写在的纸的背面。 l 保持整洁和写作清晰。您不仅会根据您的答案给分，也根据您表达它们的清晰程度给分。 l 考试在下午 9:30 结束。 l 祝您好运！ 问题 分值 得分 评分者 1 20 2 15 3 20 4 15 5 15 6 15 总分 100 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
问题10分] (a考电以下命题： R=“对于所有的x∈S,x)道潘Qx).” 对于以下的每个陈述： 如果R蓝涵这个陈述，椰么在一>上画图。 如果R被这个陈述植涵。那么在=上西圈。 :么您可以圈0个，1个或者2个和薄述相邻的箭头。（只图对所有集合S和所有谓司P 和Q成立的面面。) > 对于所有的x∈S,Q)崔涵H), => 0 对于所有的x∈5，Qx)蕴涌Yx: =3 对于所有的xS,N)蕴海Qx => 不存在X∈S,以致于丰代)植涵Qx》: =3 0 猪会飞. Pf文件使用"pdfFactory Pro”试用版本创建w.fineprint,cn
问题 1 [20 分] (a) 考虑以下命题： R = “对于所有的 x∈S， P(x) 蕴涵 Q(x)。” 对于以下的每个陈述： 如果 R 蕴涵这个陈述，那么在 ＝> 上画圈。 如果 R 被这个陈述蕴涵，那么在 <= 猪会飞。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
b)令S是所有人的集合，令Mx,y)是谓问，“x是y的母来”。把这个命题朝译成清瑞的 不涉及到变量的英文句子。 V (y (M(x,y)A M(y,)) “没有两个人中一个人都是另一个人的母彩，”或者更简单的，“没有是它门自已的厚亲的相 母。” (心)使用上面定文的集合S和谓问M翻译以下英文句子为逻辑符号： “每个人有一个母亲。” Vr =g Mf(u.z) PDF文件使用“pdfFactory Pro”试用版本创建，fineprint.cn
(b) 令 S 是所有人的集合，令 M(x，y)是谓词，“x 是 y 的母亲”。把这个命题翻译成清晰的 不涉及到变量的英文句子。 “没有两个人中一个人都是另一个人的母亲。”或者更简单的，“没有是它们自己的母亲的祖 母。” (c) 使用上面定义的集合 S 和谓词 M 翻译以下英文句子为逻辑符号。 “每个人有一个母亲。” PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
问思215分]完成证明，对于n多8的n分的郎资能够使用3和5分郎票生成。 正明：门使川强归纳法， (a令)是的命题，n分的郎资能够使用3和5分都票生成。 基本情况。 解：PH8),V9外和10都为真，既然： 8=5+3 9=3+3+3 10=5+5 (c)归钠步。 解：对于所有的n≥10，我们假设P8),“,P且正明P(n+1),特别的通过假设P(m一2， 我们能形成■一2分的部蜜。增加一个3分郎票，给出n+1分的郎资，因此P(如十1》为真， 因此由强归钠法源理得，对于所有的n≥P)为真。 Pf文件使用"pdfFactory Pro”试用版本创建w.fineprint,cn
问题 2 [15 分] 完成证明，对于 n ≥ 8 的 n 分的邮资能够使用 3 和 5 分邮票生成。 证明：们使用强归纳法。 (a) 令 P(n) 是的命题，n 分的邮资能够使用 3 和 5 分邮票生成。 (b) 基本情况。 解：P(8)，P(9)和 P(10) 都为真，既然： (c) 归纳步。 解：对于所有的 n ≥ 10，我们假设 P(8)，…，P(n)且证明 P(n+1)。特别的通过假设 P(n-2)， 我们能形成 n -2 分的邮资。增加一个 3 分邮票，给出 n +1 分的邮资，因此 P(n＋1)为真。 因此由强归纳法原理得，对于所有的 n≥P(n)为真。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
问题3[20分]】这里是如何“拧”一个无向图的 1.选择不同的顶点，b,c和d,以使包括边a-b和cd且没有边c,d,或 b-d. d 2.到除边c-d和添加边ac和d: C b d )在右边的盒子中，画一个图能通过扭曲包括在左边的图。 ●2 5● 54 PF文件使用"pdfFactory Pro”试用版本创建w.finsprint,n
问题 3 [20 分] 这里是如何“拧”一个无向图的： 1． 选择不同的顶点 a，b，c 和 d，以便图包括边 a –b 和 c—d 且没有边 a-c， a-d，或 b-d。 2． 删除边 c-d 和添加边 a-c 和 a-d： (a) 在右边的盒子中，画一个图能通过扭曲包括在左边的图。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
b)假设G是一个有欧拉回路的无向图。同时，假设G,是一个通过扭曲G获得的，G 是通过扭曲G,张得的。使用归纳法证明每个在这种方式下获得的图有一条欧轮回路。 仅优能参考： ·款2回路是经过在图中的每条边恰好有一次的闭合通路。 ●图是联通的当且仅当在每对顶点之同存在一条路径： ·定理。无向图有欧拉图，当且仅当这个图是联通的且每个项点有俱度。 解：我们使川归纳法。令刊)是G,是款控同路的命题， 基例：对于所有的≥0，我们假设G有欧拉回路且证明G:也有欧拉回路。特别的，我 们说明G,一1有偶数个项点是联通的。 ●在G。中的每个定点有再数度，因为G有欧拉回路。每个在G1中的顶点有同样 的度，除了对项点a的度多了两皮。因此，在G中的每个项点有偶数度。 ·考恩在G+:中的任意顶点u和v.因为G,是联通的，存在u到v的在G中的路径。 如果路径不包括cd,那么同样的路径存在于G+,中。如果路径包括cd,那么在 G1中存在相应的路径，这里。-d被边Ca和d替换。 这个董含着G:也有一条欧拉回路。因此，G对于多有的n≥0也有一条欧拉回路。 特别的，心▣有一条欧粒回路。 FDF文件使用“pdfFactory Pro”试用版本创建，fineprint,cn
(b) 假设 G0 是一个有欧拉回路的无向图。同时，假设 G1 是一个通过扭曲 G0 获得的，G2 是通过扭曲 G1获得的。使用归纳法证明每个在这种方式下获得的图有一条欧拉回路。 仅供您参考： l 欧拉回路是经过在图中的每条边恰好有一次的闭合通路。 l 图是联通的当且仅当在每对顶点之间存在一条路径。 l 定理。无向图有欧拉图，当且仅当这个图是联通的且每个顶点有偶度。 解：我们使用归纳法。令 P(n) 是 Gn是欧拉回路的命题。 基例：对于所有的 n ≥0，我们假设 Gn有欧拉回路且证明 Gn+1也有欧拉回路。特别的，我 们说明 Gn＝1 有偶数个顶点是联通的。 l 在 Gn 中的每个定点有偶数度，因为 Gn 有欧拉回路。每个在 Gn+1 中的顶点有同样 的度，除了对顶点 a 的度多了两度。因此，在 Gn＋1中的每个顶点有偶数度。 l 考虑在 Gn＋1中的任意顶点 u 和 v。因为 Gn是联通的，存在 u 到 v 的在 Gn中的路径。 如果路径不包括 c-d，那么同样的路径存在于 Gn＋1中。如果路径包括 c-d，那么在 Gn+1中存在相应的路径，这里 c-d 被边 c-a 和 a-d 替换。 这个蕴含着 Gn+1 也有一条欧拉回路。因此，Gn 对于多有的 n≥0 也有一条欧拉回路。 特别的，G6042有一条欧拉回路。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
间题4[15分]填空。所有的变量表示整数。不需要解释，但是我们对不正确的回答仅能给 出邻分奖陆分数，如果您说明了您的推理， ()假设x是17的倍数。写出最小的李负整数使得陈述为真。 2x32-6x2714x18- 4z十6 6 (mod 17) 解：知果x是17的信数。那么x三0(md1m。因此。在左边所有涉及到x的项全与0 同余。 (b)现在假设x不是17的倍数。写出最小的单负整数使得这个陈述为真： 2x2-6c17+4z16-4址+6 x+12 (mod 17) 解有F定来，x6三1(mOd17).因北，我能按盟知F推界 2r2-6x7+4r6-+6=2(r6)2-6r(6)+4r6-z+6(mod17 三2-6证+4-4r+6(mod17 =-2x+12(0od17】 =15x+12(m0d17) (C)在方格中写出最小的正整数让藤述为真： 存在整数5和1使阁： s·117+t·153=x 当且仅当： x三0 mod 9 解：回忆一个整登x是可以表示为a和b的组合，当切仪当x是cda。b)的整悬倍， 例如T三0(m0dgCd(a,b)）.在这种情况下，做拉算法给出： gcd(153,117)=gcd(117,36)=gcd(36,9)=9 PF文件使用"pdfFactory Pro”试用版本创建w.fineprint.cn
问题 4 [15 分] 填空。所有的变量表示整数。不需要解释，但是我们对不正确的回答仅能给 出部分奖励分数，如果您说明了您的推理。 (a) 假设 x 是 17 的倍数。写出最小的非负整数使得陈述为真。 解：如果 x 是 17 的倍数，那么 x 0 (mod 17)。因此，在左边所有涉及到 x 的项全与 0 同余。 (b) 现在假设 x 不是 17 的倍数。写出最小的非负整数使得这个陈述为真： 解：有 Fermat 定理， 。因此，我们能按照如下推理： (c ) 在方格中写出最小的正整数让陈述为真： 存在整数 s 和 t 使得： 当且仅当： 解：回忆一个整数 x 是可以表示为 a 和 b 的组合，当切仅当 x 是 gcd(a，b)的整数倍， 例如 。在这种情况下，欧拉算法给出： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
间题515分]令p,q和q是不同的质数。证明存在整数a。b和c: a·(pg)+b.(qr）+c.(rp)=1 (提示：首先考地p网和甲的线性组合。) 解：因为0d网：q平r)-q,存在整数s和：使得： s(pq)+t(gr)=q 现在d(q,p)=1,因此存在整数u和v使得： uq+v(rp)=1 因此 u(s(pq)+t(gr))+v(rp)=(us)(pq)+(ut)(gr)+v(rp)=1 Pf文件使用"pdfFactory Pro”试用版本创建w,fineprint,cn
问题 5 [15 分] 令 p，q 和 q 是不同的质数。证明存在整数 a，b 和 c： (提示：首先考虑 pq 和 qr 的线性组合。) 解：因为 gcd(pq，qr) = q，存在整数 s 和 t 使得： 现在 gcd (q，rp) = 1，因此存在整数 u 和 v 使得： 因此： PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn
同题6个问题15分]在一次鸡比赛的，每个对的鸡u和￥，任一u啄￥或v啄山，但 是不是两个，国王是鸡：以至于对于其鸡V: ·u啄v或者 ·u啄一只鸡w,并且w啄v 定成以下定理的证明。 定理如果鸟e技啄，则e技国王， 证明：令S是c的所有鸡得集合，且令D,是的所有啄c的鸡的集合。情况如下说 明 (提示：应川国王Chicken Theorem于De,) 如果鸡c被啄，则集合D丰空。因此，存在在D,中的鸡之中一次比赛，由国王鸡定理 得存在一位国王。我门将说明愿d实际是原始的比赛的国王。 ·因为它是D的国王，d啄在D的每具鸡直接或被地)， 因为d在，d直接地啄鸡e +d间接地哪在S的每只鸡。因为它啄©，并且e啄S每只鸡. PDF文件使用“pdfFactory Pro”试用版本创建，fineprint,cn
问题 6 个问题[15 分] 在一次鸡比赛的，每个对的鸡 u 和 v，任一 u 啄 v 或 v 啄 u，但 是不是两个。 国王是鸡 u，以至于对于其他鸡 v， • u 啄 v 或者 • u 啄一只鸡 w，并且 w 啄 v。 完成以下定理的证明。 定理 如果鸡 c 被啄，则 c 被国王啄。 证明： 令 Sc是 c 啄的所有鸡得集合，且令 Dc是的所有啄 c 的鸡的集合。 情况如下说 明： (提示： 应用国王 Chicken Theorem 于 Dc。) 如果鸡 c 被啄，则集合 Dc非空。 因此，存在在 Dc中的鸡之中一次比赛，由国王鸡定理 得存在一位国王。 我们将说明那 d 实际是原始的比赛的国王。 •因为它是 Dc的国王，d 啄在 Dc的每只鸡(直接或间接地)。 •因为 d 在 Dc， d 直接地啄鸡 c。 •d 间接地啄在 Sc的每只鸡，因为它啄 c，并且 c 啄 Sc每只鸡。 PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.cn