Compressing boolean formulae
Python 616
Not particularly efficient, but works in reasonable time for inputs whose results are around 5 or 6 characters. To check a string to see if it matches, it loops through every possible combination of truth/false values for all the variables and makes sure each one agrees. Using this it checks every possible string comprised of the relevant characters (not even necessarily a syntactically correct one).
It actually will print every equivalent expression (of every size) and does not actually ever terminate.
Code:
c=['t','f'];o=['1 ','0 ']
def e(s,v):
 for k in v:s=s.replace(k,v[k])
 return eval(s)
def z(t,p='~/\\() '):
 w=[]
 if p=='':return[t]*(t not in['']+c)
 for s in t.split(p[0]):w.extend(z(s,p[1:]))
 w.sort(key=lambda v:-len(v));return w
def m(v):
 l=list('~\\/()')+v
 for s in l:yield s
 for r in m(v):
    for s in l:yield s+r
def n(x):
 if x&lt;1:yield []
 else:
    for l in n(x-1):
     for b in o:yield[b]+l
t=raw_input();v=z(t)+c;l=len(v)
for s in m(v):
 g=1
 for y in n(l):
    y[-2:]=o;d=dict(zip(v+['/\\','\\/','~'],y+['and ','or ','not ']))
    try:
     if e(s,d)!=e(t,d):g=0
    except:g=0
 if g:print s

Input/Ouput:
&gt; ~(~P /\ ~Q)
Q\/P
P\/Q
...

&gt; P /\ ~P
f
~t
...

&gt; (P \/ Q) /\ P
P
(P)
...