NOIP 提高 2012 第一轮 第 21 题：本题中，我们约定布尔表达式只能包含p,q,r三个布尔变量，以及“与”（^）、“或

题目

本题中，我们约定布尔表达式只能包含 $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$ 不等价。那么，两两不等价的布尔表达式最多有_个。

答案

256

题解

考点定位

本题考「布尔函数等价类计数」,对应大纲 2.1.5 组合计数（难度【4】）。

解题过程

含 p,q,r 的布尔表达式本质是一个「三元布尔函数」f:{0,1}³→{0,1}。共有 2³=8 种输入取值，每个取值可独立取 0/1：

$$2^{2^3}=256$$

个互相不等价的表达式（等价 ⟺ 真值表相同）。

答案：256。

易错提醒

① 「表达式等价」= 真值表相同；② 通用公式：n 个变量的等价类数 = 2^(2ⁿ)。