文档介绍：逻辑模型
浙江大学数学建模基地
§9 逻辑模型
欧几里得在不加证明而被直接采用的一些基本概念和公理的基础上。运用逻辑推理方法得出了一系列的定理、推论,从而建立了完整的欧几里得几何学,这一辉煌成果至今仍然是人类的宝贵财富。
本章介绍的一些模型采用的也是类似的方法。建模者从问题应当具有的某些基本属性出发,运用逻辑推理方法或者导出满足这些基本属性的解来,或者证明在原有观念下问题不可能有解,从而从根本上改变人们对这一问题的看法
§ 几个较为简单的问题
本节将采用逻辑推理方法讨论几个颇为有趣的问题。
例1 在每一次人数不少于6人的聚会中必可找出这样的3人,他们或者彼此均认识或者彼此均不认识。
利用图的方法来描述该问题。将人看成顶点,两人彼此都认识用实线连,否则虚线。
证明:
相识问题(拉姆齐问题)
问题转化为在一个6阶图中必存在实线三角形或虚线三角形。
请大家一起画图证明
υ2
υ1
υ3
υ4
υ6
υ5
υ1
υ2
υ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阶单色完全图。
其他类似可推出的结果:
任一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
7阶2色完全图至少含有4个3阶单色安全图。
18阶2色完全图中必含有4阶单色完全图。
。利用逻辑推理方法,实际上还可获得一大批结果。。
例2 17位学者中每人都和其他人通信讨论3个方向的课题。任意两人间只讨论其中一个方向的课题,则其中必可找出3位学者,他们之间讨论的是同一方向的课题。
奇偶数校验及相关问题
证明:
采用反证法,设,其中p、q互素,则有
p2=2q2。因为2|p2,故2|p。记p=2p1,可得4p12=2q2 ,即
2p12=q2 ,故又有2|q,与p、q 互素矛盾。
例3 证明是无理数。
同样方法可以证明:若m是大于1的素数,n是大于1的整数,则必为无理数。
例4 拟用40块方形瓷砖铺设如下图所示的地面,但商店只有长方形瓷砖,其大小为方形的两块。问购买20块长方形瓷砖后,是否可能不裁开而直接铺好地面?
(a) (b)黑白相间染色。
显然,如长方形瓷砖不裁开,只能用来复盖相邻的两格,故复盖的两格必为一白一黑。
下图(a)中共有21个黑格和19个白格,故不可能直接铺好,下图(b)中黑白格各为20个,大家很容易找到直接铺设的方法。
图(a)
图(b)
例5 设一块m×n的棋盘被若干个形如的板块恰好盖满,试证明m×n必能被8整除。
证明:
显然有4|m×n,故m、n中至少有一个为偶数,不妨
设n为偶数,将棋盘按列黑白相间染色,如下图(a )
所示,由于n为偶数,黑、白列的数目相同,故黑白
格数相同,设各为2k个。
图(a)