Switching function based on hypergraphs with algorithm and python programming

Abstract

According to Boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions (it can also be described as an OR of AND’s). For each table an arbitrary T.B.T is given (total binary truth table) Boolean expression can be written as a disjunctive normal form. This paper considers a notation of a T.B.T, introduces a new concept of the hypergraphable Boolean functions and the Boolean functionable hypergraphs with respect to any given T.B.T. This study defines a notation of unitors set on switching functions and proves that every T.B.T corresponds to a minimum Boolean expression via unitors set and presents some conditions on a T.B.T to obtain a minimum irreducible Boolean expression from switching functions. Indeed, we generate a switching function in different way via the concept of hypergraphs in terms of Boolean expression in such a way that it has a minimum irreducible Boolean expression, for every given T.B.T. Finally, an algorithm is presented. Therefore, a Python programming(with complete and original codes) such that for any given T.B.T, introduces a minimum irreducible switching expression.

Keywords

Switching function hypergraphable Boolean function Boolean functionable hypergraph Boolean function–based hypergraph Unitor T.B.T.

1 Introduction

George Boole, an English mathematician, has published one of the works that founded symbolic logic in 1847. His combination of ideas from classical logic and algebra resulted in what is called Boolean algebra as a modern algebra(a complemented distributive lattice). By application of variables and symbols, Boole designed a language for describing and manipulating logical statements and determined if they are true or not(related notions had been considered by Gottfried Leibniz, who has defined the binary number system, which is the foundation of all digital computers, in 1680s). The variables stand for statements that are either true or false. The symbols +, * , - represent the logical symbols(Boolean operators) or, and, not, respectively and are equivalent in the truth tables in logic. Although truth tables use T and F (for true and false respectively) to indicate the state of the sentence, Boolean algebra uses 1 and 0, respectively. The relationship between Boolean algebra, set algebra, logic, and binary arithmetic has given a central role to Boolean algebra in the development of electronic digital computers. Besides that, its many applications in the design of computers, it forms the foundation of information theory because almost all search engines allow someone to enter queries in the form of logical expressions. Boolean algebra is based on propositions which are non-ambiguous sentences that can be either true or false. One can combine these propositions in a variety of ways using the connectives and, or, not. The results of these operations on propositions are demonstrated by the rules of Boolean algebra. Boolean algebra can be apply for designing and simplification of complex circuits present in computers because computer circuits are two-state devices off or on. This corresponds to the general representation of Boolean algebra with two elements, 0 and 1. There exists a function that can be utilized to evaluate any Boolean output in relation to its Boolean input by logical type of calculations. Such functions play a basic role in questions of complexity theory as well as the design of circuits and chips for digital computers. The properties of Boolean functions play a essential role in cryptography, particularly in the design of symmetric key algorithms. Boolean functions are often represented by sentences in propositional logic, and sometimes as multivariate polynomials over field $ℤ_{2}$ , but more efficient representations are binary decision diagrams (BDD), negation normal forms, and propositional directed acyclic graphs (PDAG). In cooperative game theory, monotone Boolean functions are called simple games (voting games); this notion is applied to solve problems in social choice theory. Concepts of Boolean algebra were applied to electronic switching circuits by Claude Shannon in 1937; after that became a standard part of electronic design methodology by 1950s [3]. The notion of hypergraph has been introduced by Berge as a generalization of graph around 1960s, one of the initial concerns was to extend some classical results of graph theory; the notion of hypergraph has been considered as a useful tool to analyze the structure of a system. Further materials with regard to the graph and hypergraph are available in the literature too [2 , 9–11]. Graphs and hypergraphs can be applied to describe the network systems. Nowadays, some features of hypergraphs are applied significantly in computer science such as in machine learning. There has been a lot of research about the application of hypergraphs in relational databases might have been viewed as a sort of data mining. The reason is that why hypergraphs seem proper to demonstrate relations in information systems, social networks, document centered information processing, web information systems, and computer science, the relationships among services within a service oriented architecture [4 , 8].

With regard to these points, this paper considers the concept of hypergraphs and their application in computer science. The notation of switching functions has been considered and investigated the relationship between of hypergraphs and switching functions. This study, for given T.B.T(total binary truth table), presents a new concept of hypergraphable Boolean functions and Boolean functionable hypergraphs. Indeed, we for any Boolean function construct a hyperdiagram which is called a hyperdiagram based on a given Boolean function and we investigate some condition that is a hypergraph based on a given Boolean function. Also for all arbitrary hypergraph, we extracted a Boolean function titled Boolean functionable hypergraph. It is demonstrated that every hypergraph is a Boolean functionable hypergraph. Based on these points a question is presented: Does it correspond to a switching expression from any given T.B.T?

The main motivation for this paper is the extraction of an irreducible switching expression from each T.B.T. So we define the concept of Boolean function–based hypergraph and the notation of unitors set of Boolean functions. Finally, these concepts has been applied it is proved that every T.B.T corresponds to a minimum Boolean expression via unitors set and presents some conditions on T.B.T to obtain a minimum irreducible Boolean expression from switching functions.

2 Preliminaries

In this section, some definitions and results are presented as follows:

Let X be an arbitrary set. Then we denote P^* (X) = P (X)\∅, where P (X) is the power set of X.

Definition 2.1. Let G = {x₁, x₂, …, x_n} be a finite set. A hypergraph on G is a pair $H = (G, {E_{i}}_{i = 1}^{m})$ such that for all 1 ≤ i ≤ m, ∅ ≠ E_i ⊆ G and $⋃_{i = 1}^{m} E_{i} = G$ . The elements x₁, x₂, …, x_n of G are called vertices, and the sets E₁, E₂, …, E_m are called the edges (hyperedges) of the hypergraph H. For each 1 ≤ k ≤ m if |E_k|≥2, then E_k is represented by a continuous curve joining its vertices, if |E_k|=1 by a cycle on the element (loop). If for all 1 ≤ k ≤ m |E_k|=2, the hypergraph becomes an ordinary (undirected) graph.

Definition 2.2. [4] Let G = {x₁, x₂, …, x_n} be a finite set. A hyperdiagram on G is a pair $H = (G, {E_{k}}_{k = 1}^{m})$ such that for all 1 ≤ k ≤ m, E_k ⊆ G and |E_k|≥1. Clearly every hypergraph is a hyperdiagram, while the converse is not necessarily true.

We say that two hyperdiagrams $H = (G, {E_{k}}_{k = 1}^{m})$ and $H^{'} = (G^{'}, {E_{k}^{'}}_{k = 1}^{m'})$ are isomorphic if m = m′ and there exists a bijection φ : G → G′ and a permutation τ : {1, 2, …, m} → {1, 2, …, m′} such that for all x, y ∈ G, if for some 1 ≤ i ≤ m, x, y ∈ E_i, then φ (x) , φ (y) ∈ E_τ(i), if for all 1 ≤ i ≤ m, x, y ∉ E_i, then φ (x) , φ (y) ∉ E_τ(i) and if for some 1 ≤ i ≤ m, x ∈ E_i, for all 1 ≤ j ≤ m, y ∉ E_j, then φ (x) ∈ E_τ(i) and φ (y) ∉ E_j. Since every hypergraph is a hyperdiagram, we define an isomorphic hypergraphs in a similar a way.

3 (Switching)Boolean functions and hypergraphs

In this section, we apply a notation of total binary truth table(T.B.T) on Boolean variables and introduce the concept of hypergraphable Boolean functions, Boolean functionable hypergraphs; also, we investigate some of their properties. We consider every (switching)Boolean function f : B_n → B = {0, 1} by $f (x_{1}, x_{2}, \dots, x_{n}) = \sum_{j = 1}^{m} \prod_{i = 1}^{k_{j}} \bar{x_{i}}$ , where for all $1 \leq i \leq n, \bar{x_{i}}$ is a literal(Boolean variable or the complement of a Boolean variable) and $m, j, k_{j} \in ℕ$ . Let $n \in ℕ, m \in ℕ^{*}$ , x₁, x₂, …, x_n be arbitrary Boolean variables and for all 0 ≤ j ≤ m, f^(m) (x₁, x₂, …, x_n) be Boolean functions. We will denote a total binary truth table(T.B.T) on Boolean variables x₁, x₂, …, x_n by a set $T (f^{(0)}, f^{(1)}, \dots, f^{(m)}, \bar{x_{1}}, \dots, \bar{x_{n}}) = {f^{(0)}, f^{(1)}, \dots, f^{(m)}, (x_{1}, \dots, x_{n})}$ , where for all 0 ≤ j ≤ m, f^(m) (x₁, x₂, …, x_n), are Boolean functions(see Table 1) and for m = 0, we will denote it by $T (f, x_{1}, x_{2}, \dots, x_{n})$ .

Table 1
T. B. T with n variables $T (f^{(0)}, f^{(1)}, \dots, f^{(m)}, x_{1}, x_{2}, \dots, x_{n})$

x ₁ x ₂ … x _n f⁽⁰⁾ (x₁, …, x_n) f⁽¹⁾ (x₁, …, x_n) … f^(m) (x₁, …, x_n)

0 0 … 0 $f_{1}^{(0)} (x_{1}, \dots, x_{n})$ $f_{1}^{(1)} (x_{1}, \dots, x_{n})$ … $f_{1}^{(m)} (x_{1}, \dots, x_{n})$

