XOR utilizzando gli operatori matematici

Question

Come posso implementare XOR utilizzando gli operatori matematici di base, come +, -, *,/

Aggiornamento: In realtà, ho bisogno di tenere traccia di cambiamento in due matrici con valori booleani. Questo può essere fatto usando XORando ogni valore con il valore corrispondente in altra matrice. Ma la libreria Lp_Solve non supporta l'operazione XOR. Inoltre, accetta solo equazioni lineari.

Answer 1

(a - b) ²

Questo funziona perché:

(a − b)² = a * (a − b) + b * (b − a) 

Da moltiplicazione ℤ₂ è conjuction (&), e 1 - a è negazione (!), la formula sopra è equivalente a XOR per a, b ∈ {0, 1}:

(a & !b) | (b & !a) 

Vedi il commento qui sotto da Pascal Cuoq spiegando il motivo per cui questo non può essere un equazione lineare.

Answer 2

L'espressione più semplice che riesco a ottenere è: a != b.

(best effort precedente era (a + b) == 1)

Answer 3

Puoi fare qualcosa di simile:

(a + b) % 2 

Answer 4

Esclusivo-O è una funzione lineare, ma la definition di 'lineare' per quanto riguarda un valore booleano la funzione non è la stessa di una funzione polinomiale. Sarà necessario consultare la documentazione della libreria lp_solve per verificare se è in grado di gestire le funzioni booleane lineari. Da quello che ho letto, non sospetto che possa farlo.

Edit: Dopo aver esaminato ulteriormente nel simplesso che lp_solve usi, sono abbastanza certo che non si può fare ciò che si sta cercando di fare.

Answer 5

abs (A + B-1). se non fa abs, allora (A + B-1) * (A + B-1) dovrebbe farlo.

Answer 6

Weellllllllllll ........

E 'non è così semplice come sembra.

Per modellare un XOR (chiamiamolo X), iniziamo con la logica.

X = (A & !B) | (!A & B) 

in matematica, quanto sopra può essere scritta come:

X = A*(1-B) + B*(1-A) 

Ma l'espressione sopra è non lineare (a causa dei termini bilineari - per preservare la linearità, non c'è permesso di moltiplicare le variabili con l'un l'altro).

Ma!Poiché siamo autorizzati a utilizzare i vincoli, possiamo riscrivere l'espressione sopra in forma lineare.

In primo luogo, abbiamo espandere i termini:

X = A*(1-B) + B*(1-A) = A + B - 2*A*B 

Ora abbiamo bisogno di prendersi cura della A * B termine (il che significa essenzialmente un & B). Lascia una variabile H rappresentano la condizione logica A & B. Ora possiamo scrivere la condizione AND come segue: (vedi citato riferimento in PDF qui sotto)

H <= A 
H <= B 
H >= A + B - 1 
H >= 0 

lineare XOR Formulazione

Infine, mettiamo tutto insieme. Questa è la tua formulazione XOR, usando solo vincoli lineari.

X = A + B - 2*H 
H <= A 
H <= B 
H >= A + B - 1 
H >= 0 

