Biology Reference
In-Depth Information
Table 1.3
The table of values for Boolean functions
x
1
∧
x
2
;x
1
∨
x
2
,and
x
1
and their equivalents in polynomial form.
x
1
x
2
x
1
∧
x
2
x
1
x
2
x
1
∨
x
2
x
1
+
x
2
+
x
1
x
2
x
1
x
1
+
1
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
The general theory we will be applying here describes a method for solving such
systems of equations in the special case where the functions
f
x
1
,
f
x
2
,...,
f
x
n
,are
polynomials of the variables
x
1
,
x
n
. This may appear to be a serious restriction
since in the case of Boolean networks the transition functions do not seem to satisfy
this condition. However, as we will see next, each Boolean function can be rewritten
as a
Boolean polynomial
, where a Boolean polynomial of the (Boolean) variables
x
1
,
x
2
,...,
x
n
is a sum of terms of the form
x
1
b
1
x
2
b
2
x
n
b
n
with
b
i
∈{
x
2
,...,
...
1
,
0
}
,
i
=
1
n
.
Example 1.6.
,
2
,...,
f
(
x
1
,
x
2
,
x
3
,
x
4
)
=
x
1
x
3
x
4
+
x
2
x
3
+
x
1
x
3
is a Boolean polynomial
of the variables
x
1
,
x
2
,
x
3
,
x
4
. For the first term, we have
b
1
=
1
,
b
2
=
0
,
b
3
=
1,
and
b
4
= 1. For the second and third terms,
b
1
=
0
,
b
2
=
1
,
b
3
=
1, and
b
4
=
0, and
b
1
=
0, respectively.
To convert any Boolean function into a Boolean polynomial, the Boolean opera-
tions AND, OR, and NOT need to be converted to polynomials as follows:
1
,
b
2
=
0
,
b
3
=
1, and
b
4
=
1.
x
1
∧
x
2
=
x
1
x
2
2.
x
1
∨
x
2
=
x
1
+
x
2
+
x
1
x
2
3.
x
1
=
x
1
+
1.
To verify that the Boolean and polynomial functions (1)-(3) are identical, we need to
compare their values and verify that the two functions return the same values for the
same inputs. Table
1.3
contains the proof that
x
1
∧
x
1
x
2
.
Since addition and multiplication are performed over the field {0,1}, the following
addition and multiplication rules apply for any value
a
x
2
=
∈{
0
,
1
}:
a
+
a
=
0 and
a
.
Exercise 1.17.
Fill in the remaining columns of Table
1.3
to show that the
equalities (2) and (3) above hold.
∗
a
=
a
Exercise 1.18.
Show that for any
a
,
b
∈{
0
,
1
}
,
a
−
b
=
a
+
b
.
As a special case,
over the field
Example 1.7.
We next translate the Boolean model of the
lac
operon defined
by Eqs. (
1.8
) into polynomial form. We will give the translation for the function
f
A
l
{
0
,
1
}
,
−
1
=
1.
=
A
∨
L
∨
L
l
and leave the rest of the functions as an exercise:
f
A
l
=
A
∨
L
∨
L
l
=
((
A
∨
L
)
∨
L
l
)
=
((
A
+
L
+
AL
)
∨
L
l
)
=
(
A
+
L
+
AL
)
+
L
l
+
(
A
+
L
+
AL
)
L
l
=
A
+
L
+
AL
+
L
l
+
AL
l
+
LL
l
+
ALL
l
.
Search WWH ::
Custom Search