The Inverse Truth-Table Problem | 逆真值表问题

📚 The Inverse Truth-Table Problem | 逆真值表问题

In logic and boolean algebra, we normally start with a compound proposition and build its truth table to study when it is true or false. The inverse truth‑table problem reverses this direction: given a truth table that specifies a desired output for every possible combination of input truth values, we must construct a logical expression that behaves exactly according to that table. This skill is essential in digital circuit design, artificial intelligence, and problem‑solving within the IB Mathematics curriculum, particularly when students explore logical equivalence and normal forms.

在逻辑与布尔代数中，我们通常从一个复合命题出发，建立它的真值表，观察它在何种情况下为真、何种情况下为假。逆真值表问题则把这个过程颠倒过来：给你一张真值表，其中对每一种可能的输入真值组合都规定好了期望的输出，你需要构造一个逻辑表达式，使其行为恰好与这张表一致。这项技能在数字电路设计、人工智能以及 IB 数学课程中都非常关键，特别是在学生探究逻辑等价和范式的时候。

1. What Is the Inverse Truth‑Table Problem? | 什么是逆真值表问题？

The inverse truth‑table problem, sometimes called the “synthesis” or “design” problem, asks us to find a compound proposition whose truth table matches a given target column. In other words, we are supplied with an exhaustive list of all possible truth assignments to a set of atomic propositions (the independent variables) and a final column indicating whether the overall statement should be true (often represented as 1 or T) or false (0 or F) in each case. The challenge is to recover – or invent – a logical expression that reproduces that exact pattern.

逆真值表问题有时也被称作“综合”或“设计”问题，它要求我们找到一个复合命题，使其真值表与给定的目标列一致。换言之，我们拿到了一份完整的列表，列出了所有可能对一组原子命题（自变量）的真值赋值，以及最后一列，指明在每种情况下整个陈述应为真（通常用 1 或 T 表示）还是假（用 0 或 F 表示）。挑战就在于复原——或者说发明——一个能重现该模式的确切逻辑表达式。

This problem is distinct from simply reading a truth table; it demands creativity and a systematic method. Fortunately, Boolean algebra provides two canonical forms – Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF) – that offer robust, step‑by‑step procedures for constructing a correct expression directly from any truth table.

这个问题不同于单纯地读取真值表；它既需要创造力，也需要系统的方法。幸运的是，布尔代数提供了两种标准形式——析取范式 (DNF) 和合取范式 (CNF)——它们给出了从任意真值表直接构造正确表达式的可靠步骤。

2. A Quick Recap of Truth Tables | 真值表快速回顾

Before tackling the inverse problem, it is helpful to review the standard forward process. A truth table lists all combinations of truth values (True/False, or 1/0) for a given set of atomic propositions. For n propositions, there are 2ⁿ rows. Each logical connective (¬, ∧, ∨, →, ↔) defines how the truth value of a compound proposition depends on its components. In IB Mathematics, students work extensively with truth tables to prove logical equivalence, identify tautologies, and understand the behaviour of complex statements.

在处理逆问题之前，先回顾一下标准的正向过程会很有帮助。真值表列出了给定原子命题集合的所有真值组合（真/假，或 1/0）。对于 n 个命题，共有 2ⁿ 行。每个逻辑联结词（¬，∧，∨，→，↔）定义了复合命题的真值如何依赖于其组成部分。在 IB 数学中，学生大量使用真值表来证明逻辑等价、识别重言式并理解复杂陈述的行为。

For example, consider two propositions P and Q. The truth table for P → Q contains four rows, and the output column is F only when P is true and Q is false. This precise mapping between input combinations and a single output is exactly the data the inverse problem begins with.

例如，考虑两个命题 P 和 Q。P → Q 的真值表包含四行，只有当 P 为真且 Q 为假时，输出列才为 F。这种输入组合与单一输出之间的精确映射，正是逆问题所基于的数据。

3. Formal Statement of the Problem | 问题的正式陈述

Given a set of m atomic propositions A₁, A₂, …, Aₘ and a truth table that assigns a specified output value (0 or 1) to each of the 2ᵐ possible combinations of truth values for these propositions, find a logical expression involving A₁, A₂, …, Aₘ and the connectives ¬, ∧, ∨ (and possibly →, ↔ as derived ones) whose truth table exactly matches the given output column.

