我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:小鱼儿玄机1站开奘结果 > 前束范式 >

离散数学的一些概念

归档日期:07-27       文本归类:前束范式      文章编辑:爱尚语录

  一个公式,如果量词均在全式的开头,它们的作用域延伸到整个公式的末尾,则称为是前束范式。例如:(x)(y)(z)(Q(x,y)R(z))的地方是并或交。任何一个谓词公式都有一个前束范式等价。

  n个集合的并集的元素的个数=每个集合元素的个数和-两两集合交+三三集合交+(-1)^n+1n个集合交。

  笛卡儿积是两个集合中所有元素两两相乘,不满足交换律、结合律、满足分配律。

  序偶可以反映集合间元素的关系,对于二元关系F,若<x,y>F,记作xFy。

  那么重要:A,B是任意两个集合,A×B即两个笛卡儿积的任意子集R成为A到B的二元关系(注意是任一子集。个数也同子集总数相同)

  答:集合A上的二元关系与A×A的子集个数相同。若A=n,则A×A=n2, AA的子集个数就有2的n2次方个。所以A上不同的二元关系有2的n2次方个。 例如,集合A={a,b}上的二元关系有16个。

  自反性:A是一个集合,那么对于RA×A,如果有xRx,那么就说R在A上是自反的二元关系。比如:集合上的全域关系、恒等关系、小于等于关系都是自反的二元关系。

  反自反关系:即对于任意xA,均有<x,x>不属于R。比如:小于关系。空关系既是自反的又是非自反的。

  对称性:对于x,yA,那么如果有xRy,yRx,则R是A上对称的二元关系。比如:恒等关系、全域关系。

  等价关系:R包含于A×A,且A不为空集,若R具有自反、对称、传递性,那么R就是等价关系。

  等势: 设A,B为两个集合,若存在从A到B的双射函数,则称A与B是等势的. A  B  双射 f:AB

  12.强连通是双向联通,有向图中任意对顶点之间都相互可达。也就是图中有回路过每个顶点至少一次。

  13.欧拉图是经过图中所有的边且每条边仅经过一次-简单回路。哈密顿图是经过图中所有的点且每个点仅经过一次。

本文链接:http://scrinzoom.com/qianshufanshi/702.html