逻辑模型 浙江大学数学建模基地.

Presentation on theme: "逻辑模型 浙江大学数学建模基地."— Presentation transcript:

1 逻辑模型 浙江大学数学建模基地

2 §9 逻辑模型 欧几里得在不加证明而被直接采用的一些基本概念和公理的基础上。运用逻辑推理方法得出了一系列的定理、推论，从而建立了完整的欧几里得几何学，这一辉煌成果至今仍然是人类的宝贵财富。 本章介绍的一些模型采用的也是类似的方法。建模者从问题应当具有的某些基本属性出发，运用逻辑推理方法或者导出满足这些基本属性的解来，或者证明在原有观念下问题不可能有解，从而从根本上改变人们对这一问题的看法 § 9.1 几个较为简单的问题 本节将采用逻辑推理方法讨论几个颇为有趣的问题。

3 例1 在每一次人数不少于6人的聚会中必可找出这样的3人，他们或者彼此均认识或者彼此均不认识 。
相识问题（拉姆齐问题）  例1 在每一次人数不少于6人的聚会中必可找出这样的3人，他们或者彼此均认识或者彼此均不认识 。 证明： 请大家一起画图证明 利用图的方法来描述该问题。将人看成顶点，两人彼此都认识用实线连，否则虚线。 问题转化为在一个6阶图中必存在实线三角形或虚线三角形。

4 任取一顶点，不妨υ1 不妨取υ1 υ2 、 υ1 υ3 、 υ1 υ4 实线 与υ1相连的边必然有： 实线条数不小于3或虚线条数不小于3 拉姆齐问题也可这样叙述： 6阶2色完全图中必含有3阶单色完全图。 考察υ2υ3、υ2υ4和υ3υ4 υ2υ3、υ2υ4和υ3υ4只能是虚线 ，否则得证 υ2 υ1 υ3 υ4 υ6 υ5 υ2 υ1 但这样三角形υ2υ3υ4的三边均为虚线 υ3 υ4

5 其他类似可推出的结果 ： 命题11.1 任一6阶2色完全图中至少含有两个3阶单色完全图。
命题11.1 任一6阶2色完全图中至少含有两个3阶单色完全图。 证明：前面证明必存在3阶单色完全图，不妨设υ1υ2υ3 为红色完全图 若υ4υ5υ6也是红色三角形，命题已得证 故至少一边与υ1υ2υ3的边异色，不妨设υ4υ5黑色 υ1υ4、υ2υ4、υ3υ4至少应有两条黑色，不妨设 υ1υ4 、υ2υ4 黑色 υ1υ5、υ2υ5、υ3υ5中至少有两条黑色、故υ1υ5 与υ2υ5中至少有一条是黑色 υ2 υ1 υ3 υ4 υ6 υ5 所以存在第二个3阶单色完全图。

6 命题 阶2色完全图至少含有4个3阶单色安全图。 命题 阶2色完全图中必含有4阶单色完全图。 对拉姆齐问题的认识不能仅仅停留在例11.1的水平上。利用逻辑推理方法，实际上还可获得一大批结果。命题11.2和命题11.3的证明留给大家自己去完成。

7 例2 17位学者中每人都和其他人通信讨论3个方向的课题。任意两人间只讨论其中一个方向的课题，则其中必可找出3位学者，他们之间讨论的是同一方向的课题。

8 同样方法可以证明：若m是大于1的素数，n是大于1的整数，则 必为无理数。
奇偶数校验及相关问题  例3 证明 是无理数。 证明： 采用反证法，设 ，其中p、q互素，则有 p2=2q2。因为2|p2，故2|p。记p=2p1，可得4p12=2q2 ，即 2p12=q2 ，故又有2|q，与p、q 互素矛盾。 同样方法可以证明：若m是大于1的素数，n是大于1的整数，则 必为无理数。

9 例4 拟用40块方形瓷砖铺设如下图所示的地面，但商店只有长方形瓷砖，其大小为方形的两块。问购买20块长方形瓷砖后，是否可能不裁开而直接铺好地面？
解 将图11.4中的(a) (b)黑白相间染色。 显然，如长方形瓷砖不裁开，只能用来复盖相邻的两格，故复盖的两格必为一白一黑。 下图(a)中共有21个黑格和19个白格，故不可能直接铺好，下图(b)中黑白格各为20个，大家很容易找到直接铺设的方法。 图(a) 图(b)

