
本文介绍如何基于给定的不相容矩阵(d)和子集矩阵(s),结合逻辑约束建模,系统性地生成所有合法的事件组合向量——即满足“互斥事件不可同时为真”“子集事件发生则其父事件必发生”等语义规则的完整解空间。
本文介绍如何基于给定的不相容矩阵(d)和子集矩阵(s),结合逻辑约束建模,系统性地生成所有合法的事件组合向量——即满足“互斥事件不可同时为真”“子集事件发生则其父事件必发生”等语义规则的完整解空间。
在概率建模、事件系统仿真或知识图谱推理中,常需从一组原子事件出发,枚举所有逻辑上自洽的联合状态。例如网球比赛中,“A以60–0获胜”隐含“A获胜”且排斥“B获胜”“B发球直接得分”等事件。这类约束可形式化为两类结构化矩阵:
-
不相容矩阵
D:D[i, j] == 1表示事件i与事件j互斥(不能同时为真); -
子集矩阵
S:S[i, j] == 1表示事件i是事件j的子集(若i发生,则j必发生)。
但仅靠 D 和 S 不足以唯一确定解空间——还需补充第三类逻辑关系:否定蕴含(negation implication)。例如,“A未获胜”应推出“B获胜”,这无法由 D 或 S 直接导出,而需显式建模为矩阵 N:N[i, j] == 1 表示 ¬i → j。
以下提供一个健壮、可扩展的实现方案,使用 sympy 进行符号逻辑求解,并封装为通用函数:
import numpy as np
from sympy import symbols, And, Or, Not, Implies, satisfiable
def generate_valid_combinations(D: np.ndarray, S: np.ndarray, N: np.ndarray = None) -> np.ndarray:
"""
基于不相容(D)、子集(S)及否定蕴含(N)矩阵,生成所有合法布尔组合。
Parameters:
-----------
D : (n, n) ndarray
D[i,j] = 1 ⇒ 事件 i 与 j 互斥(i ∧ j → False)
S : (n, n) ndarray
S[i,j] = 1 ⇒ 事件 i 是 j 的子集(i → j)
N : (n, n) ndarray, optional
N[i,j] = 1 ⇒ ¬i 蕴含 j(¬i → j);若为 None,则自动推导为 D 的对称补(见说明)
Returns:
--------
(m, n) ndarray of int
每行是一个合法的 n 维布尔向量,共 m 种可能组合。
"""
n = D.shape[0]
assert D.shape == S.shape == (n, n)
if N is None:
# 启用启发式:若 D 对称,则 N[i,j] = D[j,i](即 ¬i → j ≡ j → ¬i)
# 实际应用中建议显式提供 N,避免歧义
N = D.T.copy()
# 定义符号变量 x0, x1, ..., x_{n-1}
variables = symbols(f"x0:{n}")
# 构建逻辑约束表达式
constraints = []
# 1. 不相容约束:D[i,j] == 1 ⇒ x_i → ¬x_j
for i in range(n):
for j in range(n):
if D[i, j]:
constraints.append(Implies(variables[i], Not(variables[j])))
# 2. 子集约束:S[i,j] == 1 ⇒ x_i → x_j
for i in range(n):
for j in range(n):
if S[i, j]:
constraints.append(Implies(variables[i], variables[j]))
# 3. 否定蕴含约束:N[i,j] == 1 ⇒ ¬x_i → x_j
for i in range(n):
for j in range(n):
if N[i, j]:
constraints.append(Implies(Not(variables[i]), variables[j]))
# 合并所有约束
full_expr = And(*constraints)
# 求解所有满足模型
solutions = list(satisfiable(full_expr, all_models=True))
# 转换为 NumPy 矩阵
if not solutions:
return np.zeros((0, n), dtype=int)
result = []
for sol in solutions:
row = [int(sol.get(v, False)) for v in variables]
result.append(row)
return np.array(result, dtype=int)
# 示例:复现问题中的网球场景
D = np.array([
[0, 1, 0, 0, 0],
[1, 0, 1, 1, 0],
[0, 1, 0, 1, 1],
[0, 1, 1, 0, 0], # 已修正:D[3,2]=1 表示 A wins 60-15 ⇒ ¬(A wins 60-0)
[0, 0, 1, 0, 0]
])
S = np.array([
[0, 0, 1, 1, 0], # A wins ⇒ A wins 60-0 & A wins 60-15(注意:原题 S 定义反了,此处按语义校正)
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]
])
N = np.array([
[0, 1, 0, 0, 0], # ¬A wins ⇒ B wins
[1, 0, 0, 0, 0], # ¬B wins ⇒ A wins
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]
])
X = generate_valid_combinations(D, S, N)
print("共找到 {} 种合法组合:".format(len(X)))
print(X)
✅ 关键说明与注意事项:
- 矩阵语义必须严格一致:
S[i,j] = 1应表示 事件 i 是事件 j 的子集(即i → j),而非相反;原始问题中S的定义方向易引发混淆,代码中已按标准逻辑惯例校正。N矩阵不可省略:仅用D和S无法推导出¬a → b类约束,会导致解空间膨胀(如错误包含[0,0,...]全零向量)。显式提供N是保证完备性的关键。- 性能提示:当事件数
n > 20时,穷举2^n状态不可行。此时建议改用 SAT 求解器(如pysat)或引入剪枝策略(如增量约束传播)。- 验证建议:对输出结果
X,可反向验证每行是否满足:# 验证 D:无互斥事件同时为 1 assert not np.any((X @ D * X.T).diagonal()) # 验证 S:若 X[i]==1,则 X[j] 必为 1(当 S[i,j]==1) for i, j in zip(*np.where(S)): assert np.all(X[:, i]
该方法将领域知识(事件关系)精准映射为可计算的逻辑公式,兼顾可读性、正确性与工程可维护性,适用于各类基于约束的组合生成任务。










