Combinational Logic 1

Hirsun大约 17 分钟

Combinational Logic 1

Digital Logic

Introduction

Digital Logic 数字逻辑

计算机中的操作基于数字/二进制数据的处理。

数字逻辑：分析计算机系统中的离散(discrete)/二进制数据

将现实世界的信号(signals)表示为二进制数据
对二进制数据进行逻辑运算
数字电路(gigital circuit)的设计(implement)和实现：逻辑门(logic gates)，基本组件（加法器「adder」，解码器「decoder」等），电路（circuits）

Example

现实问题：考虑一个0到9层的电梯，如果您按一个按钮（0-9），则要显示数字，How to implement(实现) this real-world functionality(功能)?

使用组合逻辑实现

The Overview

Boolean Algebra

In working with logic relations in digital form, we need a set of rules for symbolic manipulation which will enable us to simplify complex expressions and solve for unknowns. Originally, Boolean algebra which was formulated by George Boole, an English mathematician (1815-1864) described propositions whose outcome would be either true or false. In computer work it is used in addition to describe circuits whose state can be either 1 (true) or 0 (false).Using the relations defined in the AND, OR and NOT operation......

Boolean Algebra is useful from both aspects(从两个方面来讲)

implementation (design of digital circuit): given a desired boolean function, Boolean algebra can be applied to develop a simplified implementation of that function「实现（数字电路设计）：给定所需的布尔函数，布尔代数可用于开发该函数的简化实现」
analysis: Boolean algebra provides an efficient way to describe the function of a digital circuit「分析：布尔代数提供了一种描述数字电路功能的有效方法」
P1 : X = 0 or X = 1
P2 : 0 0 = 0
P3 : 1 + 1 = 1
P4 : 0 + 0 = 0
P5 : 1 1 = 1
P6 : 1 0 = 0 1 = 0
P7 : 1 + 0 = 0 + 1 = 1

Variables and Logic Operations

A variable may take on the value 1 (True) or 0 (False)

Basic logical operations

Hirsun的批注：乘号（and）表示且，加号（or）表示或。非且（XAND），非或（NOR）。思想上NOR表示先或再全否

Switching Functions

We can use all the logical operations to construct a switching function Z = f (A,B, C, …)

input takes value 0 or 1, output also takes value 0 or 1 — this is why it’s called “switch”
switch function defines a mapping from a combination of input values to an output value

example Z = f (A,B); there are four different combinations of input values (0,0), (0,1), (1,0), (1,1) — different way of mapping defines different switching functions

Truth Table

A truth table defines the mapping from the combination of input values to output

Consider switching functions defined over N variables, how many possible switching functions could we have?

That is, how many different truth tables can we construct?

Hint: first check how many rows in the truth table (= number of combinations of input values)

Properties

Properties「特性」

Basic Postulates — stated without proof

Basic Postulates— stated without proof「公理，无需证明」

some other properties that could be proved from postulates
in any case, you can check this properties by truth table

note the difference from ordinary algebra: some are very similar; others are quite different

Basic Postulates

The under table provides the basic postulates. Each theorem is described by two parts that are duals of each other.

Commutative law（交换律） implies that the order of the input does not matter (image two wires to a gate)
Distributive law: similar to algebra, multiplication (AND) has the distributive property over adding (OR); different to algebra, OR has the distributive property over AND — A +BC = (A+B)(A+C)

Duality

The dual of a Boolean expression is the expression one obtains by interchanging addition and multiplication and interchanging 0's and 1's.「布尔表达式的对偶是通过互换加法和乘法以及互换0和1获得的表达式。」

If one expression is correct, its dual is also correct

Example, in the previous table, AB = BA and A+B = B+A

How to get the dual of an expression?

replace AND with OR; replace OR with AND
replace constant 1 with 0; replace constant 0 with 1
check duality in the previous table

Other Properties

Note the duality in the first and second column (for NOT, there’s no dual operation, thus no duality)

De Morgan's Theorem 「德摩根定理」 is important!!!

in the first equation, no AND operation (change AND to OR)
in the second equation, no OR operation (change OR to AND)
reduce the types of operations — important for implementation
completeness of functionality — a set of operations (gates) that can be
used to implement all logical expressions

learning meaning

Transform one expression to another form with specific features「将一个表达式转换为具有特定功能的另一种形式」

Simplification (Absorption theorem「Absorption theorem」 and Consensus Theorem「Consensus Theorem」)
Contain only certain operations in the expression (DeMorgan’s theorem)
Easy to implement「表达式中仅包含某些运算（德摩根定理）」

Generally, we call this process as Algebraic Simplification「代数简化」

different people may have different results
depending on the purpose, we may need different results

Absorption Theorem「吸收定理」

