原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
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