Title: Theory / Unimportant / CS / Hardware / Digital logic and computer design / Boolean algebra
Tags: récupéré examplesSwitchExample1 MissingMedia defToAlgebra hasSeenConjDef setMultiplication
On every note of this deck, unless a note says otherwise:
Chapter: 2

Name: \(x\) belongs to \(S\)
Page: 36
Section: 1
Variables: \(S\) a set,
\(x\) an element
Notation: \(x\in S\)

Name: \(x\) does not belong to \(S\)
Page: 36
Section: 1
Variables: \(S\) a set,
\(x\) an element
Notation: \(x\not\in S\)

Name: The set containing exactly \(a_1\), ... and \(a_n\)
Page: 36
Section: 1
Variables: \(a_1,\dots, a_n\) elements
Notation: \(\{a_1,\dots,a_n\}\)

Name: A binary operator
Definition: A rule associating to each pair of elements of \(S\) an element of \(S\)
Page: 36
Section: 1
Variables: \(S\) a set
Denoted by: *

Name: Closure axiom
Definition: For each \(a,b\in S\), \(a*b\in S\)
Page: 36
Section: 1
Variables: \(S\) a set,
\(*\) a binary operator
Example: \(\mathbb N\) and addition

Name: Associative axiom
Definition: \((x*y)*z=x*(y*z)\) for each \(x,y,z\in S\)
Page: 37
Section: 1
Variables: \(S\) a set,
\(*\) a binary operator

Name: Commutative law
Definition: \(x*y=y*x\) for each \(x,y\in S\)
Page: 37
Section: 1
Variables: \(S\) a set,
\(*\) a binary operator
Index: 3
Denoted by: *

Name: An identity
Definition: An element \(e\) such that \(e*x=x*e=x\) for each \(x\in S\)
Page: 37
Section: 1
Variables: \(S\) a set,
\(*\) a binary operator
Index: 3
Example: \(0\)
Denoted by: \(e\)
Applied to: \((\mathbb Z,+)\)

Name: An inverse of \(x\)
Definition: An element \(y\) such that \(y*x=x*y=e\) for each \(x\in S\)
Page: 37
Section: 1
Variables: \(S\) a set,
\(*\) a binary operator with identity
\(x\in S\)
Notation: \(x^{-1}\)
Index: 3
Notation2: \(-x\)

Name: \(*\) is distributive over \(\cdot\)
Definition: \(x*(y\cdot z)=(x*y)\cdot (x* z)\)
Page: 37
Section: 1
Variables: \(S\) a set,
\(*,\cdot\) binary operators with identity
\(x\in S\)
Index: 6
Denoted by: \(+,*\) over \(\mathbb Z\)

Name: A field
Definition: A set with two binary operators, commutative, associative, with identity and inverse, one being distributive over the other
Page: 37
Section: 1
Example: \(\mathbb R\) with \(+\), \(\times\)

Name: A Boolean Algebra
Definition: both operations admits an identity
Page: 38
Definition2: both operations are commutative
Example: Two-valued Boolean algebra
Conjdef: A set, closed under two binary operations \(+_1,+_2\), with at least 2 elements, such that
Definition3: both operations are distributive over the other one.
Name2: A set satisfying Hutington postulates
Definition4: Each elements have a complement for both operations

