新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『 计算机考研交流 』 → 一道08年北大计算机数学基础真题的证明 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 12136 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 一道08年北大计算机数学基础真题的证明 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     javacap 帅哥哟，离线，有人找我吗？
      
      
      等级：大二(研究汇编)
      文章：23
      积分：241
      门派：XML.ORG.CN
      注册：2007/9/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给javacap发送一个短消息 把javacap加入好友 查看javacap的个人资料 搜索javacap在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看javacap的博客楼主
    发贴心情 一道08年北大计算机数学基础真题的证明

    A是P元对称群。P为素数
    证明。1，A有(P-1)!个P阶元；2，有(P-2)!个P阶子群

    证明：
    1.
    1）任意A中元素都可以表示成不想交轮换的积。
    X=A1*A2...*An;
    这样X的阶为A1,A2...An的最小公分母,其中Ai的阶在2到P之间。
    2）若X的阶为P,且P已知为素数，则由1)中知，X不能分成两个或以上的轮换，若不然则P=LCM(A1，A2，。。。。An)<>P,矛盾！
    3）由2）知X为长度为P的轮换，其个数等价于P个元素排成一圈，不同排列的个数。
    我们固定其中一个，则其他P-1个的任意一个排列可构成一个不同的圈。从而其个数为(p-1)!


    2.
    1）易知P阶子群中的元素不可能有阶为P-1,P-2,P-3,..3,2的元素，从而只能有e和阶为P的元素
    2）任取对称群中阶为P的元素，由其生成的子群阶为P,结合1），我们知，所求的子群只能是由阶为P的元素生成的循环群的个数。
    3）由第一问的证明知，总数有(p-1)!个，考虑由P阶生成元C生成的循环子群，易证C^2,C^3...C^(P-1)都是P阶元，它们生成的循环群显然是同构的。因此，每(P-1)个P阶元生成一个
    同构的P阶子群，从而异构的P的子群的数目为(p-1)!/(p-1)=(p-2)!
    命题得证！


    [此贴子已经被作者于2008-5-22 22:29:07编辑过]

       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/5/22 0:06:00
     
     jason_00 帅哥哟，离线，有人找我吗？金牛座1987-5-14
      
      
      等级：大三(面向对象是个好东东!)
      文章：108
      积分：653
      门派：IEEE.ORG.CN
      注册：2007/8/18

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给jason_00发送一个短消息 把jason_00加入好友 查看jason_00的个人资料 搜索jason_00在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看jason_00的博客第2楼
    发贴心情 
    有几个问题：
    第一问：
    1》X的阶为什么是A1,A2...An的最小公分母？
    2》若X分成两个或以上的轮换，为什么P=LCM(A1，A2，。。。。An)>P？
    第二问：
    再详细点完全看不懂
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/5/22 10:46:00
     
     javacap 帅哥哟，离线，有人找我吗？
      
      
      等级：大二(研究汇编)
      文章：23
      积分：241
      门派：XML.ORG.CN
      注册：2007/9/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给javacap发送一个短消息 把javacap加入好友 查看javacap的个人资料 搜索javacap在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看javacap的博客第3楼
    发贴心情 
    以下是引用jason_00在2008-5-22 10:46:00的发言：
    有几个问题：
    第一问：
    1》X的阶为什么是A1,A2...An的最小公分母？
    2》若X分成两个或以上的轮换，为什么P=LCM(A1，A2，。。。。An)>P？
    第二问：
    再详细点完全看不懂


    1.因为每个长度为K的轮换阶为K，假设A1*A2阶为X,则（A1*A2)^X=e,从而（A1*A2)^X=E
    从而A1^X=A2^(-X),由于A1，A2是不相交，从而必有A1^X=e=A2^X，从而X为|A1|,|A2|的最小公分母
    2.不是>,是不等<>.LCM表示最小公分母，要使P=LCM(A1，A2，。。。。An),是不可能的，因为P是素数，没有因子（除了自己与1)。

    第二其实感觉很详细了，听你这么问，可能自己真的不善于答题，难怪分数出来跟我自己预期差很多.  :-（。当初第一问没很好的证出来。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/5/22 22:28:00
     
     yaoyun229 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(猛啃高等数学)
      文章：21
      积分：191
      门派：XML.ORG.CN
      注册：2008/5/7

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给yaoyun229发送一个短消息 把yaoyun229加入好友 查看yaoyun229的个人资料 搜索yaoyun229在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看yaoyun229的博客第4楼
    发贴心情 
    你有08年计算机的题吗？能不能给我发一份,yaoyun229@163.com谢谢！
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/9/3 22:30:00
     
     cpkug 帅哥哟，离线，有人找我吗？
      
      
      等级：大三暑假(ITELS考了7分!)
      文章：124
      积分：877
      门派：XML.ORG.CN
      注册：2007/7/28

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给cpkug发送一个短消息 把cpkug加入好友 查看cpkug的个人资料 搜索cpkug在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看cpkug的博客第5楼
    发贴心情 
    以下是引用javacap在2008-5-22 0:06:00的发言：
    A是P元对称群。P为素数
    证明。1，A有(P-1)!个P阶元；2，有(P-2)!个P阶子群

    证明：
    1.
    1）任意A中元素都可以表示成不想交轮换的积。
    X=A1*A2...*An;
    这样X的阶为A1,A2...An的最小公分母,其中Ai的阶在2到P之间。
    2）若X的阶为P,且P已知为素数，则由1)中知，X不能分成两个或以上的轮换，若不然则P=LCM(A1，A2，。。。。An)<>P,矛盾！
    3）由2）知X为长度为P的轮换，其个数等价于P个元素排成一圈，不同排列的个数。
    我们固定其中一个，则其他P-1个的任意一个排列可构成一个不同的圈。从而其个数为(p-1)!


    2.
    1）易知P阶子群中的元素不可能有阶为P-1,P-2,P-3,..3,2的元素，从而只能有e和阶为P的元素
    2）任取对称群中阶为P的元素，由其生成的子群阶为P,结合1），我们知，所求的子群只能是由阶为P的元素生成的循环群的个数。
    3）由第一问的证明知，总数有(p-1)!个，考虑由P阶生成元C生成的循环子群，易证C^2,C^3...C^(P-1)都是P阶元，它们生成的循环群显然是同构的。因此，每(P-1)个P阶元生成一个
    同构的P阶子群，从而异构的P的子群的数目为(p-1)!/(p-1)=(p-2)!
    命题得证！





    "3）由2）知知X为长度为P的轮换，其个数等价于P个元素排成一圈，不同排列的个数。
    我们固定其中一个，则其他P-1个的任意一个排列可构成一个不同的圈"
    这样做能保证构造出来的轮换是一个p阶轮换吗？恐怕不行吧，除去那个固定位置的元素，其它位置上的元素若是任意排列肯定会造成一定数量的恒等变换的；所以我个人认为这种办法不行。 这一块也是题目所希望证明的地方。

    另外，
    “
    2.
    1）易知P阶子群中的元素不可能有阶为P-1,P-2,P-3,..3,2的元素，从而只能有e和阶为P的元素
    ”
    这个结论我个人也认为是正确的，希望能看到证明过程，我个人还不能证明出来。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/10/6 0:29:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第6楼
    发贴心情 
    以下是引用cpkug在2008-10-6 0:29:00的发言：
    "3）由2）知知X为长度为P的轮换，其个数等价于P个元素排成一圈，不同排列的个数。
      我们固定其中一个，则其他P-1个的任意一个排列可构成一个不同的圈"
    这样做能保证构造出来的轮换是一个p阶轮换吗？恐怕不行吧，除去那个固定位置的元素，其它位置上的元素若是任意排列肯定会造成一定数量的恒等变换的；所以我个人认为这种办法不行。 这一块也是题目所希望证明的地方。

    另外，
    “
      2.
      1）易知P阶子群中的元素不可能有阶为P-1,P-2,P-3,..3,2的元素，从而只能有e和阶为P的元素
    ”
    这个结论我个人也认为是正确的，希望能看到证明过程，我个人还不能证明出来。


    前面这个构造显然是可以的
    其实我们不妨这样说：令S = { (1, i_2, i_3, ..., i_p) | 其中i_2, i_3,...,i_p为从2到p的某个排列}，那么对于2到p的每一种不同的排列，正好对应一个不同的p-轮换，不会有重复。（反设有重复，即，设f=(1, i_2, i_3, ..., i_p)，g = (1, j_2, j_3, ..., j_p)，其中i_2,...,i_p和j_2,...,j_p是两个不同的排列，但f和g是同一个置换。那么不妨设k为上述两个排列中第一个不同的位，即，i_2=j_2, i_3=j_3, ..., i_{k-1}=j_{k-2}, i_k ≠ j_k，则易见，原先在第i_{k-1}上的元素将被f映射到i_k上，而同样是这个元素，它将被g映射到j_k上，由于i_k ≠ j_k，所以f和g是不同的置换，矛盾）

    后面一个结论是Lagrange定理的直接推论，即：n阶有限群的元素的阶必然整除n。

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/10/6 12:26:00
     
     cpkug 帅哥哟，离线，有人找我吗？
      
      
      等级：大三暑假(ITELS考了7分!)
      文章：124
      积分：877
      门派：XML.ORG.CN
      注册：2007/7/28

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给cpkug发送一个短消息 把cpkug加入好友 查看cpkug的个人资料 搜索cpkug在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看cpkug的博客第7楼
    发贴心情 
    感谢 Logician细心解惑！

    我先是考虑到置换了，就说可能会出现类似下面的情况：
    1 2 3 4 5 ..i (i + 1)...j (j + 1)...(p - 2) (p -1) p
    (                                                                )
    1 3 4 5 6 ..i (i + 2)...j (j + 3)...(p - 1) (p - 2) p

    我把“javacap”的意思理解成在上面的置换表示中，对下面一行的元素，固定一个，其它的作(p - 1)的全排列，那样肯定是会产生不足p阶的置换的；

    不过“javacap”说的是轮换，这样就是另一个意思了，站在了一个非常合适的角度上解答了本题！

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/10/6 23:38:00
     
     cpkug 帅哥哟，离线，有人找我吗？
      
      
      等级：大三暑假(ITELS考了7分!)
      文章：124
      积分：877
      门派：XML.ORG.CN
      注册：2007/7/28

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给cpkug发送一个短消息 把cpkug加入好友 查看cpkug的个人资料 搜索cpkug在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看cpkug的博客第8楼
    发贴心情 
    以下是引用javacap在2008-5-22 0:06:00的发言：

    2）任取对称群中阶为P的元素，由其生成的子群阶为P,结合1），我们知，所求的子群只能是由阶为P的元素生成的循环群的个数。


    [此贴子已经被作者于2008-5-22 22:29:07编辑过]


    “任取对称群中阶为P的元素，由其生成的子群阶为P”，这个结论应该也是对的，觉得不能直接用吧；另外能给出这个结论的证明么？

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/10/8 1:27:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第9楼
    发贴心情 
    以下是引用cpkug在2008-10-8 1:27:00的发言：
    “任取对称群中阶为P的元素，由其生成的子群阶为P”，这个结论应该也是对的，觉得不能直接用吧；另外能给出这个结论的证明么？


    对任意a属于G，|<a>|=|a|，这个是书上有的简单结论。
    建议在认真温习一下书上的定理、例题和推论

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/10/8 11:28:00
     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第10楼
    发贴心情 
    另外，在代数系统这部分，我认为最重要的是掌握和理解关于代数系统的大量基本结论、常见证明思路和证明技巧，只要你确定结论简单而正确，就不用太扣细节了
    集合论部分的重点才是对推理定理的严格运用和对符号细节的关注

    以下是引用cpkug在2008-10-8 1:27:00的发言：

    “任取对称群中阶为P的元素，由其生成的子群阶为P”，这个结论应该也是对的，觉得不能直接用吧；另外能给出这个结论的证明么？


    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/10/8 11:35:00
     
     GoogleAdSense天蝎座1984-10-28
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Google AdSense  访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2026/1/5 3:27:21

    本主题贴数12，分页： [1] [2]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 127.930ms