Sintaxis

~No
/\y
\/o
tverdaderos
ffalsos
P, Q, FISH, etc: Variables

(Los operadores se dan en orden de precedencia)

Introducción

Algunas fórmulas booleanas se pueden cambiar a diferentes formas para acortarlas. Por ejemplo, la fórmula

~(~P /\ ~Q)

se puede cambiar a la forma más corta

P\/Q

mientras que la fórmula

P \/ ~P

se puede cambiar a la forma más corta

t

Desafío

En este desafío, se le requiere para escribir un programa que, dado cualquier fórmula booleana utilizando únicamente /\, \/, ~, t, f, paréntesis variables booleanas (en mayúsculas), y un espacio en blanco, da salida a una forma más corta (ya que puede haber más de una forma más corta ) en caracteres de esa expresión que es equivalente para todas las asignaciones de las variables. El código más corto (en cualquier idioma) gana. La E / S se puede hacer de cualquier manera razonable.

Además, dado que las respuestas son difíciles de verificar, sería útil (pero no es obligatorio) incluir una breve explicación de cómo funciona el código.

Ah, claro, olvidé publicar mi respuesta. Utiliza esencialmente el mismo enfoque que utiliza la respuesta de KSab , pero imprime solo la expresión válida más corta.

Python3, 493

e=lambda x:eval(x.replace('\\/','+').replace('/\\','%'),None,w)
class V(int):
 def __add__(s,o):return V(s|o)
 def __mod__(s,o):return V(s*o)
 def __invert__(s):return V(-s+1)
import re;from itertools import product as P;t=V(1);f=V(0);i=input();v=re.findall('[A-Z]+',i)
for k in range(1,len(i)):
 for m in P(''.join(v)+'~/\\tf',repeat=k):
  m=''.join(m)
  try:
   for d in P((V(0),V(1)),repeat=len(v)):
    w=dict(zip(v,d))
    if e(m)!=e(i):raise
  except:continue
  print(m);exit()
print(i)

Tenga en cuenta que el hash computé anterior incluido el salto de línea final y era antes Jugamos al golf def e(x): returnae=lambda x:

Python 616

No es particularmente eficiente, pero funciona en un tiempo razonable para entradas cuyos resultados son de alrededor de 5 o 6 caracteres. Para verificar una cadena para ver si coincide, recorre todas las combinaciones posibles de valores de verdad / falso para todas las variables y se asegura de que cada una esté de acuerdo. Con esto, verifica cada cadena posible compuesta por los caracteres relevantes (ni siquiera necesariamente uno sintácticamente correcto).

En realidad imprimirá cada expresión equivalente (de cada tamaño) y en realidad nunca termina.

Código:

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<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

Entrada / salida:

> ~(~P /\ ~Q)
Q\/P
P\/Q
...

> P /\ ~P
f
~t
...

> (P \/ Q) /\ P
P
(P)
...