10 例5 设一块m×n的棋盘被若干个形如 的板块恰好盖满，试证明m×n必能被8整除。
证明: 显然有4|m×n，故m、n中至少有一个为偶数，不妨 设n为偶数，将棋盘按列黑白相间染色，如下图 (a ) 所示，由于n为偶数，黑、白列的数目相同，故黑白 格数相同，设各为2k个。 图(a)

11 板块可以有许多种拼凑法，但容易看出，每一板块放 置的方向（称之为定向）只有八种可能的选择，如下 图(b)所示。
容易看出，不论按什么方向放置板块，每一板块均盖住 奇数个黑格（1格或3格），故盖住棋盘的板块必有偶数 个，从而，m×n的棋盘必能被8整除。 图(a) 图(b)

12 例6 拟将一批尺寸为1×2×4的的商品装入尺寸为6×6×6的正方体包装箱中，问是否存在一种装法，使装入的该商品正好充满包装箱。
例6 拟将一批尺寸为1×2×4的的商品装入尺寸为6×6×6的正方体包装箱中，问是否存在一种装法，使装入的该商品正好充满包装箱。 解 将正方体剖分成27个2×2×2的小正方体，并 按下图所示黑白相间地染色。 再将每一2×2×2的小正方体剖分成1×1×1的小正方体。 易见，27个2×2×2的正方体中，有14个是黑的，13个是白的（或13黑14白），故经两次剖分，共计有112个1×1×1的黑色小正方体和104个1×1×1的白色小正方体。 虽然包装箱的体积恰好是商品体积的27倍，但容易看到，不论将商品放置在何处，它都将占据4个黑色和4个白色的1×1×1小正方体的位置，故商品不可能充满包装箱。

13 Dürer魔方（或幻方）问题  德国著名的艺术家Albrecht Dürer( )于1514年曾铸造了一枚名为“Melencotia I”的铜币。令人奇怪的是在这枚铜币的画面上充满了数学符号、数字及几何图形。这里，我们仅研究铜币右上角的数字问题

14 什么是Dürer魔方 所谓的魔方是指由1~n2这n2个正整数按一定规则排列成的一个n行n列的正方形 。n称为此魔方的阶 。 多么奇妙的魔方！
铜币铸造时间：1514年

15 构造魔方是一个古老的数学游戏，起初它还和神灵联系在一起，带有深厚的迷信色彩。传说三千二百多年前（公元前2200年），因治水出名皇帝大禹就构造了三阶魔方（被人们称“洛书”），至今还有人把它当作符咒用于某些迷信活动，大约在十五世纪时，魔方传到了西方，著名的科尼利厄斯·阿格里帕（ ）先后构造出了3~9阶的魔方 。

16 如何构造魔方 奇数（不妨n=5）阶的情况 Step1: 在第一行中间写1
Step2: 每次向右上方移一格依次填按由小到大排列的下一个数，向上移出界时填下一列最后一行的小方格；向右移出界时填第一列上一行的小方格。若下面想填的格已填过数或已达到魔方的右上角时，改填刚才填的格子正下方的小方格，继续Step2直到填完 偶数阶的情况 偶数阶的魔方可以利用奇数阶魔方拼接而成，拉尔夫·斯特雷奇给出了一种拼接的方法 ，这里不作详细介绍 17 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 25 2 9

17 魔方数量随阶数n增长的速度实在是太惊人了！
同阶魔方的个数 五阶 没人知道有多少个！！！ 三阶 个 反射和中心旋转生成8个 四阶 个 反射和中心旋转生成7040个 魔方数量随阶数n增长的速度实在是太惊人了！

18 松驰问题的讨论 允许构成魔方的数取任意实数 问题已发生了实质性变化 n阶魔方A、B，任意实数α、β αA+βB是n阶魔方 允许取实数
具有指定性质的魔方全体构成一个线性空间 注：刻画一个线性空间只需指出它的维数并求出此线性空间的一组基底

19 仍以4阶方阵为例。 令R为行和，C为列和，D为对角线和，S为小方块和 定义0-方：R=C=D=S=0 定义1-方：R=C=D=S=4 R=C=D=S=1的方阵构成的线性空间具有什么样的性质？ 类似于构造n维欧氏空间的标准基，利用0和1我们来构造一些R=C=D=S=1的最简单的方阵。 1在第一行中共有4种取法，为保持上述性质的成立，第二行中的1还有两种取法。当第二行的1也取定后，第三行与第四行的1就完全定位了，故一共可作出8个不同的最简方阵，称之为基本魔方并记之为Q1，… ，Q8

