# Resolution trees in latex

I would like to draw a resolution tree such as this.

I have already seen this post and I could make trees like the example shown in that. However, I do not know how to point to a child node from multiple parent nodes using the qtree style. This is my MWE.

\documentclass[tikz, margin=10pt]{standalone}
\usepackage{tikz-qtree}
\usepackage{latexsym}

\begin{document}
\begin{tikzpicture}[grow'=up]
\Tree [.$\Box$ [.${\{m\}}$ [.${\{a,m\}}$ ${\{3,4\}}$ ${\{5,6\}}$ ]
[.${\{ \neg a\}}$ ${\{8\}}$ ${\{7, \neg a\}}$ ] ]
[ [.${\{\neg m\}}$ ${\{ \neg c\}}$ ${\{c, \neg m\}}$ ] ] ]
\end{tikzpicture}
\end{document}


Multiple parents to single child is done manually by adding edges to the nodes. So you build your tree as usual, and assign (easy to remember) node names to each or only to those nodes you need.

After the tree is done, inside the tikzpicture you can then draw the extra lines.

This is possible both with Tikz-qtree and with Tikz trees. I made a random edge just to show you how it's done (coloured in red). Feel free to modify as you need it.

# Tikz-qtree

## Code

\documentclass[tikz, margin=10pt]{standalone}
\usepackage{tikz-qtree}
\usepackage{latexsym}

\begin{document}
\begin{tikzpicture}[grow'=up]
\Tree [.$\Box$ [. \node(m1){${\{m\}}$}; [.${\{a,m\}}$ ${\{3,4\}}$ ${\{5,6\}}$ ]
[.${\{ \neg a\}}$ ${\{8\}}$ ${\{7, \neg a\}}$ ] ]
[ [.\node(m2){${\{\neg m\}}$}; ${\{ \neg c\}}$ ${\{c, \neg m\}}$ ] ] ]

\draw[red] (m1.north) -- (m2.south);
\end{tikzpicture}
\end{document}


# Tikz trees

## Code

\documentclass[tikz, margin=10pt]{standalone}
\usetikzlibrary{trees}

\tikzset{
every node={circle,draw}
}

\begin{document}
\begin{tikzpicture}[level distance=1.5cm,
level 1/.style={sibling distance=3.5cm},
level 2/.style={sibling distance=1cm}]

\node (Root) {1}
child {
node (n2) {2}
child { node (n4) {4} }
child { node (n5) {5} }
}
child {
node (n3) {3}
child { node (n6) {6} }
child { node (n7) {7} }
};

\draw (n2) -- (n6);
\draw (n3) -- (n5);
\end{tikzpicture}
\end{document}

• I have posted my MWE. Is it possible to use your solution when I use the tikz qtree? – positron May 23 '15 at 16:02
• @positron Yes you can. I'll edit the answer. – Alenanno May 23 '15 at 16:06
• @positron Done. Hope it helps. – Alenanno May 23 '15 at 16:15

forest is a powerful option for drawing trees of all kinds. Here is your original example in forest. Note that the curly brackets are added automatically as appropriate and that all nodes are typeset in maths mode so that $...$ need not be used.

\documentclass[tikz, border=10pt, multi]{standalone}
\usepackage{amssymb,forest}

\begin{document}
\begin{forest}
for tree={
grow'=90,
parent anchor=north,
math content,
before typesetting nodes={
if level=0{}{
if content={}{
shape=coordinate
}{
content/.wrap value={\{#1\}},
},
},
}
}
[\Box
[{m}
[{a,m}
[{3,4}]
[{5,6}]
]
[{\neg a}
[{8}]
[{7, \neg a}]
]
]
[
[{\neg m}
[{\neg c}]
[{c, \neg m}]
]
]
]
\end{forest}

\end{document}


There are several ways of drawing additional lines from parents to the children of other nodes.

The simplest is probably just to name the relevant nodes and draw the required lines after the tree is fully specified. For example:

...
[\Box
[{m}
[{a,m}
[{3,4}]
[{5,6}]
]
[{\neg a}, name=not a
[{8}]
[{7, \neg a}]
]
]
[
[{\neg m}
[{\neg c}, name=not c]
[{c, \neg m}, name=c not m]
]
]
]
\draw [red] (not a.north) edge (not c.south) -- (c not m.south);
...


Alternatively, the same output can be produced if the TikZ commands are specified within the tree. In this case, we don't need to name the node where the commands are specified because forest assumes that the current node is meant if not otherwise stated.

  [\Box
[{m}
[{a,m}
[{3,4}]
[{5,6}]
]
[{\neg a}, tikz={\draw [red] (.north) edge (not c.south) -- (c not m.south);}
[{8}]
[{7, \neg a}]
]
]
[
[{\neg m}
[{\neg c}, name=not c]
[{c, \neg m}, name=c not m]
]
]
]


If we wanted to, we could even refer to the other two nodes (not c and c not m) relative to the node hosting the TikZ commands and avoid naming any nodes explicitly at all. However, that would just make the tree less readable in this case, I think.

The image shown in your question is a bit more complicated because of the alignments to the west of the nodes. However, you might try something like this:

\documentclass[tikz, border=10pt, multi]{standalone}
\usepackage{amssymb,forest}

\begin{document}
\begin{forest}
for tree={
grow'=90,
parent anchor=north,
child anchor=south,
math content,
inner xsep=0pt,
anchor=west,
before typesetting nodes={
if level=0{}{
if content={}{
shape=coordinate
}{
content/.wrap value={\{#1\}},
},
},
},
if level=0{
before drawing tree={x=+.5em},
for children={
if n=1{
calign with current,
edge path={
\noexpand\path [draw, \forestoption{edge}] (!u.north west) +(.5em,0) coordinate (a) -- (a |- .child anchor)\forestoption{edge label};
}
}{
edge path={
\noexpand\path [draw, \forestoption{edge}] (!u.north west) +(.5em,0) -- (.child anchor)\forestoption{edge label};
}
},
}
}{
for descendants={
for parent={
for children={
if n=1{
calign with current,
edge path={
\noexpand\path [draw, \forestoption{edge}] (!u.north west) +(1em,0) coordinate (a) -- (a |- .child anchor)\forestoption{edge label};
}
}{
edge path={
\noexpand\path [draw, \forestoption{edge}] (!u.north west) +(1em,0) -- (.child anchor)\forestoption{edge label};
}
},
}
}
}
},
if n children=0{tier=terminus}{}
}
[\Box, tikz={\draw ([xshift=.5em].north west) -- (q.south);}
[{\neg Q}
[{\neg Q, \neg P}]
[P
[{P, \neg R}
[{P, \neg Q, \neg R}, tikz={\draw ([xshift=1em].north west) -- (s.south);}
[{P, \neg Q, \neg R, \neg S}]
]
[Q, tier=t, name=q, tikz={\draw ([xshift=1em].north west) -- (s.south);}
[{Q, \neg S}]
]
]
[R, tier=t
[{R, \neg S}]
[S, name=s]
]
]
]
]
\end{forest}

\end{document}


Various aspects of forest are used to achieve this output, including the different stages of drawing the tree and the ability to specify different alignments for different nodes based on various conditions. The forest manual has all the glorious details ;).