离散数学的问题

发布网友 发布时间：2022-05-05 09:28

我来回答

共3个回答

热心网友 时间：2022-06-27 06:38

用真值表法看
你命题有多少个变元
那就知道有多少个
极小项
极大项
所以例如
你的是
永真式
那主析取范式
就是所有极小项析取
反之
不用说了吧
还有定理：任何公式都有与之等价的主析取范式和主合取范式
我小学没毕业
不知道说得对或者错
希望对你有用吧

热心网友 时间：2022-06-27 06:39

图论嘛。。。自己翻书啦

热心网友 时间：2022-06-27 06:39

证明 将这n个人作为n个结点，如果某两个人认识，则这两个人对应的结点之间存在一条边，这样就得到一个具有n个结点的无向图，此时需证明的是，当n>=3时该图存在一个哈密顿路，n>=4时，该图存在一个哈密顿回路，即该图是哈密顿图，下面给出证明。
首先证明当n>=3时该图存在一个哈密顿路。
设u,v是任意两个结点，由本题题意(任何2个人合起来认识其余的n-2个人)可知，deg(u)+deg(v)>=n-2，下面需证明deg(u)+deg(v)>=n-1，否则如果deg(u)+deg(v)=n-2，分下面两种情况讨论：
1）如果u,v邻接，此时deg(u)+deg(v)>=(n-2)+2=n> n-1;
2) 如果u,v不邻接，则其余的n-2个结点仅能与u,v中的一个结点相邻接，设w是这其余的任一结点（由n>=3可知结点w存在的），由于结点w仅能u,v其中之一邻接，不妨设w与u邻接，与v不邻接，此时结点u和w均不与v邻接，这与题意矛盾；
故deg(u)+deg(v)>=n-1，则该图存在一个哈密顿路（参看任意一本离散数学书，如西北工业大学出版社出版刘长安编著《离散数学教程》P267）。
再证明当n>=4时，该图存在一个哈密顿回路。
下面需证明对任意两个结点u,v有deg(u)+deg(v)>=n，仍分下面两种情况讨论：
1）如果u,v邻接，此时deg(u)+deg(v)>=(n-2)+2=n;
2) 如果u,v不邻接，如果deg(u)+deg(v)=n-1，此时除u,v外其余的结点中存在一个结点s与u,v均邻接，另一个结点w仅与u,v其中之一邻接，（由n>=4可知结点s与w是存在的），不妨设w与u邻接，与v不邻接，此时结点u和w均不与v邻接，这又与题意矛盾；
故deg(u)+deg(v)>=n，则该图存在一个哈密顿路（参看任意一本离散数学书，同上书P268）。

参考资料：西北工业大学出版社出版刘长安编著《离散数学教程》