[csp-j 2022] 逻辑表达式

### 回答1：
题目描述：

给定一个逻辑表达式，包含变量和运算符，其中变量用大写字母表示，运算符包括与（&）、或（|）、非（!）和异或（^），请输出该表达式的真值。

输入格式：

输入共一行，为一个字符串，表示逻辑表达式，字符串长度不超过 100。

输出格式：

输出共一行，为一个整数，表示该表达式的真值，1 表示真， 表示假。

输入样例：

A&B&C|!D^E

输出样例：

1

解题思路：

本题可以使用栈来解决，具体思路如下：

1.首先定义两个栈，一个用来存储运算符，一个用来存储操作数。

2.遍历表达式中的每一个字符，如果是运算符，则将其压入运算符栈中，如果是操作数，则将其压入操作数栈中。

3.当遇到一个右括号时，从操作数栈中弹出两个操作数，从运算符栈中弹出一个运算符，进行运算，并将结果压入操作数栈中。

4.最终操作数栈中只剩下一个元素，即为表达式的真值。

代码实现：

### 回答2：
题目链接：https://www.luogu.com.cn/problem/CSP-J-2022

本题需要我们求得不含变量 `x` 的逻辑表达式的真值表。

首先分析题目中给出的逻辑运算符：`NOT`、`AND`、`OR`、`XOR`。这些逻辑运算符在计算机科学中很常见，它们分别表示取反、且、或、异或的运算。我们可以通过一个简单的真值表来表示它们的运算规则：

|p|q|NOT p|p AND q|p OR q|p XOR q|
|-|-|-----|------|------|-------|
|0|0| 1 | 0 | 0 | 0 |
|0|1| 1 | 0 | 1 | 1 |
|1|0| 0 | 0 | 1 | 1 |
|1|1| 0 | 1 | 1 | 0 |

通过这个真值表，我们可以很容易地推导出不同逻辑表达式的结果。例如，当 `p` 为真且 `q` 为假时，`p AND q` 的结果就是假；`p OR q` 的结果就是真。同理，当 `p` 和 `q` 相同的时候，它们的异或结果就是假，否则就是真。

而本题中的逻辑表达式是由多个运算符和 `x` 变量组成的，我们需要计算出真值表。为了避免直接枚举每一种情况，并逐个计算结果，我们可以采用二叉树的思路，即每个节点代表一个逻辑运算符，左右子树分别为该运算符的两个参数，直到叶节点为止，叶节点即为一个变量（可能是 `x` 或者是常量）。

具体操作方法可以采用递归实现。递归函数需要传入一个字符串表达式，返回该表达式是真还是假。具体实现细节可见代码。最终我们可以得到一个 1 行 2 的 n 次方 列的真值表。

代码：

### 回答3：
题目描述

给定 $m$ 个逻辑变量 $a_1, a_2, \cdots, a_m$，以及 $k$ 个逻辑表达式 $f_1, f_2, \cdots, f_k$，每个逻辑表达式都是由 $m$ 个逻辑变量和 $\land, \lor, \oplus, \neg$ 构成的合法逻辑表达式。

定义 $\operatorname{sat}(S)$ 为集合 $S$ 中的逻辑变量对应的真值赋值下，存在至少一个使得所有的逻辑表达式都为真。

例如，对于逻辑变量 $a, b, c$ 和两个逻辑表达式 $(a \lor b)$ 和 $(b \Rightarrow \neg c)$，$\operatorname{sat}(\{a=\mathrm{true}, b=\mathrm{false}, c=\mathrm{true}\})= false$。

给定一个逻辑表达式 $f$，定义其等效表示为 $\operatorname{simpl}(f)$。具体过程如下：

