Information Technology Reference
In-Depth Information
it is false, namely, by assuming “ L contains only strings with an odd number of 1's” and
showing that this statement is false. In particular, we show that L contains the string 11. From
the definition of the Kleene closure, L contains strings of all lengths in the “letters” 00 and 1.
Thus, it contains a string containing two instances of 1 and the predicate P is true.
Induction and proof by contradiction can also be used to establish the pigeonhole principle.
The pigeonhole principle states that if there are n pigeonholes, n + 1 or more pigeons, and
every pigeon occupies a hole, then some hole must have at least two pigeons. We reformulate
the principle as follows:
LEMMA 1.3.2 Given two finite sets A and B with |A| > |B| ,theredoesnotexista naming
function ν : A
B that gives to each element a in A a name ν ( a ) in B such that every element
in A has a unique name.
= 1. To show that the statement is Tr u e , assume it is False and show
that a contradiction occurs. If it is False , every element in A can be given a unique name.
However,sincethereisonename(theoneelementof B ) and more than one element in A ,
we have a contradiction.
|
B
|
Proof BASIS:
INDUCTION HYPOTHESIS: There is no naming function ν : A
B when
|
B
|≤
n and
|
A
|
>
|
B
|
.
INDUCTIVE STEP: When
|
B
|
= n + 1and
|
A
|
>
|
B
|
we show there is no naming function
ν : A
B . If two elements of A have the name b , the desired
conclusion holds. If not, remove b from B , giving the set B ,andremovefrom A the
element, if any, whose name is b , giving the set A .Since
B .Consideranelement b
A |
B |
B |≤
n ,bythe
induction hypothesis, there is no naming function obtained by restricting ν to A .Thus,
the desired conclusion holds.
|
>
|
and
|
1.4 Computational Models
A variety of computer models are examined in this topic. In this section we give the reader
a taste of five models, the logic circuit, the finite-state machine, the random-access machine,
the pushdown automaton, and the Turing machine. We also briefly survey the problem of
language recognition.
1.4.1 Logic Circuits
A logic gate is a physical device that realizes a Boolean function. A logic circuit ,asdefined
in Section 1.2 , is a directed acyclic graph in which all vertices except input vertices carry the
labels of gates.
Logic gates can be constructed in many different technologies. To make ideas concrete,
Fig. 1.3 (a) and (b) show electrical circuits for the AND and OR gates constructed with batteries,
bulbs, and switches. Shown with each of these circuits is a logic symbol for the gate. These
symbols are used to draw circuits, such as the circuit of Fig. 1.3 (c) for the function ( x
z .
When electrical current flows out of the batteries through a switch or switches in these circuits,
the bulbs are lit. In this case we say the value of the circuit is Tr u e ; otherwise it is False .Shown
below is the truth table for the function mapping the values of the three input variables of the
circuit in Fig. 1.3 (c) to the value of the one output variable. Here x , y ,and z have value 1
y )
Search WWH ::




Custom Search