20 显然， Dürer空间（简称D空间）中任何一个元素都可以用Q1，Q2，…，Q8来线性表示，但它们能否构成D空间的一组基呢？
显然， Dürer空间（简称D空间）中任何一个元素都可以用Q1，Q2，…，Q8来线性表示，但它们能否构成D空间的一组基呢？

21 容易看出： Q1，…，Q8这8个基本方是线性相关的，即至少存在一个Qj，可以通过其它7个基本方的线性组合得到。这8个基本方的地位是等同的，故可不妨设j=8。下面验证Q1，Q2，…，Q7是否线性相关。 令： ，即 =

22 = 等号两边对应元素相比较，得r1=r2=…=r7=0， 所以 是线性无关 是D空间的最小生成集。
所以 是线性无关 是D空间的最小生成集。 研究Albrecht Dürer铸造的铜币 令D 即解方程组： = 解得 D=

23 进一步讨论 D空间的子空间和D空间的扩展 （1）要求数字方的所有数都相等 这是集合G={rE,r∈R}， G是以βG={E}为基的一维向量空间 （2）要求列、行及每条主、付对角线上各和都相等。 得到5维泛对角方的向量空间B。例如： 它的基BB为： H=N=R=C=46 其中H为主对角线和，N为付对角线和。

24 （3）要求行和，列和及两条对角线上的元素和相等
得到8维向量空间Q。 基向量QB={Q1，Q2，…，Q7，N0}， 其中Q1，Q2，…，Q7是D的基，而 例如： R=C=D=30

25 （4）仅要求行和与列和相等 得到10维向量空间ψ 基向量ψB={Q1，Q2，…，Q7，N1，N2，N3} 其中Q1，Q2，…，Q7是D的基，而 Botsch（1976年）证明了对于1与16之间的每一个数K，都存在K维的4×4方的向量空间 （5）对数字没任何要求 所有4×4数字方组成16维向量空间M 基向量MB的元素应是标准基（即仅有一个 元素为1，其余元素均为0的阵）。 由上可知，有下式成立 ： （向量空间） （维数）

26 拼方问题  什么是拼方问题 在H.E.Dudeney所写的《Cantebury难题》一书中有一个正方形的图案，这个正方形图案是由一个小长方形和若干个边长各异的小正方形组成的。小长方形的长为 ，宽为 ，要求求出所有正方形的边长和拼接方法。这种拼接过程称为拼方，而这种类型的问题称为拼方问题。 12 8 5 3 2 7 21/4 11/4 5/2 31/4 1

27 受上一问题的启示，加拿大数学家W.T.Tutte, A.Stone等人考虑了如下问题：
怎样的长方形可以剖分成若干个边长各异的小正方形？ 正方形能否剖分成边长各异的小正方形？ 称具有上述性质的长方形为完美长方形，正方形为完美正方形。 波兰数学家Z.Moron 的工作 Z.Moron 在W.T.Tutte等之前已经作出了一个9阶完美长方形，见右图 18 14 4 10 15 7 9 8 1 Z.Moron的完美长方形很接近完美正方形

28 除表示上、下两底边的顶点以外，其余顶点处指入边边长之和应等于指出边边长之和
Tutte等人用来分析Moron给出例子的 奇特方法： 用点表示水平边，用边表示小正方形。边长即小正方形之边长，方向规定由上到下。于是一个剖分好的完美长方形被十分巧妙地转化成了一个有向图网络，见下图 A B C D E F 除表示上、下两底边的顶点以外，其余顶点处指入边边长之和应等于指出边边长之和

29 分析Moron给出的完美长方形，取高为32，则相应电网络中的电流强度xi(i=1,…,9)应满足：
其解为： （x1,x2,x3,x4,x5,x6,x7,x8,x9)=(18,15,4,7,8,1,14,10,9)， 恰为相应小正方形的边长。此外，由x1+x2=33可知，长方形的宽应为33。 若将每边看成一个单位电阻，在给出正极A与负极F之间的电势差后（相当于给出长方形的高），即可求出每条边上的电流强度（等于两顶点间的电势差），而这些数恰好就是小正方形的边长。 由上面说明：假如我们把得到的有向图网络看作电网络，则所述性质恰好就是电学中的基尔霍夫定律。 此外还可看出，解应当是唯一的，因为在给定A、F间的电势差后，各边上的电流强度是唯一确定的。

