# Hypergraph Horn Functions

Kristóf Bérczi MTA-ELTE Momentum Matroid Optimization Research Group and MTA-
ELTE Egerváry Research Group, Department of Operations Research, Eötvös Loránd
University, Budapest, Hungary. Email<EMAIL_ADDRESS> Endre Boros
MSIS Department and RUTCOR, Rutgers University, Piscataway, New Jersey, USA.
Email<EMAIL_ADDRESS> Kazuhisa Makino Research Institute for
Mathematical Sciences (RIMS) Kyoto University, Kyoto, Japan. Email:
<EMAIL_ADDRESS>
###### Abstract

Horn functions form a subclass of Boolean functions possessing interesting
structural and computational properties. These functions play a fundamental
role in algebra, artificial intelligence, combinatorics, computer science,
database theory, and logic.

In the present paper, we introduce the subclass of _hypergraph Horn_ functions
that generalizes matroids and equivalence relations. We provide multiple
characterizations of hypergraph Horn functions in terms of implicate-duality
and the closure operator, which are respectively regarded as generalizations
of matroid duality and Mac Lane – Steinitz exchange property of matroid
closure. We also study algorithmic issues on hypergraph Horn functions, and
show that the recognition problem (i.e., deciding if a given definite Horn CNF
represents a hypergraph Horn function) and key realization (i.e., deciding if
a given hypergraph is realized as a key set by a hypergraph Horn function) can
be done in polynomial time, while implicate sets can be generated with
polynomial delay.

Keywords: Algorithms, Duality, Horn functions, Hypergraphs

##  1 Introduction

In this paper we introduce and study a special subclass of Horn functions that
is rich in mathematical structure and has advantageous algorithmic properties.

Horn logic is a segment of propositional logic that came to prominence with
the advent of computers, relational databases, logic programming, see e.g.,
[17, 10, 5, 6, 19, 8, 9, 11, 14, 15, 16]. Horn expressions and functions
appear in many equivalent forms in mathematics and computers science, such as
directed hypergraphs, implications systems, closure operators, functional
dependencies in relational databases, formal concept analysis, etc. We refer
the reader to [1] for a more comprehensive overview of these equivalent areas
and related literature.

In this paper we use conjunctive normal form (CNF) representations for Boolean
functions, and view Horn clauses equivalently as simple implications. For
instance if $x_{i}$, $i=1,\dots,n$ are propositional variables (that is
logical variables that can only take false/true values), then
$\\{x_{1},x_{2}\\}\to x_{3}$ is such a simple implication that can also be
represented as a clause (an elementary disjunction) of the form
$(\overline{x}_{1}\vee\overline{x}_{2}\vee x_{3})$, where $\overline{x}_{i}$
denotes the logical negation of $x_{i}$, $i=1,\dots,n$. Horn functions can be
represented by a collection (conjunction) of such implication rules. If for
this example we also have $\\{x_{1},x_{3}\\}\to x_{2}$ and
$\\{x_{2},x_{3}\\}\to x_{1}$ as rules of the given Horn system, then we call
$\\{x_{1},x_{2}\\}\to x_{3}$ circular. The subject of our study is the family
of Horn functions that can be represented by a collection of circular
implication rules. Since such a circular rule can be represented by the set of
the propositional variables appearing in it (since any one is implied by the
others), the Horn functions we are interested in can be represented by a
hypergraph over the set of variables. For this reason we call this subfamily
hypergraph Horn.

The family of hypergraph Horn functions turns out to be highly structured and
still very general. They generalize equivalence relations, and more generally
matroids. We provide various characterizations for this class, allowing to
derive efficient algorithms for several related algorithmic problems.

We introduce a new type of “duality”, called implicate-duality or $i$-duality
for short. We show that every Boolean function has a unique $i$-dual, which is
always hypergraph Horn. Furthermore, $i$-duality is an involution over the set
of hypergraph Horn functions. It turns out that $i$-duality generalizes
matroid duality. More precisely, if a hypergraph Horn function corresponds to
a matroid, then its $i$-dual corresponds to the dual matroid. We provide a
characterization for self $i$-dual functions, which is surprisingly analogous
to the characterization of self dual monotone Boolean functions (see e.g.,
[3]). We also characterize hypergraph Horn functions in terms of the standard
closure operator. Our characterization can be regarded as an extension of the
Mac Lane – Steinitz exchange property of matroid closure (see the companion
paper [2]).

While satisfiability (SAT) is easy for Horn CNFs, one typical difficulty in
this area arises from the fact that Horn functions have many different Horn
CNF representations. For instance, an arbitrary Horn function may have several
circular rules and several rules that are not circular. It may be
representable by a collections of circular rules, but it may also have
representations that involve non-circular rules. We provide an efficient
algorithm that recognizes if a given Horn CNF defines a hypergraph Horn
function or not. If yes, the algorithm outputs a circular representation the
size of which is polynomially bounded by the size of the input CNF. We also
provide an algorithm that generates all circular rules incrementally
efficiently for a Horn function represented by a Horn CNF. Note that there
might be an exponential number of such rules.

Keys are another important notion of Horn theory. A subset of the variables is
a key of a given Horn function if the truth of these variables imply the truth
of all other variables. The set of minimal keys plays important roles in
applications, in particular in databases. We provide an efficient algorithm
that decides if a given hypergraph is the set of minimal keys of a hypergraph
Horn function or not, and if yes, it outputs a circular representation of such
a function the size of which is polynomially bounded by the size of the given
hypergraph.

The rest of the paper is organized as follows. While we use standard
terminology and notation, for clarity we introduce precise definitions in the
next section. In Section 3 we introduce the class of hypergraph Horn functions
and $i$-duality, and prove a number of structural properties. In Section 4
several equivalent characterizations are shown. In Section 5 we provide the
efficient algorithms mentioned above, while in the last section we close with
listing a few open problems.

##  2 Preliminaries

#### Hypergraphs.

For a finite set $V$, a family $\mathcal{H}\subseteq 2^{V}$ of its subsets is
called a hypergraph, where $H\in\mathcal{H}$ is called a hyperedge of
$\mathcal{H}$. A hypergraph $\mathcal{H}$ is called Sperner if no distinct
hyperedges of $\mathcal{H}$ contain one another. For a subset $X\subseteq V$
we call $V\setminus X$ its _complement_ , and we denote by
$\mathcal{H}^{c}=\\{V\setminus H\mid H\in\mathcal{H}\\}$ the _complementary
family_ of $\mathcal{H}$. Note that the operator “$c$” is an involution, i.e.,
$\left(\mathcal{H}^{c}\right)^{c}=\mathcal{H}$ holds for all hypergraphs. A
subset $T\subseteq V$ is called a _transversal_ of $\mathcal{H}$ if $T\cap
H\neq\emptyset$ for all hyperedges $H\in\mathcal{H}$. We denote by
$\mathcal{H}^{d}$ the _family of minimal transversals_ of $\mathcal{H}$. For
simplicity, we omit the parentheses from the notation when applying these
operations repeatedly, for example, we write
$\mathcal{H}^{dc}=(\mathcal{H}^{d})^{c}$ and
$\mathcal{H}^{cd}=(\mathcal{H}^{c})^{d}$. For a Sperner hypergraph
$\mathcal{H}$, the operator “$d$” is also an involution, hence we have
$\mathcal{H}^{dccd}=\mathcal{H}^{cddc}=\mathcal{H}$ for such hypergraphs. Note
that the family $\mathcal{H}^{dc}$ is the _family of maximal independent sets_
of $\mathcal{H}$, where a set $I\subseteq V$ is called independent of
$\mathcal{H}$ if it contains no hyperedge of $\mathcal{H}$. The family
$\mathcal{H}^{cd}$ consists of all minimal subsets of $V$ that are not
contained in a hyperedge of $\mathcal{H}$. Every Sperner hypergraph
$\mathcal{H}$ defines an _independence system_ $\mathcal{I}$ consisting of all
independent sets of $\mathcal{H}$, see e.g., [22]. In this correspondence,
maximal independent sets of $\mathcal{H}$ are also called _bases_ of the
associated independence system $\mathcal{I}$, while minimal dependent sets
(i.e., hyperedges) of $\mathcal{H}$ are called _circuits_ of $\mathcal{I}$.
Typically we reserve the notation $\mathcal{B}$ and $\mathcal{C}$ for the
families of bases and circuits, respectively. Note that for all independence
systems the families of bases and circuits are Sperner, and thus we have

$\mathcal{B}^{cd}=\mathcal{C}~{}~{}~{}\text{ and equivalently
}~{}~{}~{}\mathcal{C}^{dc}=\mathcal{B}.$

Independent sets are exactly the subsets of hyperedges of
$\mathcal{B}=\mathcal{C}^{dc}$, or equivalently, subsets that do not contain a
hyperedge of $\mathcal{C}$.

For an arbitrary hypergraph $\mathcal{H}\subseteq 2^{V}$ we denote by
$\mathcal{H}^{\cap}$ the _intersection closure_ of $\mathcal{H}$, defined by

$\mathcal{H}^{\cap}~{}=~{}\left\\{\left.\bigcap_{F\in\mathcal{F}}F~{}\right|~{}\mathcal{F}\subseteq\mathcal{H}\right\\}.$

We note that the intersection of an empty family is defined as $V$, and thus
we have $V\in\mathcal{H}^{\cap}$ for all hypergraphs $\mathcal{H}\subseteq
2^{V}$. Analogously, we denote by $\mathcal{H}^{\cup}$ the _union closure_ of
$\mathcal{H}$ defined as

$\mathcal{H}^{\cup}~{}=~{}\left\\{\left.\bigcup_{F\in\mathcal{F}}F~{}\right|~{}\mathcal{F}\subseteq\mathcal{H}\right\\}.$

We note that the union of an empty family is defined as the empty set, and
thus we have $\emptyset\in\mathcal{H}^{\cup}$ for all hypergraphs
$\mathcal{H}$.

#### Horn functions.

We denote by $V$ the set of $n$ Boolean variables $x$ and call these together
with their negations $\overline{x}$ as _literals_. Members of $V$ are called
_positive literals_ while their negations are _negative literals_. A
disjunction of a subset of the literals is called a _clause_ if it contains no
complementary pair of literals $x$ and $\overline{x}$, and the conjunction of
clauses is a called a _conjunctive normal form_ (or in short a CNF). It is
well-known (see e.g., [7]) that every Boolean function
$f:\\{0,1\\}^{V}\rightarrow\\{0,1\\}$ can be represented by a CNF (typically
not in a unique way). We use Greek letters to denote CNFs, and Latin letters
to denote (Boolean) functions. For a CNF $\Psi=\bigwedge_{k}C_{k}$, let
$|\Psi|$ denote the number of clauses in $\Psi$, and let $\|\Psi\|$ denote the
length of $\Psi$, i.e., $\|\Psi\|=\sum_{k}|C_{k}|$.

