Compressing boolean formulae Syntax

~ not
/\ and
\/ or
t true
f false
P, Q, FISH, etc: variables

(Operators are given in order of precedence)

Introduction

Some boolean formulae can be changed to different forms to make them shorter. For example, the formula

~(~P /\ ~Q)


can be changed to the shorter form

P\/Q


while the formula

P \/ ~P


can be changed to the shorter form

t




Challenge

In this challenge, you are required to write a program that, given any boolean formula using only /\, \/, ~, t, f, parentheses, boolean variables (in uppercase), and whitespace, outputs a shortest form (since there may be more than one shortest form) in characters of that expression which is equivalent for all assignments of the variables. Shortest code (in any language) wins. I/O can be done in any reasonable manner.

Also, since answers are difficult to verify, it would be helpful (but isn't required) to include a brief explanation of how the code works.
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)
...