当前位置：首页 > ds >正文

Python实例题：Python计算离散数学

ds 2025/7/17 19:16:17

Python实例题

题目

Python计算离散数学

代码实现

import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
from sympy import symbols, Or, And, Not, Implies, Equivalent, simplify, to_cnf, satisfiable
from itertools import combinations, permutations, productclass DiscreteMath:"""离散数学分析类，支持集合运算、逻辑运算、关系运算和图论"""def __init__(self):"""初始化分析器"""pass# ================ 集合运算 ================def union(self, A, B):"""计算两个集合的并集参数:A: 第一个集合B: 第二个集合返回:set: 并集结果"""return A.union(B)def intersection(self, A, B):"""计算两个集合的交集参数:A: 第一个集合B: 第二个集合返回:set: 交集结果"""return A.intersection(B)def difference(self, A, B):"""计算两个集合的差集（属于A但不属于B的元素）参数:A: 第一个集合B: 第二个集合返回:set: 差集结果"""return A.difference(B)def symmetric_difference(self, A, B):"""计算两个集合的对称差集（只属于其中一个集合的元素）参数:A: 第一个集合B: 第二个集合返回:set: 对称差集结果"""return A.symmetric_difference(B)def cartesian_product(self, A, B):"""计算两个集合的笛卡尔积参数:A: 第一个集合B: 第二个集合返回:set: 笛卡尔积结果，元素为元组"""return set(product(A, B))def power_set(self, A):"""计算集合的幂集（所有子集的集合）参数:A: 原始集合返回:set: 幂集，元素为集合"""subsets = []for i in range(len(A) + 1):subsets.extend(combinations(A, i))return set(frozenset(s) for s in subsets)# ================ 逻辑运算 ================def evaluate_logic_expression(self, expr, values):"""计算逻辑表达式的值参数:expr: 逻辑表达式（使用SymPy符号）values: 变量值的字典，例如 {'p': True, 'q': False}返回:bool: 表达式计算结果"""return expr.subs(values)def truth_table(self, expr, variables):"""生成逻辑表达式的真值表参数:expr: 逻辑表达式（使用SymPy符号）variables: 变量列表，例如 ['p', 'q']返回:list: 真值表，每行是一个字典，包含变量值和表达式结果"""var_symbols = [symbols(var) for var in variables]table = []# 生成所有可能的变量赋值for values in product([False, True], repeat=len(variables)):assignment = dict(zip(variables, values))result = self.evaluate_logic_expression(expr, assignment)table.append({**assignment, '结果': result})return tabledef is_tautology(self, expr):"""检查逻辑表达式是否为重言式参数:expr: 逻辑表达式（使用SymPy符号）返回:bool: 如果是重言式返回True，否则返回False"""variables = list(expr.free_symbols)table = self.truth_table(expr, [str(v) for v in variables])for row in table:if not row['结果']:return Falsereturn Truedef is_contradiction(self, expr):"""检查逻辑表达式是否为矛盾式参数:expr: 逻辑表达式（使用SymPy符号）返回:bool: 如果是矛盾式返回True，否则返回False"""variables = list(expr.free_symbols)table = self.truth_table(expr, [str(v) for v in variables])for row in table:if row['结果']:return Falsereturn Truedef is_satisfiable(self, expr):"""检查逻辑表达式是否可满足参数:expr: 逻辑表达式（使用SymPy符号）返回:bool: 如果可满足返回True，否则返回False"""return satisfiable(expr) is not Nonedef to_cnf(self, expr):"""将逻辑表达式转换为合取范式(CNF)参数:expr: 逻辑表达式（使用SymPy符号）返回:sympy表达式: 合取范式形式"""return to_cnf(expr)# ================ 关系运算 ================def is_reflexive(self, relation, set_A):"""检查关系是否自反参数:relation: 关系，元素为有序对的集合set_A: 集合A返回:bool: 如果关系自反返回True，否则返回False"""for a in set_A:if (a, a) not in relation:return Falsereturn Truedef is_symmetric(self, relation):"""检查关系是否对称参数:relation: 关系，元素为有序对的集合返回:bool: 如果关系对称返回True，否则返回False"""for (a, b) in relation:if (b, a) not in relation:return Falsereturn Truedef is_antisymmetric(self, relation):"""检查关系是否反对称参数:relation: 关系，元素为有序对的集合返回:bool: 如果关系反对称返回True，否则返回False"""for (a, b) in relation:if a != b and (b, a) in relation:return Falsereturn Truedef is_transitive(self, relation):"""检查关系是否传递参数:relation: 关系，元素为有序对的集合返回:bool: 如果关系传递返回True，否则返回False"""for (a, b) in relation:for (c, d) in relation:if b == c and (a, d) not in relation:return Falsereturn Truedef is_equivalence_relation(self, relation, set_A):"""检查关系是否为等价关系参数:relation: 关系，元素为有序对的集合set_A: 集合A返回:bool: 如果关系是等价关系返回True，否则返回False"""return (self.is_reflexive(relation, set_A) and self.is_symmetric(relation) and self.is_transitive(relation))def equivalence_classes(self, relation, set_A):"""计算等价关系的等价类参数:relation: 等价关系，元素为有序对的集合set_A: 集合A返回:list: 等价类的列表，每个等价类是一个集合"""if not self.is_equivalence_relation(relation, set_A):raise ValueError("给定的关系不是等价关系")classes = []for a in set_A:# 计算a的等价类cls = set()for b in set_A:if (a, b) in relation:cls.add(b)# 如果这个等价类还没有被记录，则添加它if not any(cls == c for c in classes):classes.append(cls)return classes# ================ 图论 ================def create_graph(self, vertices, edges, directed=False):"""创建图参数:vertices: 顶点集合edges: 边集合，元素为顶点对directed: 是否为有向图，默认为False返回:networkx图对象: 创建的图"""if directed:G = nx.DiGraph()else:G = nx.Graph()G.add_nodes_from(vertices)G.add_edges_from(edges)return Gdef draw_graph(self, G, title=None, layout='spring'):"""绘制图参数:G: networkx图对象title: 图标题，默认为Nonelayout: 布局算法，可选'spring', 'circular', 'shell', 'random'"""plt.figure(figsize=(10, 6))# 选择布局算法if layout == 'spring':pos = nx.spring_layout(G)elif layout == 'circular':pos = nx.circular_layout(G)elif layout == 'shell':pos = nx.shell_layout(G)elif layout == 'random':pos = nx.random_layout(G)else:pos = nx.spring_layout(G)# 绘制节点和边nx.draw_networkx_nodes(G, pos, node_size=700)nx.draw_networkx_edges(G, pos, width=2)nx.draw_networkx_labels(G, pos, font_size=12, font_family='sans-serif')# 设置标题if title:plt.title(title, fontsize=14)plt.axis('off')plt.show()def is_connected(self, G):"""检查图是否连通参数:G: networkx图对象返回:bool: 如果图连通返回True，否则返回False"""if G.is_directed():return nx.is_strongly_connected(G)else:return nx.is_connected(G)def degree_sequence(self, G):"""获取图的度序列参数:G: networkx图对象返回:list: 度序列，按降序排列"""degrees = [d for n, d in G.degree()]degrees.sort(reverse=True)return degreesdef shortest_path(self, G, source, target):"""计算两个顶点之间的最短路径参数:G: networkx图对象source: 源顶点target: 目标顶点返回:list: 最短路径上的顶点列表"""return nx.shortest_path(G, source, target)def graph_diameter(self, G):"""计算图的直径（最长最短路径的长度）参数:G: networkx图对象返回:int: 图的直径"""if not self.is_connected(G):raise ValueError("图不连通，无法计算直径")return nx.diameter(G)def adjacency_matrix(self, G):"""计算图的邻接矩阵参数:G: networkx图对象返回:numpy数组: 邻接矩阵"""return nx.adjacency_matrix(G).toarray()# ================ 组合数学 ================def factorial(self, n):"""计算阶乘 n!参数:n: 非负整数返回:int: 阶乘结果"""if n < 0:raise ValueError("阶乘的参数必须是非负整数")result = 1for i in range(1, n + 1):result *= ireturn resultdef permutations(self, n, k=None):"""计算排列数 P(n, k)参数:n: 元素总数k: 选取元素数，默认为n返回:int: 排列数"""if k is None:k = nif n < 0 or k < 0 or k > n:raise ValueError("排列参数必须满足 0 <= k <= n")return self.factorial(n) // self.factorial(n - k)def combinations(self, n, k):"""计算组合数 C(n, k)参数:n: 元素总数k: 选取元素数返回:int: 组合数"""if n < 0 or k < 0 or k > n:raise ValueError("组合参数必须满足 0 <= k <= n")return self.factorial(n) // (self.factorial(k) * self.factorial(n - k))def binomial_coefficient(self, n, k):"""计算二项式系数 C(n, k)，与combinations方法相同参数:n: 元素总数k: 选取元素数返回:int: 二项式系数"""return self.combinations(n, k)def catalan_number(self, n):"""计算第n个卡特兰数参数:n: 非负整数返回:int: 第n个卡特兰数"""if n < 0:raise ValueError("卡特兰数的参数必须是非负整数")return self.combinations(2 * n, n) // (n + 1)# 示例使用
def example_usage():dm = DiscreteMath()print("\n===== 集合运算示例 =====")A = {1, 2, 3, 4}B = {3, 4, 5, 6}print(f"A = {A}")print(f"B = {B}")print(f"A ∪ B = {dm.union(A, B)}")print(f"A ∩ B = {dm.intersection(A, B)}")print(f"A - B = {dm.difference(A, B)}")print(f"A ⊕ B = {dm.symmetric_difference(A, B)}")print(f"A × B = {dm.cartesian_product(A, B)}")print(f"P(A) = {dm.power_set(A)}")print("\n===== 逻辑运算示例 =====")p, q = symbols('p q')expr = Implies(p, Or(q, Not(p)))print(f"逻辑表达式: {expr}")print(f"真值表:")table = dm.truth_table(expr, ['p', 'q'])for row in table:print(row)print(f"是否为重言式: {dm.is_tautology(expr)}")print(f"是否为矛盾式: {dm.is_contradiction(expr)}")print(f"是否可满足: {dm.is_satisfiable(expr)}")print(f"合取范式: {dm.to_cnf(expr)}")print("\n===== 关系运算示例 =====")set_A = {1, 2, 3}relation = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}print(f"集合 A = {set_A}")print(f"关系 R = {relation}")print(f"是否自反: {dm.is_reflexive(relation, set_A)}")print(f"是否对称: {dm.is_symmetric(relation)}")print(f"是否反对称: {dm.is_antisymmetric(relation)}")print(f"是否传递: {dm.is_transitive(relation)}")print(f"是否为等价关系: {dm.is_equivalence_relation(relation, set_A)}")# 创建一个等价关系equiv_relation = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}print(f"\n等价关系 R = {equiv_relation}")print(f"等价类: {dm.equivalence_classes(equiv_relation, set_A)}")print("\n===== 图论示例 =====")vertices = {1, 2, 3, 4}edges = {(1, 2), (2, 3), (3, 4), (4, 1), (1, 3)}G = dm.create_graph(vertices, edges)print(f"图的顶点: {G.nodes()}")print(f"图的边: {G.edges()}")print(f"是否连通: {dm.is_connected(G)}")print(f"度序列: {dm.degree_sequence(G)}")print(f"邻接矩阵:\n{dm.adjacency_matrix(G)}")# 绘制图dm.draw_graph(G, "无向图示例")# 创建有向图directed_vertices = {1, 2, 3, 4}directed_edges = {(1, 2), (2, 3), (3, 4), (4, 1)}DG = dm.create_graph(directed_vertices, directed_edges, directed=True)print(f"\n有向图的顶点: {DG.nodes()}")print(f"有向图的边: {DG.edges()}")print(f"是否强连通: {dm.is_connected(DG)}")# 绘制有向图dm.draw_graph(DG, "有向图示例")print("\n===== 组合数学示例 =====")n = 5k = 3print(f"n! = {dm.factorial(n)}")print(f"P({n}, {k}) = {dm.permutations(n, k)}")print(f"C({n}, {k}) = {dm.combinations(n, k)}")# 计算前10个卡特兰数print("\n前10个卡特兰数:")for i in range(10):print(f"C({i}) = {dm.catalan_number(i)}")if __name__ == "__main__":example_usage()

