Сжатие логических формул

17

Синтаксис

~не
/\и
\/или
tистинные
fложные
P, Q, FISHи т.д.: переменные

(Операторы даны в порядке приоритета)

Вступление

Некоторые логические формулы могут быть изменены в различные формы, чтобы сделать их короче. Например, формула

~(~P /\ ~Q)

можно изменить на более короткую форму

P\/Q

в то время как формула

P \/ ~P

можно изменить на более короткую форму

t

Вызов

В этих проблемах, вы должны написать программу , которая при любом булева формулы с использованием только /\, \/, ~, t, f, скобок, логические переменных (в верхнем регистре), и пробелов, выводит короткую форму (поскольку может быть больше одного кратчайшей формой ) в символах того выражения, которое эквивалентно для всех назначений переменных. Самый короткий код (на любом языке) выигрывает. Ввод / вывод может быть выполнен любым разумным способом.

Кроме того, поскольку ответы трудно проверить, было бы полезно (но не обязательно) включить краткое объяснение того, как работает код.

Лили Чунг
источник
В разделе «Вызов» вы не упоминаете никаких пробелов, но в ваших примерах они есть. Должен ли я справиться с ними?
Виктор Стафуса
4
Я думаю, что точка зрения Флорента в том, что это сложная проблема, в общем, не говоря уже о гольфе. Помимо прочего, парсер должен уметь определять, имеют ли две произвольные формулы одинаковые условия истинности. Уменьшение p ^ ~ p достаточно легко, если p атомарно, но как насчет ((A ^ B) v (A ^ C)) ^ ~ (A ^ (BvC))? Я думаю, что это крутая проблема, и мне любопытно увидеть некоторые ответы. Но если вам нужны короткие решения, проблему можно сделать более подходящей для игры в гольф, используя A. с использованием префиксной записи и B. предоставляя список требуемых сокращений.
dfernig
1
У меня есть действующее (гольфовое) решение в более чем 5000 символов. Это смешно ... Он состоит из токенизатора, AST-парсера, AST-переписателя и генератора выражений.
Флоран
1
Mathematica может сделать это одним вызовом функции ( BooleanMinimize)
Florent
1
Для справки, у меня есть решение из 498 символов, чья сумма sha256 b9c98d088b78c30bb2108008a064a7b95722a4694d90ddad94a025c2eb4ed30a. Фактический код я опубликую позже, потому что не хочу задушить креативность.
Лили Чунг

Ответы:

2

Ах да, я забыл когда-либо фактически публиковать свой ответ. По сути, он использует тот же подход, который использует ответ KSab , но печатает только самое короткое допустимое выражение.

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)

Обратите внимание, что хэш, который я вычислил ранее, включал завершающий символ новой строки и был до того, как начал играть def e(x): returnв гольфe=lambda x:

Лили Чунг
источник
1

Python 616

Не особенно эффективно, но работает в разумные сроки для входных данных, результаты которых составляют около 5 или 6 символов. Чтобы проверить строку, чтобы увидеть, соответствует ли она, она просматривает все возможные комбинации значений истина / ложь для всех переменных и проверяет, согласна ли каждая из них. Используя это, он проверяет каждую возможную строку, состоящую из соответствующих символов (даже не обязательно синтаксически правильную).

Фактически он напечатает каждое эквивалентное выражение (любого размера) и фактически никогда не завершится.

Код:

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

Вход / выход:

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

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

> (P \/ Q) /\ P
P
(P)
...
KSab
источник