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 ;).