0 0 … 1 $f_{2}^{(0)} (x_{1}, \dots, x_{n})$ $f_{2}^{(1)} (x_{1}, \dots, x_{n})$ … $f_{2}^{(m)} (x_{1}, \dots, x_{n})$

⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮

0 0 … 1 $f_{2^{n - 1}}^{(0)} (x_{1}, \dots, x_{n})$ $f_{2^{n - 1}}^{(1)} (x_{1}, \dots, x_{n})$ … $f_{2^{n - 1}}^{(m)} (x_{1}, \dots, x_{n})$

1 1 … 1 $f_{2^{n}}^{(0)} (x_{1}, \dots, x_{n})$ $f_{2^{n}}^{(1)} (x_{1}, \dots, x_{n})$ … $f_{2^{n}}^{(m)} (x_{1}, \dots, x_{n})$

x ₁	x ₂	…	x _n	f⁽⁰⁾ (x₁, …, x_n)	f⁽¹⁾ (x₁, …, x_n)	…	f^(m) (x₁, …, x_n)
0	0	…	0	$f_{1}^{(0)} (x_{1}, \dots, x_{n})$	$f_{1}^{(1)} (x_{1}, \dots, x_{n})$	…	$f_{1}^{(m)} (x_{1}, \dots, x_{n})$
0	0	…	1	$f_{2}^{(0)} (x_{1}, \dots, x_{n})$	$f_{2}^{(1)} (x_{1}, \dots, x_{n})$	…	$f_{2}^{(m)} (x_{1}, \dots, x_{n})$
⋮	⋮	⋮	⋮	⋮	⋮	⋮
0	0	…	1	$f_{2^{n - 1}}^{(0)} (x_{1}, \dots, x_{n})$	$f_{2^{n - 1}}^{(1)} (x_{1}, \dots, x_{n})$	…	$f_{2^{n - 1}}^{(m)} (x_{1}, \dots, x_{n})$
1	1	…	1	$f_{2^{n}}^{(0)} (x_{1}, \dots, x_{n})$	$f_{2^{n}}^{(1)} (x_{1}, \dots, x_{n})$	…	$f_{2^{n}}^{(m)} (x_{1}, \dots, x_{n})$