Truth assignments (i.e., Boolean vectors)
$\mathbf{x}=(x_{1},\dots,x_{n})\in\\{0,1\\}^{V}$ can be viewed equivalently as
characteristic vectors of subsets. For a subset $Z\subseteq V$ we denote by
$\chi_{Z}\in\\{0,1\\}^{V}$ its characteristic vector, i.e., $(\chi_{Z})_{i}=1$
if and only if $i\in Z$. Since we use primarily a combinatorial notation in
this paper, we use for a function $f$ and Boolean expression $\Phi$ the
notation $f(Z)$ and $\Phi(Z)$ instead of $f(\chi_{Z})$ and $\Phi(\chi_{Z})$,
to denote the evaluation of $f$ and $\Phi$ at the binary vector $\chi_{Z}$,
respectively. We say that a set $Z\subseteq V$ is a _true set_ of $f$ if
$f(Z)=1$, and a _false set_ otherwise. We denote by $\mathcal{T}(f)$ and
$\mathcal{F}(f)$ the _families of true sets_ and _false sets_ of $f$,
respectively. Every Boolean expression defines/represents a unique Boolean
function. If $A$ and $B$ denote Boolean functions or Boolean expressions, we
write $A=B$ if $A(X)=B(X)$ for all $X\subseteq V$, and $A\leq B$ if $A(X)\leq
B(X)$ for all $X\subseteq V$, where $B$ is called a _majorant_ of $A$ in the
latter case. We also write $A<B$ if $A\leq B$ and $A\not=B$.

A clause is called _definite Horn_ if it contains exactly one positive
literal. It is easy to see that definite Horn clauses represent simple
implications. Namely, for a proper subset $B\subsetneq V$ and $v\in V\setminus
B$ the implication $B\to v$ is equivalent to the definite Horn clause
$C=v\vee\left(\bigvee_{u\in B}\overline{u}\right)$: the true sets of both
expressions are exactly the sets $T\subseteq V$ such that either
$T\not\supseteq B$ or $T\supseteq B\cup\\{v\\}$. A CNF is called definite Horn
if it consists of definite Horn clauses, and a Boolean function is called
definite Horn if it can be represented by a definite Horn CNF. The following
characterization of definite Horn functions is well-known.

######  Lemma 1 (see e.g., [17, 7]).

A Boolean function $f$ is definite Horn if and only if the family
$\mathcal{T}(f)$ of its true sets is closed under intersection and contains
$V$. $\Box$

Lemma 1 implies that for any set $Z\subseteq V$ there exists a unique minimal
true set containing $Z$, the so-called _closure_ of $Z$ denoted by
$\mathbb{T}_{h}(Z)$. In fact such a closure can be computed efficiently from
any definite Horn CNF representation $\Phi$ of $h$ by the so-called _forward
chaining procedure_ (see e.g., [7]): Let $A\subseteq V$ denote the set of all
variables $v\in V\setminus Z$ for which there exists a clause $B\to v$ in
$\Phi$ with $B\subseteq Z$ and $v\in V\setminus Z$, and define
$\mathbb{T}^{1}_{\Phi}(Z)\coloneqq Z\cup A$. For $i\geq 2$ we define
$\mathbb{T}^{i}_{\Phi}(Z)=\mathbb{T}^{1}_{\Phi}(\mathbb{T}^{i-1}_{\Phi}(Z))$.
Since
$Z\subseteq\mathbb{T}^{1}_{\Phi}(Z)\subseteq\mathbb{T}^{2}_{\Phi}(Z)\subseteq\dots\subseteq
V$, $\mathbb{T}^{i+1}_{\Phi}(Z)=\mathbb{T}^{i}_{\Phi}(Z)$ holds for some
integer $i\leq n$. Let $i^{*}$ be the smallest such index $i$. Then we have
$\mathbb{T}^{t}_{\Phi}(Z)=\mathbb{T}^{i^{*}}_{\Phi}(Z)$ for all $t\geq i^{*}$,
and $\mathbb{T}^{i^{*}}_{\Phi}(Z)$ is the minimal true set of $\Phi$ that
contains $Z$. Thus we can define
$\mathbb{T}_{\Phi}(Z)=\mathbb{T}^{i^{*}}_{\Phi}(Z)$, and we say that $Z$ can
be closed by $\Phi$ in $i^{*}$ steps. While we may have
$\mathbb{T}^{1}_{\Phi}(Z)\neq\mathbb{T}^{1}_{\Psi}(Z)$ for different definite
Horn CNFs $\Phi$ and $\Psi$ representing the same function $h$, it can be
shown (see e.g., [7]) that the resulting set $\mathbb{T}_{\Phi}(Z)$ does not
depend on the particular choice of the representation $\Phi$ of $h$, but only
on the underlying function $h$, that is, we can write
$\mathbb{T}_{h}(Z)=\mathbb{T}_{\Phi}(Z)$ for this uniquely defined closure of
$Z$. Note that $\mathbb{T}$ is in fact a closure operator in finite set
theory, and hence we call a subset $Z\subseteq V$ _closed_ (with respect to
$h$) if $\mathbb{T}_{h}(Z)=Z$. It is not difficult to check that a set is
closed with respect to $h$ if and only if it is a true set of $h$.

For a definite Horn function $h$, a clause $B\to v$ is called an _implicate_
of $h$ if it is a majorant of $h$, that is, if $(B\to v)\geq h$. An implicate
$B\to v$ of $h$ is _prime_ if $h$ has no other implicate
$B^{\prime}\rightarrow v$ with $B^{\prime}\subsetneq B$. The following lemma
characterizes implicates of definite Horn functions in terms of the closure
operator.

######  Lemma 2 (see e.g., [7]).

A clause $B\to v$ is an implicate of a definite Horn function $h$ if and only
if $v\in\mathbb{T}_{h}(B)\setminus B$. $\Box$

Given a definite Horn CNF $\Phi$, a subset $A\subseteq V$ and a variable $v\in
V\setminus A$, we write $A\overset{\Phi}{\to}v$ to indicate that $A\to v$ is
an implicate of $\Phi$, or equivalently that $v\in\mathbb{T}_{\Phi}(A)$. To
indicate the opposite, that is that $A\to v$ is not an implicate of $\Phi$, or
equivalently, that $v\not\in\mathbb{T}_{\Phi}(A)$ we may simply write
$A\overset{\Phi}{\nrightarrow}v$.

A subset $K\subseteq V$ is called a _key_ of the definite Horn function $h$ if
$\mathbb{T}_{h}(K)=V$. We denote by

$\mathcal{K}(h)=\\{K\subseteq V\mid\mathbb{T}_{h}(K)=V\ \text{and}\
\mathbb{T}_{h}(K^{\prime})\neq V\ \text{for all $K^{\prime}\subsetneq K$}\\},$

the family of _minimal keys_ of $h$, and $\mathcal{K}(h)$ is called the key
set of $h$.

A true set $T\in\mathcal{T}(h)$ is called _nontrivial_ if $T\neq V$. We denote
by

$\mathcal{M}(h)=\\{T\subsetneq V\mid h(T)=1\ \text{and}\ h(T^{\prime})=0\
\text{for all $T\subsetneq T^{\prime}\subsetneq V$}\\},$

the family of _maximal nontrivial true sets_ of $h$. Note that
$\mathcal{M}(h)$ is a subfamily of the so-called _characteristic models_ of
$h$ [12].

Both families, $\mathcal{K}(h)$ and $\mathcal{M}(h)$ are Sperner hypergraphs
for all definite Horn functions $h$. It is easy to verify that maximal
nontrivial true sets form the family of maximal independent sets of the family
of minimal keys, and minimal keys are exactly the minimal sets that are not
contained in a maximal nontrivial true set.

######  Lemma 3 (see e.g., [7]).

For a definite Horn function $h$ we have $\mathcal{M}(h)=\mathcal{K}(h)^{dc}$
and $\mathcal{K}(h)=\mathcal{M}(h)^{cd}$. $\Box$

For a Sperner hypergraph $\mathcal{H}$ let us denote by
$\mathcal{K}^{-1}(\mathcal{H})$ and $\mathcal{M}^{-1}(\mathcal{H})$ the sets
of definite Horn functions $h$ such that $\mathcal{K}(h)=\mathcal{H}$ and
$\mathcal{M}(h)=\mathcal{H}$, respectively. The following lemma will be used
in the subsequent sections.

######  Lemma 4.

Given a hypergraph $\mathcal{H}\subseteq 2^{V}$, the following hold.

  1. (a)

$\mathcal{K}^{-1}(\mathcal{H})=\mathcal{M}^{-1}(\mathcal{H}^{dc})$.

  2. (b)

If $f,g\in\mathcal{K}^{-1}(\mathcal{H})$ then $f\wedge
g\in\mathcal{K}^{-1}(\mathcal{H})$.

  3. (c)

If $f,g\in\mathcal{M}^{-1}(\mathcal{H})$ then $f\wedge
g\in\mathcal{M}^{-1}(\mathcal{H})$.

###### Proof.

Lemma 3 implies (a) and the equivalence of (b) and (c). We prove here (c).
Note that $X$ is a true set of $f\wedge g$ if and only if it is a true set of
both $f$ and $g$. Thus, if $\mathcal{M}(f)=\mathcal{M}(g)=\mathcal{H}$, then
we must have $\mathcal{M}(f\wedge g)=\mathcal{H}$, too. ∎

#### Matroids.

Matroids were introduced by Whitney [23] and independently by Nakasawa [18] as
abstract generalizations of linear independence in vector spaces. Matroids are
special independence systems satisfying stronger properties. There are several
equivalent, well-known axiomatizations, see e.g., [22, 20]. We recall here one
of those that will be used in our analysis. A nontrivial Sperner hypergraph
$\mathcal{C}\subseteq 2^{V}$ is the _family of circuits_ of a matroid if and
only if

$\forall C_{1},C_{2}\in\mathcal{C},\ C_{1}\neq C_{2}\text{ and }u\in C_{1}\cap
C_{2}~{}~{}\exists~{}C_{3}\in\mathcal{C}\text{ s.t. }C_{3}\subseteq(C_{1}\cup
C_{2})-u.$ (C)

##  3 Hypergraph Horn functions

To simplify our notation, we respectively write $H+v$ and $H-v$ instead of
$H\cup\\{v\\}$ and $H\setminus\\{v\\}$ for $H\subseteq V$ and $v\in V$. Given
a definite Horn function $h:2^{V}\to\\{0,1\\}$, we call an implicate $A\to v$
of it _circular_ if $((A+v)-u)\to u$ is also an implicate of $h$ for every
$u\in A$. To a hypergraph $\mathcal{H}\subseteq 2^{V}$ we associate the
definite Horn CNF $\Phi_{\mathcal{H}}$ defined as