给定一组 m 个原子命题 A₁, A₂, …, Aₘ，以及一张为这 m 个命题的 2ᵐ 种真值组合中的每一种都指定输出值（0 或 1）的真值表，找出一个涉及 A₁, A₂, …, Aₘ 以及联结词 ¬, ∧, ∨（也可能使用 →, ↔ 作为导出联结词）的逻辑表达式，使其真值表与给定的输出列完全相符。

The problem always has at least one solution, and in fact infinitely many equivalent solutions, because logical expressions can be rewritten using double negation, De Morgan’s laws, or other equivalences. The goal is often to find the simplest or most illuminating expression.

该问题始终存在至少一个解，实际上存在无穷多个等价的解，因为逻辑表达式可以利用双否律、德摩根律或其它等价关系进行重写。目标通常是找到最简单或最有启发性的表达式。

4. Building the Disjunctive Normal Form (DNF) | 构造析取范式 (DNF)

The Disjunctive Normal Form, also called the sum‑of‑products, constructs a proposition that is an OR (∨) of AND‑terms (minterms). Each minterm corresponds to a single row of the truth table where the output is 1. For that row, we form a conjunction of literals: each atomic proposition that is true in that row appears as itself, and each atomic proposition that is false appears negated.

析取范式，也称为积之和范式，它构造出的命题是由若干与项（最小项）通过 OR (∨) 连接而成的。每一个最小项对应于真值表中输出为 1 的一行。对于这一行，我们生成一个文字合取式：在该行中为真的每个原子命题保留原形，为假的每个原子命题则取其否定。

For instance, if we have propositions P, Q, and R, and a particular row has P=T, Q=F, R=T producing output 1, the corresponding minterm is P ∧ ¬Q ∧ R. We then join all such minterms with ∨. The resulting DNF expression yields 1 for every row that gave a 1, and 0 elsewhere – exactly matching the table.

例如，假设我们有命题 P, Q, R，其中某一行取值为 P=T, Q=F, R=T 且输出为 1，则对应最小项为 P ∧ ¬Q ∧ R。随后，将所有这类最小项用 ∨ 连接起来。得到的 DNF 表达式会在每一个原本给出 1 的行输出 1，而在其它行输出 0——恰好与真值表吻合。

The DNF method is constructive and mechanical, making it a powerful first approach to the inverse truth‑table problem.

DNF 方法是构造性的、机械式的，这使它成为解决逆真值表问题的一种强有力的首选方法。

5. Building the Conjunctive Normal Form (CNF) | 构造合取范式 (CNF)

Complementary to DNF, the Conjunctive Normal Form (product‑of‑sums) builds a proposition that is an AND (∧) of OR‑clauses (maxterms). Here we focus on the rows where the output is 0. For each such row, we write a clause that is false exactly for that assignment. A clause is a disjunction of literals: each proposition that is true in the row appears negated, and each that is false appears in its original form.

与 DNF 互补，合取范式（和之积范式）构造出的命题是由若干或子句（最大项）通过 AND (∧) 连接而成的。这里我们重点考察输出为 0 的行。对于每一个这样的行，我们写出一个恰好在该赋值下为假的子句。该子句是若干文字的析取式：在该行中为真的命题取否定形式，为假的命题则保持原形。

Using the same three propositions P, Q, R, suppose a row with P=F, Q=T, R=F gives output 0. The corresponding maxterm is P ∨ ¬Q ∨ R. When we AND together all such maxterms, the resulting expression outputs 0 exactly on those rows and 1 on all others – again matching the target column perfectly.

仍然使用三个命题 P, Q, R，假设某一行 P=F, Q=T, R=F 对应输出 0，那么相应的最大项为 P ∨ ¬Q ∨ R。将所有这类最大项用 ∧ 连接起来后，得到的表达式恰好在这些行上输出 0，而在其余行输出 1——再次完美匹配目标列。

Choosing between DNF and CNF often depends on which has fewer terms in a given truth table; both are systematic and reliable.

在 DNF 和 CNF 之间作出选择，往往取决于在给定真值表中哪一种形式的项数更少；两者都是系统且可靠的方法。

6. Worked Example: DNF from a Small Table | 示例：从小型真值表到 DNF

Let us consider a truth table for two propositions P and Q with target output column F (1 for true, 0 for false):

我们考虑包含两个命题 P 和 Q 的一张真值表，目标输出列 F（1 代表真，0 代表假）：

P	Q	F
0	0	0
0	1	1
1	0	1
1	1	0

