xor e logica
Pyroman
Tra colleghi è sorta la domanda se lo XOR è commutativo e associativo.
Senza tirare in gioco dimostrazioni e google io ho risposto di si ragionando
in due modi che però hanno fatto ridere a loro. Volevo quindi sapere se sono
deduzioni che sostituiscono una dimostrazione corretta e rigorosa.
1) Si perchè lo XOR essendo un operatore scomponibile in AND e OR ed essendo
quest'ultimi commutativi e associativi allora anche lo XOR lo è.
2) Si perchè come operatore booleano...qualsiasi sia l'operatore, scambiare
i valori di verità tra due operandi è la stessa cosa! A $ B $ C o A $ C $ B
è uguale dove $ è un qualsiasi operatore booleano (e quindi lineare).
D'altronde anche se scambiando B con C si ottengono 8 terne
differenti...sono pur sempre una permutazione delle 8 terne originali senza
scambiare B con C e quindi il risultato è per forza lo stesso...sia per OR
AND e composti. Proprio perchè gli operatori agiscono non "posizionalmente"
(cioè non tengono conto della posizione dei valori nella successione delle
operazioni) ma solo secondo i valori che la variabile assume.
boh?
Pyroman.
--------------------------------
Inviato via http://arianna.libero.it/usenet/
Andrea Bergia
> Volevo sapere se ho fatto il ragionamento giusto.
> Tra colleghi è sorta la domanda se lo XOR è commutativo e associativo.
Avendo lo XOR solo 4 casi, direi per la commutatività basta verificare
la tabella di verità. Per l'associatività, passo :-)
--
Andrea Bergia - studente Linux Registered User #281550
Pyroman
> la tabella di verità. Per l'associatività, passo :-)
>
sono vere. Ossia se si può dimostrare CON QUELLE 2 affermazioni che XOR è
commutativo e associativo...
Giovanni Resta
> Volevo sapere se ho fatto il ragionamento giusto.
> Tra colleghi è sorta la domanda se lo XOR è commutativo e associativo.
Il fatto che lo XOR sia commutativo direi che e' ovvio, basta
"leggere" la definizione di XOR in lingua italiana:
A XOR B = 0 se A=B e 1 altrimenti.
A=B e' una operazione simmetrica, quindi lo XOR e' commutativo.
(Anche fare la tabella di verita', che contiene solo 4 possibilita'
basta a vedere che e' commutativo).
Per quel che riguarda l'associativita' basta fare la tabella
delle 8 possibilita' di valori per A, B e C e verificare
che (A xor B) xor C = A xor (B xor C).
> Senza tirare in gioco dimostrazioni e google io ho risposto di si ragionando
> in due modi che però hanno fatto ridere a loro. Volevo quindi sapere se sono
> deduzioni che sostituiscono una dimostrazione corretta e rigorosa.
Purtroppo assolutamente non stanno in piedi.
> 1) Si perchè lo XOR essendo un operatore scomponibile in AND e OR ed essendo
> quest'ultimi commutativi e associativi allora anche lo XOR lo è.
Il problema e' che lo XOR non e' scomponibile in AND e OR.
Ti ci vuole anche il NOT (e allora bastano NOT e OR oppure NOT e AND).
Quanto poi al fatto che in generale un operatore esprimibile attraverso
operatori commutativi sia commutativo, direi che e' falso.
Per esempio la moltiplicazione di matrici e' esprimibile attraverso
somme e moltiplicazioni di numeri, ma non e' commutativa.
> 2) Si perchè come operatore booleano...qualsiasi sia l'operatore, scambiare
> i valori di verità tra due operandi è la stessa cosa! A $ B $ C o A $ C $ B
> è uguale dove $ è un qualsiasi operatore booleano (e quindi lineare).
Falso!
Per esempio l'operatore booleano "A implica B"
vale vero sempre escluso il caso in cui A=1 e B=0.
E quindi non e' commutativo.
> Pyroman.
>
>
> --------------------------------
> Inviato via http://arianna.libero.it/usenet/
--
AIUTARE= Accrescere il numero degli ingrati
(Ambrose Bierce, Il Dizionario del Diavolo)
Pyroman
> Ti ci vuole anche il NOT (e allora bastano NOT e OR oppure NOT e AND).
e' vero mi sono dimenticato del NOT
> Quanto poi al fatto che in generale un operatore esprimibile attraverso
> operatori commutativi sia commutativo, direi che e' falso.
> Per esempio la moltiplicazione di matrici e' esprimibile attraverso
> somme e moltiplicazioni di numeri, ma non e' commutativa.
ma la moltiplicazione di matrici...uhmm...è un'operazione differente. Non
riguarda la logica di cui stiamo discutendo.
> > 2) Si perchè come operatore booleano...qualsiasi sia l'operatore,
scambiare
> > i valori di verità tra due operandi è la stessa cosa! A $ B $ C o A $ C
$ B
> > è uguale dove $ è un qualsiasi operatore booleano (e quindi lineare).
>
> Falso!
> Per esempio l'operatore booleano "A implica B"
> vale vero sempre escluso il caso in cui A=1 e B=0.
> E quindi non e' commutativo.
cazz..arola...aspetta a implica b è esprimibile in or e and vero??...si...ok
allora ho cannato!
:-) mannaggia!
Kiuhnm
> 1) Si perchè lo XOR essendo un operatore scomponibile in AND e OR ed essendo
> quest'ultimi commutativi e associativi allora anche lo XOR lo è.
No. Pensa alla moltiplicazione e addizione:
a+b = b+a
(a+b)+c = a+(b+c)
a*b = b*a
(a*b)*c = a*(b*c)
però l'operazione composta
f(a,b) = a°b = a*(a+b)
non è commutativa infatti
a°b = a^2+ab
b°a = b^2+ab
Comunque per lo XOR serve anche il NOT.
Per trovare la formula si può semplicemente partire dalla descrizione in
italiano:
"a XOR b vale 1 quando {a vale 1 e b vale 0} OPPURE quando {a vale 0 e b
vale 1}"
cioè
a XOR b = (a & !b) | (!a & b).
(APERTA PARENTESI:
In generale è sempre vero. Immagina di avere la tavola di verità della
funzione f(a,b,c):
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 0
f(a,b,c) è vera se a è falso, b è falso, c è falso OPPURE
è vera se a è falso, b è falso, c è vero OPPURE
è falsa se a è falso, b è vero, c è falso OPPURE
...
cioè
f(a,b,c) = (!a & !b & !c) | (!a & !b & c) | ...
Semplificando si ottiene l'espressione minima.
CHIUSA PARENTESI).
> 2) Si perchè come operatore booleano...qualsiasi sia l'operatore, scambiare
> i valori di verità tra due operandi è la stessa cosa! A $ B $ C o A $ C $ B
> è uguale dove $ è un qualsiasi operatore booleano (e quindi lineare).
Non è sempre la stessa cosa!
Considera l'operatore
f(a,b) = a & (a|b)
0 & (0|1) = 0
mentre
1 & (1|0) = 1.
(stesso discorso di prima).
> D'altronde anche se scambiando B con C si ottengono 8 terne
> differenti...sono pur sempre una permutazione delle 8 terne originali senza
> scambiare B con C e quindi il risultato è per forza lo stesso...sia per OR
> AND e composti. Proprio perchè gli operatori agiscono non "posizionalmente"
> (cioè non tengono conto della posizione dei valori nella successione delle
> operazioni) ma solo secondo i valori che la variabile assume.
Stai andando troppo a intuito! Bisogna fare un passo alla volta e
verificare le congetture di volta in volta.
Kiuhnm
Pyroman
> (APERTA PARENTESI:
> In generale è sempre vero. Immagina di avere la tavola di verità della
> funzione f(a,b,c):
> 0 0 0
> 0 0 1
> 0 1 0
> 0 1 1
> 1 0 0
> 1 0 1
> 1 1 0
> 1 1 1
OK ti rubo un attimo la tabella!!
Occhio:
A B C
> 0 0 0
> 0 0 1
> 0 1 0
> 0 1 1
> 1 0 0
> 1 0 1
> 1 1 0
> 1 1 1
(A xor B) xor C darà un risultato che sarà quel che sarà ma...
se scambio la colonna B con C
A C B
> 0 0 0
> 0 1 0
> 0 0 1
> 0 1 1
> 1 0 0
> 1 1 0
> 1 0 1
> 1 1 1
(A xor C) xor B darà un altro risultato...ma è lo stesso se permuto le righe
opportunamente...e il fatto di dire opportunamente non intendo che ci "sto
facendo dentro" ma che le scambio per ordinarle come all'inizio.
E' macchinoso e strano come ragionamento ma credo che non sia scorretto.
Boh?
Kiuhnm
> (A xor C) xor B darà un altro risultato...ma è lo stesso se permuto le righe
> opportunamente...e il fatto di dire opportunamente non intendo che ci "sto
> facendo dentro" ma che le scambio per ordinarle come all'inizio.
> E' macchinoso e strano come ragionamento ma credo che non sia scorretto.
> Boh?
Perché dici che dà un altro risultato?
0 0 0 -> 0
0 0 1 -> 1
0 1 0 -> 1
0 1 1 -> 0
1 0 0 -> 1
1 0 1 -> 0
1 1 0 -> 0
1 1 1 -> 1
Se scambi due colonne, il risultato resta identico.
Questo accade perché lo XOR è commutativo e associativo.
Hai inoltre notato che lo XOR di più bit ha la stessa parità del numero
di bit uguali a 1?
Voglio dire che se hai un numero dispari di bit=1 allora lo xor di tali
bit vale 1, altrimenti vale 0.
Cambiando l'ordine dei bit, il loro numero non cambia e quindi il
risultato finale è sempre uguale.
Se per esempio ti chiedono:
"Quanto fa A xor B xor C xor ......., sapendo che 513 di essi valgono 1
e i rimanenti 0?"
Semplice: 513 è dispari quindi lo XOR varrà 1.
Kiuhnm
Giorgio Pastore
Giovanni Resta wrote:
...
> Il fatto che lo XOR sia commutativo direi che e' ovvio, basta
> "leggere" la definizione di XOR in lingua italiana:
> A XOR B = 0 se A=B e 1 altrimenti.
...
Ehm, veramente io sapevo che A XOR B e' = falso se A=B o se A#B.
Giorgio
Caro Estintore
...
>
> Ehm, veramente io sapevo che A XOR B e' = falso se A=B o se A#B.
> Giorgio
Scusa Giorgio, ma stai dicendo che A XOR B e' falso se
A e' uguale a B o se A e' diverso da B, cioe' sempre....
G.Resta aveva detto che A xor B vale 0 se e solo se A e' uguale
a B. Cioe' se entrambi sono 0 o 1 e questo mi sembra giusto.
e.
Giorgio Pastore
...
> Scusa Giorgio, ma stai dicendo che A XOR B e' falso se
> A e' uguale a B o se A e' diverso da B, cioe' sempre....
OK. Mai postare dopo una giornata pesante :-(((
Giorgio
Stefano Gemma
news:213Z156Z34Z234Y...@usenet.libero.it...
> Volevo sapere se ho fatto il ragionamento giusto.
> Tra colleghi è sorta la domanda se lo XOR è commutativo e associativo.
L'XOR è equivalente alla somma di due bit, senza considerare il riporto
(la tabella è la stessa). Siccome la somma è commutativa ed associativa,
anche l'XOR lo è. Il fatto che non si consideri il riporto, rende ancor più
semplice la cosa, perchè l'xor di un valore binario ad enne bit equivale
alle singole somme dei vari bit, che agiscono indipendentemente, l'uno
dall'altro.
Stefano