\documentclass{amsart}
\usepackage{amssymb,amsfonts,amsmath}
\begin{document}
\title{Chapter 1 Introduction}
\begin{abstract} This introductory chapter provides basic
concepts, devices, and notations that facilitate the
developments of the present study on threshold transformations
and dynamical systems of neural networks.
\end{abstract}
\maketitle
\section*{1.1 Basic notations}
In this chapter we describe basic concepts, devices, and
notations that facilitate the developments of the present study.
Most of the basic concepts in this chapter are found in
introductory chapters of traditional textbooks on "abstract"
algebra or in good introductory textbooks on discrete mathematics
or combinatorics such as Williamson (1985), Krishnamurthy (1986),
and Biggs (1989). We usually deal with finite sets in this book.
The number of elements of a finite set $X$ will be denoted by
$|X|$. For set operations, the prefix $^{c}$ denotes the
complement of a subset, $\backslash$ denotes the difference of
sets:
$$
A\backslash B = A\cap B^{c} = \{x \mid x \in X, x \notin
Y\},
$$
and $\dot{+}$ denotes the symmetric difference of sets:
$$
A\dot{+}B = (A\backslash B)\cup (B\backslash A).
$$
Then
$$
(A\dot{+}B)\dot{+}C = A\dot{+}(B\dot{+}C).
$$
If $q \in X$, then $A\backslash \{ q\}$ and $A\cup \{ q\}$ are
respectively written as $A\backslash q$ and $A\cup q$. A
partition of a set S is a family of disjoint subsets {A1,..,An}
such that
$$
S = \bigcup_{i=1}^n A_i.
$$
If $F$ is a function from $X$ to $Y$, denoted by $F: X
\rightarrow Y$, and if $A \subseteq X$, then the image of $A$
under $F$ is
$$
FA = \{ y \mid y = Fx \; \mbox{for some}\; x \in A\},
$$
and the inverse image of A is
$$
F^{-1}A = \{ x \mid Fx \in A, x \in X\}
$$
The inverse image of $a \in Y$ is
$$
F^{-1}a = \{ x \mid Fx = y, x \in X\} .
$$
If $B = FA$, then the expression $A \rightarrow _{F} B$ is also
used.
A function $F: X \rightarrow Y$ is called an \emph{onto}
function or a \emph{surjection} if $FX = Y$. $F$ is called a
\emph{one-to-one} function or an \emph{injection} if $Fx =
Fx\prime $ for $x$, $x\prime \in X$ implies $x = x\prime $. $F$
is called a \emph{bijection} if $F$ is both a surjection and an
injection. If $D$ and $X$ are any sets, then $X^{D}$ denotes the
set of all functions from $D$ to $X$. If $F$ is a function from
a set $X$ to a set $Y$, and if $G$ is a function from the set $Y$
to a set $Z$, then the composition $G\circ F$, often simply
written as $GF$, is the function from $X$ to $Z$ defined as
$(GF)x = G(Fx)$ for every $x \in X$. $GF$ is also called the
product of $G$ and $F$. If $C \subseteq X$, the restriction of
a function $F: X \rightarrow Y$ to $C$ is denoted by $F|C$.
The set of all integers will be denoted by $\mathbf{Z}$,
the set of non-negative integers will be denoted by
$\mathbf{Z}_{+}$,
and the set of positive integers will be denoted by
$\mathbf{Z}^{+}$.
A sequence $V = (v_0,v_1,...)$ in $X$ is a function $V:
\mathbf{Z}_{+} \rightarrow X$. The image of $V$, that is, the
set $\{ x \mid x = v_{i} \; \mbox{for some}\; i\}$, is denoted
by $\mathbf{V}$.
A \emph{graph} $G$ consists of a finite set $V$, whose
members are called \emph{vertices}, and a set $E$ of 2-element
subsets of $V$, whose members are called \emph{edges}. $V$ is
called a \emph{vertex set}, $E$ is called an \emph{edge set},
and $G$ is expressed as $G = (V,E)$. A directed \emph{graph}, or
\emph{digraph} consists of a finite set, whose members are called
\emph{vertices}, and a set $A$ of ordered pairs of elements of
$V$, whose members are called \emph{arcs}. $V$ is called a
\emph{vertex set}, $A$ is called an \emph{arc set}, and $G$ is
expressed as $G = (V,A)$. An arc $(x,y)$ will be expressed by $x
\rightarrow y$. An arc $(x,x)$ is called a \emph{loop}, and
will be expressed by $x\partial $. Let $G = (V,A)$ and $H =
(W,B)$ be digraphs. Let $F$ be a bijection from $V$ to $W$.
Assume that $(x,y) \in A$ if and only if $(Fx,Fy) \in B$. Then
a function $F\prime $ from $A$ to $B$ can be defined as $F\prime
(x,y) = (Fx,Fy)$ for each $(x,y) \in A$. In this case, $G$ and
$H$ are called \emph{isomorphic} under the \emph{isomorphism}
$(F,F\prime )$ \emph{induced} by $F$.
A \emph{walk} in a graph $G$ is a fnite sequence of vertices
$V = (v_{1}, v_{2}, ..,v_{k})$ such that $\{ v_{i},v_{i+1}\}$ is
an edge of $G$ for every $1 \leq i \leq k-1$. Similarly,
a \emph{walk} in a digraph $G$ is a sequence of vertices
$V = (v_{1}, v_{2}, ..,v_{k})$ such that $(v_{i},v_{i+1})$
is an arc of $G$ for every $1 \leq i \leq k-1$. In this case,
the walk $V$
is expressed as $v_{1} \rightarrow v_{2} \rightarrow ...
\rightarrow v_{k+1}$.
If all its vertices are distinct, a walk is called a $path$. A
walk $v_{1} \rightarrow
v_{2} \rightarrow ... \rightarrow v_{k+1}$ whose vertices are
all distinct except that $v_{1} = v_{k+1}$ is called a $k$-
\emph{cycle} or a \emph{cycle of length} $k$. A cycle of a graph
$G$ is called \emph{Hamiltonian}, if it contains all vertices of
$G$.
By a transformation of $F$ of a set $X$ we mean a function
from the set to itself. In particular, if $F$ is a bijection, it
is called a \emph{one-to-one transformation}. If $F$ is a
transformation of a set $X$, then $F$ defines its digraph,
$$
\mathrm{GRAPH}(F) = (X,A),
$$
consisting of the vertex set $X$ and the arc set $A$ defined by
$$
A = \{ (x,y) \mid x \in X, Fx = y\} .
$$
If $v_{1} \rightarrow v_{2} \rightarrow ... \rightarrow v_{k}
\rightarrow v_{1}$ is a cycle of a digraph, then $v_{i}
\rightarrow v_{i+1} \rightarrow ... \rightarrow v_{k}
\rightarrow v_{1} \rightarrow ... \rightarrow v_{i}$ is also a
cycle. Therefore, in $\mathrm{GRAPH}(F)$, these two cycles are
regarded as the same. With this identification in mind, the set
of all cycles in $\mathrm{GRAPH}(F)$ is denoted by
$\mathrm{CY}(F)$ (a loop is a 1-cycle).
If $F$ and $G$ are transformations of $X$ and $GF = FG$, then
$F$ is called \emph{commutative} with $G$. A particular case
where $F$ and $G$ are commutative is described in the following.
If $Fx = x$, that is, $(x)$ is a loop of $\mathrm{GRAPH}(F)$,
then $x$ is called a \emph{fixed point} of $F$; if $Fx \ne x$,
then $x$ is called a \emph{non-fixed point} of $F$. If $FA
\subseteq A$ for a subset $A$ of $X$, then the restriction
$F|A$ is the transformation of $A$.
We call the set of all non-fixed points of $F$ the \emph{carrier}
of $F$ and write $\mathrm{Car}F$. If $\mathrm{Car}F$ and
$\mathrm{Car}G$ are disjoint, then a transformation $H$ can be
defined by $Hx = Fx$ if $x \in \mathrm{Car}F$, $Hx = Gx$ if $x
\in \mathrm{Car}G$, and $Hx = x$ if $x \in (\mathrm{Car}F \cup
\mathrm{Car}G)^{c}$. $H$ is called the sum of $F$ and $G$ and
denoted by $F+G$. If $H = F+G$, and if the images
$F(\mathrm{Car}F)$ and $G(\mathrm{Car}G)$ are disjoint, then $F$
is commutative with $G$, and $H = GF = FG$. In this case, $H$ is
called the direct sum or more conventionally \emph{disjoint
composition} of $F$ and $G$ and denoted by $H = F\odot G$.
If $X$ and $Y$ are sets, then the \emph{Cartesian product}
$X\times Y$ is the set of ordered pairs $(x,y)$, $x \in X$ and
$y \in Y$. If $F$ is a transformation of $X$ and $G$ is a
transformation of $Y$, then the \emph{direct product} $F\times G$
is the transformation of $X\times Y$ defined by $(F\times G)(x,y)
= (Fx,Gy)$ for every $(x,y) \in X\times Y$. The Cartesian
products of $n$ sets and the direct product of $n$
transformations are similarly defined.
Let $X$ be a set and $d$ be a function from $X\times X$ to
the set of non-negative real numbers satisfy the following
conditions:
\begin{eqnarray*}
d(a,b) &=& 0 \; \mbox{if and only if}\; a = b,\\
d(a,b) &=& d(b,a) \; \mbox{for every}\; a,b,\\
d(a,b) &\leq & d(a,c)+d(c,b)\; \mbox{for every}\; a,b,c.
\end{eqnarray*}
Then, $d$ is called a \emph{distance} and $X$ is called a
\emph{metric space}. If $X$ is a finite set, then $X$ is called
a \emph{finite metric space}. The distance between a point $x$
and a non-empty subset $A$ of $X$ is defined by
$$
d(x,A) = \mbox{min}\{d(x,y) \mid y \in A \},
$$
where min denotes the minimum element. The distance between non-
empty subsets $A$ and $B$ is defined by
$$
d(A,B) = \mathrm{min}\{d(x,B) \mid x \in A \}.
$$
\section*{1.2 Permutations}
Let $m$ be a positive integer. Integers $a$ and $b$ are called
\emph{congruent modulo} $m$, and written as $a \equiv b$ mod
$m$, if $a-b$ is divisible by $m$. Further, if $0 \leq b <
m$ here, $b$ is the remainder obtained by dividing $a$ by $m$ and
denoted by $a\%m$. The relation $\equiv $ mod $m$ is an
equivalence relation on $\mathbf{Z}$. The set of all equivalence
classes with respect to this equivalence relation is called the
\emph{residue class ring with m elements}. We use the two
expressions $\mathbf{Z}_{m} = \{0,1,2,..,m-1\}$ and
$\mathbf{N}_{m} = \{1,2,..,m\}$ for the residue class ring, where
each equivalence class containing a representative integer a is
expressed by the same integer $a$. Since we mostly use the
second expression $\mathbf{N}_m$, its algebraic structure is
described in the following. If $a$ and $b$ are elements of
$\mathbf{N}_m$, then $a+b$ is the element $c$ of $\mathbf{N}_m$
such that $c \equiv a+b$ mod $m$, and $a\cdot b$ is the element
$c$ of $\mathbf{N}_m$ such that $c \equiv a\cdot b$ mod $m$.
Then $\mathbf{N}_m$ is a ring with $m$ as the zero element. For
example, $-a = n-a$ for any $a = 1,2,..,m-1$, and $-m = m$.
Further, we assume the order relation $1 < 2 < ... < m-1 < m$ in
$\mathbf{N}_m$. Hereafter, we denote $\mathbf{N}_n$ simply by
$\mathbf{N}$.\\
\textbf{Lemma 1.2.1}
The equation
$$
s\cdot x = 1
\eqno (1.2.1)
$$
in $\mathbf{N}$ has a unique solution $x$, if and only if $s$ and
$n$ are
relatively prime.
\begin{proof}
For example, see Theorem 10.2 of Ore (1988, p. 238).
\end{proof}
The unique solution $x$ of (1.2.1) is called the inverse of $s$
and denoted by $s^{-1}$ or $1/s$. Let $\mathbf{U_{n}}$ denote
the set of all elements $x$ of $\mathbf{N}$ such that $x$ and $n$
are
relatively prime. As shown by Lemma 1.2.1, $\mathbf{U_{n}}$ is
the
set of all \emph{invertible} elements of $\mathbf{N}$, that is,
elements
having multiplicative inverses, and forms a multiplicative
abelian group.
If $\mathbf{G}$ is a group, then $|\mathbf{G}|$ is
called the \emph{order} of $\mathbf{G}$. For the order $\varphi
(n)$ of $\mathbf{U_{n}}$, $\varphi $ is known as Euler's
function. If $\mathbf{H}$ is a subgroup of $\mathbf{G}$
generated by elements $\tau $,...,$\omega $ of $\mathbf{G}$, then
$\mathbf{H}$ is denoted by $\langle \tau ,..,\omega \rangle $.
If $\sigma $
and $\tau $ are elements of a group $\mathbf{G}$ and if there
exists an element $\gamma $ of $\mathbf{G}$ such that $\tau =
\gamma ^{-1}\sigma \gamma $, then $\tau $ is called a
\emph{conjugate} of $\sigma $, and $\sigma $ and $\tau $ are said
to be \emph{conjugate}.
If $h$ is a function from a group $\mathbf{G}$ to a group
$\mathbf{H}$ such that $h(\sigma \tau ) = (h\sigma )(h\tau )$ for
all elements $\sigma $ and $\tau $ of $\mathbf{G}$, then $h$ is
called a
\emph{homomorphism} from $\mathbf{G}$ to $\mathbf{H}$. The
\emph{direct
product} of $n$ groups $\mathbf{G_{1}}$,..,$\mathbf{G_{n}}$ is
the Cartesian product $\mathbf{G_{1}}\times ...\times
\mathbf{G_{n}}$ with the multiplication defined by $(g_{1},...,
g_{n})(g\prime _{1},...,g\prime _{n}) = (g_{1}g\prime
_{1},...,g_{n}g\prime _{n})$. If $X$ is a finite set, then the
set of all one-to-one transformations, which are called
\emph{permutations} of $X$, is a group with the composition of
transformations as its binary operation. This group is called
the \emph{symmetric group} on $X$ and denoted by
$\mathrm{SYM}(X)$. The order of $\mathrm{SYM}(X)$ is $|X|!$.
The identity element of $\mathrm{SYM}(X)$ is the identity
permutation $\iota $ of $X$. A one-to-one transformation $\tau $
of \emph{length} $m$ of a finite set $X$ is called a \emph{cyclic
permutation}, if $\mathrm{GRAPH}(\tau )$ consists of one
$m$-cycle and loops. In particular, a cyclic permutation $\sigma
$
of length $m$ of $X$ can be expressed by
$$
\sigma = (s_{1},s_{2},..,s_{m}),
$$
if $\sigma s_{i} = s_{i+1}$ for every $1 \leq i \leq m-1$,
$\sigma s_{m} = s_{1}$, and $\sigma j = j$ for every $j \in X$
not belonging to $\{ s_{1},s_{2},..,s_{m}\}$. In particular, the
cyclic permutation
$$
\rho = (1,2,..,n)
$$
is defined by $\rho i = i+1$ for every $i \in \mathbf{N}$. Then
we have
the following elementary theorem on permutations.\\
\textbf{Proposition 1.2.2}
If $\tau $ is not the identity permutation, then $\tau $ is a
disjoint composition of cyclic permutations, each of length at
least 2.\\
Consider a linear function $\tau$ :
$$
\tau i = a\cdot i+b
\eqno (1.2.2)
$$
on $\mathbf{N}$. For $\tau $ to be a permutation, it is
necessary and
sufficient that $a$ is invertible. We call $(a,b)$ the
\emph{coefficients}, $a$ the \emph{slope}, and $b$ the
\emph{segment} of the \emph{linear permutation} $\tau $. In this
case, it is verified that
$$
\tau \rho = \rho ^{a}\tau ,
\eqno (1.2.3)
$$
$$
\rho \tau = \tau \rho ^{a^{-1}}
\eqno (1.2.4)
$$
for the cyclic permutation $\rho = (1,2,..,n)$.
The cyclic permutation $\rho $ itself is a linear permutation
of coefficients $(1,1)$. If $\tau $ is a linear permutation of
coefficients $(a,b)$ then $\tau ^{-1}$ is a linear permutation of
coefficients $(a^{-1},-a^{-1}b)$. For example, let $\tau \in
\mathrm{SYM}(\mathbf{N})$ be a linear permutation of slope $-1 =
n-1$. If
the coefficients of $\tau $ are $(-1,t)$, then $\tau ^{-1}$ is a
linear permutation of coefficients $(1/-1,-t/-1) = (-1,t)$.
Therefore, $\tau ^{-1} = \tau $. In particular, if the
coefficients of $\tau $ are $(-1,1)$, then $\tau $ is
$$
\lambda = (1,n)(2,n-1)\cdot \cdot \cdot ([n/2],n-
[n/2]+1),
$$
where $[x]$ denotes the greatest integer equal to or less than
$x$. If $\sigma $ and $\tau $ are linear permutations of
respective coefficients $(a,b)$ and $(c,d)$, then $\sigma \tau $
is a linear permutation of coefficients $(ac,ad+b)$. If $\tau $
is a linear permutation of slope $a$, then $\tau \rho $ and $\rho
\tau $ are also linear permutations of slope $a$. Since the
coefficients of $\rho $ are $(1,1)$, the coefficients of $\tau
\rho $ and $\rho \tau $ are respectively $(a, a+b)$ and
$(a,b+1)$, if the coefficients of $\tau $ are $(a,b)$. In
summary, we have\\
\textbf{Proposition 1.2.3}
Let $\mathrm{LIN}(\mathbf{N})$ denote the set of all linear
permutations of $\mathbf{N}$.
Then $\mathrm{LIN}(\mathbf{N})$ is a subgroup of the symmetric
group
$\mathrm{SYM}(\mathbf{N})$, and the function $h$ from
$\mathrm{LIN}(\mathbf{N})$ to
$\mathbf{U_{n}}$ that associates each $\tau $ of
$\mathrm{LIN}(\mathbf{N})$ with
its slope is a homomorphism.\\
\section*{1.3 P\'{o}lya actions\label{s:PA}}
Let $\mathbf{G}$ be a group and $X$ be a set. Then it is said
that
$\mathbf{G}$ \emph{acts on} $X$, or $\mathbf{G}$ is a
\emph{transformation group} for $X$, if there is a homomorphism
$H$ from $\mathbf{G}$ to $\mathrm{SYM}(X)$. In this case, $H$ is
called an \emph{action} of $\mathbf{G}$ on $X$ or a
\emph{representation} of $\mathbf{G}$ on $X$. The action $H$ is
omitted from expressions in the following, when it is clear, so
that $(H\tau )x$ is simply written as $\tau x$ for an element
$\tau $ of $\mathbf{G}$ and an element $x$ of $X$. If
$\mathbf{G}$ acts on $X$ and $x$ is an element of $X$, then the
subgroup $\mathbf{G}_{x}$ defined by
$$
\mathbf{G}_{x} = \{ g \in \mathbf{G} \mid gx = x\}
$$
is called the \emph{stabilizer} of $x$.\\
\textbf{Example 1.3.1}
If $F$ is a one-to-one transformation of a set $X$, then the set
$\mathbf{G} = \{ F^{i}\mid i \in \mathbf{Z}\}$ is a subgroup
of
$\mathrm{SYM}(X)$ generated by $F$. $\mathbf{G}$ is a
transformation group
for $X$ since $H: \mathbf{G} \rightarrow \mathrm{SYM}(X)$
defined by
$H(F^{i}) = F^{i}$ is clearly a homomorphism. The order of
$\mathbf{G}$
is called the \emph{order} of $F$.\\
If a group $\mathbf{G}$ acts on a set $D$, and $X$ is a set, then
the \emph{P\'{o}lya action} $H$ of $\mathbf{G}$ on $X^{D}$ is
defined by
$$
((H\tau )f)d = f(\tau ^{-1}d)
$$
for every element $\tau $ of $\mathbf{G}$, every element $f$ of
$X^{D}$, and every element $d$ of $D$. If $\sigma $ and $\tau $
are elements of $\mathbf{G}$, then
\begin{eqnarray*}
((H(\sigma \tau ))f)d &=& f((\sigma \tau )^{-1}d) = f((\tau
^{-1}\sigma ^{-1})d)\\
&=& f(\tau ^{-1}(\sigma ^{-1}d)) = ((H\tau )f)(\sigma ^{-
1}d)=((H\sigma )((H\tau )f))d \\
&=& (((H\sigma )(H\tau ))f)d.
\end{eqnarray*}
That is,
$$
H(\sigma \tau ) = (H\sigma )(H\tau ).
$$
Therefore, the P\'{o}lya action is an homomorphism and hence in
fact an action.
Let $\mathbf{Q} = \{ 0,1\} $. Then $\mathbf{Q}^\mathbf{N}$
is the set of all binary strings of length $n$. Let $x =
(x_{1},x_{2},..,x_{n}) \in \mathbf{Q}^mathbf{N}$. The period of
$x$ is the minimum element $k$ of $\mathbf{N}$ such that $x_{i+k}
= x_{i}$ for every $i \in \mathbf{N}$. The density of $x$
denoted by $d(x)$ is the number of 1s in $x$, i.e.
$$
d(x) = |\{i \mid x_{i} = 1\}|.
$$
The P\'{o}lya action $H$ of $\mathrm{SYM}(\mathbf{N})$ on
$\mathbf{Q}^\mathbf{N}$ associates a permutation $\tau $ of
$\mathbf{N}$ with a
permutation of coordinates of $\mathbf{Q}^\mathbf{N}$ by
$$
(H\tau )(x_{1},x_{2},..,x_{n}) = (x_{\tau ^{-1}1},x_{\tau ^{-
1}2},..,x_{\tau ^{-1}n}).
$$
$\mathbf{Q}^\mathbf{N}$ is simply denoted by $\mathbf{Q}^{n}$
hereafter.
For example, let $\rho $ be the cyclic permutation $(1,2,..,n)$.
The transformation $\rho $ defined by the P\'{o}lya action on
$\mathbf{Q}^{n}$ is the \emph{right rotation} of coordinates of
$\mathbf{Q}^{n}$, that is,
$$
\rho (x_{1},x_{2},..,x_{n}) = (x_{n},x_{1},..,x_{n-1})
$$
for every $x = (x_{1},x_{2},..,x_{n}) \in \mathbf{Q}^{n}$.
If a group $\mathbf{G}$ acts on a set $X$, then an
equivalence relation $\sim _{\mathbf{G}}$ on $X$ can be defined
by $x \sim_{\mathbf{G}} y$ if there is an element $\tau \in
\mathbf{G}$ such that $\tau x = y$. Each equivalence class with
respect to the equivalence relation $\sim _{\mathbf{G}}$ is
called an orbit of $\mathbf{G}$ acting on $X$. The orbit
containing an element $x$ of $X$ is denoted by
$\mathrm{Orb}_{\mathbf{G}}x$. The union
$\bigcup_{x\in S}\mathrm{Orb}_{\mathbf{G}}x$ of the orbits
for a subset $S \subseteq X$ is denoted by
$\mathrm{Orb}_{\mathbf{G}}S$. Then, the equivalence relation
$\sim _{\mathbf{G}}$ is extended to the set of all non-empty
subsets of
$X$, that is, $A \sim _{\mathbf{G}} B$ if
$\mathrm{Orb}_{\mathbf{G}}A = \mathrm{Orb}_{\mathbf{G}}B$.\\
\section*{1.4 Boolean functions\label{s:BF}}
From now on, $\mathbf{Q} = \{0,1\}$ is not simply a two-point
set, but regarded as the \emph{minimal Boolean algebra} with the
unary operation $\neg $ called \emph{complementation} or
\emph{negation} and the binary operations $\vee $ called
\emph{disjunction} or \emph{OR} and $\cdot $ called
\emph{conjunction} or \emph{AND} such that
\begin{eqnarray*}
\neg 0 &=& 1, \quad \neg 1 = 0,\\
0\vee 0 &=& 0, \quad 0\vee 1 = 1\vee 0 = 1, \quad 1\vee 1
= 1,\\
0\cdot 0 &=& 0\cdot 1 = 1\cdot 0 = 0,\quad 1 \cdot 1 = 1.
\end{eqnarray*}
Further, the binary relation $(=)$ can be introduced by defining
$$
x(=)y = x\cdot y\vee \neg x\cdot \neg y.
$$
Let $L, M \subseteq \mathbf{N}$. If $x \in \mathbf{Q}^{M}$,
then
the value of $x$ at $i \in M$ is denoted by $x_{i}$. A function
from $\mathbf{Q}^{M}$ to $\mathbf{Q}^{L}$ is called a
\emph{Boolean function}. A function from $\mathbf{Q}^{M}$ to
itself is called a \emph{Boolean transformation}. If $A
\subseteq \mathbf{Q}^{M}$, then $1_{A}$ denotes the
characteristic function for $A$, i.e. $1_{A}x = 1$ if and only if
$x \in A$. Let $L \subseteq M \subseteq \mathbf{N}$. Then
the
\emph{projection function} $P_{L}: \mathbf{Q}^{M} \rightarrow
\mathbf{Q}^{L}$ is defined by
$$
(P_{L}x)_{i} = x_{i} \; \mbox{for every}\; i \in L \;
\mbox{for every}
\; x \in \mathbf{Q}^{M}.
$$
If $j \in M$, then the projection function $p_{j}:
\mathbf{Q}^{M} \rightarrow \mathbf{Q}$ is defined by
$$
p_{j}x = x_{j} \; \mbox{for every}\; x \in
\mathbf{Q}^{M}.
$$
Let $L$ and $M$ be disjoint subsets of $\mathbf{N}$. Then
$\mathbf{Q}^{L\cup M}$ can be identified with the Cartesian
product $\mathbf{Q}^{L}\times \mathbf{Q}^{M}$ by identifying $x
\in \mathbf{Q}^{L\cup M}$ with $(P_{L}x,P_{M}x) \in
\mathbf{Q}^{L}\times \mathbf{Q}^{M}$, where $P_{L}:
\mathbf{Q}^{L\cup M} \rightarrow \mathbf{Q}^{L}$ and $P_{M}:
\mathbf{Q}^{L\cup M} \rightarrow \mathbf{Q}^{M}$ are the
projection functions defined above.
Hereafter, $\mathbf{Q}^\mathbf{N}$ is simply denoted by
$\mathbf{Q}^{n}$.
Let $f$ and $g$ be Boolean functions from $\mathbf{Q}^{n}$ to
$\mathbf{Q}$. Then the \emph{conjunction} of $f$ and $g$ denoted
by $f\cdot g$ is the function: $\mathbf{Q}^{n} \rightarrow
\mathbf{Q}$ defined by
$$
(f\cdot g)x = (fx)\cdot (gx)
$$
for every $x \in \mathbf{Q}^{n}$. The \emph{disjunction} of $f$
and $g$ denoted by $f\vee g$ is the function: $\mathbf{Q}^{n}
\rightarrow \mathbf{Q}$ defined by
$$
(f\vee g)x = (fx)\vee (gx)
$$
for every $x \in \mathbf{Q}^{n}$. Also a unary operation $\neg
$ called \emph{complementation} is defined by
$$
(\neg f)x = \neg (fx)
$$
for every $x \in \mathbf{Q}^{n}$. Further, $f(=)g$ is defined
by
$$
f(=)g = f\cdot g\vee \neg f\cdot \neg g.
$$
In this book, we refer to the set $f$ for a Boolean function
$f: \mathbf{Q}^{n} \rightarrow \mathbf{Q}$ meaning the set $f^{-
1}1$, i.e. the inverse image of 1. Therefore, $x \in f$ means
$fx = 1$. Also, the set $\neg f$ is the set $f^{-1}0$. The
formula $f \subseteq g$ for Boolean functions $f$ and $g$ is
clear by this identification of a Boolean function with a set.
Also, $|f|$ is the number of elements of $f^{-1}1$.
Further,
\begin{eqnarray*}
f\cdot g &=& f\cap g,\\
f\vee g &=& f\cup g,\\
\neg f &=& f^c.
\end{eqnarray*}
Therefore, the corresponding laws such as the associative and
commutative laws for set operations $\cap $, $\cup $, and $^c$
hold for $\cdot $ ,$\vee $, and $\neg $ respectively. In
particular, we will frequently use the distributive laws:
\begin{eqnarray*}
f\cdot (g\vee h) &=& f\cdot g\vee f\cdot h,\\
f\vee (g\cdot h) &=& (f\vee g)\cdot (f\vee h),
\end{eqnarray*}
and De Morgan's law:
\begin{eqnarray*}
\neg (f\vee g) &=& (\neg f)\cdot (\neg g),\\
\neg (f\cdot g) &=& \neg f\vee \neg g.
\end{eqnarray*}
A conjunction $g = f_{1}\cdot f_{2}\cdot \cdot \cdot f_{m}$
of Boolean functions $f_{i}: \mathbf{Q}^{n} \rightarrow
\mathbf{Q}$ is called a \emph{term} of \emph{degree} $m$, if
there exists an injection $\varphi : \mathbf{N}_m \rightarrow
\mathbf{N}$ such that
$f_{i} = p_{\varphi i}$ or $\neg p_{\varphi i}$ for each $i$. A
term $g$ is called an \emph{implicant} of a Boolean function $f$
if $g \subseteq f$. An implicant $g$ of $f$ is called a
\emph{prime implicant} if $h = g$ for any implicant $h$ of $f$
such that $g \subseteq h$. The disjunction of terms are called
a disjunctive form. A Boolean function $f$ can be represented by
the disjunctive form that is the disjunction of all its prime
implicants. An irredundant disjunctive form of a Boolean function
$f$ is a disjunctive form that represents $f$ such that the
removal of any one of its terms does not represents $f$. In this
book, Boolean functions are usually expressed by an irredundant
disjunctive form.
Let $L$ and $M$ be disjoint subsets of $\mathbf{N}$, and $f$
and $g$
be respectively Boolean functions from $\mathbf{Q}^{L}$ to
$\mathbf{Q}$ and $\mathbf{Q}^{M}$ to $\mathbf{Q}$. Then the
product $f\cdot g$ is the function from $\mathbf{Q}^{L\cup M}$ to
$\mathbf{Q}$ defined by
$$
f\cdot g = (f\circ P_{L})\cdot (g\circ P_{M}).
$$
Let $a$ an element of $\mathbf{Q}^{M}$, where $M$ is a proper
subset of $\mathbf{N}$, and $f: \mathbf{Q}^{\mathbf{N}}
\rightarrow \mathbf{Q}$.
Then $f|a$ is the function from $\mathbf{Q}^{\mathbf{N}\backslash
\mathbf{M}}$ to $\mathbf{Q}$ defined by
$$
(f|a)x = f(x,a),
$$
where $(a,x)$ is an element of $\mathbf{Q}^{\mathbf{N}}$ defined
by
$$
P_M(a,x) = a \quad \mbox{and} \quad P_{N\backslash M}(a,x) = x.
$$
Clearly $\neg f|a = \neg (f|a)$. $f$ can be expressed as
$$
f = p_{i}\cdot (f|1)\vee \neg p_{i}\cdot (f|0),
$$
where $1,0 \in \mathbf{Q}^{\{i\}}$. Conversely, if $f =
p_{i}\cdot g\vee \neg p_{i}\cdot h$ for $g,h:
\mathbf{Q}^{\mathbf{N}\backslash i} \rightarrow \mathbf{Q}$,
then $g = f|1$ and $h = f|0$.
\end{document}