Domanda

È possibile convertire tutte le formule logiche in una forma in modo tale che ciascuna variabile finisca in 1 "fattore" esattamente del funzionamento? ($ Wedge $). È consentita qualsiasi combinazione di operazioni, sebbene meno operazioni usassero meglio.

$$ a sinistra ((a destra b) downarrow b a destra) wedge a sinistra (c vee d a destra) wedge a sinistra ( a sinistra (e sinistra f a destra) vee f a destra) tag {ind} $$

Ciò sarebbe valido perché tutte le istanze di ciascuna variabile esistono solo in 1 dei "fattori" anche se appare in quel fattore più volte.

$$ left ((a destra b) downarrow b a destra) weedge left (a vee b a destra) $$Questo non sarebbe valido perché il $ a $ (o il $ b $) appare in più e "fattori"

Ho chiamato questo (IND) Perché ciascuno dei fattori è indipendente l'uno dall'altro. Sono principalmente interessato a un modo per convertire 3-CNF a (IND), se è possibile.


Modifica per chiarimenti:

Ritenere $ a sinistra (a vee b vee c a destra) wedge a sinistra (a vee d vee e a destra) $. Il $ a $ appare su entrambi i lati del $ Wedge $ Vorrei convertirlo in formato: $ f (a, b, c) wedge g (d, e) $ dove $ f (a, b, c) $ e $ g (d, e) $ può utilizzare qualsiasi operazione.

Allo stesso modo

Dato $ a sinistra (a vee b vee c a destra) wedge a sinistra (a vee b vee d destra) $ Vorrei $ a $ e $ b $ essere dalla stessa parte del $ Wedge $. Non importa come sono separati o se una qualsiasi delle altre variabili si muove. Tutto ciò che conta è che ogni istanza di una variabile appare in un solo "fattore"

$ underbrace { left (a vee b vee c destra)} _ {fattore} wedge underbrace { left (d vee e vee f a destra)} _ {fattore} wedge underbrace { left (g vee h vee i a destra)} _ {fattore} $

Nessuna soluzione corretta

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top