Classical Defintions Flashcards
(72 cards)
A function is computable if
given any input the computer provides the output within a finite amount of time
Edge decision problem
The input is a nondirected graph. The output is 1 if the number of edges in the graph is larger or equal than m, and it is 0 if the graph has a number of edges smaller than m.
Intuitively, what is the complexity of a function?
The complexity is the minimal amount of elementary operations that a computer needs to evaluate a function as a function of the input size n
Define a Boolean function
Define an m-valued Boolean function
Define a basis
A basis is a set of Boolean functions
De Morgan basis
AND, OR, NOT
Monotone basis
AND, OR
Define a logic circuit of n inputs
A logic circuit of n inputs is defined as a directed, acyclic graph
G = (V, E) for which each vertex v in V satisfies one of the following:
• v has indegree (fan-in) 0 and is called an input xi for some i in {1,2,…,n};
• v has in degree k > and is labelled with g in B , where g is a k-ary Boolean function and with an ordering on the incoming edges to v.
Axiom of Boolean Algebra: closure
There exists a domain Bn having at least two distinct element and two binary operations (and, or), such that if x and y are in Bn, so are (x and y) and (x or y)
Axiom of Boolean Algebra: identity elements
x or 0 = x
x and 1 = x
Axiom of Boolean Algebra: commutativity
x and y = y and x
x or y = y or x
Axiom of Boolean Algebra: distributivity
x or ( y and z ) = (x or y) and (x or z)
x and ( y or z ) = (x and y) or (x and z)
Axiom of Boolean algebra: complementation
If x is in B there exists x bar in b such that x and x bar is 0 and x or x bar is 1
x and 1 =
x
x or 0 =
x
x bar bar =
x
x or x =
x
x and x =
x
Theorem of Boolean algebra: associativity
x or ( y or z) = (x or y) or z = x or y or z
Theorem of Boolean algebra: de Morgan’s law
Write an expression for the XOR gate in terms of Boolean algebra
Define a complete basis
A basis B is complete if any Boolean function can be computed in an B-circuit