$\Phi_{\mathcal{H}}~{}=~{}\bigwedge_{H\in\mathcal{H}}\left(\bigwedge_{v\in
H}\left((H-v)\to v\right)\right)$

and call $\Phi_{\mathcal{H}}$ the _circular CNF_ associated to the hypergraph
$\mathcal{H}$. Note that circular CNFs generalize equivalence relations.
Namely, if all hyperedges of $\mathcal{H}$ are of size two, then
$\Phi_{\mathcal{H}}$ represents an equivalence relation, and all equivalence
relations can be represented in this way. For example, if
$\mathcal{H}=\\{\\{1,2\\},\\{2,3\\},\\{4,5\\}\\}$, then $\Phi_{\mathcal{H}}$
represents two equivalence classes: $\\{1,2,3\\}$ and $\\{4,5\\}$. We remark
that even equivalence relations can be represented by different hypergraphs.
For example, $\mathcal{H}=\\{\\{1,2\\},\\{2,3\\},\\{4,5\\}\\}$ and
$\mathcal{G}=\\{\\{1,2\\},\\{1,3\\},\\{4,5\\}\\}$ satisfy
$\Phi_{\mathcal{H}}=\Phi_{\mathcal{G}}$.

We say that a definite Horn function $h:2^{V}\to\\{0,1\\}$ is _hypergraph
Horn_ if it has a circular CNF representation, that is, if there exists a
hypergraph $\mathcal{H}\subseteq 2^{V}$ such that
$h~{}=~{}\Phi_{\mathcal{H}}$. The next example shows that
$\Phi_{\mathcal{H}}=\Phi_{\mathcal{H}^{\prime}}$ can hold even if
$\mathcal{H}$ is Sperner while $\mathcal{H}^{\prime}$ is not, and that
hypergraph Horn functions might have non-circular implicates.

######  Example 5.

Consider the set $V=\\{1,2,\dots,8\\}$, the subsets $H_{1}=\\{1,2,5\\}$,
$H_{2}=\\{4,5,6\\}$, $H_{3}=\\{3,4,7\\}$, $H_{4}=\\{2,7,8\\}$,
$H_{5}=\\{1,2,3,4\\}$, $H_{6}=\\{1,2,3,5,6\\}$, and $H_{7}=\\{1,3,4,7,8\\}$,
and the hypergraphs

$\displaystyle\mathcal{H}$
$\displaystyle=~{}\\{H_{1},H_{2},H_{3},H_{4},H_{5}\\},\text{ and}$
$\displaystyle\mathcal{H}^{\prime}$
$\displaystyle=~{}\\{H_{1},H_{2},H_{3},H_{4},H_{6},H_{7}\\}.$

We claim that $\Phi_{\mathcal{H}}=\Phi_{\mathcal{H}^{\prime}}$. To see this,
we show that $\Phi_{\\{H_{5}\\}}\geq\Phi_{\mathcal{H}^{\prime}}$ and that
$\Phi_{\\{H_{6},H_{7}\\}}\geq\Phi_{\mathcal{H}}$. These relations then imply
$\Phi_{\mathcal{H}}\leq\Phi_{\mathcal{H}^{\prime}}$ and
$\Phi_{\mathcal{H}^{\prime}}\leq\Phi_{\mathcal{H}}$ from which
$\Phi_{\mathcal{H}}=\Phi_{\mathcal{H}^{\prime}}$ follows.

To see e.g., that $\Phi_{\\{H_{5}\\}}$ is a majorant of
$\Phi_{\mathcal{H}^{\prime}}$ one can show that
$\mathbb{T}_{\Phi_{\mathcal{H}^{\prime}}}(H_{5}-u)\ni u$ for all $u\in H_{5}$.
For instance, for $u=1$ and $S=H_{5}-u=\\{2,3,4\\}$ we can see that
$\mathbb{T}^{1}_{\mathcal{H}^{\prime}}(S)=S+7$ because of the clause
$H_{3}-7\to 7$ of $\mathcal{H}^{\prime}$. Then we get
$\mathbb{T}^{1}_{\mathcal{H}^{\prime}}(S+7)=S+7+8$ because of the clause
$H_{4}-8\to 8$ of $\mathcal{H}^{\prime}$. Finally, we get
$\mathbb{T}_{\mathcal{H}^{\prime}}^{1}(S+7+8)=S+7+8+1$ due to the clause
$H_{7}-1\to 1$. Thus, we have
$1\in\mathbb{T}_{\mathcal{H}^{\prime}}(\\{2,3,4\\})$. By Lemma 2, this implies
that $H_{5}-1\to 1$ is an implicate of $\Phi_{\mathcal{H}^{\prime}}$. Using
similar arguments for the other elements of $H_{5}$, we can show that
$H_{5}-2\to 2$, $H_{5}-3\to 3$ and $H_{5}-4\to 4$ are all implicates of
$\Phi_{\mathcal{H}^{\prime}}$, implying the inequality
$\Phi_{\mathcal{H}}\geq\Phi_{\mathcal{H}^{\prime}}$. Applying similar
arguments to $H_{6}$ and $H_{7}$, we can also prove the reverse inequality, as
claimed above.

Note that in this example the hypergraph $\mathcal{H}$ is Sperner, while
$\mathcal{H}^{\prime}$ is not. Furthermore, in this example there exists a
non-circular implicate of $\Phi_{\mathcal{H}}$. Namely, $\\{1,5,6\\}\to 3$ is
an implicate of $\Phi_{\mathcal{H}}$ while $\\{3,5,6\\}\to 1$ is not.

We say that a subset $I\subseteq V$ is an _implicate set_ of a definite Horn
function $h$ if $(I-v)\to v$ is an implicate of $h$ for all $v\in I$. For a
Boolean function $f$, we denote by $\mathcal{I}(f)$ its _family of implicate
sets_. By definition, we have $\emptyset\in\mathcal{I}(f)$ for all Boolean
functions $f$.

######  Lemma 6.

For every Boolean function $f:2^{V}\to\\{0,1\\}$ the hypergraph
$\mathcal{I}(f)$ is union closed, that is, $I,J\in\mathcal{I}(f)$ implies
$I\cup J\in\mathcal{I}(f)$.

###### Proof.

Take an arbitrary element $v\in I\cup J$. Without loss of generality, we may
assume that $v\in I$. As $I$ is an implicate set of $f$, we have $(I-v)\to v$.
This implies that $((I\cup J)-v)\to v$ holds. ∎

Given two families $\mathcal{G}\subseteq\mathcal{F}\subseteq 2^{V}$, we call
$\mathcal{G}$ a _generator_ of $\mathcal{F}$ if its union closure is
$\mathcal{F}$, that is, $\mathcal{G}^{\cup}=\mathcal{F}$. For every Boolean
function $f:2^{V}\to\\{0,1\\}$, there exists a unique minimal generator of
$\mathcal{I}(f)$. Indeed, let $\mathcal{G}(f)$ consist of those implicate sets
that are not the union of others. These sets are clearly contained in any
subfamily whose union closure is $\mathcal{I}(f)$, and every other set in
$\mathcal{I}(f)$ can be obtained as the union of such sets. We call
$\mathcal{G}(f)$ the _standard generator_ of $\mathcal{I}(f)$. Note that
$\mathcal{G}(f)$ may not form a Sperner hypergraph.

######  Example 7.

Let us note that the set $\mathcal{I}(h)$ can be much larger than the input
representation. Furthermore, it can happen that $\mathcal{I}(h)$ cannot be
obtained by taking unions of the input, even for hypergraph Horn functions.

For a set $V=\\{i,i^{\prime}\mid i=1,\dots,n\\}$ of $2n$ elements, consider
the hypergraph $\mathcal{H}=\\{\\{i,i^{\prime}\\}\mid
i=1,\dots,n\\}\cup\\{\\{1,2,\dots,n\\}\\}$ of $n+1$ hyperedges and the
corresponding hypergraph Horn function $h=\Phi_{\mathcal{H}}$. It is not
difficult to see that

$\mathcal{I}(h)=(\mathcal{H}\cup\left\\{Z\subseteq V\mid
Z\cap\\{i,i^{\prime}\\}\neq\emptyset~{}\forall~{}i=1,\dots,n\right\\})^{\cup}.$

This family of implicate sets contains exponentially many hyperedges that are
not in the union closure of the input.

As pointed out in Lemma 6, implicate sets of a Boolean function $f$ are closed
under taking unions. This implies that every subset $S\subseteq V$ has a
unique maximal implicate set as its subset. We denote by $\mathbb{I}_{f}(S)$
this unique maximal implicate subset of $S$ and call it the _core_ of $S$ (or
the $f$-_core_ of $S$, if the function is not clear from the context). Recall
that $\mathcal{T}(f)$ denotes the family of true sets of $f$.

######  Lemma 8.

For a definite Horn function $f$, we have the following equivalences:

$T\in\mathcal{T}(f)\,\,\iff\,\,\mathbb{T}_{f}(T)=T,$ (1a)
$I\in\mathcal{I}(f)\,\,\iff\,\,\mathbb{I}_{f}(I)=I.$ (1b)

###### Proof.

The lemma follows by the definitions, as for a subset $S\subseteq V$ the
closure $\mathbb{T}_{f}(S)$ is the unique smallest true set containing $S$,
while the core $\mathbb{I}_{f}(S)$ is the unique maximal implicate set
contained in $S$. ∎

The next technical lemma, together with its corollary, describes a certain
duality relation between true sets and implicate sets specifically for
hypergraph Horn functions, which will be useful in our proofs later.

######  Lemma 9.

For a hypergraph Horn function $h$ and subsets $I,T\subseteq V$, we have the
following equivalences:

$T\in\mathcal{T}(h)\,\,\iff\,\,\nexists\,J\in\mathcal{I}(h)\text{ with
}~{}|J\setminus T|=1,$ (2a)
$I\in\mathcal{I}(h)\,\,\iff\,\,\nexists\,S\in\mathcal{T}(h)\text{ with
}~{}|I\setminus S|=1.$ (2b)

###### Proof.

For (2a), note that the right hand side is equivalent with
$\mathbb{T}^{1}_{\Phi_{\mathcal{I}(h)}}(T)=T$, which is indeed equivalent with
$T\in\mathcal{T}(h)$ since $h=\Phi_{\mathcal{I}(h)}$ is hypergraph Horn.

For (2b), note that the right hand side is equivalent to the claim that for
every $u\in I$ and for every $S\in\mathcal{T}(h)$ the inclusion $I-u\subseteq
S$ implies $u\in S$. This is equivalent to $\mathbb{T}_{h}(I-u)\ni u$ for all
$u\in I$, which is the definition of $I$ being an implicate set of $h$. ∎

As a direct consequence, we get the following characterizations of true and
implicate sets for hypergraph Horn functions.

