Aiserman M., Gusev L., Rozonoer L., Smirnova l., Tal A. Logic, Automata, and Algorithms
Подождите немного. Документ загружается.
20
ELEMENTS
OF
MATHEMATICAL LOGIC
other words, there
are
other
cases
inwhichwe can establish identi-
ties similar to
(1.14).
Thus
far,
we have proved
all
identities of functions of one,
two,
or
more variables by
a
test involving substitution of
all
the possible
values of these variables. This method
has
two major disadvantages:
it does not afford any opportunities for deriving new identities and
in this sense
is
passive; in addition, it becomes more and more
laborious as the number of variables increases. Fortunately, how-
ever, we have at our disposal another method based on the use of
certain rules for identical transformations. Thus the collection of
simple functions
-
y=o,
y=x, y=x,8rx,, y=x,vx,,
y
=
XI
+
x2.
y
=
x,
-
x2
(1.15)
may be operated upon by means of
a
system
of
rules, usually
re-
ferred
to
as
the
algebra
of
logic
or
Boolean algebra,
which consists
of
the following identities:
- -
x
=
x,
(1.16)
-
XI
-->
X?
=
x,
v
X?,
(1.17)
(1.18)
(1.19)
(1.20)
(1.21)
(1.22)
(1.23)
(1.24)
(1.25)
Each of these identities may be proved by direct substitution of
all
the possible values of the variables appearingin the left and
the
right
sides
of
the
identity.
PROPOSITIONAL CALCULUS
21
The
OR
and
AND
operations of this algebra have much in com-
mon with addition and multiplication of ordinary algebra. Thus, they
obey the first and second commutative
laws
[identities (1.24)],
as
well
as
the first and second associative
laws
[identities (1.25)].
However, in contrast
to
ordinary algebra, they obey two distributive
laws
rather than one [identities (1.26)]; and “reduction of like
terms”
or
“multiplication of avariable by itself”
are
accomplished
via identities (1.19), without introducing any factors
or
exponents.
This system of identities permits a purely analytical solution
of
a
great variety of problems.
Moreover, standard methods may be
used for some of these solutions.
For
instance, any analytical func-
tion may be transformed directly into
a
normal disjunctive form, a
procedure illustrated by the following example.
EXAMPLE. Let the starting function be
First, let us eliminate the
-+
and
-
signs.
Applying identities
(1.17)
and (1.18),
we
obtain
Next, let
us
eliminate those negation signs that relate not just to
a
single variable but to an entire aggregation
of
such variables.
We
do this by means of identities (1.23) and (1.16) to obtain
Now, in order to
arrive
at
adisjunctive normal form it
is
sufficient
to
expand the expression
in
the braces
as
specified by identity
(1.26a). Simplifying the intermediate results by means
of
(1.16) and
(1.19)
as
we
go along,
we
obtain
y=
(~(X,~~,~x,~v~x1~X~~x,~1~~~2V~~~~v~~l~~~~
=
___
=
(x,
&
XI
&
33
&
X~)V(XI
&
~3
8t
Xp)
V
(XI
&
XI
&
xg
&
X3)V
(1.30)
v(X,&X,~x,)v(x,G).
The first, third, and fourthdisjunctive terms of the above disjunctive
normal form
are
0,
since they contain expressions of
the
form
22
ELEMENTS
OF
MATHEMATICAL LOGIC
x
&
x.
The second and last terms
lack
suchexpressions, and there-
fore
our
function does not reduce to
y
=
0;
it may therefore be
written as
Thus,
To
reduce a given function to its complete disjunctive normal
form, it must first
be
reduced to some normal disjunctive form by
the methods already
discussed.
Let
us
follow the remainder of the
procedure on
our
example.
Our
normal form (1.32)
is
notfull because its second disjunctive
term does not comprise all the variables:
x,
(or
x;)
is
missing.
HOW-
ever, it
is
readily seen that the following identity
is
true:
Substituting the disjunction given by (1.33) for the second dis-
junctive term of the normal form (1.32),
we
obtain
which
is
the full disjunctive normal form
of
the given function. Of
course,
if
these transformations would have given an expression
containing several identical disjunctive terms,
we
would have
re-
tained only one of these.
Reduction to a conjunctive normal form differs from the above
technique only in the last step where, instead of expanding the ex-
pression derived in the preceding steps in accordance with identity
(1.26a),
we
use the second distributive law, thatis, identity (1.26b).
EXAMPLE.
Let the conjunctive normal form of
a
function of
three variables be
y
:--
XI
&
(X,
VX,VX,).
(1.35)
To
transform this into a complete normal form,
we
use the identities
PROPOSITIONAL CALCULUS
23
and
we
get
which
is
the complete conjunctive normal form of the starting func-
tion.
So
far,
we
have demonstrated the use of Boolean algebra by
re-
ducing
a
given logical function of several variables to its full nor-
mal
(or
any normal) disjunctive
(or
conjunctive) form. However, the
function may be given by means of atable. In this
case,
we
can
ob-
tain
a
unique complete disjunctive normal form via the method
al-
ready described.
We
can then transform this expression by means
of Boolean identities and thus arrive at other analytic expressions
of the same function. Given the varietyofpossible forms of a func-
tion,
we
are
faced with the problem of determining which of these
is
optimum for our purposes.
We
shall return to this somewhat later.
1.4.
TWO-VALUED PREDICATE CALCULUS
We
shall now return to
a
subject which
we
have briefly considered
at the end
of
Section
1.2.
Thus
we
shall consider two-valued predi-
cates,
that
is,
logical functions which themselves assume only the
values of
0
or
1,
but whose argumentsmay take on values from any
set
whatsoever.
Predicate functions
are
denoted by capital letters. This permits
us to distinguish visually between
a
predicate (a nonhomogeneous
logical function) and
a
complex proposition
(a
homogeneous logical
function). Thus, an n-place predicate may be written as
where
x,=
(xll,
.
.
.,
xlP],
.
.
.,
x,,
=
{xnl,
.
.
.,
xnqj
are the objectvari-
ables and their alphabets.
Since two-valued predicates assume values from
a
binary set
0
and
1,
they may themselves be the arguments of two-valued
24
ELEMENTS
OF
MATHEMATICAL LOGIC
homogeneous logical functions; for this reason, we can apply to
them the symbolism
of
propositional calculus. Thus, suppose
we
have the predicates
We
can subject these predicates to any one of
the
operations of
propositional calculus to obtain
a
new predicate; for example,
(1.39)
This use
of
operations of propositional calculus permits
us
to achieve
several ends. To begin with,
we
can
relate
several simple predicates
to each other and form
a
compound predicate,
as
in the above example.
Also,
we
can relate predicates to any and
all
simple propositions,
as
well
as to the compound propositions that can be formed from the
simple ones by the same operations of propositional calculus. Thus
from the predicates (1.38) and the binary logical variables
x3=
[O,
I],
xq=
(9,
1)
we
can construct a composite function,
for
example,
(1.40)
where
Z
can only
be
two-valued.
The only variables
which
we
have encountered in the compound
function of propositional calculus
were
the simple prepositions. In
the predicate calculus, however, not only simple propositions, but
also the object variables of the predicates,
as
well
as
variable
predicates
can act as variables. The presence of these elements
constitutes
the
main characteristic of this calculus, and necessi-
tates new operations that
are
qualitatively different from those em-
ployed in propositional calculus. The operators corresponding to
these new operations
are
called
quantifiers.
There are two types of quantifiers: the
univevsal
and the
exis-
tential.
The universal quantifier
is
an, operator that matches any one-
place predicate
q
=
P(x)
with the binarylogicalvariable
2
which be-
comes
1
if,
and only
if,
g
=
I
at
all
values of
x.
This
is
written
2
=
(VX)
IJ
(X),
TWO-VALUED PREDICATE CALCULUS
25
where
ccV~97
is
the universal quantifier. The above expression
is
then read
as
“for
all
x
there
is
P(x).”
The existential quantifier
is
an operator that matches
a
one-place
predicate
y
=
P
(x)
with
a
binary logical variable
z
which
becomes
0
if, and only
if,
y
=
Oat
all
values of
x.
This
is
written
2
=
(3x)
P
(x),
where
“3x7’
is
the existential quantifier. The above expression
is
then
read
as
“there
is
an
x
such thaty
=
P(n).”
Let us discuss some general properties
of
these operators. In
accordance with the definitions
of
quantifiers, the logical variable
z
in
(1.41)
is
not a function of the object variable
x;
here,
z
is
an “integral”
characteristic of the predicate
P
(x).
To underscore the absence of
functional dependence of
z
on
x,
the object variable
x
in such cases
is
said to be
bound.
Object variables that are not bound
are
said to
be
free.
Of course, the universal and existential quantifiers may
also be applied to functions of propositional calculus. But
if
we
do
that, then they degenerate into finite conjunctions and disjunctions.
Indeed,
suppose
we
have a functionq
=
y(x,,
.
.
.
,
x,,)
in which both
the variables and
the
function
are
two-valued logical variables. The
same function may be given in the form
y
=
~(k),
where
k
is
a
nu-
meral denoting
a
point in an n-dimensional binary logical space.
From
the definition of quantifiers,
we
have
For this reason
we
can consider the universal and existential
quanti
f
ie
r
s
as
generalized conjunction and generalized di
s
j
unc ti on,
respectively. And because of the analogy between conjunction
or
dis-
junction and the summation of
real
numbers, one can draw an analogy
between the operations specified by quantifiers and the integration
of
functions of
a
real
variable. If one applies
a
quantifier (either uni-
versal or existential) to an m-place (rather than a one-place) predi-
cate,
the
result
is
again a predicate; this time it
is,
however, an
(rn
-
1)-place predicate since one object variable becomes bound.
26
ELEMENTS
OF
MATHEMATICAL LOGIC
Thus, in dealing with predicates, we employ not only the opera-
tions of propositional calculus, but also operations involving binding
of object variables by universal andexistential quantifiers. The
cal-
culus in which the above operations
are
used to construct compound
functions
is
called
restricted predicate
calculus.
This
new
operation of binding by quantifiers introduces identities
which differ from those of the Section
1.3.
Examples of such identi-
ties
are
(3x1
P
(XI
=
(Vx)
P(x).
(1.42a)
(1.42b)
The identities
of
propositional calculus, supplemented by identi-
ties
(1.42),
comprise a mechanism useful for solving
a
variety of
problems.
As
in propositional calculus, the most important problem
of predicate calculus
is
that of decision, but because the independent
variables are different, the manner in which this problem posed
is
also somewhat different.
Thus, the decision problem of propositional calculus in deter-
mining whether a given compound functionis identically true, feasi-
ble,
or
identically false. However, the following must be asked in
predicate calculus:
(a)
Is
a
given compound function identically true;
that is, does it assume the value of
1
with any object variable and
any predicate?
Or
(b)
Is
it identically true only over
a
certain set
of object variables; that
is,
does it assume the value of
1
only over
a
certain set of object variables and for any predicate from this set?
Or
(c)
Is
it feasible;
that is, does it assume the value
of
1
at some
values of object variables and at some predicates? And, finally, (d)
Is it, identically false, that is, unfeasible? Incontrast to the case of
propositional calculus, the decision problem of predicate calculus
can be solved only for special kinds
of
compound functions.
2
Engineering Applications
of
Propositional Calculus
2.1.
COMBINATIONAL RELAY SWITCHING CIRCUITS
We
have already said that the promise of mathematical logic in
engineering design first became apparent during the analysis of elec-
trical relay switching circuits. In time, it became progressively
more evident that this logic
is
not only applicable to
the analysis
of
relay switching
circuits but that the operation of such circuits mir-
rors
the postulates of the logic. The result of this discovery was the
relay switching theory. Then, when contactless devices that perform
the same functions
as
relay switches came into existence, the spe-
cial
theovy
of
relay circuits
was
extended into
a
general theory of
switching systems.
We
shall now examine this most conspicuous example
of
appli-
cation of logic to engineering, concentrating on the so-called com-
binational relay switching circuits.
Every electric relay switching circuit contains two types of con-
verters: electrical-to-mechanical and
mechanical-to-electvical.
The electromechanical relay converts electrical input signals into
a
mechanical displacement
of
its contacts. On the other hand, the
mechanical-to-electrical converter
is
an electrical network com-
prising contacts and
relay
coils: it converts the mechanical
dis-
placement
of
its (input) contacts into electrical output signals (cur-
rents flowing in the coils
of
the relays). Connection
of
outputs of
converters
of
one type to the inputs
of
converters
of
the other type
gives
a
variety of relay switching networks.
The simplest electromechanical relay consists of a coil
I,
a
core
2,
an armature
3,
and
two
groups of contacts: normally closed
4‘,
and normally open
4”
(Fig. 2.1,a).
If
acurrent larger than the ac-
tuating current
i2
(Fig. 2.1,b) flows in the coil, the armature
is
27
28
Component
ELEMENTS OF MATHEMATICAL
LOGIC
.
1
0
attracted to the core, and this causes
all
the normally open contacts
to close and
all
the normally closed contacts to open. On the other
hand,
if
a
current smaller than
i,
flows in the coil (in particular,
when the coil
is
de-energized, the armature recedesfrom the core,
causing the normally closed contacts to close and the normally
open contacts to open. To avoid the complications arising in tran-
sient states,
we
shall consider only the stable states
of
the relay,
that
is,
states when the coil current
i
has
either of the following
values:
i
<
i,
or
i
>
iz.
Thus the relay has
two
stable states
or,
to
say it in another way, there
are
two states which are characteristic
for
all
the elements of the
relay.
We
are,
however, interested only
in the coil and in the contacts.
Each contact has two states: closed
and open.
We
shall designate
these
states by
1
and
0,
respectively;
that
is,
we
shall
treat the state of
a
contact
as
a
binary logical vari-
able assuming these values.
The coil also
has
two states. The first
of
these occurs at
i
>
iz,
and
we
denote it by
1.
In the second state, denoted by
0,
the coil
is
de-energized
(i
<
it).
Thus the coil states can also be represented
by
a
logical variable that can be either
0
or
1.
The physical signifi-
cance of these values
is
shown in Table
2.1.
Table
2.1
Symbol
energized de-energized
I
Open
Contact closed
COMBINATIONAL RELAY SWITCHING CIRCUITS 29
The
state
of
a
relay contact
is
goverenedby the state of the coil
in the following manner:
--
FQr
a
normally open contact
x
=
X,
For
a
normally closed contact
x‘
=
X
=
x
where
X,
x, x’
are
the
logical variables specifying the states of the
coil, of the normally open contact and of the normally closed con-
tact, respectively.
If
a
relay has more than one coil, it becomes convenient to an
“equivalent coil.” Thus, let the relay have
two coils
(XI
and
X,)
and let
these
be
so
connected that the relay shall operate only
if
both
are
energized, that
is,
if
X,
&
X2
=
1.
Letus now imagine
a
coil
4,
such that
it
will
cause the relay to operate only
if
Xi
&
X2
=
I.
Ob-
viously the action of our equivalent coil, which
is
related to that of
the actual coils by
xe= x,
&
x,
and which governs the state of the relay contacts in accordance with
x
=
Xe
x’
=
x,
=
,?
(for normally closed contacts),
(for normally open contacts)
is
completely equivalent to the action of the
two
actual
coils.
So
far,
we
have discussed
a
relay with two coils. By the same
reasoning,
we
can imagine
a
relay with
rn
coils connected
so
that
the relay operates only at certaincombinationsofthe
1
and
0
states
of the constituent coils.
A
relay circuit incorporating
m
coils in
a
specific arrangement
is
described by
a
logical function specific to this circuit:
x,
=
M
(X,,
x,,
.
.
.
,
Xm).
However,
this
specificity
does
not change the general relationship
between
the
contacts of the relay and its equivalent coil.
We
shall now turn to the representation of the mechanical-to-
electrical converter, that is,
of
contacts connected to relay coils.
Let us start with the
case
when the circuit (Figs. 2.2,
a
and
2.2,a‘)
consists of
a
contact
I
of
an
input relay and
a
coil
2
of another relay
(the output relay),
the
coil being either in
series
(Fig. 2.2,a) or in
parallel
(Fig.
2.2,a’) with the contact.