A (A+B) = A; A+AB = A
no B in the expression — simplified, less input

Consensus Theorem 「共识定理」

simplified, less operations「简化，减少操作」

Completeness of Functionality

Functionally Complete Sets of Gates

AND, OR, NOT: self evident
AND, NOT: question, can OR be expressed by AND and NOT? Yes
OR, NOT: same as above
NAND
NOR

Prove (AND, NOT) is a Complete Set of Gates

Prove (NAND) is a Complete Set of Gates

Use NAND to express A OR B

待补充

Show NOR is a complete set of gates

待补充

Two Rules of Thumbs

We can write the same logical expression in different forms (algebraic simplification)

There are two general rules

less operations (gates)
less types of operations (gates)

There is a trade-off between these two rules「在这两个规则之间需要权衡取舍」

附件

Laws and Theorems of Boolean Algebra


1a.	X • 0 = 0	1b.	X + 1 = 1	Annulment Law
2a.	X • 1 = X	2b.	X + 0 = X	Identity Law
3a.	X • X = X	3b.	X + X = X	Idempotent Law
4a.	X • X = 0	4b.	X + X = 1	Complement Law
5.	X = X			Double Negation Law
6a.	X • Y = Y • X	6b.	X + Y = Y + X	Commutative Law
7a.	X (Y Z) = (X Y) Z = (X Z) Y = X Y Z			Associative Law
7b.	X + (Y + Z) = (X + Y) + Z = (X + Z) + Y = X + Y + Z			Associative Law
8a.	X • (Y + Z) = X Y + X Z	8b.	X + Y Z = (X + Y) • (X + Z)	Distributive Law
9a.	X • Y = X + Y	9b.	X + Y = X • Y	de Morgan's Theorem
10a.	X • (X + Y) = X	10b.	X + X Y = X	Absorption Law
11a.	(X + Y) • (X + Y) = X	11b.	X Y + X Y = X	Redundancy Law
12a.	(X + Y) • Y = XY	12b.	X Y + Y = X + Y	Redundancy Law
13a.	(X + Y) • (X + Z) • (Y + Z) = (X + Y) • (X + Z)			Consensus Law
13b.	X Y + X Z + Y Z = X Y + X Z			Consensus Law
14a.	X ⊕ Y = (X + Y) • (X + Y)	14b.	X ⊕ Y = X Y + X Y	XOR Gate
15a.	X ⊙ Y = (X + Y) • (X • Y)	15b.	X ⊙ Y = X Y + X Y	XNOR Gate
15c.	X ⊙ Y = (X + Y) • (X + Y)			XNOR Gate

Combinational Logic 1

Combinational Logic 1

Digital Logic

Introduction

Example

The Overview

Boolean Algebra

Variables and Logic Operations

Basic logical operations

Switching Functions

Truth Table

Properties

Basic Postulates — stated without proof

Basic Postulates

Duality

Other Properties

learning meaning

Absorption Theorem「吸收定理」

Consensus Theorem 「共识定理」

Completeness of Functionality

Prove (AND, NOT) is a Complete Set of Gates

Prove (NAND) is a Complete Set of Gates

Use NAND to express A OR B

Show NOR is a complete set of gates

Two Rules of Thumbs

附件

Laws and Theorems of Boolean Algebra

推荐网站

引用

Combinational Logic 1

# Combinational Logic 1

# Digital Logic

# Introduction

# Example

# The Overview

# Boolean Algebra

# Variables and Logic Operations

# Basic logical operations

# Switching Functions

# Truth Table

# Properties

# Basic Postulates — stated without proof

# Basic Postulates

# Duality

# Other Properties

# learning meaning

# Absorption Theorem「吸收定理」

# Consensus Theorem 「共识定理」

# Completeness of Functionality

# Prove (AND, NOT) is a Complete Set of Gates

# Prove (NAND) is a Complete Set of Gates

# Use NAND to express A OR B

# Show NOR is a complete set of gates

# Two Rules of Thumbs

# 附件

# Laws and Theorems of Boolean Algebra

# 推荐网站

# 引用

Combinational Logic 1

Digital Logic

Introduction

Example

The Overview

Boolean Algebra

Variables and Logic Operations

Basic logical operations

Switching Functions

Truth Table

Properties

Basic Postulates — stated without proof

Basic Postulates

Duality

Other Properties

learning meaning

Absorption Theorem「吸收定理」

Consensus Theorem 「共识定理」

Completeness of Functionality

Prove (AND, NOT) is a Complete Set of Gates

Prove (NAND) is a Complete Set of Gates

Use NAND to express A OR B

Show NOR is a complete set of gates

Two Rules of Thumbs

附件

Laws and Theorems of Boolean Algebra

推荐网站

引用