######  Corollary 10.

For a hypergraph Horn function $h$, we have the following equalities:

$\mathcal{T}(h)~{}=~{}\\{T\subseteq V\mid\nexists~{}I\in\mathcal{I}(h)\text{
with }~{}|I\setminus T|=1\\},$ (3a) $\mathcal{I}(h)~{}=~{}\\{I\subseteq
V\mid\nexists~{}T\in\mathcal{T}(h)\text{ with }~{}|I\setminus T|=1\\}.$ (3b)

$\Box$

Let us remark that (2b) and (3b) hold for arbitrary Boolean functions $h$, not
only for hypergraph Horn ones. Moreover, later we show that both (2a) and (3a)
provide necessary and sufficient conditions for $h$ being hypergraph Horn.

Observe that the conjunction of two hypergraph Horn functions $h_{1}$ and
$h_{2}$ is also hypergraph Horn. Indeed, if $\mathcal{H}_{1}$ and
$\mathcal{H}_{2}$ are hypergraph such that $h_{i}=\Phi_{\mathcal{H}_{i}}$ for
$i=1,2$, then $h_{1}\wedge h_{2}=\Phi_{\mathcal{H}_{1}\cup\mathcal{H}_{2}}$.
Therefore any Boolean function $f$ admits a unique minimal hypergraph Horn
majorant which we denote by $f^{\circ}=\Phi_{\mathcal{I}(f)}$. Note that
$f^{\circ}=1$ may hold for a Boolean function $f$. Note also that $f$ is a
hypergraph Horn function if and only if $f=f^{\circ}$.

The natural “duality” between the families of true sets and implicate sets
pointed out above motivates the following definition. To a given Boolean
function $f$ we associate another Boolean function, called its _implicate-
dual_ and denoted by $f^{i}$, defined uniquely by the equality

$\mathcal{T}(f^{i})~{}=~{}\mathcal{I}(f)^{c}.$ (4)

Since $\mathcal{I}(f)=\mathcal{I}(f^{\circ})$ for every Boolean function $f$,
we have $f^{i}=(f^{\circ})^{i}=f^{\circ i}$. Furthermore, since
$\emptyset\in\mathcal{I}(f)$ we have $V\in\mathcal{T}(f^{i})$ and by Lemma 6
the family $\mathcal{I}(f)^{c}$ is closed under intersections. Consequently,
by Lemma 1, the function $f^{i}=f^{\circ i}$ is definite Horn for every
Boolean function $f$.

##  4 Characterizations of hypergraph Horn functions

In this section we provide multiple characterizations of hypergraph Horn
functions. Recall that for a Boolean function $f$, $\mathcal{G}(f)$ denotes
the standard generator of $\mathcal{I}(f)$. Our main theorem below summarizes
these equivalences.

######  Theorem 11.

For a definite Horn function $f:2^{V}\to\\{0,1\\}$, the following claims are
equivalent.

  1. (i)

$f$ is hypergraph Horn.

  2. (ii)

$f^{\circ}=f$.

  3. (iii)

$f^{ii}=f$.

  4. (iv)

For every false set $F$ of $f$, there exists an implicate set
$I\in\mathcal{I}(f)$ such that $|I\setminus F|=1$.

  5. (v)

For every false set $F$ of $f$, there exists an implicate set
$I\in\mathcal{G}(f)$ such that $|I\setminus F|=1$.

  6. (vi)

For every false set $F$ of $f$, there exists a variable
$u\in\mathbb{T}_{f}(F)\setminus F$ such that $v\in\mathbb{T}_{f}(F-v+u)$ holds
for every $v\in F$ with $f(F-v)=1$.

Let us note that property (iii) is a generalization of _matroid duality_.
Property (iv) above is the same as (2a) and (3a) and characterizes hypergraph
Horn functions. This property will be used in Section 5.2 for an efficient
algorithm to recognize hypergraph Horn functions from definite Horn CNFs.
Property (vi) is a generalization of the so-called Mac Lane – Steinitz
exchange property for closure operator of matroids [22].

In what follows, we show several simpler claims and we use those put together
at the end of this section to prove Theorem 11. Our first result shows the
equivalence of (ii) and (iv) in Theorem 11.

######  Lemma 12.

For a Boolean function $f:2^{V}\to\\{0,1\\}$, we have $f^{\circ}=f$ if and
only if for every false set $F$ of $f$ there exists an implicate set
$I\in\mathcal{I}(f)$ such that $|I\setminus F|=1$.

###### Proof.

Since $f=f^{\circ}$ is equivalent to the condition that $f$ is hypergraph
Horn, the only-if part follows from (2a). For the if part, assume that $f\neq
f^{\circ}$. Since $f\leq f^{\circ}$ holds for all Boolean functions, there
exists a subset $F\subseteq V$ for which $f(F)=0$ and $f^{\circ}(F)=1$. By
applying (2a) to $f^{\circ}$, no implicate set $I\in\mathcal{I}(f)$ satisfies
$|I\setminus F|=1$, which completes the proof of the if part. ∎

Next we provide a characterization of hypergraph Horn functions that proves
the equivalence of (i) and (vi) of Theorem 11.

######  Lemma 13.

A definite Horn function $h$ is hypergraph Horn if and only if for every false
set $F$ of $h$, there exists a variable $u\in V\setminus F$ such that

  1. (i)

$F\overset{h}{\to}u$, and

  2. (ii)

$F-v+u\overset{h}{\to}v$ for all variables $v\in F$ with $h(F-v)=1$.

###### Proof.

Consider a hypergraph Horn function $h$, i.e., $h=\Phi_{\mathcal{I}(h)}$. Let
us consider an arbitrary false set $F\subseteq V$ of $h$. Then (2a) implies
that there exists an implicate set $I\in\mathcal{I}(h)$ with $I\setminus
F=\\{u\\}$ for some $u\in V$. We claim that $u$ satisfies (i) and (ii) in
Lemma 13. Indeed, $I\setminus F=\\{u\\}$ implies $F\overset{h}{\to}u$.
Moreover, for any $v\in F$ with $h(F-v)=1$, we have
$I\setminus(F-v)=\\{v,u\\}$, as otherwise $I\setminus(F-v)=\\{u\\}$ holds,
implying that $F-v$ is a false set of $h$, a contradiction. Therefore, we have
$(F-v+u)\overset{h}{\to}v$, which proves (ii).

For the reverse implication, assume that $h<h^{\circ}$ (i.e.,
$h\not=h^{\circ}$), and choose a minimal subset $F\subseteq V$ such that
$h(F)=0$ and $h^{\circ}(F)=1$. By the minimality of $F$ and by $h\leq
h^{\circ}$, for every variable $v\in F$ we have either $h(F-v)=1$ or
$h^{\circ}(F-v)=0$. Let us define $Q=\\{v\in F\mid h(F-v)=1\\}$ and
$R=F\setminus Q=\\{v\in F\mid h^{\circ}(F-v)=0\\}$. Since $h^{\circ}(F)=1$ and
$h^{\circ}(F-v)=0$ for a variable $v\in R$, there exists an implicate set
$I\in\mathcal{I}(h)=\mathcal{I}(h^{\circ})$ such that $v\in I\subseteq F$.
This implies that $(F-v)\overset{h}{\to}v$ for all $v\in R$. If we assume that
some $u\in V\setminus F$ satisfies (i) and (ii), then $F+u$ is an implicate
set of $h$. This however contradicts $h^{\circ}(F)=1$, which completes the
proof of the if part of the theorem. ∎

We say that a hypergraph $\mathcal{H}$ is a _minimal representation_ of a
hypergraph Horn function $h$ if $\Phi_{\mathcal{H}}=h$ but
$\Phi_{\mathcal{H}^{\prime}}\neq h$ for every
$\mathcal{H}^{\prime}\subsetneq\mathcal{H}$. The next lemma, that is of
independent combinatorial interest on its own, shows that hypergraph Horn
functions can be represented by their standard generators; this in turn
implies the equivalence of (iv) and (v).

######  Lemma 14.

If $\mathcal{H}\subseteq\mathcal{I}(h)$ is a minimal representation of the
hypergraph Horn function $h$ and $H\in\mathcal{H}\setminus\mathcal{G}(h)$,
then $H$ can be replaced by a member $H^{\prime}$ of $\mathcal{G}(h)$ such
that for the resulting hypergraph
$\mathcal{H}^{\prime}=\mathcal{H}\setminus\\{H\\}\cup\\{H^{\prime}\\}$ we have
$\Phi_{\mathcal{H}^{\prime}}=h$.

###### Proof.

Take an arbitrary hyperedge $H\in\mathcal{H}\setminus\mathcal{G}(h)$, and let
$\mathcal{J}=\\{J_{1},\dots,J_{k}\\}$ be an inclusionwise minimal family of
sets from $\mathcal{G}(h)$ whose union is $H$. Let $H_{j}=\bigcup_{\ell\neq
j}J_{\ell}$. By the minimality of $\mathcal{J}$, $H_{j}$ is a proper subset of
$H$ for every $j$.

We claim that $H$ can be replaced by $H_{j}$ for some $j$; the repeated
application of such a step immediately proves the theorem. Suppose to the
contrary that the claim does not hold. Then for each $j$, by Lemma 9 and the
minimality of $\mathcal{H}$, there exists an element $x_{j}\in H\setminus
H_{j}$ and a false set $F_{j}\in\mathcal{F}(h)$ such that $H\setminus
F_{j}=\\{x_{j}\\}$ and $H$ is the unique hyperedge of $\mathcal{H}$ with that
property. Let $F=F_{1}\cap F_{2}$. As $|J_{1}\setminus F|=1$, $F$ is a false
set by Lemma 9. Since $H$ is the only set in $\mathcal{H}$ such that
$|H\setminus F_{j}|=1$ for both $j=1$ and $2$, there exists no hyperedge
$K\in\mathcal{H}$ with $|K\setminus F|=1$. This contradicts our assumption
that $\Phi_{\mathcal{H}}=h$. ∎

The equivalence of (iv) and (v) then follows: (iv) is clearly a strengthening
of (v), while the other direction holds as $h=\Phi_{\mathcal{G}(h)}$ by Lemma
14. It is worth formulating the latter observation as a corollary.

######  Corollary 15.

Any hypergraph Horn function $h$ admits a minimal representation $\mathcal{H}$
such that $\mathcal{H}\subseteq\mathcal{G}(h)$. $\Box$

We show next that implicate-duality associates a hypergraph Horn function to
every Boolean function.

######  Lemma 16.

The function $f^{i}$ is hypergraph Horn for every Boolean function $f$.

###### Proof.

By the definition of the $i$ operator in (4), $f^{i}$ is always definite Horn.
Thus, it suffices to show that every false set $F$ of $f^{i}$ has a variable
$v\in V\setminus F$ that satisfies (i) and (ii) of Lemma 13, since this proves
that $f^{i}$ is hypergraph Horn by Lemma 13.

