- Ridurre al minimo le espressioni booleane

Question

Sto provando a scrivere un pezzo di codice che può ridurre al minimo la LUNGHEZZA di un'espressione booleana, quindi il codice dovrebbe ridurre il numero di elementi nell'espressione al minimo possibile. In questo momento sono bloccato e ho bisogno di aiuto = [

Ecco la regola: ci può essere un numero arbitrario di elementi in un'espressione booleana, ma contiene solo operatori AND e OR, più parentesi.

Ad esempio, se passo un'espressione booleana: ABC + BCD + DE, l'uscita ottimale sarebbe BC (A + D) + DE, che salva 2 spazi unitari rispetto a quello originale perché i due BC sono combinati in uno.

La mia logica è che tenterò di trovare l'elemento più frequentemente apparso nell'espressione, e di tenerlo fuori. Quindi chiamo ricorsivamente la funzione per fare la stessa cosa con l'espressione fattorizzata fino a quando non viene completamente fattorizzata. Tuttavia, come posso trovare l'elemento più comune nell'espressione originale? Cioè, nell'esempio sopra, BC? Sembra che dovrei provare tutte le diverse combinazioni di elementi e trovare il numero di volte in cui ogni combinazione appare nell'intera espressione. Ma questo suona davvero ingenuo. Secondo

Qualcuno può dare un suggerimento su come farlo in modo efficiente? Anche alcune parole chiave che posso cercare su Google lo faranno.

Answer 1

dispiace non ho letto su tutte quelle ancora algoritmi di fresco, ma lei ha chiesto di trovare il fattore comune, così ho pensato di quanto segue:

import itertools 
def commons(exprs): 
    groups = [] 
    for n in range(2, len(exprs)+1): 
     for comb in itertools.combinations(exprs, n): 
      common = set.intersection(*map(set, comb)) 
      if common: 
       groups.append(
          (len(common), n, comb, ''.join(common))) 
    return sorted(groups, reverse=True) 

>>> exprs 
['ABC', 'BCD', 'DE', 'ABCE'] 

>>> commons(exprs) 
[(3, 2, ('ABC', 'ABCE'), 'ACB'), 
(2, 3, ('ABC', 'BCD', 'ABCE'), 'CB'), 
(2, 2, ('BCD', 'ABCE'), 'CB'), 
(2, 2, ('ABC', 'BCD'), 'CB'), 
(1, 2, ('DE', 'ABCE'), 'E'), 
(1, 2, ('BCD', 'DE'), 'D')] 

La funzione restituisce un elenco ordinato per:

1. la lunghezza del fattore comune
2. il numero di termini che hanno questo fattore comune

Answer 2

Quello che stai cercando è un modo per ridurre al minimo una funzione booleana. Questo è qualcosa che interessa in particolare alla comunità di progettazione dei chip. Una tecnica utilizzata per i propri scopi è Quine-McCluskey algorithm oppure è possibile utilizzare Karnaugh Maps come suggerito da Li-aung Yip nei commenti.

Answer 3

Utilizzare l'algoritmo Quine-McCluskey per ridurre al minimo le espressioni booleane. È funzionalmente equivalente all'approccio Karnaugh Map, ma molto più suscettibile all'implementazione su un computer.

Answer 4

Ecco un'applet che implementa le mappe di Karnaugh: http://www-ihs.theoinf.tu-ilmenau.de/~sane/projekte/karnaugh/embed_karnaugh.html

Puoi inserire la tua espressione o compilare una tabella di verità.

Answer 5

Potrebbe piacerti anche guardare Espresso heuristic logic minimizer.

Answer 6

Sfortunatamente, la maggior parte dei suggerimenti forniti potrebbe non fornire effettivamente a @turtlesoup ciò che sta cercando. @turtlesoup ha chiesto un modo per ridurre al minimo il numero di caratteri per una determinata espressione booleana. La maggior parte dei metodi di semplificazione non mira al numero di caratteri come punto di riferimento per la semplificazione. Quando si tratta di ridurre al minimo l'elettronica, gli utenti in genere vogliono il minor numero di porte (o parti). Questo non sempre si traduce in un'espressione più breve in termini di "lunghezza" dell'espressione - la maggior parte delle volte lo fa, ma non sempre. In effetti, a volte l'espressione può diventare più grande, in termini di lunghezza, anche se potrebbe essere più semplice dal punto di vista dell'elettronica (richiede meno porte da costruire).

boolengine.com è il miglior strumento di semplificazione che conosca quando si tratta di semplificazione booleana per i circuiti digitali. Non consente centinaia di input, ma ne consente 14, che è molto più della maggior parte degli strumenti di semplificazione.

Quando si lavora con l'elettronica, i programmi di semplificazione solitamente suddividono l'espressione in forma di somma di prodotto. Quindi l'espressione '(ab) +' cd diventa 'c +' b + 'a + d. Il risultato "semplificato" richiede più caratteri da stampare come espressione, ma è più facile da costruire dal punto di vista dell'elettronica. Richiede solo un singolo gate OR a 4 ingressi e 3 inverter (4 parti). Mentre l'espressione originale richiederebbe 2 porte AND, 2 inverter e una porta OR (5 parti).

Dopo aver dato l'esempio di @ turtlesoup a BoolEngine, mostra che BC (A + D) + DE diventa E + D + ABC. Questa è un'espressione più breve e di solito sarà. Ma certamente non sempre.