- 根据与运算和或运算的结合律联想律，将逻辑表达式化为形如 $\ell_1 \land \ell_2 \land \cdots \land \ell_p$ 的简单合取范式，其中每个 $\ell_i$ 都是形如 $x_1 \lor x_2 \lor \cdots \lor x_q$ 的简单析取项；
- 对于每个简单析取项 $x_1 \lor x_2 \lor \cdots \lor x_q$，在线性时间内计算一个包含了 $S$ 中逻辑变量对应的所有真值赋值中满足其为真的赋值的指示函数 $\phi_{x_1 \lor x_2 \lor \cdots \lor x_q}$。具体地，使用一个变量 $f=\mathrm{false}$ 并进行以下操作 $q$ 次：若 $S$ 中某个逻辑变量对应的值可以使得 $x_i$ 为 true，则让 $f$ 取为 $\mathrm{true}$，最终令 $\phi_{x_1 \lor x_2 \lor \cdots \lor x_q}=f$；
- 最终得到的 $\operatorname{simpl}(f)$ 是 $\ell_1', \ell_2', \cdots, \ell_p'$ 的形式，其中每个 $\ell_i'$ 是二元组 $(\phi_{x_{i,1}}, \phi_{x_{i,2}})$，表示存在一组完全赋值 $v$ 使得 $\operatorname{sat}(\{a_i=v_i\})=\mathrm{true}$ 当且仅当 $x_{i,1}(v) \lor x_{i,2}(v)=\mathrm{true}$。

例如，对于逻辑表达式 $(a \land b) \Rightarrow ((a \lor b) \land (\neg a \lor \neg b))$，其 $\operatorname{simpl}$ 值为 $((a, b), ((a,b), (\neg a, \neg b)))$。

现在，请你构造一个逻辑表达式 $g$，使得 $\operatorname{simpl}(g)$ 中只有 $O(k+2^m)$ 个二元组，且对于所有的 $S$，$\operatorname{sat}(S)$ 在 $\operatorname{simpl}(g)$ 中的判定时间复杂度为 $O(k)$。

数据范围

对于所有测试点，保证 $1 \leqslant m \leqslant 10, 1 \leqslant k \leqslant 3m$。

本题满分为 $100$ 分。对于在此公开测试数据中得分为 $0$ 分的提交，我们将根据提交的相似度情况视情况给出提示，请注意查看提交结果页面。

算法1

(打表找规律) $O(m 2^{3m})$

我们需要解决两个问题：如何根据 $\operatorname{simpl}(f)$ 判断 $\operatorname{sat}(S)$ 是否为 $\mathrm{true}$，以及如何构造出一个表达式 $g$，使得对于所有 $S$ 都有 $\operatorname{simpl}(g)$ 可以在 $O(k)$ 时间内判断 $\operatorname{sat}(S)$ 是否为 $\mathrm{true}$。

先考虑第一个问题。容易发现，对于一个二元组 $(\phi_{x_1}, \phi_{x_2})$，如果 $\operatorname{simpl}(f)$ 中存在一个简单析取项 $x_1 \lor x_2$，且 $\phi_{x_1}$ 和 $\phi_{x_2}$ 均为真函数，则 $\operatorname{simpl}(f)$ 在 $S$ 中的真值即为 $\mathrm{true}$。注意到 $\phi_{x_1}, \phi_{x_2}$ 都是只由 $S$ 中的逻辑变量决定的 01 函数，因此我们可以使用一个 $3^m \times 3^m$ 的矩阵 $mat_x$ 表示 $x$ 对 $S$ 的真值的影响。$mat_x(i,j)=1$ 表示当 $x$ 中逻辑变量取值的指示函数为 $i$ 和 $j$ 时，$\operatorname{sat}(S)$ 是否为 $\mathrm{true}$。注意到 $x$ 有 $2^m$ 种取值，因此我们需要计算 $O(2^m)$ 个矩阵 $mat_x$，每个矩阵的计算可以使用一组对应的二元组 $(\phi_{x_1}, \phi_{x_2})$ 和矩阵加法计算得到。接着我们可以把 $\operatorname{simpl}(f)$ 中所有的简单析取项的对应矩阵加起来，最终得到 $k$ 个 $3^m \times 3^m$ 的矩阵 $mat_1, mat_2, \cdots, mat_k$。判断 $\operatorname{simpl}(f)$ 在 $S$ 中的真值即可以通过计算 $\prod_{i=1}^k mat_i$ 得到。

