IJPAM: Volume 24, No. 3 (2005)

THE MINIMIZATION OF BOOLEAN FUNCTION
USING HAMILTONIAN CYCLES

Pinar Dundar
Department of Mathematics
Faculty of Science
Ege University
Bornova, Izmir, 35100, TURKEY
e-mail: pinar.dundar@ege.edu.tr


Abstract.Let $x_{i}$ be elements of the set B=$\{0, 1\}$ and $f$ be a function of $x_{i},$ $i=1,2,. . . ,n$, it is denoted by $f(x_{1},x_{2},. . . ,x_{n})$. The function $f(x_{1},x_{2},. . . ,x_{n})$ is named Boolean function. The value of a Boolean function is 0 or 1. Designing of the circuit of Boolean function, it is very important its minimal form find out. The sub terms of Boolean function is called as real prime implicants such that they defined whole function. Karnaugh maps is used for finding the real prime implicants. $n$ variable Boolean function can be modeled as $n$-dimension hypercube graph. In this paper we consider a Boolean function as a subgraph of $n$-dimensional hypercube. Our aim in this paper will be to develop procedure for obtaining a minimal expression for any Boolean function. We offer a new method to find the real prime implicants using the minimal number and maximal Hamiltonian Cycles of this subgraph.

Received: October 1, 2005

AMS Subject Classification: 94C10,94C15, 05C45

Key Words and Phrases: switching theory, application of Boolean algebra, Boolean functions, applications of graph theory, Eulerian and Hamiltonian graphs

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2005
Volume: 24
Issue: 3