Operazioni su OBDD: negazione attraverso l'espansione di Shannon

Question

Ho un problema con l'applicazione del Shannon espansione per avere la negazione di un formula booleana, che avrà bisogno per implementare l'operatore di negazione su OBDD ( Ordinare binario decisione Diagramma ) che è , mostrano che:

$ \ qquad \ displaystyle \ neg f (x_1, \ ldots, x_n) = (\ neg x_1 \ wedge \ neg f | _ {x_1 = 0}) \ vee (x_1 \ wedge \ neg f | _ {x_1 = 1}) $

dove $ f | _ {x_i = b} $ è la funzione booleana in cui sostituisce $ x_i $ con B, che è il seguente:

$ \ qquad \ displaystyle f | _ {x_i = b} (x_1, \ ldots, x_n) = f (x_1, \ ldots, x_ {i-1}, b, x_ {i + 1}, \ ldots , x_n) $.

La prova dice:

$ \ qquad \ displaystyle \ neg f (x_1, \ ldots, x_n) = \ neg ((\ neg x_1 \ wedge f | _ {x_1 = 0}) \ vee (x_1 \ wedge f | _ {x_1 = 1})) $.

L'applicazione della negazione (saltare i passaggi intermedi), otteniamo:

$ \ qquad \ displaystyle (x_1 \ wedge \ neg x_1) \ vee (\ neg x_1 \ wedge \ neg f | _ {x_1 = 0}) \ vee (x_1 \ wedge \ neg f | _ {x_1 = 1 }) \ vee (\ neg f | _ {x_1 = 0} \ wedge \ neg f | _ {x_1 = 1}) $.

Ora $ (x_1 \ wedge \ neg x_1) = \ mathrm {false} $ può essere eliminato, che porta a

$ \ qquad \ displaystyle (\ neg x_1 \ wedge \ neg f | _ {x_1 = 0}) \ vee (x_1 \ wedge \ neg f | _ {x_1 = 1}) \ vee (\ neg f | _ {x_1 = 0} \ wedge \ neg f | _ {x_1 = 1}) $

a sua volta, infine, uguale a

$ \ qquad \ displaystyle (\ neg x_1 \ wedge \ neg f | _ {x_1 = 0}) \ vee (x_1 \ wedge \ neg f | _ {x_1 = 1}). $

Perché questo attesa?

Answer 1

Forse è meglio per capire se si effettua una tabella di verità per entrambe le funzioni. Si può vedere che se $ (\ neg f | _ {x_1 = 0} \ wedge \ neg f | _ {x_1 = 1}) $ è vero allora $ (\ neg x_1 \ wedge \ neg f | _ {x_1 = 0 }) \ vee (x_1 \ wedge \ neg f | _ {x_1 = 1}) $ è anche vero, perché entrambi $ f $ termini sono vere e sia $ x_1 $ è vero o $ \ neg x_1 $ è vero. E se $ (\ neg f | _ {x_1 = 0} \ wedge \ neg f | _ {x_1 = 1}) $ è falsa, allora devi fare un caso di studio:

• Se sia $ f $ termini sono false, allora è $ (\ neg x_1 \ wedge \ neg f | _ {x_1 = 0}) \ vee (x_1 \ wedge \ neg f | _ {x_1 = 1}) $ anche false
• Se esattamente un $ f $ termine (WLOG $ \ neg f | _ {x_1 = 0} $) è falsa, allora è equivalente a $ (x_1 \ wedge \ neg f | _ {x_1 = 1}) $

Pertanto, entrambe le formule $ (\ neg x_1 \ wedge \ neg f | _ {x_1 = 0}) \ vee (x_1 \ wedge \ neg f | _ {x_1 = 1}) \ vee (\ neg f | _ {x_1 = 0} \ wedge \ neg f | _ {x_1 = 1}) $ e $ (\ neg x_1 \ wedge \ neg f | _ {x_1 = 0}) \ vee (x_1 \ wedge \ neg f | _ { x_1 = 1}) $ sono equivalenti.