- What is logic
- Boolean Logic
- Boolean Functions
- Conjunctive and Disjunctive Normal Form
- Canonical DNF
- Karnaugh Maps
- Boolean Algebras
What is logic
Logic is about formalizing reasoning and defining truth
- Adding rigour
- Removing ambiguity
- Mechanizing the process of reasoning
Loose history of logic
(Ancient times): Logic exclusive to philosophy
Mid-19th Century: Logical foundations of Mathematics (Boole, Jevons, Schr¨oder, etc)
1910: Russell and Whitehead’s Principia Mathematica
1928: Hilbert proposes Entscheidungsproblem
1931: G¨odel’s Incompleteness Theorem
1935: Church’s Lambda calculus
1936: Turing’s Machine-based approach
1930s: Shannon develops Circuit logic
1960s: Formal verification; Relational databases
Logic in Computer Science
Computation = Calculation + Symbolic manipulation
Logic as 2-valued computation (Boolean logic):
- Circuit design
- Code optimization
- Boolean algebra
- Nand game
Logic as symbolic reasoning (Propositional logic, and beyond):
- Formal verification
- Proof assistance
- Knowledge Representation and Reasoning
- Automated reasoning
- Databases
Boolean Logic
Boolean logic is about performing calculations in a “simple” mathematical structure.
- complex calculations can be built entirely from these simple ones
- can help identify simplifications that improve performance at the circuit level
- can help identify simplifications that improve presentation at the programming level
The Boolean Algebra $\mathbb{B}$
Definition
The (two-element) Boolean algebra is defined to be the set $\mathbb{B}$ ={0,1}, together with the functions
, defined as follows:
Alternative notation
For $\mathbb{B}$
For $!x$
For $x \&\& y$
For $x || y$
Alternative notation
Definition
The (two-element) Boolean algebra is defined to be the set $\mathbb{B}$ ={false,true}, together with the functions $! :\mathbb{B} \to \mathbb{B}, \&\&: B^2 →B, and \quad ∥: B^2 →B$, defined as follows:
x | !x |
---|---|
false | true |
true | false |
x | y | x&&y |
---|---|---|
false | false | false |
false | true | false |
true | false | false |
true | true | true |
x | y | x or y |
---|---|---|
false | false | false |
false | true | true |
true | false | true |
true | true | true |
Properties:Commutativity,Associativity,Distribution,Identity,Complementation
We observe that !, &&, and ∥ satisfy the following:
For all $x,y,z ∈ \mathbb{B}$:
Commutativity
Associativity
Distribution
Identity
Complementation
Boolean Functions
Definition
An n-ary Boolean function is a map f : $\mathbb{B}^n \to \mathbb{B}$.
Q: How many unary Boolean functions are there? How many binary functions? N-ary?
$\mathbb{B}^2 \to \mathbb{B}$, we found there are 4 possible inputs and 2 possible outputs of each input, so here is $2222=16$ *possible outputs.
Note, the question didnot mention the specific function, so don’t think 0,0->0 directly, cause maybe 0,0->1 function. Additionally, the different outputs should multiple as possible results. Just regard different combination of the outputs as a new function.
4 means how many input here.
How many unary Boolean functions are there? n-ary?
unary means One-dimensional relation. So how many, it’s 2+2=4 obviously.
So n-ary is:
example
$!$ is a unary Boolean function
$\&\&, ∥$ are binary Boolean functions
$f(x,y) =!(x \&\& y)$ is a binary boolean function (NAND)
$And(x_0,x_1,…) = (···((x_0 \&\& x_1) \&\& x_2)···)$ is a (family) of Boolean functions
$Or(x_0,x_1,…) = (···((x_0 ∥ x_1) ∥ x_2)···)$ is a (family) of Boolean functions
Application: Adding two one-bit numbers
Question. How can we implement:
$add: \mathbb{B}^2 \to \mathbb{B}^2$
defined as
x | y | add(x,y) |
---|---|---|
0 | 0 | 00 |
0 | 1 | 01 |
1 | 0 | 01 |
1 | 1 | 10 |
Take Notice
Observe that this is not a Boolean function. Boolean functions can output either 0 or 1 (a single bit). This function outputs 2 bits.
(Short) Answer. Use two Boolean functions!
Take Notice
Digital circuits are just sequences of Boolean functions.
Conjunctive and Disjunctive Normal Form
Definition
A literal is a unary Boolean function
A minterm is a Boolean function of the form $And(l_1(x_1),l_2(x_2),…,l_n(x_n))$ where the $l_i$ are literals
A maxterm is a Boolean function of the form $Or(l_1(x_1),l_2(x_2),…,l_n(x_n))$ where the $l_i$ are literals
A CNF Boolean function is a function of the form $And(m_1,m_2, …)$, where the $m_i$ are maxterms.
A DNF Boolean function is a function of the form $Or(m_1,m_2, …)$, where the $m_i$ are minterms.
Take Notice
CNF
: product of sums; DNF
: sum of products
秘笈:“C与D或”,“C与小D或大”,“min AND, max OR, C与积,D或和”
Examples
Question. Are these functions in CNF? Are they in DNF?
DNF , but not CNF
CNF function, but not DNF
both CNF and DNF
Note! Paul Hunter (lecturor):
Note: CNF/DNF/minterms/maxterms are only concerned with how the formula appears as written. You cannot "change" the formula (e.g. "x can be regarded as x or x") and have things be meaningful.
(x && !y) && z is:
A maxterm
An OR of maxterms: because OR(m) = m, so it is equal to OR((x&&!y)&&z) - therefore it is in DNF
An AND of minterms: because x is a minterm, !y is a minterm, and z is a minterm, so it is equal to AND(x, !y, z) - therefore it is in CNF
Leo Liu:
I'm still confused, why x, !y and z are miniterms? Because x = AND(x)? So x can be considered as literal (x), miniterm (AND(x)), and maxterm (OR(x))?
Paul Hunter:
Yes, that's correct.
AND and OR are "generalizations" of && and ||.
&& and || are functions that take two inputs, AND and OR are (families of) functions that take arbitrarily many inputs.
My thought:
Neither CNF nor DNF
2 Theorems
Every Boolean function can be written as a function in DNF.
Every Boolean function can be written as a function in CNF.
Canonical DNF
Given an n-ary Boolean function $f: \mathbb{B}^n \to \mathbb{B}$ we construct an equivalent DNF Boolean function as follows:
For each $b = (b_1, \dots, b_n) \in \mathbb{B}^n$ we define the minterm
Note, $\mathbb{B}^n$ means $\mathbb{B} \times \mathbb{B} \times \mathbb{B} \times \dots$, so $b = (b_1, \dots, b_n)$ is a product (AND) of them, and the product means minterm.
where
We then define the DNF formula:
that is, $f_{DNF}$ is the disjunction (or) over all minterms corresponding to elements $b ∈ \mathbb{B}$ where $f(b) = 1$.
Note, $m_b$ is the each expression of $l_i(x_i)$. Cause we want to build a DNF, so the external operation is AND().
Note to distinguish the opposite operations. Firstly, $+$ and $\times$; Secondly, $AND()$(CNF,$\times$) and $OR()$(DNF,$+$).
“C与D或,与乘或加”
Theorem
f and $f_{DNF}$ are the same function.
Exercise
Find the canonical DNF form of each of the following expressions in variables x,y,z
- $xy$
- $\overline{z}$
- $xy + \overline{z}$
- $f(x,y,z)=1$
Note Jiaojiao’s handwriting below, the addtional expressions with different colors are the corresponding answers.
Karnaugh Maps
Jiaojiao remark:”Not very useful.”
For up to four variables (propositional symbols) a diagrammatic method of simplification called Karnaugh maps works quite well.
- For every propositional function of k = 2,3,4 variables we construct a rectangular array of $2^k$ cells.
- Column labels and row labels are ordered by Gray code.
- Squares corresponding to the value true are marked with eg “+”.
- We try to cover these squares with as few rectangles with sides 1 or 2 or 4 as possible.
proof process of Karnaugh Maps (K Maps for short)
The section would be in Chinese… just for next quiz of Data Structure.
卡诺图只是为了获取一个随机DNF的方法。
首先需要找到变量 w,x,y,z
,然后我们还知道 f(w, x, y, z)
, 我们先做一个真值表(Truth table),然后我们让f(w, x, y, z)
是随机的0或1.
如下图,右侧真值表,得到左侧卡诺图,这是我们的题目,我们在随机真值的cell中打’+’
画卡诺图,比如4变量,就画4x4=16的table,如果是3变量,就画3x3=9的table。
注意table的title,行列的title一次只变一个。比如,wx->w!x->!w!x->!wx, 不要一下子wx->!w!x,这样会错。
Why, how to use Karnaugh Maps
接下来说卡诺图能解决的问题,主要就是为了消除单个minterm的无关变量,获得DNF的所有minterms。
圈的时候,从最大往最小圈,记得每行每列首位相连。如图,左下侧俩和左上侧俩是最大的,因为一下子占2x2的方的四个cells,所以先圈他俩。
然后开始往小圈,全部的+都被圈完后,就可以得到minterms。
比如图中,有个孤零零的w!x!y!z
,肯定是最后圈,可惜消不了任何变量,因此这个minterm就是w!x!y!z
。
how to correctly circle to eliminate variables?
In the pic of the sample before mid-term test, it is wrong. Because it is not $n \times m$ cells with full $+$.
Follow me, it is the correct way to circle them. We must circle $n \times m$ cells with fully $+$.
blue:xy
green: xz
red: yz
example
Note, the Karnaugh Map is at the first, and then we got the Expression. Don’t confuse the order of the pic and the expression.
Use $2^n$ to circle the cells, and cover all the true cells.
Canonical form would consist of writing all cells separately (6 clauses).
For optimisation, the idea is to cover the + squares with the minimum number of rectangles. One cannot cover any empty cells.
- The rectangles can go ‘around the corner’/the actual map should be seen as a torus.
- Rectangles must have sides of 1, 2 or 4 squares (three adjacent cells are useless).
Of course it is similar to the manual calcute the 0 and 1.
Exercise
The Karnaught Map just generate the expression rapidly.
Boolean Algebras
definition
A Boolean algebra is a structure $(T, \lor, \land, ‘, 0, 1)$ where
- 0, 1 ∈ T
- ∨,∧ : T ×T →T (called join and meet respectively)
- ′ : T→T (called complementation)
property
and the following laws hold for all x,y,z ∈ T:
Commutativity:
Associativity:
Distributivity:
Identity:
Complementation:
Example
The set of subsets of a (singleton) set X = {x}:
- T : Pow(X)=
{{x},∅}
- ∨ (join) : ∪
- ∧ (meet) : ∩
- ′ (complement) : $·^c$
- 0 : ∅
- 1 : $X \qquad (\mathbb{U})$
The Laws of Boolean algebra follow from the Laws of Set Operations.
The two element Boolean Algebra :
where !,&&,∥ are defined as:
- !true = false; !false = true,
- true && true = true; …
- true ∥ true = true; …
Cartesian products of $\mathbb{B}$, that is n-tuples of 0’s and 1’s with Boolean operations, e.g. $\mathbb{B}^4$:
join: $(1,0,0,1) ∨ (1,1,0,0) = (1,1,0,1)$
meet: $(1,0,0,1) ∧ (1,1,0,0) = (1,0,0,0)$
complement: $(1,0,0,1)’ = (0,1,1,0)$
0 : $(0,0,0,0)$
1 : $(1,1,1,1)$
Functions from any set $S$ to $\mathbb{B}$; that is, $\mathbb{B}^S$
If $f,g:S \to \mathbb{B}$ then
Proofs in Boolean Algebras
If you can show that an identity holds using the laws of Boolean Algebra, then that identity holds in all Boolean Algebras.
Example
Claim: In all Boolean Algebras
Proof:
Duality
Definition
If $E$ is an expression defined using variables $(x, y, z, etc)$, constants $(0 and 1)$, and the operations of Boolean Algebra $(∧, ∨, and ‘)$ then $dual(E)$ is the expression obtained by replacing $∧$ with $∨$ (and vice-versa) and $0$ with $1$ (and vice-versa).
Definition
If $(T,∨,∧, ‘,0,1)$ is a Boolean Algebra, then $(T,∧,∨, ‘,1,0)$ is also a Boolean algebra, known as the dual Boolean algebra.
(Dual means the contray operation and element: ∨->∧; ∧->∨; 0->1; 1->0; )
Theorem (Principle of duality)
If you can show $E_1 = E_2$ using the laws of Boolean Algebra, then $dual(E_1) = dual(E_2)$.
Example
We have shown $x ∧x = x$.
By duality: $x ∨ x = x$.
Welcome to point out the mistakes and faults!