So che sembra complicato (per un'operazione semplice come un XOR). Potrebbe esserci una formulazione più compatta.

Tuttavia, in generale, la scrittura di condizioni logiche in un contesto di programmazione lineare è complicata perché di solito è severamente limitato nelle operazioni che è possibile eseguire, al fine di evitare di distruggere le proprietà teoriche del problema.

Riferimento

Vedere qui per un elenco di formulazioni interi standard per rappresentare la logica lineare. http://brblog.typepad.com/files/mipformref-1.pdf

---

Edit:

spiegazione su come il modello H vincoli la condizione "AND" logico. Essenzialmente, in un LP, poniamo dei vincoli di disuguaglianza che devono essere soddisfatti al punto della soluzione: quello che stiamo facendo qui sta giocando un trucco per "spremere" H al valore corretto. Ad esempio, data la tupla (A, B) = (0,0), i vincoli per H sarebbero:

H <= 0 
H <= 0 
H >= -1 
H >= 0 

Nel caso precedente, l'unico valore H può assumere è 0, perché H appartiene l'intervallo [0,0]. Quindi otteniamo (A, B) = (0,0) => H = 0.

Proviamo un altro esempio, (A, B) = (1,1).

H <= 1 
H <= 1 
H >= 1 
H >= 0 

Da quanto sopra, vi renderete subito conto che 1 < = H < = 1 implica che H = 1. Otteniamo (A, B) = (1,1) => H = 1.

E così via. Vedrai che i vincoli H modellano esattamente la condizione "AND".

Answer 7

In Brown, G. e Dell, R., Formulazione programmi lineari lineari e interi: galleria una schiera la seguente formulazione di programmazione lineare per la XOR può essere trovato:

Z3 = Z1 XOR Z2 

risolve

Z3 <= Z1 + Z2 
Z3 >= Z1 - Z2 
Z3 >= -Z1 + Z2 
Z3 <= 2 - Z1 - Z2 

Answer 8

2 Fattore XOR

Mentre (x-y)² è una grande equazione compatta per XOR a 2 fattori, mi dà fastidio che la spiegazione di glebm sia wr ong in alcuni modi.

Sebbene la valutazione di queste equazioni è lo stesso per i valori di 1 e 0, non sono algebricamente uguali ...

(a − b)² ≠ a * (1 − b) + b * (1 − a)

Inoltre, l'operatore logico OR non traduce aritmeticamente come + senza vincoli. Questo ti darebbe un valore di 2 per la condizione AND di due 1. Se si considera prima traduzioni di NOT e AND ..

NOT = (1-x)

AND = x*y

cosa si ha realmente bisogno è qualcosa di simile ...

OR = (1-(1-a)(1-b)) = a + b - ab

Nota che, in genere, OR è puramente additivo per cui ti sei unito a due set, MA non vuoi duplicare alcuna sovrapposizione dei set, quindi devi sottrarre la condizione AND che si ottiene moltiplicando. Così hai il tuo termine additivo a+b meno la tua sovrapposizione o AND condizione a*b. Se si è certi che il vostro set non si sovrappongono, quindi è possibile utilizzare

OR = a + b, se sappiamo che a*b = 0 per tutti i valori di un & b

Allo stesso modo, possiamo derivare un'equazione per XOR. Utilizzando la logica composita (a && !b) || (!a && b) si otterrebbe ...

XOR = 1 - (1 - a(1-b))(1 - b(1-a)) ≠ (a-b)²

Quindi la spiegazione è sbagliato nella sua traduzione di logica e di algebra. Come risulta, questi errori vengono mascherati dal vincolo di input binario e poiché le condizioni a(1-b) e b(1-a) si escludono a vicenda, il che riduce il vincolo dell'operatore OR che gestisce la condizione AND e consente di modellarlo come +.

La risposta di Gilead aiuta a spiegare perché (x-y)² funziona davvero. Quando espandi (x-y)² = x² + y² - 2xy puoi vedere come soddisfa questo modello di base ...

X = A + B - 2*H 
H <= A 
H <= B 
H >= A + B - 1 
H >= 0 

Utilizzando quel po 'di conoscenza, è possibile vedere che ci sono un certo numero di equazioni che funzioneranno. Per esempio, l'attuale equazione di base che soddisfa queste condizioni è ...

x + y - 2xy

Questo è esattamente lo stesso come equazione siamo arrivati ​​per OR solo che adesso non stiamo solo rimuovendo il duplicato della AND condizione (-xy), ma rifiutando la condizione AND tutti insieme (-2xy). Come risulta, questo è anche l'equivalente algebrico effettivo per l'espressione glebm menzionata ...

a * (1 − b) + b * (1 − a) = a + b - 2ab ≠ (a-b)².

(a-b)² possono essere utilizzati al posto di questo perché,

(a-b)² = a² + b² - 2ab

e per valori di 1 e 0,

a² + b² - 2ab = a + b - 2ab

cui l'equazione (a-b)² è veramente approfittando solo di due vincoli: semplificazione dell'operatore OR a causa di reciprocamente esclu termini sivi, e la compattezza e l'equivalenza binaria della notazione di potenza per compattare la scrittura dell'equazione.

---

Al di là di 2 fattori

Che dire quando si vuole XOR (A, B, C ...)? Il problema qui è che se proviamo a discernere tutte le condizioni di verità come abbiamo fatto nella logica composita per XOR a 2 fattori, non è molto gradevole, dato che devi aggiungere ogni permutazione della verità. Tuttavia, la logica è quello che è, possiamo arrivare a XOR il modo in omaggio ...

XOR = !(A & B & C...) & !(!A & !B & !C...)

Da cui si può costruire un XOR aritmetica per qualsiasi numero di fattori in forma di ...

(1 - A*B*C...)(1 - (1-A)(1-B)(1-C)...)

fun fun ... voglia di provarlo? Ecco alcune Excel VBA per XOR un intero intervallo di celle ...

Function ArithmeticXOR(R As Range, Optional EvaluateEquation = True) 

Dim AndOfNots As String 
Dim AndGate As String 
For Each c In R 
    AndOfNots = AndOfNots & "*(1-" & c.Address & ")" 
    AndGate = AndGate & "*" & c.Address 
Next 
AndOfNots = Mid(AndOfNots, 2) 
AndGate = Mid(AndGate, 2) 

'Now all we want is (Not(AndGate) AND Not(AndOfNots)) 
ArithmeticXOR = "(1 - " & AndOfNots & ")*(1 - " & AndGate & ")" 
If EvaluateEquation Then 
    ArithmeticXOR = Application.Evaluate(xor2) 
End If 

End Function 

---

Ottenere Fuzzy

E 'interessante fermarsi a riflettere per un secondo che, se usiamo il multi- equazione del fattore sopra per un'equazione a 2 fattori otteniamo il seguente ...

a + b - ab(1 + a + b - ab)

La prima cosa da notare è che questo è simile ma non uguale alla equazione 2 fattori abbiamo derivato da condizioni di verità ...

1 - (1 - a(1-b))(1 - b(1-a)) = a + b - ab(3 - a - b + ab)

infatti, la differenza è nei seguenti termini ...

1 + a + b - ab ≠ 3 - a - b + ab

Quindi cosa dà? Penso che questo sia un artefatto aritmetico dell'uso dei complimenti. Se noti che questi due termini si completano a vicenda, stanno facendo la stessa cosa da direzioni diverse: uno sale da 1 a 2 e l'altro scende da 3 a 2. Entrambi arrivano a 2, ma le loro direzioni di arrivo differiscono perché si stanno avvicinando come complimenti.

La seconda cosa da notare è che entrambe le equazioni sono molto più complicate delle equazioni minime come x + y - 2xy e (x-y)². Questo significa qualcosa, e c'è qualche valore in questa complessità aggiunta?

Ovviamente, per questo, è necessario preoccuparsi dei valori decimali esterni ai punti discreti (0,0), (0,1), (1,0) e (1,1) . Perché mai questo importa? A volte vuoi rilassare il vincolo di interi per un problema discreto. In tal caso, è necessario esaminare le premesse utilizzate per convertire gli operatori logici in equazioni.

quando si tratta di tradurre la logica booleana in aritmetica, i blocchi di costruzione di base sono i AND e NOT operatori, con cui è possibile costruire sia OR e XOR.

OR = (1-(1-a)(1-b)(1-c)...)

XOR = (1 - a*b*c...)(1 - (1-a)(1-b)(1-c)...)

Quindi, se stai pensando di regione decimale, allora vale la pena pensare a come abbiamo definito questi operatori e come si comportano in quella regione.

Traducendo NOT

abbiamo espresso NOT come 1-x. Ovviamente, questa semplice equazione funziona per i valori binari di 0 e 1, ma la cosa veramente interessante è che fornisce anche il complimento in termini percentuali o frazionari per valori compresi tra 0 e 1. Ciò è utile dal momento che NOT è anche noto come il Compliment in logica booleana, e quando si tratta di set, NOT fa riferimento a tutto ciò che è al di fuori del set corrente.

Traducendo AND

abbiamo espresso AND come x*y. Ancora una volta, ovviamente funziona per 0 e 1, ma il suo effetto è un po 'più arbitrario per valori tra 0 e 1 dove la moltiplicazione si traduce in verità parziali (valori decimali) che diminuiscono a vicenda. È possibile immaginare che si vorrebbe modellare la verità come media o accumulativa in questa regione.Ad esempio, se due condizioni sono ipoteticamente dimezzate, la condizione AND è solo un quarto vero (0,5 * 0,5), oppure è interamente vera (0,5 + 0,5 = 1) oppure rimane a metà vero ((0,5 + 0,5)/2)? A quanto pare, la verità del quarto è in realtà vera per condizioni che sono del tutto discrete e la verità parziale rappresenta la probabilità. Ad esempio, capovolgeresti le code (condizione binaria, probabilità del 50%) sia ora che ancora una seconda volta? La risposta è 0.5 * 0.5 = 0.25 o 25% true. L'accumulo non ha molto senso perché è fondamentalmente la modellazione di una condizione OR (ricorda che + può essere modellato da + quando la condizione AND non è presente, quindi la somma è tipicamente OR). La media ha senso se stai osservando accordi e misurazioni, ma è davvero la modellazione di un ibrido di AND e OR. Ad esempio, chiedi a 2 persone di dire su una scala da 1 a 10 quanto sono d'accordo con la frase "Fuori fa freddo"? Se entrambi dicono 5, allora la verità della frase "Fuori fa freddo" è del 50%.

Il take away qui è che, se si rilassano i vincoli di interi, allora c'è un significato per la regione decimale. Potresti voler fare questo per rendere i problemi discreti più facili/possibili da risolvere. Dovrai riflettere su come i valori interagiscono in questa regione e su come verranno convertiti.

Ogni n di k

Un ultimo bocconcino qui. A volte si desidera che una condizione sia vera se qualsiasi numero n di input è true. Questo può essere visto come un rilassato AND condizione, per cui si è disposti ad accettare un & b o un & c o b & c per esempio. Questo può essere aritmeticamente modellato dalla logica composita ...

(a && b) || (a && c) || (b && c) ...

e applicando le nostre traduzioni ...

1 - (1-ab) (1-ac) (1-bc). ..

Questo è utile per conto proprio, ma c'è anche un modello interessante quando si espandono i termini. Esiste un modello di combinazioni variabili ed esponenti, ma questo diventa molto lungo; tuttavia, puoi semplificare ignorando i poteri per un contesto binario. Il modello esatto dipende da quanto n si riferisce a k. Per n = k-1, dove k è il numero totale di condizioni in fase di test, il risultato è il seguente:

c1 + c2 + c3 ... ck - n * Π

Dove C1 ck sono tutte le combinazioni n-variabili.

Per esempio, vero se 3 su 4 condizioni soddisfatte sarebbe

abc + abe + ace + bce - 3abce

Questo ha perfettamente senso logico dal momento che quello che abbiamo è l'additivo OR di AND condizioni meno la condizione di sovrapposizione AND.

Se inizi a guardare n = k-2, k-3, ecc. Il modello diventa più complicato perché abbiamo più sovrapposizioni da sottrarre. Se questo è completamente esteso al valore più piccolo di n = 1, non arriviamo a nulla di più di una normale condizione OR.