[Risolto] Implicanti primi,implicanti essenziali e non

[ubuntumate]

Ho letto dal libro (Mano Kime) la definizione di implicante ma non l'ho capita. Riporto una breve citazione dal libro:

Un prodotto P è un implicante di una funzione se essa assume il valore 1 per tutti i mintermini che compongono il prodotto P considerato.

Un mintermine è un prodotto logico che contiene tutte le variabili una e una sola volta in forma diretta o negata. Quel che non mi è chiaro è come il prodotto P debba essere composto dato che un mintermine è già un prodotto

In una funzione booleana del genere

Codice: Seleziona tutto

F (X,Y,Z) = ∑ m(1,3,4,6,7)

quali sono gli implicanti?

Insomma vorrei una spiegazione a prova di imbecille sui concetti citati nel titolo

[M_A_W_ 1968]

Non c'è problema, stai ancora nuotando a pochi metri dal bagnasciuga. Questi banali concetti si trovano ovunque e in tutte le salse, perfino in lingua italiana: basta avere l'accortezza di incrociare tre o quattro fonti accademiche. Eccone intanto un paio: uno, due. E, come omaggio della ditta, guarda anche questo e, soprattutto, questo.

[gila75]

OT: ma quante ca....caspita di cose sai MAW...???!!! Prima o poi troveremo un argomento che non conosci

[M_A_W_ 1968]

OT: ma quante ca....caspita di cose sai MAW...???!!! Prima o poi troveremo un argomento che non conosci

Ci vuole poco, caro Gila: non so nulla (e me ne vanto) di web e cloud programming, scraping, burotica, gaming, gambling, gestionali fiscali assortiti (anche se da studente ho scritto diverse applicazioni borderline per MRP-II, scheduling di produzione, ottimizzazione tagli in una e due dimensioni, interfacciamento tra PC, Atari ATW800 e AS/400, generatori di codice Clipper e COBOL, convertitori di formati e un paio di librerie verticali per programmatori di tale settore)... ci sono interi settori applicativi che per me potrebbero allegramente non esistere, e ci sono linguaggi che al solo rammentarli mi causano violente reazioni emetiche, da java a PHP ai vari BASIC. Per non parlare di "Arduino"!

[ubuntumate]

Grazie @MAW per le risorse. Ammetto che era una domanda un po' RTMF, ma comincio a tenere molto alle definizioni e al loro uso corretto, perciò ho chiesto.

PS: Vogliamo ricordare a MAW l'esistenza di Java? Un crivello di Erastotene in Java magari?

[M_A_W_ 1968]

PS: Vogliamo ricordare a MAW l'esistenza di Java? Un crivello di Erastotene in Java magari?

Per codesti "scherzi" è prevista la crocefissione in sala mensa con clisterone purificatore da 11 galloni.

[ubuntumate]

Banalmente

Un implicante di una funzione è quindi un termine prodotto che coinvolge solo alcune variabili di f e tale per cui la funzione vale 1.

dall'odiatissimo sito (Wikipedia) dagli amanti del formalismo e del rigore.

[M_A_W_ 1968]

Beh, statisticamente non possono sbagliare sempre e tutto. Anche non volendo, qualcosa ogni tanto devono pur azzeccarla. Specialmente quando "citano" come in questo caso da qualche libro di testo elementare (la bibliografia in italiano sulle reti logiche è decisamente enorme), o da altri siti (vedi ad esempio la biografia di Leonardo Pisano di Bonaccio detto Fibonacci e relativa "discussione").

Il problema, come sempre, rimane quello di trovare occasionalmente qualche sprazzo di correttezza e qualche barlume di senso in mezzo al ciarpame e all'alluvione poltaceo di argomenti assolutamente non enciclopedici, dalle "biografie" di illustri sconosciuti viventi (e un bellissimo camilleriano "macuminchiasennestracatafotte" non ce lo vogliamo schiaffare?) all'elenco completo di pokemon e gormiti. Il problema più colossale è proprio questa sesquipedale varianza qualitativa: chi non possiede gli strumenti per valutare a priori la correttezza di una voce non può certo sperare di affidarsi a wikipedia per imparare o capire qualcosa.

[ubuntumate]

Ho letto le definizioni dai link da te forniti e le ho comparate con altre tra cui quella di Wikipedia. In questo caso mi è stato utile per poter procedere con le reti logiche dopo una breve passeggiata con Gentzen. Se dopo aver compreso espressioni funtoriali, linguaggio predicativo,quantificatori,deduzioni naturali etc etc nell'altra disciplina procede tutto a gonfie vele, qui, con le rete logiche, sono in alto mare in mezzo a Karnaugh, Quine-McCluskey e i vari algoritmi Espresso. Nel caso aprirò una nuova discussione cercando di riprendere un buon ritmo anche in questa bottega.

Implicante = prodotto logico per il quale la funzione assumere il valore 1
Implicante primo = prodotto logico che cessa di essere un implicante se ad esso viene rimosso un qualsiasi letterale che lo compone
Implicante essenziale = questo non lo saprei ben spiegare

[M_A_W_ 1968]

Dovresti fare esercizi su Karnaugh usando carta e penna e confrontando con l'output dei programmini indicati. Si tratta di un metodo veramente elementare, e in questo caso l'approccio inverso (dalla ricerca tabulare dei cluster di valori alla definizione di implicante essenziale) ti aiuterà a capire meglio la definizione e il suo scopo.

[ubuntumate]

Avevo messo risolto, ma in realtà non avevo risolto. Ho lasciato perdere lo studio di queste cose perché ero impegnato a studiare altro per il serale.