Let $U=\mathbb{T}_{f^{i}}(F)\setminus F$. Since $F$ is a false set of $f^{i}$,
we have $U\not=\emptyset$ and

$F\overset{f^{i}}{\to}u~{}~{}~{}\mbox{ for all}~{}u\in U,$

implying that (i) of Theorem 13 holds for any $u\in U$. Let us denote by

$W~{}=~{}\\{w\in F\mid F-w\in\mathcal{T}(f^{i})\\}.$

If $W=\emptyset$, then (ii) of Theorem 13 is vacuous for this false set $F$,
and we have nothing else to show. Thus, let us assume for the rest of the
proof that $W\neq\emptyset$. Let $\bar{F}=V\setminus F$,
$I_{0}=\bar{F}\setminus U$, and $I_{w}=\bar{F}+w$ for $w\in W$. Then, by the
definition of the $i$ operator in (4), we have $\bar{F}\notin\mathcal{I}(f)$,
$I_{0}\in\mathbb{I}_{f}(\bar{F})$, and $I_{w}\in\mathcal{I}(f)$ for every
$w\in W$. Let us observe that $\bar{F}-u\overset{f}{\to}u$ holds for all $u\in
I_{0}$, since $\bar{F}-u\supseteq I_{0}-u$ and $I_{0}$ is an implicate set of
$f$. Therefore, by $\bar{F}\notin\mathcal{I}(f)$, there exists a variable
$u\in U$ such that

$\bar{F}-u\overset{f}{\nrightarrow}u.$ (5)

We claim that this $u\in U$ satisfies (ii) of Lemma 13, which complete the
proof of the lemma.

To prove the claim, let us assume that there exists a variable $w\in W$ such
that $F-w+u\overset{f^{i}}{\nrightarrow}w$. Let $I_{uw}$ be an implicate set
of $f$ defined by $I_{uw}=V\setminus\mathbb{T}_{f^{i}}(F-w+u)$, where we note
that $\mathbb{T}_{f^{i}}(F-w+u)$ is a true set of $f_{i}$. Since
$F-w+u\overset{f^{i}}{\nrightarrow}w$, we have
$w\not\in\mathbb{T}_{f^{i}}(F-w+u)$, i.e., $w\in I_{uw}$. Thus,
$I_{uw}\setminus(\bar{F}-u)=\\{w\\}$ holds. This, together with
$I_{w}=\bar{F}+w$, implies that $\mathbb{T}_{f}(\bar{F}-u)\supseteq\bar{F}+w$.
This means by Lemma 2 that $\bar{F}-u\to u$ is an implicate of $f$, which
contradicts (5). ∎

Next we show that implicate-duality is an involution when restricted to the
family of hypergraph Horn functions. More precisely, we prove the following
statement.

######  Lemma 17.

We have $f^{ii}=f^{\circ}$ for every Boolean function $f$.

###### Proof.

Since a Boolean function is uniquely determined by its family of true sets,
the statement is equivalent to the equality

$\mathcal{T}(f^{\circ})~{}=~{}\mathcal{I}(f^{i})^{c}.$ (6)

by the definition of the implicate-dual of $f^{i}$. Note that $f^{\circ}$ and
$f^{i}$ are both hypergraph Horn by the definition of $f^{\circ}$ and Lemma
16. Thus, we shall show (6) by applying Lemma 9 for both $f^{\circ}$ and
$f^{i}$. By applying (2a) of Lemma 9 to $f^{\circ}$, we get the equivalence

$T\in\mathcal{T}(f^{\circ})\,\,\iff\,\,\nexists\,J\in\mathcal{I}(f^{\circ})\text{
s.t. }|J\setminus T|=1.$

Since the true sets of $f^{i}$ are exactly the complements of implicate sets
of $f^{\circ}$ by our definition of the implicate-dual, we also have (for an
arbitrary set $T$) the equivalence

$\nexists J\in\mathcal{I}(f^{\circ})\text{ s.t. }|J\setminus
T|=1\,\,\iff\,\,\nexists S\in\mathcal{T}(f^{i})\text{ s.t. }|\bar{T}\setminus
S|=1.$

Finally, by applying (2b) of Lemma 9 to $f^{i}$, we get the equivalence of

$\nexists S\in\mathcal{T}(f^{i})\text{ s.t. }|\bar{T}\setminus
S|=1\iff\bar{T}\in\mathcal{I}(f^{i}).$

Putting together the above three equivalences, we obtain (6), and the lemma
follows. ∎

Now we are ready to prove the main theorem of this section.

###### Proof of Theorem 11:.

Note first that the equivalence of (i) and (ii) follows by our definitions.
The equivalence of (ii) and (iv) follows by Lemma 12. The equivalence of (iv)
and (v) follows by Lemma 14. The equivalence of (i) and (vi) is implied by
Lemma 13. Finally, the equivalence of (ii) and (iii) follows by Lemma 17. ∎

######  Remark 18.

Let us note that the equivalence between (i), (ii), (iii), (iv), and (v) in
Theorem 11 follows for an arbitrary Boolean function $f$. Property (vi) makes
sense only for definite Horn functions, since the closure operator
$\mathbb{T}$ is defined only when $f$ is definite Horn.

We also remark that Lemmas 16 and 17 imply the following property on
hypergraph Horn functions.

######  Corollary 19.

Operator $i$ provides a bijection on hypergraph Horn functions, and hence all
hypergraph Horn functions arise as implicate-duals of hypergraph Horn
functions.

###### Proof.

By Theorem 11, we have $h^{ii}=h$ for every hypergraph Horn function $h$. This
implies the statement. ∎

Corollary 19 naturally raises the following question: how to characterize dual
pairs $h,h^{i}$ of hypergraph Horn functions in terms of their implicate sets,
for example? In Section 5, we discuss the related topics from an algorithmic
point of view.

Let us call a hypergraph Horn function $h$ _self implicate-dual_ if $h^{i}=h$.
Even the characterization of hypergraphs $\mathcal{H}\subseteq 2^{V}$ for
which $h=\Phi_{\mathcal{H}}$ is self implicate-dual is open. We shall see in
an accompanying paper [2] that the families of circuits of self-dual matroids
are such hypergraphs. However, there are self implicate-dual functions that do
not correspond to matroids, as shown by the following example.

######  Example 20.

For $V=\\{1,2,3,4,5\\}$, consider a hypergraph Horn function $f$ represented
by $\Phi_{\mathcal{H}}$, where

$\mathcal{H}=\left\\{\emptyset,\\{1,2,3\\},\\{4,5\\},\\{1,2,4,5\\},\\{1,3,4,5\\},\\{2,3,4,5\\},V\right\\}.$

It is not difficult to verify that

$\mathcal{I}(h)=\mathcal{H}~{}~{}~{}\text{ and
}~{}~{}~{}\mathcal{T}(h)=\mathcal{H}^{c}.$

implying that $h^{i}=h$, i.e., $h$ is self implicate-dual. On the other hand,
minimal nontrival sets in $\mathcal{H}$ do not satisfy the circuit axiom (C),
implying that $f$ is not matorid-Horn; for further details, we refer the
interested reader to [2].

##  5 Computational problems for hypergraph Horn functions

In this section, we consider computational problems for hypergraph Horn
functions. We first show that the core $\mathbb{I}_{\Psi}(S)$ can be computed
in polynomial time from a definite Horn CNF $\Psi$ and an arbitrary set
$S\subseteq V$. Note that operators $\mathbb{T}$ and $\mathbb{I}$ play a dual
role in hypergraph Horn functions. While $\mathbb{T}_{\Psi}(S)$ is possible to
compute in linear time, $\mathbb{I}_{\Psi}(S)$ seems to be difficult to
compute in linear time. We then show that the recognition problem (i.e., the
problem of deciding if a given definite Horn CNF represents a hypergraph Horn
function) and the key realization problem (i.e., the problem of deciding if a
given hypergraph is realized as the set of minimal keys of a hypergraph Horn
function $h$) can be solved in polynomial time, and implicate sets can be
generated with polynomial delay. We also discuss problems related to
implicate-duality.

###  5.1 Core computation

Let us start with the core computation, i.e., finding the largest implicate
set contained in a given set. For a definite Horn CNF $\Psi$, we define

$\mathbb{I}^{1}_{\Psi}(S)~{}=~{}\\{v\in S\mid v\in\mathbb{T}_{\Psi}(S-v)\\}.$

Algorithm 1 Core Computation

1:Input: A definite Horn CNF $\Psi$ and a set $S\subseteq V$.

2:Output: Core $\mathbb{I}_{\Psi}(S)$ of $S$ .

3:Initialize: $\mathbb{I}^{0}_{\Psi}(S)\coloneqq S$

4:for $k=1,2,\dots,|S|$ do

5: Compute
$\mathbb{I}^{k}_{\Psi}(S)=\mathbb{I}^{1}_{\Psi}(\mathbb{I}^{k-1}_{\Psi}(S))$

6:end for

7:return $\mathbb{I}^{|S|}_{\Psi}(S)$

The following theorem shows that Algorithm Core Computation computes the core
in polynomial time.

######  Theorem 21.

For a definite Horn CNF $\Psi$ and a subset $S\subseteq V$, core
$\mathbb{I}_{f}(S)$ of $S$ can be obtained in $O(|S|^{2}{\cdot}\|\Psi\|)$
time.

###### Proof.

By definition, we have $\mathbb{I}^{1}_{\Psi}(S)\subseteq S$, and note that
equality holds if and only if $S$ is an implicate set. We also note that
$\mathbb{I}^{k}_{\Psi}(S)=\mathbb{I}^{k-1}_{\Psi}(S)$ implies
$\mathbb{I}^{\ell}_{\Psi}(S)=\mathbb{I}^{k-1}_{\Psi}(S)$ for all $\ell\geq
k-1$. Since $\emptyset$ is an implicate set for any Boolean function,
Algorithm 1 always outputs an implicate set of $\Psi$ contained in $S$.
Moreover, for any implicate set $I\subseteq S$ of $\Psi$, all variables $v\in
I$ satisfy $v\in\mathbb{T}_{f}(S-v)$, since $I-v\subseteq S-v$. Thus, the set
generated by the algorithm contains all implicate sets $I$ contained in $S$.
This implies that the algorithm computes the core of $S$ correctly. Since for
a subset $X\subseteq V$ and variable $v\in X$ we can test the condition
$v\in\mathbb{T}_{\Psi}(X-v)$ in $O(\|\Psi\|)$ time, the theorem follows. ∎

###  5.2 Hypergraph Horn recognition problem

We now move to the recognition problem of hypergraph Horn functions. The
following algorithm uses Algorithm 1 as a subroutine polynomially many times.