接着考虑第二个问题。我们需要构造出一个表达式 $g$，使得 $\operatorname{simpl}(g)$ 在 $O(k)$ 时间内能判断 $\operatorname{sat}(S)$ 是否为 $\mathrm{true}$。首先考虑简单情况即 $m=1$。设 $a$ 为 $S$ 中唯一的变量。如果 $k=1$，令 $g=a$ 即可；如果 $k=2$，令 $g=\neg a \land f_2 \lor a\land \neg f_2$ 即可；如果 $k=3$，令 $g=\neg a (\neg f_2 \land \neg f_3) \lor a(\neg f_2 \land f_3) \lor f_2 \land f_3$ 即可；如果 $k=4$，令 $g=a(\neg f_2 \land f_4) \lor \neg a(f_3 \land f_4)$ 即可。可发现，对于给定的 $m,k$，这些表达式都不超过常数个。接着考虑如何推广到一般情况。

设 $a_1, a_2, \cdots, a_m$ 为 $S$ 中的 $m$ 个变量。考虑令 $g_i$ 表示 $S$ 中变量 $a_i$ 的值（$0$ 或 $1$）。首先考虑对一个简单析取项 $x_1 \lor x_2 \lor \cdots \lor x_q$ 进行处理。对于 $i \in [1,q]$，设 $x_i$ 的指示函数为 $(\phi_{x_i,1}, \phi_{x_i,2})$，考虑令 $y_i$ 表示“至少有一个 $x_1, x_2, \cdots, x_i$ 在 $S$ 中是真的”，即 $y_1=x_1, y_i=y_{i-1} \lor x_i$。注意到 $y_i$ 极易通过 $\mathrm{or}$ 的结合律计算得到，因此我们可以直接把所有的二元组加入表达式 $g$ 中。此外，为了判断 $\operatorname{sat}(S)$ 是否为 $\mathrm{true}$，我们只需要计算 $y_q$ 即可。

接着考虑如何计算 $g_i$。我们构建一个由 $2^m$ 个节点组成的满二叉树，每个节点代表一个赋值 $v_1, v_2, \cdots, v_m$。根节点对应所有变量的值都是未定的赋值。为了方便起见，我们设根节点所在的深度为 $1$（节点深度定义为从根节点到该节点的从上到下路径上穿过的边数目加一）。除了根节点外，每个节点 $u$ 都对应一个深度为 $i_u$ 的变量 $a_{u, i_u}$ 的值。仅当 $a_{u, i_u}$ 的值已经被确定时，才可以计算 $g_{i_u}(u)$（为了防止重复计算，不考虑已经被计算过的 $g$ 值）。$g_{i_u}(u)$ 的值也是二元组 $(\phi_{x_{i_u,1}}, \phi_{x_{i_u,2}})$ 的形式，表示当前 $\operatorname{sat}(S)$ 在 $u$ 对应的赋值下为真的充要条件为 $\phi_{x_{i_u,1}}(u)=\mathrm{true}$ 或 $\phi_{x_{i_u,2}}(u)=\mathrm{true}$。这些值可以通过矩阵乘法计算得到（注意到构成 $g_{i_u}(u)$ 的所有简单析取项的矩阵已经计算得到）。最后根据 $g_1(\mathrm{root}) \lor g_2(\mathrm{root}) \lor \cdots \lor g_m(\mathrm{root})$ 判断 $\operatorname{sat}(S)$ 是否为 $\mathrm{true}$ 即可。

时间复杂度

计算 $\operatorname{simpl}(f)$ 中所有 二元组需 $O(k \cdot 2^m \cdot 3^{2m})$ 的时间，处理 $g$ 的过程中遍历了一个深度为 $m+1$ 的二叉树，节点数为 $2^{m+1}-1$。每个节点计算 $g_{i_u}(u)$ 的时间复杂度为 $O(2^{3m})$，因此总时间复杂度为 $O(k \cdot 2^m \cdot 3^{2m} + (2^{m+1}-1)2^{3m}) \leqslant O(m 2^{3m})$。