ALevel-CS Chapter 19 Logic circuits and Boolean algebra
19.01 Logic circuits
Key Terms
- Half adder circuit - a circuit which performs binary addition of two individual bits
- Full adder circuit - a circuit which performs binary addition of two individual bits and an input carry bit
The half adder
half adder logic
half adder truth table
half adder circuit
The simplest circuit that can be used for binary addition is the half adder.
The circuit takes two input bits and outputs a sum bit (S) and a carry bit (C).
The full adder
The full adder is a circuit that has three inputs including the previous carry bit.
The truth table for a full adder
A possible implementation of a full adder
A full adder circuit constructed from NAND gates
19.02 Sequential logic circuits
Key Terms
- Combinational circuit - a circuit in which the output is dependent only on the input values
- Sequential circuit - a circuit in which the output depends on the input values and the previous output
触发器 (flip-flop)
触发器是一种能存储一位二进制数码的基本电路，它能够自行保持“1”或“0”两个稳定的状态，又称为双稳态电路。在不同的输入信号作用下，其输出可以置成 1 态或 0 态，并且当输入信号消失后，触发器获得的新状态能保持下来。触发器是数字电路中广泛应用的器件之一，在计数器、智力抢答器、计算机、数码相机、数字式录音机中都能见到它。
The SR flip-flop
The SR flip-flop or ‘latch’ is a simple example of a sequential circuit. It can be constructed with two NAND gates or two NOR gates.
The flip-flop is therefore a two-state device. Either it has Q=1 and Q’=0 or it has the reverse.
These properties explain why the SR flip-flop can be used as a storage device for 1 bit and therefore could be used as a component in RAM because a value is stored but can be altered.
The JK flip-flop
In addition to the possibility of entering an invalid state there is also the potential for a circuit to arrive in an uncertain state if inputs do not arrive quite at the same time. In order to prevent this, a circuit may include a clock pulse input to give a better chance of synchronising inputs.
The JK flip-flop behaves in a similar way to the SR flip-flop as a storage device for one bit. The JK flip-flop a more reliable device because there is no combination of input states that leave uncertainty as to which values are stored.
19.03 Boolean algebra basics
Boolean algebra basics
you can use the terms ‘product’ and ‘sum’ in the context of Boolean algebra.
Example
19.04 Boolean algebra applications
Creating a Boolean algebra expression directly from a truth table
The Boolean algebra representation of a logic circuit
19.05 Karnaugh maps (K-maps)
卡诺图简化法
诺图相邻性的特点保证了几何相邻两方格所代表的最小项只有一个变量不同。因此，若相邻的方格都为1（简称1格）时，则对应的最小项就可以合并。合并的结果是消去这个不同的变量，只保留相同的变量。这是图形化简法的依据。
综上所述，卡诺图具备以下特性：
卡诺图中两个相邻1格的最小项可以合并成一个与项，并消去一个变量。
卡诺图中四个相邻1格的最小项可以合并成一个与项，并消去两个变量。
卡诺图中八个相邻1格的最小项可以合并成一个与项，并消去三个变量。
首先，有这么几点需要明确：
列出逻辑函数的最小项表达式，由最小项表达式确定变量的个数（如果最小项中缺少变量，应按例的方法补齐）。
画出最小项表达式对应的卡诺图。
将卡诺图中的1格画圈，一个也不能漏圈，否则最后得到的表达式就会与所给函数不等；1格允许被一个以上的圈所包围。
圈的个数应尽可能得少。即在保证1格一个也不漏圈的前提下，圈的个数越少越好。因为一个圈和一个与项相对应，圈数越少，与或表达式的与项就越少。
按照2k个方格来组合（即圈内的1格数必须为1，2，4，8等），圈的面积越大越好。因为圈越大，可消去的变量就越多，与项中的变量就越少。
每个圈应至少包含一个新的1格，否则这个圈是多余的。
用卡诺图化简所得到的最简与或式不是唯一的。
例1：
错误 （多画一个圈）
正确
例2
例4：
错误（圈的面积不够大）
例3
错误（有一个圈无新的1格）
Karnaugh maps
A Karnaugh map is a method of creating a Boolean algebra expression from a truth table.
A K-map can make the process much easier than if you use sum-of-products to create minterms.
The interpretation of a Karnaugh map follows these rules.
- Only cells containing a 1 are considered.
- Groups of cells containing 1s are identified where possible, with a group being a row, a column or a rectangle.
- Groups must contain 2, 4, 8 and so on cells.
- Each group should be as large as possible.
- Groups can overlap and all overlapping groups must be used.
- If an individual cell cannot be contained in any group it is treated as being a group.
- Within each group, the only input values retained are those which retain a constant value throughout the group.
Example 19.03 Using a K-map to interpret a three-input problem