实现原理

这个离散数学计算工具基于以下技术实现：

集合运算：
- 使用 Python 内置的集合数据结构实现并、交、差等基本运算
- 支持笛卡尔积和幂集的计算
- 提供集合操作的可视化展示
逻辑运算：
- 使用 SymPy 库进行符号逻辑计算
- 支持真值表生成、重言式检查、矛盾式检查等
- 提供逻辑表达式到合取范式 (CNF) 的转换
关系运算：
- 实现关系的自反性、对称性、反对称性和传递性检查
- 支持等价关系和等价类的计算
- 提供关系性质的判定和验证
图论：
- 使用 NetworkX 库创建和操作图结构
- 支持图的可视化、连通性检查和最短路径计算
- 提供度序列、邻接矩阵等图的基本属性计算
组合数学：
- 实现阶乘、排列数、组合数等基本组合计算
- 支持卡特兰数等特殊数列的计算
- 提供组合计数问题的解决方案

关键代码解析

1. 集合运算

def union(self, A, B):"""计算两个集合的并集"""return A.union(B)def cartesian_product(self, A, B):"""计算两个集合的笛卡尔积"""return set(product(A, B))def power_set(self, A):"""计算集合的幂集"""subsets = []for i in range(len(A) + 1):subsets.extend(combinations(A, i))return set(frozenset(s) for s in subsets)

