题解:P7020 [NWRRC2017] Boolean Satisfiability

Zheng_iii

2024-11-17 21:35:57

Solution

首先,我们需要明确一个重要的恒等式:

x \mid \neg a = 1

x = 1 时,x \mid \neg x = 1 \mid 0 的结果为 1
x = 0 时,x \mid \neg x = 0 \mid 1 的结果同样为 1
因此,我们可以得出结论,该式子的结果恒为 1

接下来,我们观察到,当表达式中仅包含 | 运算时,由于每个变量都有两种取值(0 或 1),所以在这种情况下,总的方案数为 2^n - 1-1 是因为我们需要排除所有变量均为 0 的情况)。

当我们引入 ¬ 运算时,如果 ¬xx 单独存在,我们可以将它们视为一个独立的变量。然而,当 ¬xx 同时存在时,我们可以通过交换律将它们组合在一起。根据我们之前的发现,这个组合的结果恒为 1

因此,在这种情况下,不存在所有变量均为 0 的情况。由此可得,总的方案数为 2^n