To construct the DNF, we select the rows where F = 1: (P=0, Q=1) and (P=1, Q=0). The minterms are ¬P ∧ Q and P ∧ ¬Q. Therefore, the DNF expression is (¬P ∧ Q) ∨ (P ∧ ¬Q). This is recognisable as the exclusive or (XOR) of P and Q, often written P ⊕ Q.

为了构造 DNF，我们选出 F=1 的行：(P=0, Q=1) 和 (P=1, Q=0)。最小项分别为 ¬P ∧ Q 和 P ∧ ¬Q。因此 DNF 表达式为 (¬P ∧ Q) ∨ (P ∧ ¬Q)。这可以看作是 P 和 Q 的异或运算 (XOR)，通常写作 P ⊕ Q。

This example illustrates how a truth table that looks irregular can translate directly into a clean logical formula.

这个示例说明，一张看起来不规律的真值表可以直接翻译成一个整洁的逻辑公式。

7. Worked Example: CNF from a Three‑Variable Table | 示例：从三变量真值表到 CNF

Imagine a truth table for propositions A, B, C, where the output G is 1 in most rows except two: when (A=0, B=1, C=0) and when (A=1, B=1, C=1). The CNF method instructs us to look at the zero‑output rows. For (0,1,0) we form the clause A ∨ ¬B ∨ C, because A is false (so A appears as itself), B is true (so ¬B), C is false (so C). For (1,1,1) the clause becomes ¬A ∨ ¬B ∨ ¬C. The final CNF is (A ∨ ¬B ∨ C) ∧ (¬A ∨ ¬B ∨ ¬C).

设想一张关于命题 A, B, C 的真值表，其中输出 G 在大多数行都为 1，只有两行例外：当 (A=0, B=1, C=0) 和当 (A=1, B=1, C=1) 时。CNF 方法让我们着眼于输出为 0 的行。对于 (0,1,0) 我们构造子句 A ∨ ¬B ∨ C，因为 A 为假（故取原形 A），B 为真（故取 ¬B），C 为假（取 C）。对于 (1,1,1)，子句变为 ¬A ∨ ¬B ∨ ¬C。最终的 CNF 为 (A ∨ ¬B ∨ C) ∧ (¬A ∨ ¬B ∨ ¬C)。

This CNF expression is a compact representation of the condition “it is not the case that (A=0 and B=1 and C=0) and not the case that (A=1 and B=1 and C=1)”. By applying De Morgan’s laws, one could also rewrite it to see its equivalence to other forms.

这个 CNF 表达式紧凑地表达了“‘A=0 且 B=1 且 C=0’不成立，并且‘A=1 且 B=1 且 C=1’也不成立”这一条件。应用德摩根律，还可以将其改写为其它等价形式。

8. Simplifying the Canonical Expressions | 简化范式表达式

DNF and CNF obtained directly from a truth table are often lengthy, containing many literals and terms. In IB Mathematics, students are encouraged to simplify these expressions using algebraic laws: identity, domination, idempotent, commutative, associative, distributive, absorption, and De Morgan’s laws. Simplification can reduce the number of gates in a circuit or make a statement easier to analyse.

直接从真值表得到的 DNF 和 CNF 往往很长，包含许多文字和项。在 IB 数学中，鼓励学生使用代数定律来简化这些表达式：同一律、支配律、幂等律、交换律、结合律、分配律、吸收律以及德摩根律。简化可以减少电路中的门数，或使陈述更易于分析。

For example, the DNF (¬A ∧ ¬B ∧ C) ∨ (¬A ∧ B ∧ C) can be simplified by factoring ¬A ∧ C out of both terms, yielding ¬A ∧ C ∧ (¬B ∨ B), which reduces to ¬A ∧ C because (¬B ∨ B) is always true. Such algebraic manipulation reinforces students’ understanding of logical equivalence and prepares them for more advanced proofs.

例如，DNF 表达式 (¬A ∧ ¬B ∧ C) ∨ (¬A ∧ B ∧ C) 可以从两项中提取公因式 ¬A ∧ C，得到 ¬A ∧ C ∧ (¬B ∨ B)，由于 (¬B ∨ B) 恒真，表达式简化为 ¬A ∧ C。这类代数操作巩固了学生对逻辑等价的理解，并为他们进行更高级的证明做好准备。

9. Verifying Your Solution | 验证你的解

After constructing an expression, it is crucial to verify its correctness by building its truth table and comparing it to the original target column. This does not need to be done mentally; a systematic computation for all 2ⁿ rows confirms that no mistake was made in writing minterms or maxterms.

