§9逻辑模型 欧几里得在不加证明而被直接采用的一些基本概念和 公理的基础上。运用逻辑推理方法得出了一系列的定理 推论,从而建立了完整的欧几里得几何学,这一辉煌成果 至今仍然是人类的宝贵财富。 本章介绍的一些模型采用的也是类似的方法。建模者 从问题应当具有的某些基本属性出发,运用逻辑推理方法 或者导出满足这些基本属性的解来,或者证明在原有观念 下问题不可能有解,从而从根本上改变人们对这一问题的 看法 §9.1几个较为简单的问题 本节将采用逻辑推理方法讨论几个颇为有趣的问题
§9 逻辑模型 欧几里得在不加证明而被直接采用的一些基本概念和 公理的基础上。运用逻辑推理方法得出了一系列的定理、 推论，从而建立了完整的欧几里得几何学，这一辉煌成果 至今仍然是人类的宝贵财富。 本章介绍的一些模型采用的也是类似的方法。建模者 从问题应当具有的某些基本属性出发，运用逻辑推理方法 或者导出满足这些基本属性的解来，或者证明在原有观念 下问题不可能有解，从而从根本上改变人们对这一问题的 看法 § 9.1 几个较为简单的问题 本节将采用逻辑推理方法讨论几个颇为有趣的问题
相识问题(拉姆齐问题) 例1在每一次人数不少于6人的聚会中必可找出 这样的3人,他们或者彼此均认识或者彼此均不 认识。 证明: 请大家一起画图证明 看成顶 问题转化小位,啊图中必存在实线三角 形或虛毙三角形
例1 在每一次人数不少于6人的聚会中必可找出 这样的3人，他们或者彼此均认识或者彼此均不 认识 。 利用图的方法来描述该问题。将人看成顶 点，两人彼此都认识用实线连，否则虚线。 证明： ➢ 相识问题（拉姆齐问题） 问题转化为在一个6阶图中必存在实线三角 形或虚线三角形。 请大家一起画图证明
任取一顶点,不妨U1 与υ相连的边必然有: 实线条数不小于3或虚线条数不小于3 不妨取υ1U2、U13、U1U4实线 考察u(拉姆齐问题也可这样叙述:6 阶2色完全图中必含有3阶单色 0,0 完全图。 但这样三角形3的三边均为虚线 6
υ2 υ1 υ3 υ4 υ6 υ5 υ2 υ1 υ3 υ4 任取一顶点，不妨υ1 考察υ2 υ3、υ2 υ4和υ3 υ4 υ2 υ3、υ2 υ4和υ3 υ4只能是虚线，否则得证 但这样三角形υ2 υ3 υ4的三边均为虚线 不妨取υ1 υ2 、υ1 υ3 、 υ1 υ4 实线 与υ1相连的边必然有： 实线条数不小于3或虚线条数不小于3 拉姆齐问题也可这样叙述： 6 阶2色完全图中必含有3阶单色 完全图
其他类似可推出的结果 命题1.1任-6阶2色完全图中至少含有两个3阶单色完全图。 证明:前面证明必存在3阶单色完全图,不妨设U1U2U3 为红色完全图 着U4U53也是红色三角形,命题已得证 故至少一边与u12U3的边异色,不妨设4黑色 U14U204U3至少应有两条黑色,不妨设 U14v204黑色 0,1 中至少有两条黑色、故 00 )s 与U2中至少有一条是黑色 所以存在第二个3阶单色完全图
其他类似可推出的结果 ： 命题11.1 任一6阶2色完全图中至少含有两个3阶单色完全图。 证明：前面证明必存在3阶单色完全图，不妨设υ1υ2υ3 为红色完全图 υ1 υ5、υ2 υ5、υ3 υ5中至少有两条黑色、故υ1 υ5 与υ2 υ5中至少有一条是黑色 若υ4 υ5 υ6也是红色三角形，命题已得证 故至少一边与υ1 υ2 υ3的边异色，不妨设υ4 υ5黑色 υ1 υ4、υ2 υ4、υ3 υ4至少应有两条黑色，不妨设 υ1 υ4 、υ2 υ4 黑色 所以存在第二个3阶单色完全图。 υ2 υ1 υ3 υ4 υ6 υ5
命题1.27阶2色完全图至少含有4个3阶单色安全图。 命题1.318阶2色完全图中必含有4阶单色完全图。 对拉姆齐问题的认识不能仅仅停留在例 10水平上。利用逻辑推理方法,实 际上还可获得一大批结果。命题11.2和 命题11.3的证明留给大家自己去完成
命题11.2 7阶2色完全图至少含有4个3阶单色安全图。 命题11.3 18阶2色完全图中必含有4阶单色完全图。 对拉姆齐问题的认识不能仅仅停留在例 11.1的水平上。利用逻辑推理方法，实 际上还可获得一大批结果。命题11.2和 命题11.3的证明留给大家自己去完成
例217位学者中每人都和其他人通信讨论3个方向的课题 任意两人间只讨论其中一个方向的课题,则其中必可找出3 位学者,他们之间讨论的是同一方向的课题 证明 将每一学者看成一个顶点,作一个17阶完 全图。按讨论课题的方向对边染色,相同方向染 成同一颜色,得到一个17阶3色完全图。 任取一顶点A,与它相关联的有16条边, 其中必能找出6条相同颜色的边,不妨设A与 U1,…,υ6的连线有相同颜色。连接A和6个 顶点υ1,…,υ6如果这6个顶点间也有这种 颜色的边,则已找到讨论同一方向课题的三位学 者;否则,U1,…,υ6及连接它们的边构成 个6阶2色完全图,由例1,必可从中找到一个 3阶单色完全图,即找出三位讨论同一方向课题 的学者
例2 17位学者中每人都和其他人通信讨论3个方向的课题。 任意两人间只讨论其中一个方向的课题，则其中必可找出3 位学者，他们之间讨论的是同一方向的课题。 证明 将每一学者看成一个顶点，作一个 17 阶完 全图。按讨论课题的方向对边染色，相同方向染 成同一颜色，得到一个 17 阶 3 色完全图。 任取一顶点 A，与它相关联的有 16 条边， 其中必能找出 6 条相同颜色的边，不妨设 A 与 υ1，…，υ6的连线有相同颜色。连接 A 和 6 个 顶点υ1，…，υ6。如果这 6 个顶点间也有这种 颜色的边，则已找到讨论同一方向课题的三位学 者；否则，υ1，…，υ6及连接它们的边构成一 个 6 阶 2 色完全图，由例 1，必可从中找到一个 3 阶单色完全图，即找出三位讨论同一方向课题 的学者
>奇偶数校验及相关问题 例3证明、是无理数 证明: 采用同样方法可以证明:若m是大 于1的素数,n是大于1的整数, 则m必为无理数。 即 2 p1q
➢ 奇偶数校验及相关问题 q p 2 = 证明： 采用反证法，设 ，其中p、q互素，则有 p 2=2q 2 。因为2|p2 ，故2|p。记p=2p1，可得4p1 2=2q 2 ，即 2p1 2=q2 ，故又有2|q，与p、q 互素矛盾。 例3 证明 2 是无理数。 同样方法可以证明：若m是大 于1的素数，n是大于1的整数， 则 必为无理数。 n m
例4拟用40块方形瓷砖铺设如下图所示的地面,但商店只 有长方形瓷砖,其大小为方形的两块。问购买20块长方形瓷 砖后,是否可能不裁开而直接铺好地面? 解将图10a)(b黑白相间染色。 显然,如长方形瓷砖不裁开,只能用来复盖相 邻的两格,故复盖的两格必为一白一黑 下图a)中共有21个黑格和19个白格,故不可能 直接铺好,下图(b中黑白格各为20个,大家很 容易找到直接铺设的方法。 袭 图(b)
例4 拟用40块方形瓷砖铺设如下图所示的地面，但商店只 有长方形瓷砖，其大小为方形的两块。问购买20块长方形瓷 砖后，是否可能不裁开而直接铺好地面？ 解 将图11.4中的(a) (b)黑白相间染色。 显然，如长方形瓷砖不裁开，只能用来复盖相 邻的两格，故复盖的两格必为一白一黑。 下图(a)中共有21个黑格和19个白格，故不可能 直接铺好，下图(b)中黑白格各为20个，大家很 容易找到直接铺设的方法。 图(a) 图(b)
例5设一块mxn的棋盘被若干个形如□的板块恰好盖 满,试证明mxn必能被8整除。 证明: 显然有4mxn,故m、n中至少有一个为偶数,不妨 设n为偶数,将棋盘按列黑白相间染色,如下图(a) 所示,由于n为偶数,黑、白列的数目相同,故黑白 格数相同,设各为2k个。 图(a)
例5 设一块m×n的棋盘被若干个形如 的板块恰好盖 满，试证明m×n必能被8整除。 证明: 显然有4|m×n，故m、n中至少有一个为偶数，不妨 设n为偶数，将棋盘按列黑白相间染色，如下图 (a ) 所示，由于n为偶数，黑、白列的数目相同，故黑白 格数相同，设各为2k个。 图(a)
板块可以有许多种拼凑法,但容易看出,每一板块放 置的方向(称之为定向)只有八种可能的选择,如下 图(b)所示。 容易看出,不论按什么方向放置板块,每一板块均盖住 奇数个黑格(1格或3格),故盖住棋盘的板块必有偶数 个,从而,mxn的棋盘必能被8整除。 图(a) 图(b)
板块可以有许多种拼凑法，但容易看出，每一板块放 置的方向（称之为定向）只有八种可能的选择，如下 图(b)所示。 图(b) 容易看出，不论按什么方向放置板块，每一板块均盖住 奇数个黑格（1格或3格），故盖住棋盘的板块必有偶数 个，从而，m×n的棋盘必能被8整除。 图(a)