Compactando fórmulas booleanas

16

Sintaxe

~não
/\e
\/ou
tverdadeiros
ffalsos
P, Q, FISH, etc: variáveis

(Os operadores são dados em ordem de precedência)

Introdução

Algumas fórmulas booleanas podem ser alteradas para formas diferentes para torná-las mais curtas. Por exemplo, a fórmula

~(~P /\ ~Q)

pode ser alterado para a forma mais curta

P\/Q

enquanto a fórmula

P \/ ~P

pode ser alterado para a forma mais curta

t

Desafio

Neste desafio, você é obrigado a escrever um programa que, dado qualquer fórmula booleana usando apenas /\, \/, ~, t, f, parênteses variáveis booleanas (em letras maiúsculas), e espaços em branco, produz uma forma mais curta (uma vez que pode haver mais de uma forma mais curta ) em caracteres dessa expressão que é equivalente a todas as atribuições das variáveis. O código mais curto (em qualquer idioma) vence. A E / S pode ser feita de qualquer maneira razoável.

Além disso, como as respostas são difíceis de verificar, seria útil (mas não obrigatório) incluir uma breve explicação de como o código funciona.

Lily Chung
fonte
Na seção "Desafio", você não menciona nenhum espaço em branco, mas seus exemplos os incluem. Devo lidar com eles?
Victor Stafusa
4
Penso que o argumento de Florent é que é um problema difícil de resolver em geral, sem falar no golfe. Entre outras coisas, o analisador precisará ser capaz de determinar se duas fórmulas arbitrárias têm as mesmas condições de verdade. Reduzir p ^ ~ p é fácil o suficiente se p for atômico, mas e quanto a ((A ^ B) v (A ^ C)) ^ ~ (A ^ (BvC))? Eu acho que é um problema interessante e estou curioso para ver algumas respostas. Mas se você quiser soluções curtas, o problema pode ser mais favorável ao golfe por A. usando a notação de prefixo e B. fornecendo uma lista das reduções necessárias.
dfernig
11
Eu tenho uma solução válida (com golf) em mais de 5000 caracteres. Isso é ridículo ... É composto de um tokenizador, um analisador AST, um reescritor AST e um gerador de expressão.
Florent
11
Mathematica pode fazê-lo em uma chamada de função ( BooleanMinimize)
Florent
11
Para o registro, eu tenho uma solução de 498 caracteres agora, cujo sha256sum é b9c98d088b78c30bb2108008a064a7b95722a4694d90ddad94a025c2eb4ed30a. Postarei o código real em uma data posterior, pois não quero sufocar a criatividade.
Lily Chung

Respostas:

2

Ah, claro, eu esqueci de realmente postar minha resposta. Ele usa essencialmente a mesma abordagem que a resposta do KSab usa, mas imprime apenas a expressão válida mais curta.

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)

Observe que o hash que eu calculei anteriormente incluía a nova linha à direita e foi antes de jogar def e(x): returnparae=lambda x:

Lily Chung
fonte
1

Python 616

Não é particularmente eficiente, mas funciona em tempo razoável para entradas cujos resultados estão em torno de 5 ou 6 caracteres. Para verificar uma string para ver se ela corresponde, ela percorre todas as combinações possíveis de valores verdadeiros / falsos para todas as variáveis ​​e garante que cada uma concorda. Usando isso, ele verifica todas as sequências possíveis compostas pelos caracteres relevantes (nem mesmo necessariamente as sintaticamente corretas).

Na verdade, ele imprime todas as expressões equivalentes (de todos os tamanhos) e 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 / Saída:

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

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

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