\cup \{\neg \hat{b}\}) 
- MN(S \cup \{\neg \hat{b}\}) \neq \emptyset$. Hence $\hat{b}$ is false in all models of $MOD(S \cup tk(S))$ and so inconsistent with $S \cup tk(S)$ (or with $S \cup \{l\}$, respectively). Thus typical kernel is the largest set of atoms necessarily consistent with any $S$. $\Box$

The following algorithm checks for $S$ presented in a propositional CNF whether a typical atom $\hat{a}$ is its kernel atom.

\[alg-neigh\] (Clauses $c \in S$ are sets of literals; $\hat{a}$ is a typical atom of $S$).\
1. Count $N_1 = |MOD(S \cup \{\neg\hat{a}\})|$;\
2. Compute $S_1 = \{c - \{\neg\hat{a}\}\; |\; c \in S \; \wedge \;\hat{a} 
\not\in c\}$;\
3. Compute $S_2 = \{c - \{\hat{a}\} \;|\; c \in S \;\wedge \; \neg\hat{a} 
\not\in c\}$;\
4. Count $N_2 = |MOD(S_1 \cup S_2)|$;\
5. If $N_1 = N_2$ return “Yes, $\hat{a}$ is a kernel atom of $S$” else return “No”. $\Box$

There is a bijection between $MOD(S_1)$ and $MOS(S \cup \{\hat{a}\})$, and between $MOD(S_2)$ and $MOD(S \cup \{\neg \hat{a}\})$ such that to every model $m' \in MOD(S_1)$\
corresponds a model $(m' \cup \{\hat{a}\}) \in MOD(S \cup \{\hat{a}\})$ and to every model\
$m'' \in MOD(S_2)$ corresponds a model $(m'' \cup \{\neg \hat{a}\}) \in 