在构造出一个表达式后，关键一步是建立它的真值表并与原始目标列进行比较，以验证其正确性。这并不需要心算；对所有 2ⁿ 行进行系统计算，即可确认在书写最小项或最大项时没有出错。

In an exam or while using computational tools, this verification step catches common errors such as confusing a row’s truth assignment, omitting a negation, or misplacing parentheses. The ability to verify solutions also helps students self‑assess their understanding of the inverse truth‑table problem.

在考试中或在使用计算工具时，这一验证步骤可以发现常见错误，例如混淆某行的真值赋值、遗漏否定符号或放错括号。验证解的能力也有助于学生自我评估对逆真值表问题的理解。

10. Multiple Solutions and Logical Equivalence | 多个解与逻辑等价

Because different logical expressions can have identical truth tables, the inverse truth‑table problem does not have a unique answer. For instance, P → Q, ¬P ∨ Q, and ¬(P ∧ ¬Q) all share the same truth table. When solving an inverse problem, you may produce one form while your classmate produces a different‑looking one, yet both can be correct.

由于不同的逻辑表达式可以拥有完全相同的真值表，逆真值表问题并没有唯一答案。例如，P → Q, ¬P ∨ Q 以及 ¬(P ∧ ¬Q) 都共享同一张真值表。在求解逆问题时，你可能得出了一种形式，而你的同学得出了另一种不同的形式，但两者都可能是正确的。

Showing that two different syntheses are equivalent is an excellent exercise in applying logical identities. This aspect of the problem underscores the richness of boolean algebra and directly connects to the IB Mathematics emphasis on the logic of mathematical reasoning and proof.

证明两个不同的合成式等价，是应用逻辑恒等式的绝佳练习。逆问题的这一面凸显了布尔代数的丰富性，并直接与 IB 数学强调的数学推理与证明中的逻辑相联系。

11. Connection to Digital Circuits and Beyond | 与数字电路及其它领域的联系

Although this article is framed within IB Mathematics, the inverse truth‑table problem is the foundation of combinational logic circuit design. Engineers start with a specification in the form of a truth table and use DNF or CNF to derive a circuit of AND, OR, and NOT gates. Minimisation techniques such as Karnaugh maps or the Quine–McCluskey algorithm further reduce complexity, but the core idea remains the same as what students learn in the IB classroom.

虽然本文设定在 IB 数学的框架内，但逆真值表问题是组合逻辑电路设计的基础。工程师们从一张以真值表形式提供的规格说明出发，利用 DNF 或 CNF 推导出由与门、或门和非门组成的电路。卡诺图或奎因–麦克拉斯基算法等极小化技术可以进一步降低复杂度，但核心思想与学生们在 IB 课堂上学到的是一致的。

The same logical reasoning also underpins conditional statements in programming, database queries, and artificial intelligence rule bases. Recognising the connection between abstract truth tables and real‑world systems motivates learners and showcases the practical power of pure mathematics.

同样的逻辑推理也支撑着编程中的条件语句、数据库查询以及人工智能规则库。认识到抽象真值表与现实世界系统之间的联系，能够激励学习者，并展示纯数学的实际力量。

12. Common Pitfalls and Exam Tips | 常见陷阱与考试技巧

When constructing a minterm for a DNF, ensure that every atomic proposition appears exactly once, either in original or negated form. Missing one variable leads to an expression that does not fully constrain the output.
在为 DNF 构造最小项时，确保每个原子命题恰好出现一次，要么以原形、要么以否定形式。遗漏一个变量会导致表达式不能完整约束输出。
For CNF maxterms, the rule of negating the true propositions is the opposite of DNF – double‑check you have not instinctively applied the DNF pattern.
对于 CNF 最大项，否定那些为真的命题这一规则与 DNF 相反——要反复检查，避免不自觉地套用了 DNF 的模式。
Always count the number of rows in the truth table. For n variables, there must be 2ⁿ rows; if the table provided has fewer, you may be dealing with a “don’t care” condition, which is a more advanced scenario not typically examined in standard IB questions but worth being aware of.
始终要数清真值表的行数。对于 n 个变量，必须有 2ⁿ 行；如果给出的表行数更少，你可能遇到了“无关项”条件，那是一种更复杂的情况，标准 IB 考题中并不常见，但值得注意。
Simplifying your final answer using Boolean algebra not only makes it neater but also reduces the risk of transcription errors in further questions.
用布尔代数简化最终答案，不仅能让答案更整洁，还能降低在后续问题中转录时出错的风险。

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

The Inverse Truth-Table Problem | 逆真值表问题