30 可以不管长方形的剖分，直接根据图的各种情况利用计算机来搜查 前面分析是在对完美长方形作了剖分的前提下作出的，不知道剖分情况怎么办？
几种最简单的情况及寻查过程的简要说明 可以不管长方形的剖分，直接根据图的各种情况利用计算机来搜查 前面分析是在对完美长方形作了剖分的前提下作出的，不知道剖分情况怎么办？ 有向图只有三条边的图见图1。 由x1= x3可知不存在3阶完美长方形。 由四条边组成的有向图可以有两种形式， 见图2中的（a）、(b)，它们均不可能对 应完美长方形。 图1 图2（a） 图2（b）

31 逐阶寻查下去可发现，完美长方形对应的电网络必有以下性质
(性质1) 除两端顶点外，其余各项点的进出边之和至少为3。 (性质2) 电网络不具有对称性。 几点说明： 对一个指定的有向图求相应的完美长方形时，高可以先随意选取一个整数。求出所有小正方形的边长后再将所有数据同乘一个适当的数，使所有有数据均化为整数。显然，变动长方形的高所得到的剖分是相似的，在将相似看作等同的意义下，这种剖分是唯一的。 根据这两条性质，可以发现完美长方形的最小阶数为9，进而可作出各种9阶、10阶、11阶…完美长方形。 当然，随着阶数增大，计算量将按指数增长，因为相应电网络的数目是按指数增长的。 Tutte等人将他们用人工方法得到的完美长方形列成了一个表，其中包括有二百多个完美长方形。1960年，人们用电子计算机求得了9至15阶的全部完美长方形，可其中没有一个是完美正方形！

32 是否存在完美正方形？ 当求得的完美长方形的长恰好等于宽的十分巧合的情况下，我们才能得到一个正方形的剖分。由于计算量过大，在计算机上寻查并未获得成功，最早作出的正方形的剖分是基于非常复杂的图形并用对称性人工凑出来的，它具有69阶。后来又作出了39阶和38阶的完美正方形。接着Tutte等人利用他们获得的完美长方形表又拼凑出一个26阶的完美正方形，它是由一个边长为231的正方形和两个完美长方形拼合而成的，如图所示。 完美长方形 正方形 在此之前，人们对图论还没有多少研究。Tutte等人在引入网络图方法后，十分自然地将兴趣转向了对图论的研究，并因此而获得了许多具有重大意义的开创性结果，直接促进了图论的发展。

33 对偶理论  两个有向图是由同一个完美长方形得出的，它们之间必然存在着某种密切的关系，这种关系被称为对偶关系。在A、F和a、f之间各添加一条线段，对偶关系就显示出来，添线后的网络称为拼方完美长方形的完全网或C-网。每一个C-网将平面分割成若干个区域（称为面），而两个互为对偶的C-网是指具有如下性质的两个C-网：可以把它们画在平面上使任一个C-网的每一面中有且仅有另一个C-网的一个顶点，见图。 A B C D E F a b c d e f 对一个完美长方形也可用垂直线代替水平线，用类似方法作出另一个有向图。所以对一个确定的完美长方形，我们可以获得的两个不同的有向图。 c a b d e f D E A B C F 添加 添加

34 3-连通理论  前面我们已经看到，由几个完美长方形可以拼出一个新的完美长方形。相应地，新网络图与原有的完美长方形的网络之间存在着十分密切的联系。应当看到这种拼合而成的完美长方形是比较特殊的，它们与那些非拼合而成的（基本）完美长方形有着重大的区别，这些区别必然会在图论中反映出来。例如，考察由两个完美长方形拼接成的完美长方形，可以导出下述定义： 定义11.1 一个连通图如可分成两部分，这两部分只有一个公共顶点，且每一部分均含有另一部分所没有的顶点，则称此图为可分离的。不可分离的图称为2-连通图。 定义11.2 一个2-连通图若可被分成两部分，这两部分恰有两个公共顶点，且每一部分均含有另一部分所没有的顶点，则称此图为2-可分离的，2-连通但非2-可分离的图称为3-连通图。 Tutte等人从着迷于一个数学游戏开始，而最终却成了研究图论问题的专家创建了图的对偶理论、3-连通理论等。在他们取得的极其丰硕的研究成果中，人们可以清晰地看到丰富的想象力、敏锐的洞察力和严密的逻辑推理能力得到了巧妙的结合。 可分离图 2-可分离图