← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

34 第34章 NP完全性

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.780Z

he other two gates takes two binary inputs x and y and produces a single binary output z.

The operation of each gate, or of any boolean combinational element, is defined by a truth table, shown under each gate in Figure 34.7. A truth table gives the outputs of the combinational element for each possible setting of the inputs. For example, the truth table for the OR gate says that when the inputs are x = 0 and y = 1, the output value is z = 1. The symbol ¬ denotes the NOT function, ∧ denotes the AND function, and ∨ denotes the OR function. Thus, for example, 0 ∨ 1 = 1. AND and OR gates are not limited to just two inputs. An AND gate’s output is 1 if all of its inputs are 1, and its output is 0 otherwise. An OR gate’s output is 1 if any of its inputs are 1, and its output is 0 otherwise. A boolean combinational circuit consists

of one or more boolean combinational elements interconnected by wires. A wire can connect

此预览只包含定位所需的摘录和上下文。

原书定位详情

来源:a19c7933-4eda-4176-aebd-30fe7e1ad292

正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea