从1994年至今, DNA计算已成为数学、生物学、化学、计算机科学等领域的一个研究热点,并解决了很多NP—完全问题。如何减少编码量大的问题,即解决“指数爆炸”问题,是DNA计算面临诸多困难和主要技术问题之一。这就需要我们对已有的算法进行改进或寻找新的算法。目前, DNA计算在计算原理可行性的论证上比较成熟,对于表面技术的研究还处在探索阶段,随着表面技术的日益成熟, DNA计算将会从理论走向实践。离散数学是数学的一个分支,离散数学中有诸多的NP—完全问题,如:求主范式问题,图着色问题,求传递闭包问题,最大匹配问题,旅行商问题等等。目前, DNA计算是解决NP—完全问题最有效的方法,本文采用DNA计算解决了离散数学中具有代表性的三个难计算问题:命题逻辑中“求主范式问题”;图论中“图着色问题”;集合论中“求传递闭包问题”。本文首先介绍了DNA计算背景、现状、原理与基本模型。然后,解决了离散数学中上述的三个问题。第一,根据DNA发夹结构的突出优点,即不需要特殊的生物操作,这样从很大程度上减少了生物反应时间,并且根据主范式的定义与DNA发夹结构的定义知,完全可利用DNA发夹结构模型,求解离散数学中命题公式的主范式;第二,利用DNA计算机模型,采取合理编码使得解空间的生成基于三进制,并采取逐步产生满足定义的DNA链的方法,将离散数学中图3-着色问题的DNA分子链数由O( 3 n)减少到了O( 2 n),这样很好地解决了图3—着色问题中的“指数爆炸”问题,并给出了其应用;第三,利用Adleman试管模型,借鉴Hamilton路径问题的思想,求解了难计算的传递闭包问题。最后,总结了全文,讨论DNA计算与数学的密切关系及其在数学领域内的应用,并讨论了进一步的研究方向。