Algorithm 2 Hypergraph Horn Recognition

1:Input: A definite Horn CNF $\Psi$.

2:Output: A hypergraph $\mathcal{H}\subseteq 2^{V}$ such that
$\Psi=\Phi_{\mathcal{H}}$ if $\Psi$ represents a hypergraph Horn function, and
“No” otherwise.

3:Initialize: $\mathcal{H}\coloneqq\emptyset$

4:for each clause $A\to v$ of $\Psi$ do

5: while $A\overset{\Phi_{\mathcal{H}}}{\nrightarrow}v$ do

6: $T\coloneqq\mathbb{T}_{\Phi_{\mathcal{H}}}(A)$

7: for each $u\in V\setminus T$ do

8: if $u\in\mathbb{I}_{\Psi}(T+u)$ then

9: $\mathcal{H}\coloneqq\mathcal{H}\cup\\{\mathbb{I}_{\Psi}(T+u)\\}$

10: end if

11: end for

12: if $T=\mathbb{T}_{\Phi_{\mathcal{H}}}(A)$ then

13: return “No”

14: end if

15: end while

16:end for

17:return $\mathcal{H}$

######  Theorem 22.

For a definite Horn CNF $\Psi$, we can decide in
$O(|V|^{4}{\cdot}|\Psi|{\cdot}\|\Psi\|)$ time if $\Psi$ represents a
hypergraph Horn function, and if yes, construct a hypergraph
$\mathcal{H}\subseteq 2^{V}$ such that $h=\Phi_{\mathcal{H}}$ and
$|\mathcal{H}|\leq|V|{\cdot}|\Psi|$.

###### Proof.

We show that Algorithm 2 satisfies the statement of the theorem. The algorithm
makes use of Characterization (iv) of Theorem 11 and the efficient computation
of the cores by Algorithm 1.

Let us observe first that the algorithm collects in $\mathcal{H}$ implicate
sets of $\Psi$ (see lines 8-9), and thus $\Psi\leq\Phi$ always holds during
the iterations of the algorithm. We also note that $T$ computed in line 6 is a
false set of $\Psi$, since $A\overset{\Psi}{\to}v$, $A\subseteq T$, and
$v\not\in T$. Thus, if the condition in line 8 holds for none of the elements
$u\in V\setminus T$, then by Theorem 11 (iv), $\Psi$ does not represent a
hypergraph Horn function, and the algorithm halts correctly in line 13.

On the other hand, if the condition in line 8 holds, then we get an implicate
set $I$ of $\Psi$, and by adding this implicate set to $\mathcal{H}$ changes
$\Phi_{\mathcal{H}}$ such that the set $T$ recomputed on line 6 strictly
increases in size. Thus the while-loop will be executed for every clause of
$\Psi$ at most $|V|$ times, and if the while-loop for clause $A\to v$ does not
stop in line 13, then the clause becomes an implicate of $\Phi_{\mathcal{H}}$
at the end. Consequently, we have $\Psi=\Phi_{\mathcal{H}}$, if the algorithm
halts in line 17. Moreover, we have $|\mathcal{H}|\leq|V|{\cdot}|\Psi|$ upon
termination, since $\mathcal{H}$ is updated at most $|V|{\cdot}|\Psi|$ times.

As for the time complexity, we can see that the core $\mathbb{I}_{\Psi}$ in
line 8 and the closure $\mathbb{T}_{\Phi_{\mathcal{H}}}$ in lines 6 and 12 can
be computed at most $|V|^{2}{\cdot}|\Psi|$ and $2{\cdot}|V|{\cdot}|\Psi|$
times, respectively. Therefore, the algorithm requires
$O(|V|^{4}{\cdot}|\Psi|{\cdot}\|\Psi\|)$ time by Theorem 21 and
$\|\Phi\|\leq|V|^{2}{\cdot}|\Psi|$. ∎

###  5.3 Key realization

In the key realization problem we are given a hypergraph $\mathcal{K}\subseteq
2^{V}$, and the goal is to decide if $\mathcal{K}$ can be realized as the set
of minimal keys of a hypergraph Horn function $h$, i.e.,
$\mathcal{K}=\mathcal{K}(h)$. Note that the _key set_ (i.e., family of all
minimal keys) of a definite Horn function is Sperner and any Sperner
hypergraph is realized as the key set of a definite Horn function. Thus we may
assume that $\mathcal{K}$ is Sperner.

Let us first review basic properties of minimal keys and maximal nontrivial
true sets of definite Horn functions. For a Sperner hypergraph
$\mathcal{K}\subseteq 2^{V}$, let $\mathcal{K}^{+}$ denote the family of
supersets of the hyperedges of $\mathcal{K}$, i.e.,

$\mathcal{K}^{+}=\\{W\subseteq V\mid W\supseteq K\mbox{ for some
}K\in\mathcal{K}\\},$

and we denote by $\mathcal{M}=\mathcal{K}^{dc}$ the associated family of
maximal independent sets of $\mathcal{K}$. Recall that if
$\mathcal{K}=\mathcal{K}(h)$ for a definite Horn function $h$, then we have
$\mathcal{M}=\mathcal{M}(h)$ by Lemma 3.

######  Lemma 23.

A Sperner hypergraph $\mathcal{K}$ is realized as a key set of a definite Horn
function $h$ if and only if

  1. (i)

$\mathcal{M}\subseteq\mathcal{T}(h)$, and

  2. (ii)

$\mathcal{K}^{+}\setminus\\{V\\}\subseteq\mathcal{F}(h)$.

###### Proof.

The statement follows from the definitions of $\mathcal{K}(h)$ and
$\mathcal{M}(h)$ and their relation $\mathcal{M}(h)=\mathcal{K}(h)^{dc}$ by
Lemma 3. ∎

We restate this lemma for the key realization problem in more constructive
terms. We call a subset $I\subseteq V$ a _potential implicate set_ for a
hypergraph $\mathcal{K}$ if $\mathcal{M}\subseteq\mathcal{T}(\Phi_{\\{I\\}})$.
By Lemma 23(i), any implicate set of a definite Horn function $h$ with
$\mathcal{K}(h)=\mathcal{K}$ must be a potential implicate set, since
$\mathcal{M}=\mathcal{K}(h)^{dc}=\mathcal{M}(h)\subseteq\mathcal{T}(h)$. Let
$\mathcal{P}(\mathcal{K})\subseteq 2^{V}$ denote the _family of all potential
implicate sets_ for a Sperner hypergraph $\mathcal{K}$. As
$\mathcal{T}(\Phi_{I})\cup\mathcal{T}(\Phi_{J})\subseteq\mathcal{T}(\Phi_{I\cup
J})$ holds for any pair $I,J\subseteq V$ of subsets,
$\mathcal{P}(\mathcal{K})$ is closed under taking union.

######  Lemma 24.

A Sperner hypergraph $\mathcal{K}$ is realized as a key set of a hypergraph
Horn function $h$ if and only if

  1. (i)

$\mathcal{I}(h)\subseteq\mathcal{P}(\mathcal{K})$, and

  2. (ii)

for any $F\in\mathcal{K}^{+}\setminus\\{V\\}$ there exists
$I\in\mathcal{I}(h)$ with $|I\setminus F|=1$.

###### Proof.

The statement follows from (2a) and Lemma 23. ∎

Clearly, having more implicate sets makes it easier to satisfy Lemma 24 (ii),
which implies the following lemma.

######  Lemma 25.

A Sperner hypergraph $\mathcal{K}$ is realized as the key set of a definite
Horn function if and only if the hypergraph Horn function
$h=\Phi_{\mathcal{P}(\mathcal{K})}$ realizes $\mathcal{K}$ as its key set.
Furthermore, $\Phi_{\mathcal{P}(\mathcal{K})}$ is the unique maximal circular
minorant of the hypergraph Horn functions that have $\mathcal{K}$ as their key
sets, i.e., any hypergraph Horn function $f$ such that
$\mathcal{K}=\mathcal{K}(f)$ satisfies $f\geq\Phi_{\mathcal{P}(\mathcal{K})}$.

###### Proof.

Let $h$ be a hypergraph Horn function represented by
$\Phi_{\mathcal{P}(\mathcal{K})}$. Then $h$ satisfies (i) of Lemma 23 by the
definition of potential implicate sets. Furthermore, we have $h\leq f$ for any
hypergraph Horn function $f$ satisfying Lemma 23(i). This together with Lemma
23(ii) completes the proof. ∎

In order to compute a hypergraph Horn function that realizes $\mathcal{K}$ as
its key set, let us first consider potential implicate sets. The following
characterization shows that it can be checked in polynomial time whether a
given a subset is in $\mathcal{P}(\mathcal{K})$ or not.

######  Lemma 26.

A subset $I\subseteq V$ is a potential implicate set for a hypergraph
$\mathcal{K}$ if and only if

$\text{for every}\ K\in\mathcal{K}\ \text{and}\ u\in K\cap I\ \text{there
exists}\ K^{\prime}\in\mathcal{K}\text{ such that }K^{\prime}\subseteq(K\cup
I)-u.$ (7)

###### Proof.

We first assume that $I$ is not a potential implicate set for $\mathcal{K}$,
i.e., $\Phi_{\\{I\\}}(S)=0$ for some $S\in\mathcal{M}$. Then there exists a
variable $u$ such that $I\setminus S=\\{u\\}$. By the definition of
$\mathcal{M}=\mathcal{K}^{dc}$, there exists a set $K\in\mathcal{K}$ such that
$K-u\subseteq S$ and $u\in K$. For these $I$, $u$, and $K$, we have $(K\cup
I)-u\subseteq S$, which implies that no $K^{\prime}\in\mathcal{K}$ satisfies
the inclusion in (7) since $S\in\mathcal{K}^{dc}$.

To show the other direction, let us assume that no set in $\mathcal{K}$ is
contained in $(K\cup I)-u$ for some $K\in\mathcal{K}$ and $u\in K\cap I$. Then
by $\mathcal{M}=\mathcal{K}^{dc}$, some $S\in\mathcal{M}$ contains $(K\cup
I)-u$. This implies that $\Phi_{\\{I\\}}(S)=0$, since $I\setminus S=\\{u\\}$,
and thus the claim follows. ∎

By definition, condition (7) only deals with sets $K\in\mathcal{K}$ with
$K\cap I\not=\emptyset$. We note that condition (7) can be checked in
$O(|I|+\|\mathcal{K}\|^{2})$ time for a given set $I\subseteq V$, where
$\|\mathcal{K}\|=\sum_{K\in\mathcal{K}}|K|$.

######  Lemma 27.

Let $\mathcal{K}$ be a Sperner hypergraph. For any set $S\subseteq V$, there
exists a unique maximal potential implicate set contained in $S$.

###### Proof.