"Un prodotto P è un implicante di una funzione se essa assume il valore 1 per tutti i mintermini che compongono il prodotto P considerato."

Mi chiedo come possa un mintermine comporre qualcos'altro se la definizione di termine è la seguente:
"Un mintermine è un prodotto logico in cui compaiono una sola volta, in forma diretta o negata, tutte le variabile di una funzione f"

[M_A_W_ 1968]

Una nota leggenda urbana vuole che James Joseph Sylvester, illustre matematico discreto ottocentesco e allievo addirittura di Augustus De Morgan (lupus in fabula...) chiese scandalizzato ed infuriato ad un suo allievo, nel bel mezzo di una dimostrazione in sede d'esame: "Ma dove diavolo ha letto una simile eresia? Chi è quel cretino che ha detto tale bestialità?". La risposta del tremebondo allievo fu un fantozziano "Ma Professore, questo teorema ce lo ha spiegato e dimostrato lei, lo scorso semestre... lo ha anche pubblicato in un suo articolo...".

Eviterò quindi di emulare cotanto illustre maestro, presumendo che tu abbia letto codesta baggianata su uno dei tanti testi di reti logiche da me consigliati, quelli sui quali hanno studiato tutti. Voglio sperare che si tratti dell'ennesima bislacca traduzione fatta dal solito amanuense pagato a cottimo per ogni chilogrammo di carta inchiostrata...

[ubuntumate]

Il libro in questione è Reti Logiche di Morris Mano e Charles Kime, quarta edizione italiana del 2008, curata e tradotta da Antonio Gentili e alcuni colleghi dell'università di Catania. Si legge a pagina 48 a proposito di mintermini:

Un prodotto nel quale tutte le variabili di una data funzione appaiono solo una volta, o in forma diretta o in forma negata, si chiama mintermine.

mentre riguardo agli implicanti si ha le seguente definizione a pagina 67:

Un prodotto P è un implicante di una funzione se assume il valore 1 per tutti i mintermini che compongono il prodotto P considerato.

Ora ho riportato le definizione così come si trovano scritte nel libro.

[M_A_W_ 1968]

...il che ti suggerisce immediatamente, senza incoerenze, che un implicante è essenzialmente un prodotto di prodotti.

Col Mano-Kime non si sbaglia, alcune traduzioni possono forse suonare un po' criptiche in prima lettura, ma sostanzialmente rimangono corrette, anche se io preferisco in ogni caso l'originale.

[ubuntumate]

Ne deduco che non devo pensare alla forma canonica di una funzione logica per comprendere cosa sia un implicante. In modo non rigoroso si può dire che un implicante è una parte comune ad almeno due mintermini che raccolgo quando semplifico un'espressione booleana tramite manipolazioni algebriche?
Qui

Codice: Seleziona tutto

f(X,Y,Z) = ~X~YZ + ~X~Y~Z

~X~Y non è un implicante?

Poi non è che non mi sia accorto che talvolta anche con le mappe di Karnaugh si ottengono delle funzioni non completamente semplificate, è che non so come selezionare solo i termini strettamente necessari.

[ubuntumate]

Sto provando a fare esercizi con le K-Maps confrontando i risultati con un software per la semplificazione di funzioni booleane. Sono riuscito a farne un paio ottenendo la forma minima senza introdurre ridondanza, ma al terzo tentativo la successione di soluzioni corretta si è interrotta insieme alla fievole speranza di averci capito qualcosa. La funzione che si oppone al mio progresso nelle discipline computazionali è la seguente:

Codice: Seleziona tutto

F(A,B,C) = E(0,2,3,4,6)¹

Usando la mappa di Karnaugh ottengo quanto segue:

Codice: Seleziona tutto

~AB + ~B~C + B~C

quando in realtà la forma minima è questa:

Codice: Seleziona tutto

~AB + ~C

Il software utilizzato, probabilmente non tra i migliori disponibili, mostra evidenziati sulla mappa di Karnaugh gli stessi sottocubi che ho selezionato io. Non capisco come esso possa essere giunto alla forma minima senza usare manipolazioni algebriche. Le K-maps dovrebbero fornire, e forniscono a chi le padroneggia a dovere, uno strumento visuale e "deterministico" per la semplificazione di funzioni booleane senza dover ricorrere direttamente all'algebra di Boole prima, dopo o durante l'uso delle stesse; dunque a parità di sottocubi scelti si deve necessariamente giungere al medesimo risultato. Non mi spiego come io possa essere arrivato ad una soluzione differente da quella proposta dal programma pur avendo selezionato gli stessi implicanti ².
Allego di seguito un'immagine che permetta di comprendere meglio di cosa io stia parlando e ringrazio in anticipo chi avrà la pazienza di aiutarmi a levare le gambe da questo argomento.



--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

¹: si ponga E uguale al simbolo di sommatoria.
²: se ho ben capito la fugace spiegazione a margine del mio insegnante, sottocubo è sinonimo di implicante.

[ubuntumate]

Finalmente ho capito!

Implicanti: tutti i prodotti per cui la funzione vale 1, quindi tutte le celle con un 1 quando si esprime la funzione tramite SOP e tutti i prodotti che derivano dai questi mintermini perché ovviamente 1 AND 1 fa sempre 1.
Primi implicanti: si trovano graficamente cercando tutti i raggruppamenti composti da 2^n celle adiacenti contenenti 1 che non siano interamente contenuti in raggruppamenti più grandi.
Implicanti primi essenziali: contengono un cella a 1 che non è contenuta in nessun altro primo implicante.

Mi è stato particolarmente utile questo link.

Grazie per l'aiuto MAW