Python, 609 chars
for f,a in M:U[f]=0
s=lambda x:x if x else''
while all(f-N for f,a in sum(M,)):
for f,a in M[L-1]:
for i in range((L+1)/2):
for f,a in M[L-1-i]:
A=max(len(x)for x in a)
for g,b in M[i]:
d=[u'├'+u'─'*(A-1)+u'┐']+map(lambda x,y:s(x)+' '*(A-len(s(x)))+s(y),a,b)
print '\n'.join([a for f,a in sum(M,)if f==N])
Functions are specified by listing their truth table values as a binary input. The first bit is the output for ABCD=0000, the second bit is the output for ABCD=0001, and the last bit is the output for ABCD=1111. Does a brute-forceish search for the minimal circuit that computes the function. It never shares subcomputations, so it will always be a tree.
M[L] contains a list of functions computable with
L gates, represented as a pair (function,array of strings) where the function is computable with the circuit drawn by the strings when printed one per line. To make sure we get the minimum circuit, we run in increasing
L order and
U keeps track of which functions we've already found a circuit for.
$ echo 0b1110000000000111 | ./gates.py
ᗣ ᗝ A
ᗣ Aᗣ B
ᗝ B CD
I used some awesome Unified Canadian Aboriginal syllabics unicode glyphs for the gates, and box drawing glyphs for the connections. Yes, you heard right: *Unified Canadian Aboriginal*! If they don't display correctly in your browser, upgrade your unicode-fu. (They look awesome in my terminal; they are a bit misaligned on stackexchange.)
Depending on the input, could be fast or could take up to ~1/2 hour.
You might need to add something like
# -*- coding: utf-8 -*- to the start of the program if running as a script.