Define a binary operation “+” on $T (f, f^{'}, x_{1}, \dots, x_{n})$ by (f + f′) (x₁, …, x_n) = f (x₁, …, x_n) + f′ (x₁, …, x_n), a binary operation “.” on $T (f, f^{'}, x_{1}, \dots, x_{n})$ by (f . f′) (x₁, …, x_n) = f (x₁, …, x_n) . f′ (x₁, …, x_n) and a unary operation $c : T (f, f^{'}, x_{1}, \dots, x_{n}) \to T (f, f^{'}, x_{1}, \dots, x_{n})$ by c (x_i) =1 - x_i, and c (f (x₁, …, x_n)) =1 - f (x₁, …, x_n). Clearly $T (f, f^{'}, x_{1}, \dots, x_{n}), +, ., c)$ is a Boolean algebra.

Example 3.1. Consider a T.B.T $T (f, g, x_{1}, x_{2}, x_{3})$ in Table 2. The binary operations together with a unary operation are computed in this Table.

Table 2

T.B.T $T (f, g, x_{1}, x_{2}, x_{3})$

x ₁	x ₂	x ₃	f	g	f + g	f . g	c (f)
0	0	0	1	1	1	1	0
0	0	1	1	1	1	1	0
0	1	0	1	0	1	0	0
0	1	1	0	0	0	0	1
1	0	0	1	0	1	0	0
1	0	1	1	1	1	1	0
1	1	0	0	1	1	0	1
1	1	1	0	1	1	0	1

Definition 3.2 Let $T (f, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T.

for all 1 ≤ j ≤ m, consider $E_{j}^{f} = {\bar{x_{1}}, \bar{x_{2}}, \dots, \bar{x_{k_{j}}}}$ and $H^{f} = (G^{f}, {E_{j}^{f}}_{j = 1}^{m})$ , where $G^{f} = (⋃_{i = 1}^{n} x_{i}) \cup (⋃_{j = 1}^{m} E_{j}^{f})$ .

Boolean function f (x₁, …, x_n) is called a hypergraphable Boolean function, if H^f is a hypergraph and we say H^f is a hypergraph based on a Boolean function f (x₁, …, x_n).

Let $H^{'} = (G^{'}, {E_{i}^{'}}_{i = 1}^{n})$ be a hypergraph. Then H′ is sailed to be a Boolean functionable hypergraph, if there exists a Boolean function as f (x₁, …, x_n) such that H^f ≅ H′ and we call a Boolean function f (x₁, …, x_n) is obtained from hypergraph H′.

Because each hypergraph is a hyperdiagram, we have the following lemma:

Lemma 3.3. Let $T (f, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T. Then f (x₁, x₂, …, x_n) is a hyperdiagramable Boolean function. Proof. Let $f (x_{1}, x_{2}, \dots, x_{n}) = \sum_{j = 1}^{m} \prod_{i = 1}^{k_{j}} \bar{x_{i}}$ be a Boolean function. Thus $H^{f} = (G^{f}, {E_{j}^{f}}_{j = 1}^{m})$ is a hyperdiagram, where for all 1 ≤ j ≤ m, $E_{j}^{f} = {\bar{x_{1}}, \bar{x_{2}}, \dots, \bar{x_{k_{j}}}}$ and $G^{f} = (⋃_{i = 1}^{n} x_{i}) \cup (⋃_{j = 1}^{m} E_{j}^{f})$ . □ Let f (x₁, …, x_n) be a Boolean function. From now on, we denote the hyperdiagram based on Boolean function f (x₁, …, x_n) by f^↗ (x₁, …, x_n).

Example 3.4. (i) Let f (x, y, z) = x′y′z + x′y′z′. Then, we have the hyperdiagram $H^{f} = (G^{f}, {E_{i}^{f}}_{i = 1}^{2})$ in Figure 1, where $E_{1}^{f} = {x^{'}, y^{'}, z}$ a nd $E_{2}^{f} = {x^{'}, y^{'}, z^{'}}$ (by definition, the vertices x, y do not belong to every hyperedge).

Fig.1

Hyperdiagram f^↗ (x, y, z).

Since $⋃_{i = 1}^{2} E_{i}^{f} = {x^{'}, y^{'}, z, z^{'}} \neq {x, y, x^{'}, y^{'}, z,$ z′} = G^f, so $H^{f} = (G, {E_{i}^{f}}_{i = 1}^{2})$ is not a hypergraph. Thus, f (x, y, z) is not a hypergraphable Boolean function.

(ii) Let g (x, y, z) = xz′ + xyz + yz′. So we obtain the hypergraph $H^{g} = (G^{g}, E_{1}^{g}, E_{2}^{g}, E_{3}^{g})$ in Figure 2, where $E_{1}^{g} = {x, y, z}, E_{2}^{g} = {z^{'}, y}$ and $E_{3}^{g} = {x, z^{'}} .$ Thus g (x, y, z) is a hypergraphable Boolean function.

Fig.2

Hypergraph g^↗ (x, y, z).

Theorem 3.5. Every hypergraph is a Boolean functionable hypergraph.

Proof. Let $H = (G, {E_{i}}_{i = 1}^{m})$ be an arbitrary hypergraph, where G = {g₁, g₂, …, g_n}. Now, define a bijection φ : G → G′ = {x₁, x₂, …, x_n} by $φ (g_{i}) = \bar{x_{i}} \in B$ and for all $1 \leq i \leq m, E_{i}^{'} = φ (E_{i})$ . Clearly $H = (G, {E_{i}}_{i = 1}^{m}) ≅ H^{'} = (G^{'}, {E_{i}^{'}}_{i = 1}^{m})$ and we consider for all $1 \leq i \leq m, f_{i} (x_{1}, x_{2}, \dots, x_{n}) = \prod_{j = 1}^{| E_{i}^{'} |} \bar{x_{j}},$ where for $1 \leq j \leq | E_{i}^{'} |$ we have $\bar{x_{j}} \in E_{j}^{'} .$ If $f (x_{1}, x_{2}, \dots, x_{n}) = \sum_{i = 1}^{m} f_{i} (x_{1}, x_{2}, \dots, x_{n})$ , then it is easy to see that H^′f ≅ H′ ≅ H and so it is a Boolean functionable hypergraph. □ Let $H = (G, {E_{i}}_{i = 1}^{m})$ be a hypergraph. From now on, we denote the each Boolean function which is obtained from hypergraph $H = (G, {E_{i}}_{i = 1}^{m})$ by H^↙ and

$H^{↙} = {H^{↙} | H^{↙} is a Boolean function which$ $obtained from hypergraph H = (G, {E_{i}}_{i = 1}^{m})}$ .

Example 3.6. Consider the hypergraph $H = (G, {E_{i}}_{i = 1}^{3})$ in Figure 3. Define a bijection φ : G → G′ by $φ = {(g_{1}, x_{1}), (g_{2}, x_{2}), (g_{3}, x_{3}), (g_{1}^{'}, x_{1}^{'}), (g_{2}^{'}, x_{2}^{'}), (g_{3}^{'},$ $x_{3}^{'}), (E_{1}, E_{1}^{'}), (E_{2}, E_{2}^{'}), (E_{3}, E_{3}^{'})}$ , where for all $1 \leq i \leq 3, x_{i}, x_{i}^{'} \in {0, 1}$ . So, we obtain $H = (G, {E_{i}}_{i = 1}^{3}) ≅ H^{'} = (G^{'}, {E_{i}^{'}}_{i = 1}^{3})$ , where $G^{'} = {x_{1}, x_{2}, x_{3}, x_{1}^{'}, x_{2}^{'}, x_{3}^{'}}, E_{1}^{'} = {x_{1}^{'}, x_{2}, x_{3}}, E_{2}^{'} = {x_{1}^{'}, x_{2}^{'}, x_{3}}$ and $E_{3}^{'} = {x_{1}, x_{2}, x_{3}^{'}} .$ We consider $f_{1} (x_{1}, x_{2}, x_{3}) = x_{1}^{'} x_{2} x_{3}, f_{2} (x_{1}, x_{2}, x_{3}) = x_{1}^{'} x_{2}^{'} x_{3}$ , $f_{3} (x_{1}, x_{2}, x_{3}) = x_{1} x_{2} x_{3}^{'}$ and $f (x_{1}, x_{2}, x_{3}) = x_{1}^{'} x_{2} x_{3} + x_{1}^{'} x_{2}^{'} x_{3} + x_{1} x_{2} x_{3}^{'}$ . Then, it is easy to see that H^′f ≅ H′ ≅ H and so it is a Boolean functionable hypergraph.

Fig.3

Hypergraph H.

Corollary 3.7. Let $H = (G, {E_{i}}_{i = 1}^{m})$ be a hypergraph. Then

(H^↙) ^↗ ≅ H.

$| H^{↙} | \geq 1$ .

$| H^{↙} | = | G |!$ .

In Example 3.4 (i), since f^↗ is not a hypergraph(but f^↗ always is a hyperdiagram), we can not obtain the Boolean function (f^↗) ^↙ .

Theorem 3.8. Let $T (f, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T. If f is a hypergraphable Boolean function, then (f^↗) ^↙ ∼ f.

Proof. Since f (x₁, x₂, …, x_n) is a hypergraphable Boolean function, we get $H^{f} = (G^{f}, {E_{j}^{f}}_{j = 1}^{m})$ is a hypergraph, where for all 1 ≤ j ≤ m, $E_{j}^{f} = {\bar{x_{1}}, \bar{x_{2}}, \dots, \bar{x_{j}}}$ and $G^{f} = (⋃_{i = 1}^{n} x_{i}) \cup (⋃_{j = 1}^{m} E_{j}^{f})$ . Consider $g (x_{1}, x_{2}, \dots, x_{n}) = \sum_{j = 1}^{m} \prod_{\bar{x_{i}} \in E_{j}} \bar{x_{i}}$ . Indeed, by Theorem 3.5, g (x₁, x₂, …, x_n) = (f^↗) ^↙ (x₁, x₂, …, x_n) □

Example 3.9. Consider f (x, y, z) = xz′ + xy′z + yz′. So we obtain the hypergraph $H^{f} = (G^{f}, E_{1}^{f}, E_{2}^{f}, E_{3}^{f})$ in Figure 4, where $E_{1}^{f} = {x, z^{'}}, E_{2}^{f} = {x, y^{'}, z}$ and $E_{3}^{f} = {y, z^{'}} .$ Thus f (x, y, z) is a hypergraphable Boolean function.

So by Theorem 3.8, $g (x_{1}, x_{2}, x_{3}) = (\sum_{j = 1}^{3} \prod_{\bar{x_{i}} \in E_{j}^{f}} \bar{x_{i}}) \sim (f^{↗})^{↙} .$

Theorem 3.10. Let $T (f, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T. If f (x₁, x₂, …, x_n) is a d.n.f and m ≥ 1 +2^n-1, then it is a hypergraphable Boolean function.

Proof. Let x₁, x₂, …, x_n be arbitrary Boolean variables. Then, we reconstruct a minterm of disjunctive normal form(d.n.f) of Boolean function f (x₁, x₂, …, x_n) in a form such that all its literal be complement of Boolean variables and denote by $m_{1} = x_{1}^{'} x_{2}^{'} \dots x_{n - 1}^{'} x_{n}^{'}$ . Then, we consider the following sequence of minterms(with at most complement of variables) of f (x₁, x₂, …, x_n): $\begin{matrix} m_{1} = (x_{1}^{'} x_{2}^{'} \dots x_{n - 1}^{'}) (x_{n}^{'}), m_{2} = (x_{1}^{'} x_{2}^{'} \dots x_{n - 1}^{'}) (x_{n}), \\ m_{3} = (x_{1}^{'} x_{2}^{'} \dots x_{n - 2}^{'}) (x_{n - 1} x_{n}^{'}), \\ m_{4} = (x_{1}^{'} x_{2}^{'} \dots x_{n - 2}^{'}) (x_{n - 1} x_{n}), \\ m_{5} = (x_{1}^{'} x_{2}^{'} \dots x_{n - 3}^{'}) (x_{n - 2} x_{n - 1} x_{n}^{'}), \\ m_{6} = (x_{1}^{'} x_{2}^{'} \dots x_{n - 3}^{'}) (x_{n - 2} x_{n - 1}^{'} x_{n}), \\ m_{7} = (x_{1}^{'} x_{2}^{'} \dots x_{n - 3}^{'}) (x_{n - 2} x_{n - 1}^{'} x_{n}^{'}), \\ m_{8} = (x_{1}^{'} x_{2}^{'} \dots x_{n - 3}^{'}) (x_{n - 2} x_{n - 1} x_{n}), \dots . \end{matrix}$ If $m_{k} = (x_{1}^{'} x_{2}^{'} \dots x_{n - k}^{'}) (x_{n - k + 1} x_{n - k + 2} \dots x_{n - 1} x_{n})$ , then, by above sequence x_n-k+1 is fixed and for all 0 ≤ i ≤ k - 2, the variable x_n-i has two cases self variable or its complement; hence, a Boolean function x_n-k+1x_n-k+2 … x_n-1x_n has 2^k-1 cases, where 1 ≤ k ≤ n - 2. It follows that for all k ≤ n - 2 at least a literal has not in a form self variable; therefore, we have 2 + 2 +2² + … +2^(n-2) = 2^(n-1) choices such that at least a literal has not in a form self variable. Thus, if m ≥ 1 +2^n-1, then a disjunctive normal form(d.n.f) of Boolean function f (x₁, x₂, …, x_n) is a hypergraphable Boolean function. □

Example 3.4 (i), demonstrate that f (x, y, z) is not a hypergraphable Boolean function, while it is a d.n.f. By Theorem 3.10, if f (x, y, z) = (x′y′) z′ + (x′y′) z + (x′) yz′ + (x′) yz, then, d.n.f f (x, y, z) is not a hypergraphable Boolean function.

Definition 3.11. Let $n \in ℕ$ and $T (f, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T. For all 1 ≤ j ≤ 2ⁿ define Unitor (f_j) = {(x₁, x₂, …, x_n) | f_j (x₁, x₂, …, x_n) =1} and will denote by Un (f_j), in the same way Unitor (f) is defined and it is denoted by Un (f).

Theorem 3.12. Let $n \in ℕ, 1 \leq j \leq 2^{n}$ and $T (f, f^{'}, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T. Then

$Un (f) = ⋃_{j = 1}^{2^{n}} Un (f_{j})$ ;

Un (f′) = Un (f) if and only if f ∼ f′;

If Un (f′) ⊆ Un (f), then (f + f′) ∼ f;

Un (f + f′) = Un (f) ∪ Un (f′);

Un (f . f′) = Un (f) ∩ Un (f′);

Un (c (f)) = B_n \ Un (f).

Proof. It is clear by definition. □

Corollary 3.13. Let $n \in ℕ, 1 \leq j \leq n$ and $T (f, f^{'}, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T. If (f + f′) ∼ f, then |Un (f′) | ≤ |Un (f) |.

Proof. Since (f + f′) ∼ f, by Theorem 3.12, Un (f + f′) = Un (f). It follows that Un (f) ∪ Un (f′) = Un (f + f′) = Un (f) and so Un (f′) ⊆ Un (f). □

4 Switching expression based on hypergraph

In this section, we consider an arbitrary T.B.T; with respect to the concept of unitors set, it looks to extract associated switching expression to given T.B.T. Indeed, we show that every T.B.T, corresponds to a hypergraph and with the application of intersection hyperedges of associated hypergraph, we generate a minimum Boolean expression. We prove that minimum Boolean expression that is obtained from any given T.B.T is not same to its D.N.F.

Theorem 4.1. Let $n \in ℕ$ . Then every $T (f ≢ 0, x_{1}, x_{2}, \dots, x_{n})$ corresponds to a hypergraph.

Proof. Let x₁, x₂, …, x_n be arbitrary Boolean variables. Consider a total binary truth table (T.B.T) $T (f, x_{1}, x_{2}, \dots, x_{n})$ in Table 1. Suppose that for $k \in ℕ$ and for all i ∈ {j₁, j₂, …, j_k}, we have Un (f_i)≠ ∅. Since $\prod_{j = 1}^{n} \bar{x_{j}} = 1$ if and only if for all $1 \leq j \leq n, \bar{x_{j}} = 1$ , for all j₁ ≤ i ≤ j_k define $f_{j_{i}} (x_{1}, x_{2}, \dots, x_{n}) = \bar{x_{1}} \bar{x_{2}} \dots \bar{x_{n}}$ , where $\prod_{j = 1}^{n} \bar{x_{j}} = 1$ . Now, for all j₁ ≤ i ≤ j_k, set $E_{i} = {\bar{x_{1}}, \bar{x_{2}}, \dots, \bar{x_{n}} | \prod_{j = 1}^{n} \bar{x_{j}} = f_{j} (x_{1}, x_{2}, \dots, x_{n})} .$ Thus, it is easy to see that $H = (G = ⋃_{i = j_{1}}^{j_{k}} E_{i}, {E_{i}}_{i = j_{1}}^{j_{k}})$ is a hypergraph. □

We will call the hypergraph H in Theorem 4.1, as Boolean function–based hypergraph and will denote by $(H, T)$ .

Example 4.2. Consider a T.B.T $T (f, x_{1}, x_{2}, x_{3})$ in Table 3. Computations demonstrate that $Un (f_{2}) = {(x_{1}^{'}, x_{2}^{'}, x_{3})}, Un (f_{3}) = {(x_{1}^{'}, x_{2}, x_{3}^{'})}, Un (f_{5}) = {(x_{1}, x_{2}^{'}, x_{3}^{'})}, Un (f_{8}) = {(x_{1}, x_{2}, x_{3})}$ . Now, it is obtained a Boolean function–based hypergraph $(H, T)$ in Figure 5.

Fig.4

Hypergraph f^↗ (x, y, z).

Fig.5

Hypergraph $(H, T)$ .

Table 3

T. B. T with 3 variables $T (f, x_{1}, x_{2}, x_{3})$

x ₁	x ₂	x ₃	f (x₁, x₂, x₃)
0	0	0	f₁ (x₁, x₂, x₃) =0
0	0	1	f₂ (x₁, x₂, x₃) =1
0	1	0	f₃ (x₁, x₂, x₃) =1
0	1	1	f₄ (x₁, x₂, x₃) =0
1	0	0	f₅ (x₁, x₂, x₃) =1
1	0	1	f₆ (x₁, x₂, x₃) =0
1	1	0	f₇ (x₁, x₂, x₃) =0
1	1	1	f₈ (x₁, x₂, x₃) =1

Define a relation ∼ on a T.B.T $T (f, f^{'}, x_{1}, x_{2}, \dots, x_{n})$ by f ∼ f′ if and only if for all (x₁, x₂, …, x_n) ∈ B_n, we have f (x₁, x₂, …, x_n) = f′ (x₁, x₂, …, x_n) (f ≡ f′). It is clear that ∼ is a congruence equivalence relation on $T (f, f^{'}, x_{1}, x_{2}, \dots, x_{n})$ . For 0 ≤ j, j′ ≤ m, we say that $T (f^{(j)}, x_{1}, x_{2}, \dots, x_{n})$ and $T^{'} (f^{(j^{'})}, x_{1}, x_{2}, \dots, x_{n})$ are equivalent, if f^(j) ∼ f^(j′).

Theorem 4.3. Let 0 ≤ j, j′ ≤ m. If $T (f^{(j)}, x_{1}, \dots, x_{n})$ and $T^{'} (f^{(j^{'})}, x_{1}, \dots, x_{n})$ are equivalent, then their Boolean function–based hypergraph are isomorphic.

Proof. Let 0 ≤ j, j′ ≤ m. Since $T (f^{(j)}, x_{1}, \dots, x_{n}) \sim T^{'} (f^{(j^{'})}, x_{1}, \dots, x_{n})$ , for all 1 ≤ i ≤ 2ⁿ we get that $Un (f_{i}^{(j)}) = Un (f_{i}^{(j^{'})})$ . Using Theorem 4.1, $T (f^{(j)}, x_{1}, x_{2}, \dots, x_{n})$ corresponds to $(H, T)$ if and only if $T (f^{(j^{'})}, x_{1}, x_{2}, \dots, x_{n})$ corresponds to $(H^{'}, T^{'})$ . Hence $(H, T) ≅ (H^{'}, T^{'})$ □

Definition 4.4. Let $n \in ℕ, m \in ℕ^{*}$ , 1 ≤ k ≤ n and $T (f^{(0)}, \dots, f^{(m)}, x_{1}, \dots, x_{n})$ be a T.B.T, where for 0 ≤ t ≤ m, f^(t) (x₁, …, x_n) $= \sum_{i = 1}^{2^{n}} f_{i}^{(t)} (x_{1}, x_{2}, \dots, x_{n})$ . Then

$I (n, f^{(t)}, 1) = {j | f_{j}^{(t)} (x_{1}, x_{2}, \dots, x_{n}) = 1, where 1 \leq j \leq 2^{n}}$ ;

$P (k, x_{1}, x_{2}, \dots, x_{k}, 1) = {\prod_{i = 1}^{n} \bar{x_{i}} | (\prod_{i = 1}^{k} x_{i}) (\prod_{i = k + 1}^{n} \bar{x_{i}}) = 1}$ .

Example 4.5. Consider a T.B.T $T (f, x_{1}, x_{2}, x_{3})$ in Table 3. Simple computations demonstrate $I (n, f, 1) = {j | f_{j} (x_{1}, x_{2}, x_{3}) = 1, where 1 \leq j \leq 8} = 4, P (3, x_{1}, x_{2}, x_{3}, 1) = {x_{1} x_{2} x_{3}}, P (2, x_{1}, x_{2}, 1) = {x_{1} x_{2} x_{3}^{'}, x_{1} x_{2} x_{3}},$ $P (1, x_{1}, 1) = {x_{1} x_{2}^{'} x_{3}^{'}, x_{1} x_{2}^{'} x_{3}, x_{1} x_{2} x_{3}^{'}, x_{1} x_{2} x_{3}}, | P (3, x_{1}, x_{2}, x_{3}, 1) | = 1, | P (2, x_{1}, x_{2}, 1) | = 2$ and |P (1, x₁, 1) |=4.

Theorem 4.6. Let $n \in ℕ, 1 \leq j \leq n$ and $T (f, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T. Then, |P (k = j, x₁, x₂, …, x_k, 1) |=2^n-j.

Proof. Let x₁, x₂, …, x_j be j Boolean variables. Then, $\prod_{i = 1}^{j} x_{i} = 1$ if and only if x₁ = x₂ = … = x_j = 1. So $\prod_{i = j + 1}^{n} \bar{x_{i}} = 0$ or $\prod_{i = j + 1}^{n} \bar{x_{i}} = 1$ . Now, $\prod_{i = j + 1}^{n} \bar{x_{i}} = 0$ if and only if for some j + 1 ≤ t ≤ n we have $\bar{x_{t}} = 0,$ where have 2^n-j - 1 cases. In addition, $\prod_{i = j + 1}^{n} \bar{x_{i}} = 1$ if and only if for all j + 1 ≤ t ≤ n we have $\bar{x_{t}} = 1 .$ So |P (j, x₁, x₂, …, x_j, 1) |=2^n-j. □

Corollary 4.7. Let $n \in ℕ, m \in ℕ^{*}$ and $T (f, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T. Then

if k = 1, then |P (k, x₁, x₂, …, x_k, 1) |=2^n-1;

if k = n - 1, then |P (k, x₁, x₂, …, x_k, 1) |=2;

if k = n - i, then |P (k, x₁, x₂, …, x_k, 1) |=2ⁱ;

if k = n, then |P (k, x₁, x₂, …, x_k, 1) |=1.

Let $n \in ℕ$ and $T (f^{(0)}, \dots, f^{(m)}, x_{1}, \dots, x_{n})$ be a T.B.T, 1 ≤ k ≤ n, 0 ≤ t, t′ ≤ m. Define $(f^{(t)} f^{(t^{'})}) (x_{1}, \dots, x_{n}) = {f^{(s)} (x_{1}, \dots, x_{n}) | f_{j}^{(s)} (x_{1}, \dots, x_{n}) = f_{j}^{(t)} (x_{1}, \dots, x_{n}) f_{j}^{(t^{'})} (x_{1}, \dots, x_{n}) for all 1 \leq j \leq 2^{n}}$ and $(f^{(t)} + f^{(t^{'})}) (x_{1}, \dots, x_{n}) = {f^{(s)} (x_{1}, \dots, x_{n}) | f_{j}^{(s)} (x_{1}, \dots, x_{n}) = f_{j}^{(t)} (x_{1}, \dots, x_{n}) + f_{j}^{(t^{'})} (x_{1}, \dots, x_{n}) for all 1 \leq j \leq 2^{n}}$ . So we have the following Theorem.

Theorem 4.8. Let $n \in ℕ$ and $T (f^{(0)}, \dots,$ f^(m), x₁, …, x_n) be a T.B.T, 1 ≤ k ≤ n, 0 ≤ t, t′ ≤ m. Then

$I (n, \bar{x_{k}}, 1) = 2^{n - 1}$ ;

I (n, 1, 1) =2ⁿ and I (n, 0, 1) =0;

$I (n, \bar{x_{k}} + f^{(t)}, 1) = [I (n, \bar{x_{k}}, 1) + I (n, f^{(t)}, 1)] - I (n, \bar{x_{k}} f^{(t)}, 1)$ .

Proof. (i) Let 1 ≤ k ≤ n. Then by Corollary 4.7, we obtain that $I (n, \bar{x_{k}}, 1) = | P (1, x_{1}, x_{2}, \dots, x_{k}, 1) | = 2^{n - 1}$ .

(ii) In the same way it is obtained from Corollary 4.7.

(iii) Let 1 ≤ k ≤ n, 1 ≤ j ≤ 2ⁿ. Because $\bar{x_{k}} \sim 0$ or $\bar{x_{k}} \sim 1$ , for all 1 ≤ j ≤ 2ⁿ, we get that $(\bar{x_{k}} + f_{j}^{(t)}) \sim f_{j}^{(t)}$ or $(\bar{x_{k}} + f_{j}^{(t)}) \sim 1$ . If $(\bar{x_{k}} + f_{j}^{(t)}) \sim f_{j}^{(t)}$ , then $I (n, \bar{x_{k}} + f_{j}^{(t)}, 1) = 0 + I (n, f_{j}^{(t)}, 1)$ . If $(\bar{x_{k}} + f_{j}^{(t)}) \sim 1$ , since for all $1 \leq j \leq 2^{n}, 1 f_{j}^{(t)} = f_{j}^{(t)}$ by item (ii), we have $\begin{matrix} I (n, \bar{x_{k}} + f_{j}^{(t)}, 1) = 2^{n} = 2^{n} + I (n, f_{j}^{(t)}, 1) - I (n, f_{j}^{(t)}, 1) \\ = [I (n, \bar{x_{k}}, 1) + I (n, f_{j}^{(t)}, 1)] - I (n, \bar{x_{k}} f_{j}^{(t)}, 1) . \end{matrix}$ □

Theorem 4.9. Let $n \in ℕ$ and $T (f^{(0)}, \dots, f^{(m)},$ x₁, …, x_n) be a T.B.T, 1 ≤ k ≤ n, 1 ≤ i ≤ 2ⁿ, 0 ≤ t, t′ ≤ m. Then

I (n, f^(t)+ f^(t′), 1) = [I (n, f^(t), 1) + I (n, f^(t′), 1)] - I (n, f^(t)f^(t′), 1) ;

I (n, f^(t)f^(t′), 1) ≤ min {I (n, f^(t), 1) , I (n, f^(t′), 1)}.

Proof. (i) Because for all 1 ≤ j ≤ 2ⁿ and 1 ≤ t ≤ m we have $f_{j}^{(t)} = \prod_{i = 1}^{n} \bar{x_{i}}$ and $\prod_{i = 1}^{n} x_{i} \sim 0, \prod_{i = 1}^{n} x_{i} \sim 1$ or there exists 1 ≤ j ≤ 2ⁿ such that $\prod_{i = 1}^{n} x_{i} \sim x_{j}$ , so by Theorem 4.8 (iii), the proof is obtained.

(ii) By definition, for all $1 \leq j, j \leq 2^{n}, f_{j}^{(t)} (x_{1}, x_{2}, \dots, x_{n}) . f_{j}^{(t^{'})} (x_{1}, x_{2}, \dots, x_{n}) = 1$ if and only if $f_{j}^{(t)} (x_{1}, x_{2}, \dots, x_{n}) = f_{j}^{(t^{'})} (x_{1}, x_{2}, \dots, x_{n}) = 1$ , so $\begin{matrix} I (n, f^{(t)} f^{(t^{'})}, 1) = {j | f_{j}^{(t)} (x_{1}, x_{2}, \dots, x_{n}) = \\ f_{j}^{(t^{'})} (x_{1}, x_{2}, \dots, x_{n}) = 1, where 1 \leq j \leq 2^{n}} \\ \leq {j | f_{j}^{(t)} (x_{1}, x_{2}, \dots, x_{n}) = 1, \\ where 1 \leq j \leq 2^{n}} \end{matrix}$ and $\begin{matrix} I (n, f^{(t)} f^{(t^{'})}, 1) = {j | f_{j}^{(t)} (x_{1}, x_{2}, \dots, x_{n}) = \\ f_{j}^{(t^{'})} (x_{1}, x_{2}, \dots, x_{n}) = 1, where 1 \leq j \leq 2^{n}} \\ \leq {j | f_{j}^{(t^{'})} (x_{1}, x_{2}, \dots, x_{n}) = 1, \\ where 1 \leq j \leq 2^{n}} . \end{matrix}$ Hence I (n, f^(t)f^(t′), 1) ≤ min {I (n, f^(t), 1) , I (n, f^(t′), 1)}. □

Corollary 4.10. Let $n \in ℕ$ and $T (f, f^{'}, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T. Then (f + f′) ∼ f if and only if I (n, f + f′, 1) = I (n, f, 1).

Theorem 4.11. Let $n \in ℕ, 1 \leq j \leq n$ and $T (f, f^{'}, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T. If there exists some 1 ≤ i₁, i₂, …, i_k ≤ n such that $f^{'} \sim \prod_{j = 1}^{k} x_{i_{j}}$ , then I (n, f + f′, 1) >2^n-k.

Proof. Let 1 ≤ i₁, i₂, …, i_k ≤ n and $f^{'} \sim \prod_{j = 1}^{k} x_{i_{j}}$ . By Theorem 4.9, $\begin{matrix} I (n, f^{(t)} + f^{(t^{'})}, 1) \\ = [I (n, f^{(t)}, 1) + I (n, f^{(t^{'})}, 1)] - I (n, f^{(t)} f^{(t^{'})}, 1) \\ = [I (n, f^{(t)}, 1) + I (n, \prod_{j = 1}^{k} x_{i_{j}}, 1)] - I (n, (f^{(t)}) \prod_{j = 1}^{k} x_{i_{j}}, 1) \\ > I (n, f^{(t)}, 1) + 2^{n - k} - I (n, (f^{(t)}), 1) = 2^{n - k} . \end{matrix}$ □

Theorem 4.12 Let $n \in ℕ, 1 \leq j \leq n$ and $T (f, f^{'}, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T and $f^{'} \sim \prod_{j = 1}^{k} x_{i_{j}}$ , where 1 ≤ i₁, i₂, …, i_k ≤ n.

If I (n, f, 1) <2^n-1, then (f + f′) ≁ f;

If I (n, f′, 1) = I (n, f, 1) and Un (f′) ⊆ Un (f) imply that f′ ∼ f;

Proof. (i) Let (f + f′) ∼ f. Using Theorem 4.9, I (n, f + f′, 1) = I (n, f, 1) + I (n, f′, 1) - I (n, f . f′, 1). Because I (n, ff′, 1) ≤ min {I (n, f, 1) , I (n, f′, 1)}, we get that I (n, f + f′, 1) ≥ I (n, f, 1) +2^n-k - I (n, f, 1) =2^n-k, which is a contradiction.

(ii) Let f′ (x₁, …, x_n) =1. Then Un (f′) ⊆ Un (f) implies that (x₁, …, x_n) ∈ Un (f) and so f (x₁, …, x_n) =1. Suppose that f′ (x₁, …, x_n) =0, then Un (f′) ⊆ Un (f) implies that (x₁, …, x_n) ∈ Un (f) \ Un (f′) or (x₁, …, x_n) ∉ Un (f). If (x₁, …, x_n) ∉ Un (f), then f (x₁, …, x_n) =0 and in this case f ∼ f′. If (x₁, …, x_n) ∈ Un (f), then f (x₁, …, x_n) =1 and it follows that I (n, f′, 1) < I (n, f, 1), which is a contradiction. □

Theorem 4.13. Every T.B.T corresponds to a Boolean expression.

Proof. Let $n \in ℕ$ and $T (f, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T. If for all 1 ≤ j ≤ 2ⁿ, f_j (x₁, x₂, …, x_n) =0, then consider g (x₁, x₂, …, x_n) ≡0. In a similar a way that, if for all 1 ≤ j ≤ 2ⁿ, f_j (x₁, x₂, …, x_n) =1, then consider g (x₁, x₂, …, x_n) ≡1. Now, if there exist $k \in ℕ$ and 1 ≤ j₁, j₂, …, j_k ≤ 2ⁿ such that f_{j
_k} (x₁, x₂, …, x_n) =1, then consider $f_{j} (x_{1}, x_{2}, \dots, x_{n}) = \prod_{i = 1}^{n} \bar{x_{i}}$ in such a way that for all $1 \leq i \leq n, \bar{x_{i}} = 1$ . The application of Theorem 4.1, $H = (G = ⋃_{j = 1}^{k} E_{j}, {E_{j}}_{j = 1}^{k})$ is a hypergraph, where for all 1 ≤ j ≤ k, $E_{j} = {\bar{x_{1}}, \bar{x_{2}}, \dots, \bar{x_{n}} | \prod_{j = 1}^{n} \bar{x_{j}} = f_{j} (x_{1}, x_{2}, \dots, x_{n}) = 1}$ and for all 1 ≤ i ≠ j ≤ k we set F_ij = E_i ∩ E_j. If for all 1≤ i ≠ j ≤ k, F_ij = ∅, then consider $g (x_{1}, \dots, x_{n}) = \sum_{1 \leq j \leq k} \prod_{α \in E_{j}} α$ . In this case, since for all $1 \leq j \leq k, Un (f_{j}) = Un (\prod_{α \in E_{j}} α)$ , by Theorem 3.12, Un (f) = Un (g) and so f (x₁, x₂, …, x_n) = g (x₁, x₂, …, x_n) . If there exist 1 ≤ r ≤ k and i ≠ j ∈ {i₁, i₂, …, i_r} such that F_ij≠ ∅, consider $g_{ij} (x_{1}, x_{2}, \dots, x_{n}) = \prod_{α \in F_{ij}} α$ . Clearly for all i₁ ≤ i, j ≤ i_r, Un (g_ij) ⊆ Un (f), so if I (n, dis∑_{substacki₁≤i≤i_ri₁≤j≤i_s}g_ij, 1) = I (n, f, 1), thus by Theorems 3.12 and 4.12, g ∼ f, where g (x₁, x₂, …, x_n) = dis∑_{substacki₁≤i≤i_ri₁≤j≤i_s}g_ij (x₁, …, x_n). But if I (n, dis∑_{substacki₁≤i≤i_ri₁≤j≤i_s}g_ij, 1) < I (n, f, 1), consider 1 ≤ s ≤ k, j ∈ {j₁, j₂, …, j_s} and $f_{j} (x_{1}, x_{2}, \dots, x_{n}) = \prod_{β \in E_{j}} β$ such that Un (dis∑_{substacki₁≤i≤i_ri₁≤j≤i_s}g_ij) ≠ Un (f_j) ⊆ Un (f) and $I (n, \sum_{i_{1} \leq i \leq i_{r} i_{1} \leq j \leq i_{s}} g_{ij} + \sum_{j = j_{1}}^{j_{s}} f_{j}, 1) = I (n, f, 1)$ . Thus by Theorem 4.12, we get that g ∼ f, where $g (x_{1}, x_{2}, \dots, x_{n}) = \sum_{j = j_{1}}^{j_{s}} f_{j} (x_{1}, \dots, x_{n}) + \sum_{i_{1} \leq i \leq i_{r} i_{1} \leq j \leq i_{s}} g_{ij} (x_{1}, \dots, x_{n})$ . □

Consider a T.B.T $T (f, x_{1}, x_{2}, \dots, x_{n})$ and $E (f) = {g = g_{1} + g_{2} + \dots + g_{m} | g \sim f}$ . Clearly, f ∼ f, and so $E (f) \neq \emptyset$ . We say that f has a minimum Boolean expression if, there exists $g \neq f \in E (f)$ such that m is the minimum natural in such a way that g = g₁ + g₂ + … + g_m.

Theorem 4.14. Every T.B.T corresponds to a minimum Boolean expression.

Proof. Let $n \in ℕ$ and $T (f, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T. Using Theorem 4.13, $E (f) \neq \emptyset$ and there exists a hypergraph $H = (G = ⋃_{j = 1}^{k} E_{j}, {E_{j}}_{j = 1}^{k})$ , where for all 1 ≤ j ≤ k, $E_{j} = {\bar{x_{1}}, \bar{x_{2}}, \dots, \bar{x_{n}} | \prod_{j = 1}^{n} \bar{x_{j}} = 1}$ . Thus, there exist $m \in ℕ$ and Boolean functions g₁, g₂, …, g_m in such a way that f ∼ (g₁ + g₂ + … + g_m), where for all 1 ≤ i ≤ m, there exist 1 ≤ j, j′ ≤ k in such a way that $\bar{x_{1}}, \bar{x_{2}}, \dots, \bar{x_{n}} \in F_{{jj}^{'}} \neq \emptyset$ and $g_{i} (x_{1}, x_{2}, \dots, x_{n}) = \prod_{l = 1}^{n} \bar{x_{l}}$ . In addition, if for all 1≤ j, j′ ≤ k, F_jj′ = ∅, we consider k = m and $g_{i} (x_{1}, x_{2}, \dots, x_{n}) = \prod_{l = 1}^{n} \bar{x_{l}}$ , where $\bar{x_{1}}, \bar{x_{2}}, \dots, \bar{x_{n}} \in E_{i}$ . If there exist 1 ≤ j, j′ ≤ k in such a way that $\bar{x_{1}}, \bar{x_{2}}, \dots, \bar{x_{n}} \in F_{{jj}^{'}} \neq \emptyset$ , we select 1 ≤ j, j′ ≤ k such that |F_jj′| = n - 1 and $M = {1 \leq j, j^{'} \leq k | | F_{{jj}^{'}} | = n - 1}$ . Clearly, $| M | \leq k$ , so if $I (n, f, 1) = I (n, g_{1} + g_{2} + \dots + g_{| M |}, 1)$ , then f ∼ g. But if $I (n, f, 1) > I (n, g_{1} + g_{2} + \dots + g_{| M |}, 1)$ , we consider the minimum 1 ≤ i ≤ k, and Boolean functions f_i such that g′ = dis∑_if_i, Un (g) ≠ Un (g′) ⊆ Un (f) and $I (n, f, 1) = I (n, g^{'} + \sum_{j = 1}^{| M |} g_{j}, 1)$ . Because $Un (g^{'} + \sum_{j = 1}^{| M |} g_{j}) \subseteq Un (f)$ , by Theorem 4.12, we get that (g + g′) ∼ f. □ Let $n, k, λ \in ℕ^{*}$ . A hypergraph $H = (G, {E_{j}}_{j = 1}^{k})$ is called a λ-intersection hypergraph, if for all 1 ≤ i, j ≤ k, we have |E_i ∩ E_j| = λ.

Theorem 4.15. Let $n \in ℕ$ and $T (f, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T. If $(H, T)$ is a 0-intersection hypergraph, then the T.B.T corresponds to an irreducible Boolean expression.

The following Example demonstrates that the converse of Theorem 4.15, is not necessarily true.

Example 4.16. (i) Consider a T. B. T $T (f, x, y, z)$ in Table 4.

Table 4

T. B. T $T (f, x, y, z)$

x	y	z	f (x, y, z)	f′ (x, y, z)
0	0	0	0	0
0	0	1	0	1
0	1	0	0	0
0	1	1	1	0
1	0	0	0	0
1	0	1	0	0
1	1	0	0	0
1	1	1	1	1

Clearly $(H, T)$ is an 2-intersection hypergraph, while the T.B.T corresponds to a reducible Boolean expression.

(ii) Consider a T. B. T $T (f^{'}, x, y, z)$ in Table 4. Obviously, $(H, T)$ is an 1-intersection hypergraph, while the T.B.T corresponds to an irreducible Boolean expression.

Let $n, k, λ \in ℕ^{*}$ . A hypergraph $H = (G, {E_{j}}_{j = 1}^{k})$ is called a strong λ-intersection hypergraph, if for some 1 ≤ i, j ≤ k, we have 1 ≤ |E_i ∩ E_j| ≤ λ.

Theorem 4.17. Let $n \in ℕ$ and $T (f, x_{1}, x_{2}, \dots, x_{n})$ be a T.B.T. If $(H, T)$ is an (n - 2)-intersection hypergraph, then the T.B.T corresponds to an irreducible Boolean expression.

Proof. The application of Theorem 4.13, $E (f) \neq \emptyset$ and there exists a hypergraph $(H, T) = (G = ⋃_{j = 1}^{k} E_{j}, {E_{j}}_{j = 1}^{k})$ , where for all 1 ≤ j ≤ k, $E_{j} = {\bar{x_{1}}, \bar{x_{2}}, \dots, \bar{x_{n}} | \prod_{j = 1}^{n} \bar{x_{j}} = 1}$ . Thus, there exist $m \in ℕ$ and Boolean functions g₁, g₂, …, g_m in such a way that f ∼ (g₁ + g₂ + … + g_m). Since $(H, T)$ is an (n - 2)-intersection hypergraph, for all 1 ≤ i, j ≤ m we get that |F_ij| = n - 2. It follows that $g_{ij} (x_{1}, x_{2}, \dots, x_{n}) = \prod_{α \in F_{ij}} α$ and so $\begin{matrix} {\bar{x_{1}}, \bar{x_{2}}, \dots, \bar{x_{n}} | \prod_{j = 1}^{n} \bar{x_{j}} = g_{ij} (x_{1}, x_{2}, \dots, x_{n}) = 1} \cap \\ {\bar{x_{1}}, \bar{x_{2}}, \dots, \bar{x_{n}} | \prod_{j = 1}^{n} \bar{x_{j}} = g_{ij} (x_{1}, x_{2}, \dots, x_{n}) = 1} \\ = {\bar{x_{i_{1}}}, \bar{x_{i_{2}}}, \dots, \bar{x_{i_{n - 2}}}} \end{matrix}$ $g (x_{1}, x_{2}, \dots, x_{n}) = \sum_{i_{1} \leq i \leq i_{r} i_{1} \leq j \leq i_{s}} g_{ij} (x_{1}, \dots, x_{n}) = (\prod_{j = 1}^{n - 2} \bar{x_{i_{j}}}) (f_{1} + f_{2} + \dots + f_{r})$ , where for all $1 \leq k \leq r, f_{i} = \prod_{1 \leq i \neq j \leq n} (\bar{x_{i}} \bar{x_{j}})$ and ${\bar{x_{i}}, \bar{x_{j}}} \cap {\bar{x_{i_{1}}}, \bar{x_{i_{2}}}, \dots, \bar{x_{i_{n - 2}}}} = \emptyset$ . Hence, g (x₁, x₂, …, x_n) is an irreducible Boolean expression. □

The method for the construction of a Boolean expression from a T.B.T is explained in Table 5, Algorithm 1 based on Theorem 4.14.

Table 5

Algorithm 1

Begin:

1. Input a T.B.T

T (f, x_{1}, x_{2}, \dots, x_{n})

2. If f ≡ 0 or f ≡ 1, then consider g ≡ 0 or g ≡ 1, respectively.

3. If there exists j ∈ {1 ≤ j₁, j₂, …, j_s ≤ 2ⁿ}, such that f_j (x₁, x₂, …, x_n) =1, then

consider

E_{j} = {\bar{x_{1}}, \bar{x_{2}}, \dots, \bar{x_{n}} | \prod_{j = 1}^{n} \bar{x_{j}} = f_{j} (x_{1}, x_{2}, \dots, x_{n}) = 1}

With regard to the step 3 consider the following formula:

4. For all 1 ≤ i ≠ j ≤ k and

k \in ℕ

, set F_ij = E_i ∩ E_j.

5. If for all 1≤ i ≠ j ≤ k, F_ij = ∅ or |F_ij| < n - 1, then consider

g (x_{1}, x_{2}, \dots, x_{n}) = \sum_{1 \leq i \leq k} \prod_{α \in E_{i}} α

6. If there exists 1 ≤ r ≤ k, and i ≠ j ∈ {i₁, i₂, …, i_r} such that F_ij≠ ∅ and

|F_ij| ≥ n - 1, then put

g_{ij} (x_{1}, x_{2}, \dots, x_{n}) = \prod_{α \in F_{ij}} α .

7. If I (n, dis∑_{substacki₁≤i≤i_ri₁≤j≤i_s}g_ij, 1) = I (n, f, 1), then consider g (x₁, x₂, …, x_n) =

∑_{substacki₁≤i≤i_ri₁≤j≤i_s}g_ij (x₁, …, x_n) that Un (g_ij) ⊆ Un (f) .

8. If I (n, dis∑_{substacki₁≤i≤i_ri₁≤j≤i_s}g_ij, 1) < I (n, f, 1), then consider 1 ≤ s ≤ k, j ∈ {j₁, j₂, …, j_s},

f_{j} (x_{1}, x_{2}, \dots, x_{n}) = \prod_{β \in E_{j}} β

such that Un (dis∑_{substacki₁≤i≤i_ri₁≤j≤i_s}g_ij) ≠ Un (f_j) ⊆ Un (f) and

I (n, \sum_{i_{1} \leq i \leq i_{r} i_{1} \leq j \leq i_{s}} g_{ij} + \sum_{j = j_{1}}^{j_{s}} f_{j}, 1) = I (n, f, 1)

End.

Example 4.18. (i) Consider a T. B. T $T (f, x, y, z)$ in Table 6.

Table 6

T. B. T $T (f, x, y)$

x	y	f (x, y)
0	0	1
0	1	1
1	0	1
1	1	0

Let H = {x, y, x′, y′}. Consider the undirected hypergraph $H^{'} = (H, E_{1}, E_{2}, E_{3})$ in Figure 6, where E₁ = {x′, y′} , E₂ = {x′, y} and E₃ = {x, y′} .

Fig.6

Undirected hypergraph $H^{'} = (H, E_{1}, E_{2}, E_{3}) .$

Since E₁ ∩ E₂ = {x′} and E₁ ∩ E₃ = {y′}, we get that f (x, y) = x′ + y′.

(ii) Consider a T. B. T $T (f, x, y, z)$ in Table 7.

Table 7

T. B. T $T (f, x, y, z)$

x	y	z	f (x, y, z)
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

Let H = {x, y, z, x′, y′, z′}. Consider the undirected hypergraph $H^{'} = (H, E_{1}, E_{2}, E_{3}, E_{4})$ in Figure 7, where E₁ = {x′, y′, z′} , E₂ = {x′, y, z′} , E₃ = {x′, y, z} and E₄ = {x, y, z′} .

Fig.7

Undirected hypergraph $H^{'} = (H, E_{1}, E_{2}, E_{3}, E_{4}) .$

Since E₁ ∩ E₂ = {x′, z′}, E₁ ∩ E₃ = {x′} , E₁ ∩ E₄ = {z′} , E₂ ∩ E₃ = {x′, y} , E₂ ∩ E₄ = {y, z′} and E₃ ∩ E₄ = {y}, we get that f (x, y) = x′z′ + x′y + yz′.

4.1 Accessible minimum boolean expression based on a program

In this subsection, we present a program(Python programming) to accesses of minimum Boolean expression for any given T.B.T, based on the Algorithm 1, Table 5.

1 import xlrd

3 sheet = xlrd.open_workbook("input.xlsx").sheet_

by_index(0)

5 element_names = sheet.row_values(0)[:-1]

6 elements = []

7 for i in range(1, sheet.nrows):

8 elements.append(sheet.row_values(i)) 9 10 if len(elements) != pow(2, len(element_names)): 11 print("Error in input file, rows count isn’t equal

to 2∧n.") 12 exit(0) 13 14 E_i = [] 15 for i, elm in enumerate(elements): 16 if(elm[-1] == 1): # check if f is equal to 1 17 E = [] 18 for c in range(0, len(elm)-1): 19 if(elm[c] == 1):

20 E.append(element_names[c]) 21 else: 22 E.append(element_names[c]+"’") 23 E_i.append([i, E]) 24 25 def print_g(g_expr): 26 print("g("+",".join(element_names)+") = "+g_expr)

27 28 input("") 29 exit(0) 30 31 if len(E_i) == len(elements): 32 print_g("1") 33

34 if len(E_i) == 0: 35 print_g("0") 36 37 F_ij = [] 38 for i in E_i: 39 F = [] 40 for j in E_i:

41 if(i != j): 42 intersection = [x for x in i[1] if x in j[1]] 43 if(len(intersection) > = (len(element_names)-1)): 44 F.append([j[0], intersection]) 45 if(F): 46 F_ij.append([i[0], F]) 47

48 if(F_ij == []): 49 g = [] 50 for i in E_i: 51 g.append("".join(i[1])) # multiply elements 52 print_g("+".join(g)) 53 54 g_ij = []

55 for i in F_ij: 56 for j in i[1]: 57 g_ij.append("".join(j[1])) # multiply elements 58 g_ij = list(dict.fromkeys(g_ij)) # remove duplicates 59 sigma_g_ij = "+".join(g_ij) 60 61

62 def calc_mult_and(expr): 63 expr = expr.split("+") 64 for i in expr: 65 if "0" not in i: 66 return 1 67 return 0 68

69 true_g_ij = [] 70 for elm in elements: 71 tmp_g = sigma_g_ij 72 for c in range(0, len(elm)-1): 73 if(elm[c] == 1): 74 tmp_g = tmp_g.replace(element_names[c]+"’", "0") 75 tmp_g = tmp_g.replace(element_names[c], "1")

76 else: 77 tmp_g = tmp_g.replace(element_names[c]+"’", "1") 78 tmp_g = tmp_g.replace(element_names[c], "0") 79 true_g_ij.append(calc_mult_and(tmp_g)) 80 81 f_j = [] 82 for i, elm in enumerate(elements):

83 if(elm[-1] == 1 and true_g_ij[i] == 0):

84 f_j.append("".join([x for x in E_i if x[0] == i][0][1]))

86 print_g("+".join(g_ij + f_j))

Remark 4.1. We take n as number of variables in table, and k as number of elements of E_j. Then

T (E_j) = O (n × 2ⁿ), because one outer loop through rows and one inner loop through columns.

T (F_ij) = O (k² × n), because two nested loops through elements of E_j and one inner loop for getting intersection.

If for 1 ≤ j ≤ 2ⁿ, F_j (x₁, . . . , x_n) =0 or F_j (x₁, . . . , x_n) =1 complexity is O (2ⁿ) for one loop through rows.

Others complexity is T (E_j) + T (F_ij) = O (n × (k² + 2ⁿ)).

5 Application of switching function based on hypergraphs

In this section, we introduce some real life applications of switching function based on hypergraphs.

Three-Floor Elevator: Numerous functions must be performed by the circuitry of an elevator (open/close door, move up/down, light up/down indicator and so on. This focuses on one aspect of a three-floor elevator, deciding when to move to other floor. Five inputs are needed.

x= first floor button. (1=pushed, 0=not pushed)

y= second floor button. (1=pushed, 0=not pushed)

z= third floor button. (1=pushed, 0=not pushed)

the present floor indicator requires two bits (w and t): 01 for first floor, 10 for second floor, 11 for third floor. Note that 00 is an impossible combination and output f (x, y, z, w, t)=move function (1=move or change floor, 0=stay). A hypergraph is modified based on move deciding as follows: $\begin{matrix} E_{1} = {x^{'}, y^{'}, z, w^{'}, t}, E_{2} = {x^{'}, y^{'}, z, w, t^{'}}, \\ E_{3} = {x^{'}, y, z^{'}, w^{'}, t}, E_{4} = {x^{'}, y, z^{'}, w, t}, \\ E_{5} = {x^{'}, y, z, w^{'}, t}, E_{6} = {x, y^{'}, z^{'}, w, t^{'}}, \\ E_{7} = {x, y^{'}, z^{'}, w, t}, E_{8} = {x, y^{'}, z, w, t^{'}}, \\ E_{9} = {x, y, z^{'}, w, t} . \end{matrix}$ Now by Algorithm 1, for all 1 ≤ i ≠ j ≤ 9, set F_ij = E_i ∩ E_j. So, we have $\begin{matrix} F_{12} = {x^{'}, y^{'}, z}, F_{13} = {x^{'}, w^{'}, t}, \\ F_{14} = {x^{'}, t}, F_{15} = {x^{'}, z, w^{'}, t}, \\ F_{16} = {y^{'}}, F_{17} = {y^{'}, t}, \\ F_{18} = {y^{'}, z}, F_{19} = {t}, \\ F_{23} = {x^{'}}, F_{24} = {x^{'}, w}, \\ F_{25} = {x^{'}, z}, F_{26} = {y^{'}, w, t^{'}}, \\ F_{27} = {y^{'}, w}, F_{28} = {y^{'}, z, w, t^{'}}, \\ F_{29} = {w}, F_{34} = {x^{'}, y, z^{'}, t}, \\ F_{35} = {x^{'}, y, w^{'}, t}, F_{36} = {z^{'}}, \\ F_{37} = {z^{'}, t}, F_{38} = {}, \\ F_{39} = {y, z^{'}, t}, F_{45} = {x^{'}, y, t}, \\ F_{46} = {z^{'}, w}, F_{47} = {z^{'}, w, t}, \\ F_{48} = {w}, F_{49} = {y, z^{'}, w, t}, \\ F_{56} = {}, F_{57} = {t}, \\ F_{58} = {z}, F_{59} = {y, t}, \\ F_{67} = {x, y^{'}, z^{'}, w}, F_{68} = {x, y^{'}, w, t^{'}}, \\ F_{69} = {x, z^{'}, w}, F_{78} = {x, y^{'}, w}, \\ F_{79} = {x, z^{'}, w, t} and F_{89} = {x, w} . \end{matrix}$ The application of Theorem 4.17, we obtain Boolean expression based above hypergraph as f (x, y, z, w, t) = x′zw′t + y′zwt′ + xy′z′w + xy′wt′ + x′yz′t + x′yw′t + xz′wt + yz′wt . For instance f (1, 1, 1, 1, 1) =0, implies that elevator does not move.

Social Networks: Emotional intelligence is a conceptualization which progressively discussed in social psychology. Recently, emotional intelligence has been given much concentration in research especially in psychological research. Academic success or success is the product of instruction the extent to which a student, educator, and institution have attained their educational aims. It is defined as the degree to which students attain the information, proficiency, aptitudes, and skills that the teacher is going to teach or assign. Numerous investigations have revealed that there is a positive relationship between higher level of emotional intelligence and excellent academic success among adolescent students. Let X={Alexander, Daniel, Michael, Thomas, William} be a set of 5 students who are chosen to an associated research and answered the researcher’s questions with 6 questions, where students are free to answer some questions (1=correct, 0=incorrect, X= positive answer, X’= negative answer). Suppose that 1 ≤ i ≤ 6, E_i be a set of students who answered to i-th question. We want to find a target function f (A, D, M, T, W) in such a way that researcher decides to start a related work or not. Thus, we obtain a hypergraph as follows: $\begin{matrix} E_{1} = {A, D, M, T^{'}, W^{'}}, E_{2} = {A, D^{'}, M, T^{'}}, \\ E_{3} = {A, D, M, T, W^{'}}, E_{4} = {A, M, T^{'}, W^{'}}, \\ E_{5} = {A^{'}, D, M}, E_{6} = {A, W^{'}} . \end{matrix}$

Now by Algorithm 1, for all 1 ≤ i ≠ j ≤ 6, set F_ij = E_i ∩ E_j. So we have $\begin{matrix} F_{12} = {A, M, T^{'}}, F_{13} = {A, D, M, W^{'}}, \\ F_{14} = {A, M, T^{'}, W^{'}}, F_{15} = {D, M}, \\ F_{16} = {A, W^{'}}, F_{23} = {A, M}, \\ F_{24} = {A, M, T^{'}}, F_{25} = {M}, \\ F_{26} = {A}, F_{34} = {A, M, W^{'}}, \\ F_{35} = {D, M}, F_{36} = {A, W^{'}}, \\ F_{45} = {M}, F_{46} = {A, W^{'}} and F_{56} = {} . \end{matrix}$ Using Theorem 4.17, we obtain Boolean expression based above hypergraph as f (A, D, M, T, W) = ADMW′ + AMT′W′ + A′DM . For instance, f (0, 1, 1, 1, 0) =1, implies that researchers start their project and they can make the right decision. The importance of this issue is best seen when the number of participants in these questionnaires is more than ten students. For this reason 1024 cases should be checked. This is very difficult with T · B · T table.

Logic Circuit: Logic circuit is one that treats like a switch, i.e. a two-positive devise with ON or OFF states. This is called as binary device, in which the ON state is represented by 1 and the OFF state by 0. We require to devising a logic statement which can be expressed in only one of the two forms. For instance, computers store information in gigabytes, megabytes, and so on. The fundamental unit of storage is the bit or binary digit, which is similar to a switch. Like a switch, which has two states on or off, the bit has two states 1 and 0 (sometimes represented as true and false. We apply this abstraction to represent numbers with the binary number system. In order to perform calculations, the computer manipulates bits by means of logical operations which use inputs to yield a particular output based on the input bits states. To define the logic clearly, the truth table is used to which express the outputs in terms of all combinations of inputs. A logic gate might sound horribly complex, but its simply an electric circuit with two inputs and an output. It receives two incoming electric currents, compares them, and sends on a new, outgoing electric current depending on what it finds. A logic gate is a bit like a doorman or bouncer who is allowed to let people into a nightclub only if they pass certain tests. There are quite a few different types of logic gate, the most common of which are called AND, OR, NOT, XOR (Exclusive Or), NAND (NOT AND), and NOR (NOT OR). To convert a logic circuit to a hypergraph, the following map is used. Each literal in the logic circuit maps to one vertex in the hypergraph. Each clause maps a hyperedge and connects to the vertices that correspond to the literals in the clause. Therefore, for any given logic circuit, a hypergraph and a Boolean expression can be obtained.

6 Discussion of conclusion and future works

For any given finite set, there are some clustering sets, and by each cluster set, a decision can be made. Sometimes we have to make a cluster set by binary codes, so some irregular subsets with non-empty intersections are obtained. We need to give an order to the information, so apply the concept of hypergraphs. We correspond any information to a Boolean literal and give in a hyperedge, so we have a hypergraph. Based on this hypergraph, we generate a T.B.T and the values 0, 1 are placed in rows and columns. Now we can generate a Boolean expression in any way and apply it to our aims(for instance from D.N.F). However, we need to generate a minimum Boolean expression which is an irreducible Boolean expression(which D.N.F has a limitation in this regard). Since disjunctive normal forms are reducible Boolean expressions, we need to make another way in generating of Boolean expressions. The non-empty intersections in hyperedges of hypergraphs help to generate minimum Boolean expressions from T.B.T in such a way that are irreducible Boolean expressions and are not same to D.N.F necessarily. To egularify access to obtain the minimum Boolean expressions, we introduce an Algorithm and so Python programming which compute irreducible Boolean expressions. There are some advantages based on the results of this paper including defining and considerning the notion of hypergraphs based on Boolean functions, hypergraphable Boolean functions and Boolean functionable hypergraphs. Moreover, it is demonstrated that:

Each Boolean function, is a hyperdiagramable Boolean function.

Every hypergraph is a Boolean functionable hypergraph.

Every T.B.T corresponds to a Boolean expression.

Every T.B.T corresponds to a minimum Boolean expression.

The concept of Boolean function–based hypergraph is introduced and will be denoted by $(H, T)$ . Moreover, it is demonstrated that if $(H, T)$ is an 0-intersection hypergraph, then the T.B.T corresponds to an irreducible d.n.f.

These result might be helpful for further studies in Boolean function theory. In our future research there is an inclination for obtaining more findings with regard to irreducible Boolean function, graphs, hypergraphs, decision tree based on Boolean function–based hypergraph and their applications.

Compliance with ethical standards

Conflict of interest

The authors declare that they have no conflict of interest.

References

Akram

and Luqman

, Certain networks models using single-valued neutrosophic directed hypergraphs, Journal of Intelligent & Fuzzy Systems 33 (2017), 575–588.

Berge

, North Holland, Graphs and Hypergraphs (1979).

Eldon

, Whitesitt, Boolean Algebra and Its Applications, New York Dover Publications Inc (1995).

Hamidi

and Borumandsaied

, Accessible single-valued neutrosophic graphs, J Appl Math Comput 57 (2018), 121–146.

Hamidi

and Borumandsaied

, Achievable Single-Valued Neutrosophic Graphs in Wireless Sensor Networks, New Mathematics and Natural Computation 14(2) (2018), 157–185.

Hamidi

and Borumand Saeid

, On Derivable Trees, Transactions on Combinatorics 8(2) (2019), 21–43.

Hamidi

and Smarandache

, Single-Valued Neutrosophic Directed (Hyper)Graphs And Applications in Networks, Journal of Intelligent & Fuzzy Systems 37(2) (2019), 2869–2885.

Molnar

, Applications of Hypergraphs in Informatics a Survey and Opportunities for Research, Annales Univ Sci Budapest Sect Comp 42 (2014), 261–282.

Poulik

and Ghorai

, Detour g-interior nodes and detour g-boundary nodes in bipolar fuzzy graph with applications, Hacettepe University Bulletin of Natural Sciences and Engineering Series B: Mathematics and Statistics 49(1) (2020), 106–119.

10.

Poulik

and Ghorai

, Certain indices of graphs under bipolar fuzzy environment with applications, Soft Computing 24(7) (2020), 5119–5131.

11.

Poulik

and Ghorai

, Note on Bipolar fuzzy graphs with applications, Knowledge-Based Systems 192 (2020), 1–5.