NOIP 提高组初赛 · NOIP 2012 提高组初赛试题 第 21 题

本题中，我们约定布尔表达式只能包含 $p, q, r$ 三个布尔变量，以及“与”（$\land$）、“或”（$\lor$）、“非”（$\neg$）三种布尔运算。如果无论 $p, q, r$ 如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，$(p\land q)\lor r$ 和 $p\lor (q\lor r)$ 等价，$p\lor \neg p$ 和 $q\lor \neg q$ 也等价；而 $p\lor q$ 和 $p\land q$ 不等价。那么，两两不等价的布尔表达式最多有_________个。

这题核心是把‘等价’翻译成‘真值表相同’，三变量真值表有8行，每行非0即1，所以不等价个数就是8位二进制数的总数，直接算2^8即可。

学生常把‘不等价’当成‘真值表不同’，于是去数8位二进制里有多少个‘不一样’的数，容易绕进组合数或容斥里；还有把变量数当成真值表行数，误以为三变量只有3行，导致算出2^3=8；另外容易忽略‘无论p,q,r如何取值’这个全称条件，只考虑部分赋值，从而漏掉很多等价类。

这道题考查的是布尔表达式的等价类计数，属于逻辑代数里的真值表思想。

先说概念：两个布尔表达式等价，意味着对任意一组变量取值，它们的输出值都相同。换句话说，它们对应的真值表完全一样。真值表就是把变量所有可能的取值组合列出来，然后给出表达式的结果。

三变量p,q,r一共有2^3=8种取值组合（000,001,010,011,100,101,110,111）。对每一种组合，表达式的结果要么是真（1）要么是假（0），所以一个表达式对应一个8位的二进制串。

命题人挖坑的地方往往在‘等价’的定义上：题目强调‘无论p,q,r如何取值’，就是要求对所有8种情况都一致。如果只考虑部分情况，就会把本应视为等价的表达式当成不等价，或者反过来。另外，学生容易把变量个数当成真值表的行数，以为三变量就3行，从而算出2^3=8，这是典型的‘数错了维度’。

思考心法：拿到题先想‘等价→真值表相同’，再想‘三变量→8行真值表’，然后想‘每个真值表由8个0/1决定→2^8种可能’。不需要去构造具体表达式，因为题目问的是‘最多’有多少个不等价的表达式，也就是问有多少种不同的真值表。

具体计算：8位二进制数从00000000到11111111，一共2^8=256个。每个二进制串对应一个唯一的真值表，也就对应一个唯一的等价类。因此，两两不等价的布尔表达式最多有256个。

避坑提示：别把‘不等价’理解成‘真值表不同’就去数‘不同的数’，那样会陷入组合计数；也别把三变量当成三行真值表，那是把变量数和行数搞混了。记住，等价类的个数就是真值表的可能个数，直接指数运算。

考频与趋势：逻辑代数在历年NOIP/GESP中非常活跃，题库共47题，覆盖2007-2026的7个级别。从逐年分布看，2024年考了9题，2025年更是15题，说明最近两年命题人明显加大了对逻辑与布尔代数的考查力度，尤其是真值表、等价类这类基础概念。分赛事来看，GESP五级考了20题，NOIP提高组初赛考了9题，GESP八级6题，普及组5题，可见无论是入门级还是提高级，这类题目都高频出现。

预测：基于2024-2025年的爆发式增长，可以预见未来两三年逻辑代数仍将是初赛和GESP的热点，命题人可能会继续用‘等价类计数’‘真值表构造’‘逻辑运算优先级’等角度出题，甚至可能出现多变量（如4变量）的变式，考察学生能否快速抽象出真值表行数与等价类个数的关系。因此，掌握‘变量数n→真值表行数2^n→等价类个数2^{2^n}’这一链条，是应对此类题目的关键。