Since $\emptyset$ is a potential implicate set for $\mathcal{K}$, the lemma
follows by $\mathcal{P}(\mathcal{K})$ being closed under taking union. ∎

Let us now describe an algorithm for computing such potential implicate sets.
For a subset $S\subseteq V$, let $\mathbb{P}_{\mathcal{K}}(S)$ denote the
maximal potential implicate set for $\mathcal{K}$ included in $S$, and define

$\mathbb{P}^{1}_{\mathcal{K}}(S)~{}=~{}\\{u\in
S\mid(S+K)-u\in\mathcal{K}^{+}\mbox{ for all }K\in\mathcal{K}\mbox{ with }u\in
K\\}.$

By definition, a subset $I\subseteq V$ is a potential implicate set for
$\mathcal{K}$ if and only if
$I=\mathbb{P}_{\mathcal{K}}(I)=\mathbb{P}^{1}_{\mathcal{K}}(I)$.

Algorithm 3 Potential Implicate Set Computation

1:Input: A Sperner hypergraph $\mathcal{K}\subseteq 2^{V}$ and a set
$S\subseteq V$.

2:Output: A unique maximal potential implicate set for $\mathcal{K}$ contained
in $S$.

3:Initialize: $\mathbb{P}^{0}_{\mathcal{K}}(S)\coloneqq S$

4:for $k=1,2,\dots,|S|$ do

5: Compute
$\mathbb{P}^{k}_{\mathcal{K}}(S)=\mathbb{P}^{1}_{\mathcal{K}}(\mathbb{P}^{k-1}_{\mathcal{K}}(S))$

6:end for

7:return $\mathbb{P}_{\mathcal{K}}(S)=\mathbb{P}^{|S|}_{\mathcal{K}}(S)$

######  Lemma 28.

For a Sperner hypergraph $\mathcal{K}\subseteq 2^{V}$ and a set $S\subseteq
V$, the unique maximal potential implicate set for $\mathcal{K}$ contained in
$S$ can be obtained in $O(|S|{\cdot}\|\mathcal{K}\|^{2})$ time.

###### Proof.

Similarly to the operator $\mathbb{I}$, we have
$\mathbb{P}^{1}_{\mathcal{K}}(S)\subseteq S$, where equality holds if and only
if $S$ is a potential implicate set for $\mathcal{K}$. Furthermore,
$\mathbb{P}^{k}_{\mathcal{K}}(S)=\mathbb{P}^{k-1}_{\mathcal{K}}(S)$ implies
that $\mathbb{P}^{\ell}_{\mathcal{K}}(S)=\mathbb{P}^{k-1}_{\mathcal{K}}(S)$
for all $\ell\geq k-1$. Since $\emptyset$ is a potential implicate set, it
follows from Lemma 27 that Algorithm 3 outputs the unique maximal potential
implicate set for $\mathcal{K}$ contained in $S$.

As for the time complexity, let $A=S\setminus(\bigcup_{K\in\mathcal{K}}K)$ and
$B=S-A$, and consider the slightly different version of Algorithm 3 which is
obtained by first replacing $S$ by $B$ and then modifying the output by
$\mathbb{P}^{|B|}_{\mathcal{K}}(B)\cup A$. Then it is not difficult to see
that this modification still computes a desired potential implicate set and
each for-loop can be executed in $O(\|\mathcal{K}\|^{2})$ time. Therefore, in
total, the algorithm requires $O(|S|{\cdot}\|\mathcal{K}\|^{2})$ time, which
completes the proof. ∎

By Lemma 25, the key realization problem can be solved by generating all
potential implicate sets. However, in general, $|\mathcal{P}(\mathcal{K})|$
may be exponentially larger than $|\mathcal{K}|$ and $|V|$. Algorithm 4 has
similar characteristics to the hypergraph Horn recognition algorithm, and
constructs only polynomially many potential implicate sets for $\mathcal{K}$
that satisfy Lemma 23(ii).

Algorithm 4 Key Realization

1:Input: A Sperner hypergraph $\mathcal{K}\subseteq 2^{V}$.

2:Output: A hypergraph $\mathcal{H}\subseteq 2^{V}$ with
$\mathcal{K}(\Phi_{\mathcal{H}})=\mathcal{K}$ if $\mathcal{K}$ is realizable
as the key set of a hypergraph Horn function, and “No” otherwise.

3:Initialize: $\mathcal{H}\coloneqq\emptyset$

4:for each $J$ in $\mathcal{K}$ do

5: while $\mathbb{T}_{\Phi_{\mathcal{H}}}(J)\not=V$ do

6: $T\coloneqq\mathbb{T}_{\Phi_{\mathcal{H}}}(J)$

7: for each $v\in V\setminus T$ do

8: if $v\in\mathbb{P}_{\mathcal{K}}(T+v)$ then

9: $\mathcal{H}\coloneqq\mathcal{H}\cup\\{\mathbb{P}_{\mathcal{K}}(T+v)\\}$

10: end if

11: end for

12: if $T=\mathbb{T}_{\Phi_{\mathcal{H}}}(J)$ then

13: return “No”

14: end if

15: end while

16:end for

17:return $\mathcal{H}$

######  Theorem 29.

For a Sperner hypergraph $\mathcal{K}\subseteq 2^{V}$, we can decide in
$O(|V|^{3}{\cdot}|\mathcal{K}|{\cdot}\|\mathcal{K}\|^{2})$ time if
$\mathcal{K}$ is realizable as the key set of a hypergraph Horn function, and
if yes, construct a hypergraph $\mathcal{H}\subseteq 2^{V}$ such that
$\mathcal{K}=\mathcal{K}(\Phi_{\mathcal{H}})$ and
$|\mathcal{H}|\leq|V|{\cdot}|\mathcal{K}|$.

###### Proof.

Algorithm 4 satisfies the statement of the theorem; the proof is analogous to
that of Theorem 22. ∎

###  5.4 Implicate set generation

Finally, we consider the problem of generating implicate sets of a given
definite Horn CNF. Note that a definite Horn function might have exponentially
many implicate sets in the size of its CNF representation (see e.g., Example
7). It is customary to measure the complexity of such generation problems in
both the size of the input and output, see e.g., [13, 21]. A generation
algorithm is called _polynomial delay_ if the time intervals between the start
and the first output, between consecutive outputs, and between the last output
and the halt are all bounded by a polynomial in the input size.

In order to have such an algorithm for generating implicate sets, we apply the
so-called flashlight search discussed e.g., in [4], where flashlight search
explores the space of all possible solutions by checking if the current
partial solution can be extended to a complete solution. More precisely, our
algorithm solves the following problem as a subroutine.

Implicate Set Extension($\Psi,X,Y$)
Input: A definite Horn CNF $\Psi$ and disjoint subsets $X$ and $Y$ in $V$.
Question: Does $\Psi$ has an implicate set $I$ such that $X\subseteq I$ and
$I\cap Y=\emptyset$?

######  Lemma 30.

Let $X$ and $Y$ be disjoint subsets in $V$, and let $\Psi$ be a definite Horn
CNF. Then $\Psi$ has an implicate set $I$ such that $X\subseteq Y$ and $I\cap
Y=\emptyset$ if and only if $\mathbb{I}_{\Psi}(V\setminus Y)\supseteq X$.
Hence Implicate Set Extension$(\Psi,X,Y)$ can be solved in
$O(|V|^{2}{\cdot}\|\Psi\|)$ time.

###### Proof.

The claim follows by the fact that $\mathbb{I}_{h}(V\setminus Y)$ is the
unique maximal implicate set of $h$ that is disjoint from $Y$. The complexity
of Problem Implicate Set Extension$(\Psi,X,Y)$ follows by Theorem 21. ∎

Therefore we get the following theorem.

######  Theorem 31.

For a given definite Horn CNF $\Psi$, we can generate implicate sets of $\Psi$
in polynomial delay.

###### Proof.

The claim follows from Lemma 30 and the flashlight search, see e.g., [4]. ∎

Note that $\mathcal{I}(\Psi)$ is closed under union and
$\mathbb{I}_{h}(V\setminus Y)$ is the unique maximal implicate set of $h$ that
is disjoint from $Y$. Hence, by utilizing such properties, implicate sets can
be generated faster than the standard flashlight search, although we do not
discuss it in this paper.

###  5.5 Checking implicate-duality

Deciding the computational complexity of checking implicate-duality remains an
intriguing open question. In this problem, we are given two definite Horn CNFs
$\Psi$ and $\Gamma$, and the goal is to decide if $\Psi=\Gamma^{i}$. The
problem is open even when $\Psi=\Gamma$, that is, one would like to check if a
definite Horn CNF $\Psi$ represents a self $i$-dual Horn function or not. We
call a definite Horn function $h$ self $i$-dual if $h^{i}=h$. We know by Lemma
16 that $h$ must be hypergraph Horn in this case.

As initial steps toward understanding these problems, we show that
$\Psi\geq\Gamma^{i}$ can be checked in polynomial time and that the problem of
deciding $\Psi=\Psi^{i}$ belongs to co-NP.

######  Theorem 32.

Let $\Psi$ and $\Gamma$ be two definite Horn CNFs. Then $\Psi\geq\Gamma^{i}$
can be checked in $O(|V|^{2}{\cdot}|\Psi|{\cdot}\|\Gamma\|)$ time.

###### Proof.

Note that $\Psi\not\geq\Gamma^{i}$ holds if and only if there exists a false
set $F$ of $\Psi$ such that $V\setminus F$ is an implicate set of $\Gamma$.
This is equivalent to the existence of a clause $A\to v$ in $\Psi$ such that
the output of Implicate Set Extension($\Gamma,\\{v\\},A$) is “Yes”. Therefore,
by Lemma 30, $\Psi\geq\Gamma^{i}$ can be checked in
$O(|V|^{2}{\cdot}|\Psi|{\cdot}\|\Gamma\|)$ time. ∎

We show next that self implicate duality of $h$ can be characterized as a
property of its complete implicate set $\mathcal{I}(h)$. This characterization
then allows us to show that the problem of deciding $h=h^{i}$ for a function
$h$ represented by definite Horn CNF belongs to co-NP.

######  Theorem 33.

A definite Horn function $h$ is self $i$-dual if the hypergraph
$\mathcal{H}=\mathcal{I}(h)$ satisfies the following properties.

  1. (a)

$|H\cap H^{\prime}|\neq 1$ for all $H,H^{\prime}\in\mathcal{H}$.

  2. (b)

$\mathcal{H}$ is a maximal subfamily of $2^{V}$ with respect to property (a).

Let us remark that since $H=H^{\prime}$ is possible in (a), $|H|\geq 2$
follows for all $H\in\mathcal{I}(h)$ for a self $i$-dual Horn function $h$.

Before proving this theorem, we need a technical lemma that maybe of interest
on its own.

######  Lemma 34.

