Newsgroup: it.hobby.enigmi
Titolo: 3 NOT con 2 NOT

Tempo fa in area "matenigmici" .... Luca C. proponeva
un interessante problema che diede filo da trocere
a tutti.....Lo propongo per chi non lo conosce:
Il problema: costruire la seguente rete logica
    _ _
A -|   |- !A
B -|   |- !B
C -|_ _|- !C
 
(ovvero: tre ingressi A, B e C e tre uscite pari ad A negato,
B negato e C negato).
Si possono utilizzare porte AND e OR in quantita` industriali,
ma solo "due" porte NOT.
Minimizzare il numero di porte logiche.
CiaO,
Massimo
-- 
Posted from 
net128-007.mclink.it
 [195.110.128.7] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG


s
p
o
i
l
e
r
Spero di farmi capire.
!A = (A AND !B) AND B
!C = (C AND !B) AND B
!B = !B
Dimostro la prima:
A B !B A&!B (A&!B)&B
--------------------
1 1  0  0      0
1 0  1  1      0
0 1  0  1      1
0 0  1  0      1
In questo modo utilizzo 4 AND, nessun OR e un NOT = 5 operatori.
Una soluzione migliore si ha, pero', cosi':
!A = (A AND !B) AND B
!C = !C
!B = !B
che usa 2 AND e 2 NOT, per un totale di 4 operatori.
Si puo' fare di meglio?
--AG

 !A = (A AND !B) AND B
mmmmhhhhh... questo fa zero (F, Falso, False) con buona pace del povero A.
(A AND !B) AND B = A AND (!B AND B) = A AND 0 = 0
Silv:o)

#include "Armando Grimaldi.h"

Usare una XOR? 
---
Blackstorm
*Vicario d'Armi di idf*
Tittums e' il nostro gatto, ed ha le dimensioni di un rotolo di soldini.
Inarcava la schiena e bestemmiava come uno studente in medicina.
(Jerome Klapka Jerome)
E da oggi anche su ICQ! UIN 116647346 (nick: blacks)          

#include "Silvio Sergio.h"

E se si provasse con un A= (A XOR B)? 


Silvio Sergio wrote:

Mah... questa fa zero se e solo se A=1, e fa 1 se invece A=0. Cioe' fa !A, che
e' esattamente quello che volevo ottenere.
--AG

Nel testo si parla di AND, OR e NOT, e non si parla di XOR. Suppongo che se
vuoi usare un'XOR devi ricavarlo utilizzando gli operatori descritti in
precedenza.
Ma questo puo' dircelo Massimo M.
--AG


 
Nel testo si legge....:
"Si possono utilizzare porte AND e OR in quantita` industriali,
ma solo "due" porte NOT".
Direi che non e' lecito usare una porta XOR.
CiaO,
Massimo


   Ha ragione Silvio Sergio, B & !B fa sempre 0 [if ((b == 1) && (b != 1))],
poi, nel calcolo di A&!B, c'e` un errore nella 3^ riga.
 A B !B A&!B (A&!B)&B
 --------------------
 1 1  0  0      0
 1 0  1  1      0
 0 1  0  0      0
 0 0  1  0      0

 Direi che non e' lecito usare una porta XOR.
   Anche perche 1 XOR A = NOT A. E cosi`, con tre XOR ho finito. :-)
1 |  A | 1^A
--+----+-----
1 |  0 |  1
1 |  1 |  0


   Se c'e` la soluzione, posso realizzare qualsiasi rete logica con solo due
porte NOT. Infatti, se mi servono 10 porte NOT, prendo una di queste
scatolette, e uso A-!A, come porta not, poi uso B-!B e C-!C come i due NOT
che servono per costruire un'altra scatoletta, uso A'-!A' come seconda porta
NOT per la mia rete, e B'-!B' e C'-!C' per costruire un'altra scatoletta, e
cosi` via... Bello!

 E se si provasse con un A= (A XOR B)?
Per fare uno XOR ci vogliono due NOT credo (comunque almeno uno).
Es.:
A XOR B = (A AND !B) OR (!A AND B)
Silv:o)

 Usare una XOR?
Beh... di fatto, e' quello che ho fatto io, visto che ho usato l'AND come se
fosse un'XOR (nella mia soluzione ho usato 0 AND 0 = 1, mentre questo e'
vero solo per l'XOR).
--AG

#include "Armando Grimaldi.h"

Ah, ecco... cmq suppongo che vada usato una specie di selettore...


 con solo due porte NOT.......
Esiste....e' difficile ma esiste.
;-)


 A XOR B = (A AND !B) OR (!A AND B)
   Sol. con un solo NOT (praticamente da definizione: a o b, ma non
entrambi)
   (A OR B) AND !(A AND B)

#include "Totuccio.h"

Si, pero' cosi' si e' punto e a capo... manca sempre una porta not, che
pero' non serve... :(((


 porte NOT.....
Se interessa posto la soluzione che ho in archivio
ottimizzata dal mitico "Quick Nick"....Chissa' se ci
segue?
;-)
CiaO,
Massimo
-- 
Posted from 
net128-053.mclink.it
 [195.110.128.53] 



.
Sono xurioso! (cambio
di iniziale)
.
Ciao  :o)
Livio
--------------------------------
Inviato via 
http://usenet.iol.it
 

 ;-)
   Posta, si`, grazie.

 Se interessa posto la soluzione che ho in archivio
.
.
.
.
.
.
.
S
.
p
.
o
.
i
.
l
.
e
.
r
.
.
.
.
Questa la soluzione data dal proponente:
x = (ab+c)(a+b)
y = (!x + abc)(a+b+c)   ...(vero se ingressi alti sono pari)
!a = (bc+!x)!y + (b+c)!x
!b = (ac+!x)!y + (a+c)!x
!c = (ab+!x)!y + (a+b)!x
Totale 12 AND e 12 OR
L'ottimizzazione fatta da Nicola...:
x = ab + (a + b)c
y = (ab + !x)c + !x(a + b)
!a = b(c!y + !x) + !x(c + !y)
!b = a(c!y + !x) + !x(c + !y)
!c = (ab + !x)!y + !x(a + b)
Totale 9 AND e 9 OR
Si puo' fare meglio...?
CiaO,
Massimo
PS...Leggenda....:
     a+b = a OR b
     ab = a*b = a AND b
     !a = NOT a


...
.
.
.
Poiche' non ci
credevo, l'ho verificato in tutti i modi: e' vero!  :)
Possiamo trarre
qualche pensiero filosofico? E' come dire che avendo il Bene e il Male, il
Tutto e il Nulla, possiamo ricavare il Nero dal Bianco, il Rosso dal Verde,
la Sapienza dall'Ignoranza, la Luce dal Buio, etc, etc???
Bah!


 Livio
******************************************
Bravo Massimo,
Ci hai fatto rimanere tutti di m...
Eravamo tutti pronti a saltarti addosso sfidandoti a mostrare la famosa
soluzione (io ho dovuto fare due volte i calcoli per convincermi che era
vero!!!!!).
Credo che ci sarebbe una grande lezione da trarre: non credere mai
ciecamente in nulla!!!
Ciao, Giuseppe

 Ci hai fatto rimanere tutti di m...
Come ho precisato nel post iniziale tale problema non
e' mio.....Anzi quando l'ho visto in area "matenigmici"
ci ho lavorato molto senza esito come voi!
;-(
CiaO,
Massimo
-- 
Posted from 
net128-007.mclink.it
 [195.110.128.7] 
