构造任意公示真值表：递归消减法实现

在《离散数学应用实践》的实验报告中，计科一班学生赵霏霏针对“构造任意合适公式的真值表”进行了深入探讨。实验的目标是给出任意变元的布尔公式，通过递归消减求值算法来构建其真值表。以下是关键步骤的详细解析： 1. **问题描述**： 实验的核心任务是理解并构造一个给定变元的布尔公式，例如AB（A与B的逻辑运算）。为了完成真值表，需要考虑所有可能的变元组合，即A和B的两种状态（True或False），这会生成四个不同的二进制值：00, 01, 10, 和11，分别代表A和B的假和真。对于每个组合，都需要将这些值代入公式中，计算其结果，形成完整的真值表。 2. **算法分析**： 主要使用的算法是递归消减求值，这是一种通过逐步简化和递归处理表达式的方法。这种方法首先处理嵌套的括号，如(x#y)、(x@y)等，按照一定的优先级顺序（如先括号后无括号，优先计算逻辑与(&)和逻辑或(|)），直到得出最终结果。在本实验中，digui()函数实现了这一递归过程。 3. **实现步骤**： - **数据预处理**：读取输入数据，去除空格，并处理多非（~）操作。例如，输入的"-(1&1)|0"会被转化为"0|0"。 - **变元提取与二进制序列生成**：通过get()函数提取变元，如AB，然后生成对应的二进制序列00, 01, 10, 11。 - **递归求解**：用docopy2_data()函数替换二进制值，逐个计算公式结果。对于不合适公式，第一次求值时就会判断出来。 - **digui()函数**：这个函数采用分治策略，递归地处理括号内的式子，直到没有剩余的括号，如(-(1&1))会先计算1&1得到0，再取反得到-0，最终结果为0。 4. **程序代码**： 报告展示了部分C语言代码片段，如头文件导入和函数定义，这些代码用于实现数据处理、提取变元、二进制转换以及递归求值的功能。例如，time.h, stdio.h, stdlib.h, 和 string.h 等库被用于处理时间和文件操作。 通过这个实验，学生可以巩固离散数学中的布尔逻辑和递归算法的理解，并能够应用到实际编程中，构建复杂布尔表达式的真值表。