Name: A complement of \(X\)
Definition: An element \(y\) such that \(x*y=0\)
Page: 38
Variables: \(S\) a set,
\(*\) a binary operator with zero
\(x\in S\)
Context: Boolean Algebra
Denoted by: \(x'\)

Page: 39, 40
Chapter: 2
Name: Two-valued Boolean algebra
Set: \(\{0,1\}\)
*: *
+: +
Commutative: y
Name2: Switching algebra
Name3: Binary logic
¬: \(x\mapsto 1-x\)

Question: Let \(e\) an equation which holds over Boolean algebra
Answer: the equation obtained by reversing OR and AND, and using complement of constant/variables of \(e\), also holds
Page: 41
Chapter: 2
Section: 3
Context: Boolean Algebra
Name: Duality principle

Question: Let \(e\) an equation which holds over Boolean algebra
Answer: the equation obtained by reversing OR and AND, and using complement of constant/variables of \(e\), also holds
Page: 41
Chapter: 2
Section: 3
Name: Duality principle

Question: \(x\cdot 1\)
Answer: equals \(x\)
Page: 41
Chapter: 2
Section: 3
Variables: \(x\) a Boolean variable

Question: \(x+0\)
Answer: equals \(x\)
Page: 41
Chapter: 2
Section: 3
Variables: \(x\) a Boolean variable

Question: \(x\cdot x'\)
Answer: equals \(0\)
Page: 41
Chapter: 2
Section: 3
Variables: \(x\) a Boolean variable
Context: Boolean algebra

Question: \(x+x'\)
Answer: equals \(1\)
Page: 41
Chapter: 2
Section: 3
Variables: \(x\) a Boolean variable

Question: \(x\cdot x\)
Answer: equals \(x\)
Page: 41
Chapter: 2
Section: 3
Variables: \(x\) a Boolean variable

Question: \(x+x\)
Answer: equals \(x\)
Page: 41
Chapter: 2
Section: 3
Variables: \(x\) a Boolean variable

Question: \(x+1\)
Answer: equals \(1\)
Page: 41
Chapter: 2
Section: 3
Variables: \(x\) a Boolean variable

Question: \((x\cdot y)'\)
Answer: equals \(x'+ y'\)
Page: 41
Chapter: 2
Section: 3
Variables: \(x\) a Boolean variable
Name: De morgan

Question: \((x+y)'\)
Answer: equals \(x'\cdot y'\)
Page: 41
Chapter: 2
Section: 3
Variables: \(x\) a Boolean variable
Name: De morgan

Question: \(x\cdot(x+y)\)
Answer: equals \(x\)
Page: 41
Chapter: 2
Section: 3
Variables: \(x\) a Boolean variable
Name: Absorption

Question: \(x+xy\)
Answer: equals \(x\)
Page: 41
Chapter: 2
Section: 3
Variables: \(x\) a Boolean variable
Context: Boolean algebra
Name: Absorption

Question: \((x')'\)
Answer: equals \(x\)
Page: 41
Chapter: 2
Section: 3
Variables: \(x\) a Boolean variable
Name: Involution

Name: Venn diagram
Definition: Overlapping circles, labelled by a variable. Interior of the circle represents the truth of the label, and exterior represents the falsehood.
Page: 44
Section: 3

Name: Boolean function
Definition: An expression formed with binary variables, the two binary operators OR and AND and unary operator NOT, parentheses, and an equal sign
Page: 45
Section: 4

Question: The number of Boolean valuations for \(n\) variables is
Answer: \(2^n\)
Page: 45
Chapter: 2
Section: 4

Question: The number of Boolean function with \(n\) variables is
Answer: \(2^{2^n}\)
Page: 45
Chapter: 2
Section: 4

Name: The truth table of \(f\)
Definition: A table associating to each assignation of the variables a Boolean value
Page: 45
Section: 4
Variables: \(f\) a Boolean function

Name: A literal
Definition: A primed or unprimed variable
Page: 46
Section: 4

Name: A circuit
Definition: Litterals, gates applied to litterals and output of other gates
Page: 46
Section: 4

Name: The complement of \(f\)
Definition: The function obtained by exchanging 0 and 1 in the value of \(F\)
Page: 48
Section: 4
Variables: \(f\) a Boolean function
Notation: \(f'\)

Name: A maxterm
Definition: The sum of \(x\) or \(x'\) for each \(x\in X\)
Page: 49
Section: 5
Variables: \(X\) a set of variables
Name2: A standard sum

Name: A minterm
Definition: The product of \(x\) or \(x'\) for each \(x\in X\)
Page: 49
Section: 5
Variables: \(X\) a set of variables
Name2: A standard product

Name: A normal form of \(f\)
Definition: \(f\) as a sum of minterm or a product of maxterm
Page: 51
Section: 5
Variables: \(X\) a set of variables
\(f:2^X\to 2\) a Boolean function

Page: 51
Section: 5
Notation: \(f\) as a product of maxterm
Variables: \(X\) a set of variables
\(f:2^X\to 2\) a Boolean function
Chapter: 2
Example: Use de Morgan to put negation on atoms.
Uses recursively the rule \((AB)+C=(A+C)(B+C)\)
If some variable is missing from a rule, uses the rule \(A=A+(BB')\)

Page: 51
Section: 5
Notation: \(f\) as a sum of minterm
Variables: \(X\) a set of variables
\(f:2^X\to 2\) a Boolean function
Chapter: 2
Example: Use de morgan to put negation on atoms.
Uses recursively the rule \(A(B+C)=AB+AC\)
If some variable is missing from a rule, uses the rule \(A=A(B+B')\)

Name: Standard form of \(f\)
Definition: \(f\) written as a sum of product, or as a product of sum
Page: 55
Section: 5
Variables: \(X\) a set of variables
\(f:2^X\to 2\) a Boolean function