2. 逻辑运算

def truth_table(self, expr, variables):"""生成逻辑表达式的真值表"""var_symbols = [symbols(var) for var in variables]table = []for values in product([False, True], repeat=len(variables)):assignment = dict(zip(variables, values))result = self.evaluate_logic_expression(expr, assignment)table.append({**assignment, '结果': result})return tabledef is_tautology(self, expr):"""检查逻辑表达式是否为重言式"""variables = list(expr.free_symbols)table = self.truth_table(expr, [str(v) for v in variables])for row in table:if not row['结果']:return Falsereturn True

3. 关系运算

def is_reflexive(self, relation, set_A):"""检查关系是否自反"""for a in set_A:if (a, a) not in relation:return Falsereturn Truedef equivalence_classes(self, relation, set_A):"""计算等价关系的等价类"""if not self.is_equivalence_relation(relation, set_A):raise ValueError("给定的关系不是等价关系")classes = []for a in set_A:cls = set()for b in set_A:if (a, b) in relation:cls.add(b)if not any(cls == c for c in classes):classes.append(cls)return classes

4. 图论

def create_graph(self, vertices, edges, directed=False):"""创建图"""if directed:G = nx.DiGraph()else:G = nx.Graph()G.add_nodes_from(vertices)G.add_edges_from(edges)return Gdef draw_graph(self, G, title=None, layout='spring'):"""绘制图"""plt.figure(figsize=(10, 6))if layout == 'spring':pos = nx.spring_layout(G)elif layout == 'circular':pos = nx.circular_layout(G)# 其他布局选项...nx.draw_networkx_nodes(G, pos, node_size=700)nx.draw_networkx_edges(G, pos, width=2)nx.draw_networkx_labels(G, pos, font_size=12)if title:plt.title(title, fontsize=14)plt.axis('off')plt.show()