Given a hypergraph $\mathcal{H}\subseteq 2^{V}$, we have
$\Phi_{\mathcal{H}}\geq\Phi^{i}_{\mathcal{H}}$ if and only if $\mathcal{H}$
satisfies condition (a) of Theorem 33.

###### Proof.

Let us introduce $h=\Phi_{\mathcal{H}}$. By definition
$\mathcal{T}(h^{i})=\mathcal{I}(h)^{c}$. Thus we have
$\mathcal{T}(h^{i})\subseteq\mathcal{T}(h)$ if and only if
$\mathcal{I}(h)^{c}\subseteq\mathcal{T}(h)$. By Lemma 9 we have that a subset
$S\subseteq V$ is a true set of $h$ if and only if there exists no implicate
set $I\in\mathcal{I}(h)$ such that $|I\setminus S|=1$. Thus, we have
$\mathcal{I}(h)^{c}\subseteq\mathcal{T}(h)$ if and only if for all
$S\in\mathcal{I}(h)^{c}$ and $I\in\mathcal{I}(h)$ we have $|I\setminus S|\neq
1$, or equivalently, for all $I,I^{\prime}\in\mathcal{I}(h)$ we have $|I\cap
I^{\prime}|\neq 1$.

We claim that this latter condition holds if and only if $\mathcal{H}$
satisfies property (a) of Theorem 33. Since
$\mathcal{H}\subseteq\mathcal{I}(h)$, the necessity of condition (a) is
implied. For the sufficiency, assume for a contradiction that there exist
implicate sets $I,I^{\prime}\in\mathcal{I}(h)$ such that $|I\cap
I^{\prime}|=1$, i.e., $|I\setminus(V\setminus I^{\prime})|=1$. This relation
then implies that $\mathbb{T}_{h}(V\setminus I^{\prime})\neq(V\setminus
I^{\prime})$. Since $\mathbb{T}_{h}=\mathbb{T}_{\Phi_{\mathcal{H}}}$, there
exists a hyperedge $H\in\mathcal{H}$ such that $|H\setminus(V\setminus
I^{\prime})|=1$, or equivalently, $|H\cap I^{\prime}|=1$. We can write this
equivalently, as $|I^{\prime}\setminus(V\setminus H)|=1$ from which
$\mathbb{T}_{h}(V\setminus H)\neq(V\setminus H)$ follows, implying the
existence of an $H^{\prime}\in\mathcal{H}$ such that
$|H^{\prime}\setminus(V\setminus H)|=1$. Thus these $H$ and $H^{\prime}$ would
violate condition (a), completing the sufficiency. ∎

###### Proof of Theorem 33.

Since $\Phi_{\mathcal{H}}\geq\Phi^{i}_{\mathcal{H}}$ must hold for
self-$i$-dual functions, property (a) of Theorem 33 is necessary by Lemma 34.
Assume first that $\mathcal{H}$ satisfies that
$\Phi_{\mathcal{H}}>\Phi_{\mathcal{H}}^{i}$. Then we have a subset $S\subseteq
V$ such that $\Phi_{\mathcal{H}}^{i}(S)=0$ and $\Phi_{\mathcal{H}}(S)=1$. The
equality $\Phi_{\mathcal{H}}^{i}(S)=0$ implies $(V\setminus
S)\notin\mathcal{H}$ by the definition of $i$-duality. The equality
$\Phi_{\mathcal{H}}(S)=1$ implies that for all $H\in\mathcal{H}$ we have
$|H\setminus S|\neq 1$, or equivalently that $|H\cap(V\setminus S)|\neq 1$.
This implies that $\mathcal{H}\cup\\{V\setminus S\\}$ satisfies (b), that is,
$\mathcal{H}$ is not maximal with respect to (a).

For the converse direction, assume that $\mathcal{H}$ satisfies (a), but not
maximal with respect to (a), i.e., there exists a subset $S\subseteq V$ such
that $S\notin\mathcal{H}$ and $|S\cap H|\neq 1$ for all $H\in\mathcal{H}$. The
latter condition implies $\Phi_{\mathcal{H}}(V\setminus S)=1$ by Lemma 9. On
the other hand, since $\mathcal{H}=\mathcal{I}(h)$, we have
$\mathcal{T}(\Phi_{\mathcal{H}}^{i})=\mathcal{H}^{c}$. Thus
$S\notin\mathcal{H}$ implies that $\Phi_{\mathcal{H}}^{i}(V\setminus S)=0$,
which concludes that $\Phi_{\mathcal{H}}>\Phi^{i}_{\mathcal{H}}$. ∎

The characterization given above is analogous to the characterization of
monotone duality, see [3] for further details.

######  Corollary 35.

The decision problem $h=h^{i}$ for functions $h$ represented by definite Horn
CNFs belongs to co-NP.

###### Proof.

To prove $h\neq h^{i}$ it is enough by Theorem 33 to present either two
implicate sets $I,I^{\prime}\in\mathcal{I}(h)$ such that $|I\cap
I^{\prime}|=1$ or a subset $S\subseteq V$ such that $S\notin\mathcal{I}(h)$
and $|S\cap I|\neq 1$ for all $I\in\mathcal{I}(h)$.

In the first case we can test memberships $I,I^{\prime}\in\mathcal{I}(h)$ in
polynomial time using any Horn CNF representation of $h$.

In the second case we can also test $S\notin\mathcal{I}(h)$ in polynomial time
using the Horn CNF representing $h$. Furthermore, we can test for all $v\in S$
if $v\in I=\mathbb{I}_{h}((V\setminus S)+v)$ in polynomial time by Theorem 21.
If the answer is “No” for all $v\in S$, then we must have $|S\cap I|\neq 1$
for all $I\in\mathcal{I}(h)$. ∎

##  6 Conclusions and open problems

In the present paper, we introduced the notion of hypergraph Horn functions, a
subclass of Boolean functions with rich structural properties that generalizes
matroids and equivalence relations. We gave several equivalent
characterizations of hypergraph Horn functions, introduced a new duality that
generalizes matroid duality, and studied algorithmic problems including the
recognition problem, key realization, and implicate set generation.

We conclude our paper with listing a few open problems. Assume that $\Psi$ and
$\Gamma$ are definite Horn CNFs, and all questions are about polynomial time
computability.

######  Question 1.

Does $\Psi\leq\Gamma^{i}$ hold?

######  Question 2.

Does $\Psi=\Psi^{i}$ hold?

######  Question 3.

Is there a Sperner hypergraph $\mathcal{H}\subseteq 2^{V}$ such that
$\Psi=\Phi_{\mathcal{H}}$?

#### Acknowledgements.

This work was supported by the Research Institute for Mathematical Sciences,
an International Joint Usage/Research Center located in Kyoto University. The
first author was supported by the Lendület Program of the Hungarian Academy of
Sciences – grant number LP2021-1/2021 and by the Hungarian National Research,
Development and Innovation Office – NKFIH, grant number FK128673. The third
author was supported by JSPS KAKENHI Grant Numbers JP20H05967, JP19K22841, and
JP20H00609.

## References

  * [1] K. V. Adaricheva, G. F. Italiano, H. K. Büning, and G. Turán.  Horn formulas, directed hypergraphs, lattices and closure systems: related formalisms and applications (Dagstuhl Seminar 14201).  Dagstuhl Reports, 4(5):1–26, 2014.
  * [2] K. Bérczi, E. Boros, and K. Makino.  Matroid Horn functions.  arXiv preprint arXiv:2301.06642, 2023.
  * [3] J. C. Bioch and T. Ibaraki.  Complexity of identification and dualization of positive boolean functions.  Information and Computation, 123(1):50–63, 1995.
  * [4] E. Boros, V. Gurvich, L. Khachiyan, and K. Makino.  Dual-bounded generating problems: Partial and multiple transversals of a hypergraph.  SIAM Journal on Computing, 30(6):2036–2050, 2001.
  * [5] A. Chandra, H. Lewis, and J. Makowsky.  Embedded implicational dependencies and their inference problem.  In ACM STOCS, pages 342–354, 1981.
  * [6] C. Chang and R. Lee.  Symbolic Logic and Mechanical Theorem Proving.  Academic Press, New York, 1973.
  * [7] Y. Crama and P. L. Hammer.  Boolean functions: Theory, algorithms, and applications.  Cambridge University Press, 2011.
  * [8] R. Fagin.  Horn clauses and database dependencies.  J. Assoc. Comput. Machinery, 29:952–985, 1982.
  * [9] W. Hodges.  Logical features of Horn clauses, volume 1 of Handbook of Logic in Artificial Intelligence and Logic Programming, pages 449–503.  Oxford University Press, 1993.
  * [10] A. Horn.  On sentences which are true of direct unions of algebras.  Journal of Symbolic Logic, 16:14–21, 1951.
  * [11] A. Itai and J. Makowsky.  Unification as a complexity measure for logic programming.  Journal of Logic Programming, pages 105–117, 1987.
  * [12] R. Khardon and D. Roth.  Reasoning with models.  Artificial Intelligence, 87:187–213, 1996.
  * [13] E. L. Lawler, J. K. Lenstra, and A. H. G. R. Kan.  Generating all maximal independent sets: Np-hardness and polynomial-time algorithms.  SIAM Journal on Computing, 9:558–565, 1980.
  * [14] D. Maier.  The theory of relational databases.  Computer Science Press, Rockville, MD, 1983.
  * [15] D. Maier and D. Warren.  Computing with Logic: Logic Programming with PROLOG.  Benjamin/Cummings Publ. Co.,, Menlo Park, CA, 1988.
  * [16] J. Makowsky.  Why Horn formulas matter in computer science: initial structures and generic examples.  J. Comput. System Sci., 34:266–292, 1987.
  * [17] J. McKinsey.  The decision problem for some classes of sentences without classifiers.  Journal of Symbolic Logic, 8:61–76, 1943.
  * [18] H. Nishimura and S. Kuroda.  A Lost Mathematician, Takeo Nakasawa: The Forgotten Father of Matroid Theory.  Springer Science & Business Media, 2009.
  * [19] Y. Sagiv, C. Delobel, D. Parker, and R. Fagin.  An equivalence between relational database dependencies and a fragment of propositional logic.  Journal of the ACM, 28(3):435–453, 1981.
  * [20] W. Tutte.  Introduction to the theory of matroids, volume Modern Analytic and Computational Methods in Science and Mathematics, vol. 37.  American Elsevier Publishing Company, New York, 1971.
  * [21] L. Valiant.  The complexity of enumeration and reliability problems.  SIAM Journal on Computing, 8:410–421, 1979.
  * [22] D. J. A. Welsh.  Matroid Theory, volume L.M.S. Monographs, vol. 8.  Academic Press, 1976.
  * [23] H. Whitney.  On the abstract properties of linear dependence.  In Hassler Whitney Collected Papers, pages 147–171. Springer, 1992\.