使用说明

安装依赖：

pip install numpy matplotlib networkx sympy

基本用法：

from discrete_math import DiscreteMath# 创建分析器实例
dm = DiscreteMath()# 集合运算
A = {1, 2, 3}
B = {3, 4, 5}
print(f"A ∪ B = {dm.union(A, B)}")
print(f"A × B = {dm.cartesian_product(A, B)}")# 逻辑运算
from sympy import symbols, Implies, Or, Notp, q = symbols('p q')
expr = Implies(p, Or(q, Not(p)))
print(f"真值表: {dm.truth_table(expr, ['p', 'q'])}")
print(f"是否为重言式: {dm.is_tautology(expr)}")# 关系运算
set_A = {1, 2, 3}
relation = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
print(f"是否自反: {dm.is_reflexive(relation, set_A)}")
print(f"是否对称: {dm.is_symmetric(relation)}")# 图论
vertices = {1, 2, 3, 4}
edges = {(1, 2), (2, 3), (3, 4), (4, 1)}
G = dm.create_graph(vertices, edges)
dm.draw_graph(G, "四边形图")
print(f"是否连通: {dm.is_connected(G)}")# 组合数学
print(f"5! = {dm.factorial(5)}")
print(f"C(5, 3) = {dm.combinations(5, 3)}")

示例输出：

A ∪ B = {1, 2, 3, 4, 5}
A × B = {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 3), (3, 4), (3, 5)}
真值表: [{'p': False, 'q': False, '结果': True}, {'p': False, 'q': True, '结果': True}, {'p': True, 'q': False, '结果': False}, {'p': True, 'q': True, '结果': True}]
是否为重言式: False
是否自反: True
是否对称: True
5! = 120
C(5, 3) = 10

扩展建议

增强功能：
- 添加更多逻辑运算功能（如 DNF 转换、逻辑表达式简化）
- 实现更复杂的图算法（如最小生成树、图着色）
- 增加数论相关功能（如素数测试、最大公约数）
- 支持更复杂的组合计数问题（如容斥原理）
用户界面：
- 开发命令行交互界面
- 创建图形界面（如使用 Tkinter 或 PyQt）
- 实现 Web 界面（如使用 Flask 或 Django）
性能优化：
- 针对大规模计算进行优化
- 添加并行计算支持
- 优化符号计算的效率
教学辅助：
- 添加离散数学概念解释和公式推导
- 提供交互式可视化（如动态调整图结构）
- 实现练习题生成和解答功能