Esercizio connettivi funzionalmente completi
Ho ripostato questo esercizio in modo che sia più leggibile e chiaro a tutti.Ho un esame tra poco e non riesco proprio a chiarire i miei dubbi sui connettivi funzionalmente completi.Posto questo esercizio svolto:
Si definisce un connettivo: $v(a*b)=1hArr v(a)=v(notb)=0$;
1)esprimere in funzione di $^^$e$vv$: $nota^^b$ e $not(avvnotb)$;
2)verificare se il connettivo è commutativo:$a*b=nota^^b$ e $b*a=notb^^a$,quindi non è commutativo;
3)vedere se esistono B,B',B'': ( e già qui non ho capito cosa sono sti B)
$a*B=_|_ $
$a*B'=a$
$B''*a=nota$
essendo non commutativo lo vede sia a dx che sx:
$a*a=nota^^a=_|_ $
$a*nota=nota^^nota=nota$ --- $nota*a=a^^a=a$
$a*_|_ =nota^^_|_ =_|_ $ --- $_|_ *a=T^^a=a$
$a*T=nota^^T=nota$ --- $T*A=_|_ ^^a=_|_ $
poi dice che B' non c'è a destra ma c'è a sinistra(ce ne sono due),ci va bene sia il $nota$ che il $_|_ $(potreste spiegarmi questa affermazione?)
ed arriviamo al succo dell'esercizio,
4)dire se i seguenti insiemi di connettivi sono funzionalmente completi:
a)${*,not}$
b)${*,_|_ }$
c)${*,T}$
per quanto riguarda l'insieme a) dice che se trova $^ì$oppure$vv$ è funzionalmete completo. E qui non capisco il motivo:perchè proprio $^^$e$vv$?
per l'insieme b) dice che per dimostrare che è funzionalmente completo deve trovare il $not$.Anche qui la stessa domanda:perchè?
per l'insieme c) non c'è scritto niente sull'esercizio svolto quindi non so proprio.
Si definisce un connettivo: $v(a*b)=1hArr v(a)=v(notb)=0$;
1)esprimere in funzione di $^^$e$vv$: $nota^^b$ e $not(avvnotb)$;
2)verificare se il connettivo è commutativo:$a*b=nota^^b$ e $b*a=notb^^a$,quindi non è commutativo;
3)vedere se esistono B,B',B'': ( e già qui non ho capito cosa sono sti B)
$a*B=_|_ $
$a*B'=a$
$B''*a=nota$
essendo non commutativo lo vede sia a dx che sx:
$a*a=nota^^a=_|_ $
$a*nota=nota^^nota=nota$ --- $nota*a=a^^a=a$
$a*_|_ =nota^^_|_ =_|_ $ --- $_|_ *a=T^^a=a$
$a*T=nota^^T=nota$ --- $T*A=_|_ ^^a=_|_ $
poi dice che B' non c'è a destra ma c'è a sinistra(ce ne sono due),ci va bene sia il $nota$ che il $_|_ $(potreste spiegarmi questa affermazione?)
ed arriviamo al succo dell'esercizio,
4)dire se i seguenti insiemi di connettivi sono funzionalmente completi:
a)${*,not}$
b)${*,_|_ }$
c)${*,T}$
per quanto riguarda l'insieme a) dice che se trova $^ì$oppure$vv$ è funzionalmete completo. E qui non capisco il motivo:perchè proprio $^^$e$vv$?
per l'insieme b) dice che per dimostrare che è funzionalmente completo deve trovare il $not$.Anche qui la stessa domanda:perchè?
per l'insieme c) non c'è scritto niente sull'esercizio svolto quindi non so proprio.
Risposte
La prima parte è poco chiara... forse il copiancolla? 
Comunque, il tuo problema principale è il punto (4). Dovresti aver già visto nel tuo corso gli insiemi minimi con due elementi (lascio perdere il singoletto con l'operatore di Sheffer), dai quali si può costruire qualunque altro operatore. I più "classici" sono ${^^,not}$ e ${vv,not}$.
Quindi, se dall'insieme (4.a) ${*,not}$ riesci a trovare una formula che "simula" $^^$ oppure $vv$ (cioè che crea la stessa tabella di verità di "and" ed "or" per intenderci) ottieni l'insieme ${*,not,^^}$ (oppure ${*,not,vv}$) che è completo poiché contiene un insieme completo già noto.
Per il (4.b)(4.c) idem: se riesci a ricavare l'operatore $not$ ottieni un insieme che contiene ${*,not}$ che hai già verificato essere completo dal (4.a).
Spiacente se sono scarso nello spiegare, ma del resto non insegno... Ti lascio due riferimenti utili per un ripasso rapido:
http://en.wikipedia.org/wiki/Logical_connective
http://en.wikipedia.org/wiki/Functional_completeness
A volte la notazione è differente, ma di poco, e non dovresti avere difficoltà.
Comunque, il tuo problema principale è il punto (4). Dovresti aver già visto nel tuo corso gli insiemi minimi con due elementi (lascio perdere il singoletto con l'operatore di Sheffer), dai quali si può costruire qualunque altro operatore. I più "classici" sono ${^^,not}$ e ${vv,not}$.
Quindi, se dall'insieme (4.a) ${*,not}$ riesci a trovare una formula che "simula" $^^$ oppure $vv$ (cioè che crea la stessa tabella di verità di "and" ed "or" per intenderci) ottieni l'insieme ${*,not,^^}$ (oppure ${*,not,vv}$) che è completo poiché contiene un insieme completo già noto.
Per il (4.b)(4.c) idem: se riesci a ricavare l'operatore $not$ ottieni un insieme che contiene ${*,not}$ che hai già verificato essere completo dal (4.a).
Spiacente se sono scarso nello spiegare, ma del resto non insegno...
Ti lascio due riferimenti utili per un ripasso rapido:http://en.wikipedia.org/wiki/Logical_connective
http://en.wikipedia.org/wiki/Functional_completeness
A volte la notazione è differente, ma di poco, e non dovresti avere difficoltà.
Sei stato chiarissimo ora,finalmente inizio a capire. e se avessi avuto anche ${*,->}$ e ${*,hArr}$ ?cosa avredi dovuto trovare qui?
Per l'insieme ${*,->}$ se trovi $not$ sei a posto, ottenendo ${*,->, not}$...
Per la doppia implicazione dovrei mettermi a scrivere un po' di formulette, ma non ho un granché di tempo... informatica teorica incombe!
[ A proposito, visto che non ho scritto né tantomeno verificato nulla, posta le soluzioni appena hai fatto, che le verifichiamo ]
Per la doppia implicazione dovrei mettermi a scrivere un po' di formulette, ma non ho un granché di tempo... informatica teorica incombe!
[ A proposito, visto che non ho scritto né tantomeno verificato nulla, posta le soluzioni appena hai fatto, che le verifichiamo ]
Allora secondo i miei calcoli:
$[*,not}$:$a^^b$
${*,_|_}$:non lo è
${*,T}$:$nota^^T=nota$
Fin qui ci siamo.Però per quanto riguarda gli insiemi con due connettivi binari non so come fare. Ad esempio:${*,=>}$,{*,^^}$.
Come dovrei fare praticamente in questi casi?Nei casi precedenti era più semplice.
$[*,not}$:$a^^b$
${*,_|_}$:non lo è
${*,T}$:$nota^^T=nota$
Fin qui ci siamo.Però per quanto riguarda gli insiemi con due connettivi binari non so come fare. Ad esempio:${*,=>}$,{*,^^}$.
Come dovrei fare praticamente in questi casi?Nei casi precedenti era più semplice.
E' corretto, riaggiusto solo un po' per essere più chiari:
${*,not}$ è f.c. in quanto posso ottenere l'operatore $^^$: $not a * b = a^^b$
${*,_|_}$ non è completo
${*,T}$ è f.c. in quanto posso ottenere l'operatore unario di negazione: $a*T=not a$, che ho già visto formare assieme all'operatore $*$ un insieme f.c.
Per i connettivi binari procedi analogamente, è solo apparentemente più complicato; inizio io:
$a->(a*a)=not a$
Ed ho già trovato un operatore che mi dà un insieme completo: è il tuo risultato di sopra.
Essendo pochi casi, puoi anche scriverti le tabelle di verità mentri procedi sulle formule, il che ti aiuta a verificare.
${*,not}$ è f.c. in quanto posso ottenere l'operatore $^^$: $not a * b = a^^b$
${*,_|_}$ non è completo
${*,T}$ è f.c. in quanto posso ottenere l'operatore unario di negazione: $a*T=not a$, che ho già visto formare assieme all'operatore $*$ un insieme f.c.
Per i connettivi binari procedi analogamente, è solo apparentemente più complicato; inizio io:
$a->(a*a)=not a$
Ed ho già trovato un operatore che mi dà un insieme completo: è il tuo risultato di sopra.
Essendo pochi casi, puoi anche scriverti le tabelle di verità mentri procedi sulle formule, il che ti aiuta a verificare.
Allora ti scrivo le combinazioni per quanto riguarda l'insieme ${*,=>}$:
$a=>(a*a)$
$a=>(a*nota)$
$a=>(a*_|_)$
$a=>(a*T)$
essendo l'operatore $*$ non commutativo faccio anche così:
$a=>(nota*a)$
$a=>(_|_*a)$
$a=>(T*a)$
poi:
$(a*a)=>a$
$(a*nota)=>a$
$(a*_|_)=>a$
$(a*T)=>a$
e anche qui per il fatto della non commutatività di $*$:
$(nota*a)=>a$
$(_|_*a)=>a$
$(T*a)=>a$
ho fatto bene?che ne pensi?poi basta che trovo da uno solo di questi il $not$ e posso considerarlo funzionalmente completo?
$a=>(a*a)$
$a=>(a*nota)$
$a=>(a*_|_)$
$a=>(a*T)$
essendo l'operatore $*$ non commutativo faccio anche così:
$a=>(nota*a)$
$a=>(_|_*a)$
$a=>(T*a)$
poi:
$(a*a)=>a$
$(a*nota)=>a$
$(a*_|_)=>a$
$(a*T)=>a$
e anche qui per il fatto della non commutatività di $*$:
$(nota*a)=>a$
$(_|_*a)=>a$
$(T*a)=>a$
ho fatto bene?che ne pensi?poi basta che trovo da uno solo di questi il $not$ e posso considerarlo funzionalmente completo?
"FELPONE":
Allora ti scrivo le combinazioni per quanto riguarda l'insieme ${*,=>}$:
$a=>(a*a)$
$a=>(a*nota)$
$a=>(a*_|_)$
$a=>(a*T)$
...
Aspetta, stai facendo un po' di confusione (o non capisco cosa stai facendo, il che è lo stesso). Il tuo insieme di partenza è ${*,->}$ che non contiene gli altri connettivi che elenchi nelle combinazioni che hai scritto.
Per l'insieme ${*,->}$ ti ho già fatto vedere come, dai soli due connettivi presenti nell'insieme stesso, sia possibile ottenere $not$. Questo permette di dire che l'insieme ${*,->}$ è funzionalmente equivalente all'insieme ${*,->,not}$, che è funzionalmente completo (in quanto contiene ${*,not}$ che hai già visto essere completo).
Proviamo per l'insieme con l'altro connettivo ovvero ${*,^^}$. Prova a fare la valutazione (o costruire le tabelle di verità) di
$a^^a$
$a*a$
$a^^(a*a)$
$(a*a)^^a$
in funzione di $a$.
Nota bene, ti basta la prima
In effetti, le ho messe solo per farti vedere il metodo generale. Ovvero scrivi le formule con una sola variabile per provare ad ottenere un connettivo unario (normalmente $not$), poi con due per provare ad ottenere uno binario, e così via.
Allora riscrivo le combinazioni per l'insieme ${*,=>}$:
$a=>(a*a)$
$(a*a)=>a$
va bene ora?
per quanto riguarda l'insieme da te proposto ${*,^^}$ dobbiamo cercare di trovare il $not$ vero?
non capisco perchè dici che basta la prima $a^^a$?non è uguale ad $a$?
Poi quando dici di usare una o più variabili non ho capito:usiamo sempre la a alla fine vero?
$a=>(a*a)$
$(a*a)=>a$
va bene ora?
per quanto riguarda l'insieme da te proposto ${*,^^}$ dobbiamo cercare di trovare il $not$ vero?
non capisco perchè dici che basta la prima $a^^a$?non è uguale ad $a$?
Poi quando dici di usare una o più variabili non ho capito:usiamo sempre la a alla fine vero?
"FELPONE":
non capisco perchè dici che basta la prima $a^^a$?non è uguale ad $a$?
Evidentemente ho sbagliato, perché riguardando mi accorgo che nessuna è sufficiente per trovare $not$. Ci bastava anche $T$ ...
"FELPONE":
Poi quando dici di usare una o più variabili non ho capito:usiamo sempre la a alla fine vero?
Non sempre "solo" una variabile. Con una possiamo trovare un connettivo unario, come $not$.
Nell'esempio che ho messo non troviamo nulla con una sola variabile, e allora si deve provare a vedere anche se qualcosa corrisponde ad un connettivo binario.
[ NOTA: mi sa che l'esempio ${*,^^}$che ho fatto è incompleto
però non ho verificato, magari prova tu ]Quindi, dovresti provare a vedere se qualche formula con due variabili
$a*(a^^b)$
$b*(a^^b)$
eccetera, corrisponde a qualche formula con un altro operatore binario.
Per quanto riguarda l'insieme ${*,^^}$:
$a^^a=a$
$a*a=nota$
$a*(a^^a)=nota$
$a^^(a*a)=_|_$
Ok penso sia completo perchè abbiamo trovato il $nota$ giusto?Poi ho un dubbio siamo sicuri che le prime due combinazioni sono giuste?:
$a^^a=a$
$a*a=nota$
non dobbiamo per forza avere una combinazione con tutti e due gli operatori dell'insieme ${*,^^}$ ?
$a^^a=a$
$a*a=nota$
$a*(a^^a)=nota$
$a^^(a*a)=_|_$
Ok penso sia completo perchè abbiamo trovato il $nota$ giusto?Poi ho un dubbio siamo sicuri che le prime due combinazioni sono giuste?:
$a^^a=a$
$a*a=nota$
non dobbiamo per forza avere una combinazione con tutti e due gli operatori dell'insieme ${*,^^}$ ?
cavoli che casino,ti sto postando dei risultati che sono di un altro esercizio ma non di questo:allora ti riscrivo tutte le soluzioni giuste per uqesto esercizio per ogni insieme di connettivi.Sorry.
Vedo
Infatti nell'esercizio che hai postato all'inizio vale $a*a=_|_$ (e NON $a*a=not a$).
Infatti nell'esercizio che hai postato all'inizio vale $a*a=_|_$ (e NON $a*a=not a$).
Ok ci siamo,ti posto solo il risultato di questo insieme che da solo esprime un pò tutti i dubbi che mi sono rimasti:
${*,vv}$
$a*(avva)=_|_$
$avv(a*a)=a$
$a*(avvb)=a*b=(nota^^b)$ quì simula il comportamento di $(a*b)$ posso definirlo completo con questo?
$b*(avvb)$
Un dubbio che mi è rimasto è: ho usato solo combinazioni di entrambi gli operatori dell'insieme e non di un solo tipo ad esempio $avva$ oppure $a*a$, ho fatto bene?
Anche se ho visto che tu in qualche esempio lo hai fatto.
${*,vv}$
$a*(avva)=_|_$
$avv(a*a)=a$
$a*(avvb)=a*b=(nota^^b)$ quì simula il comportamento di $(a*b)$ posso definirlo completo con questo?
$b*(avvb)$
Un dubbio che mi è rimasto è: ho usato solo combinazioni di entrambi gli operatori dell'insieme e non di un solo tipo ad esempio $avva$ oppure $a*a$, ho fatto bene?
Anche se ho visto che tu in qualche esempio lo hai fatto.
L'operatore "star" $*$ è ancora quello dell'esercizio che hai postato? Mi sembra torni tutto.
Il procedimento è corretto. Certo, puoi anche usare un solo operatore; in questo caso non serviva a nulla però perché le formule $a vv a=a$ e $a*a=_|_$ non ti aiutano a trovare altri operatori e $_|_$ non rendeva l'insieme completo. Ma a volte potrebbe essere utile.
Parti sempre a cercare un operatore unario (e quindi usi una sola variabile, e vedi se una formula con una sola variabile è equivalente ad un altro operatore unario). Se non trovi nulla, cerca operatori binari usando due variabili, sviluppando quindi formule con due variabili e controllando se sono equivalenti ad altri operatori binari.
Se non trovi nulla nemmeno così (e se non avete fatto operatori ternari) termini la ricerca.
PS. guarda che dopo due/tre esercizi ti accorgi quasi subito delle formule "giuste" senza stare a scriverle tutte (e tantomeno a provarle tutte).
Il procedimento è corretto. Certo, puoi anche usare un solo operatore; in questo caso non serviva a nulla però perché le formule $a vv a=a$ e $a*a=_|_$ non ti aiutano a trovare altri operatori e $_|_$ non rendeva l'insieme completo. Ma a volte potrebbe essere utile.
Parti sempre a cercare un operatore unario (e quindi usi una sola variabile, e vedi se una formula con una sola variabile è equivalente ad un altro operatore unario). Se non trovi nulla, cerca operatori binari usando due variabili, sviluppando quindi formule con due variabili e controllando se sono equivalenti ad altri operatori binari.
Se non trovi nulla nemmeno così (e se non avete fatto operatori ternari
) termini la ricerca.PS. guarda che dopo due/tre esercizi ti accorgi quasi subito delle formule "giuste" senza stare a scriverle tutte (e tantomeno a provarle tutte).
quindi anche se uso un solo operatore di un insieme di due operatori ed ottengo l'operatore che mi serviva,va bene?
Mi sembra strano...
Cmq ti ringrazio infinitamente per la pazienza che mi hai dedicato.
Mi sembra strano...
Cmq ti ringrazio infinitamente per la pazienza che mi hai dedicato.
Ti disturbo per l'ultima volta:potresti vedere se ho applicato bene l'associatività....?
$a*b=(nota^^notb)vv(a^^notb)$
$(a*b)*c=(not((nota^^notb)vv(a^^notb))^^notc)vv((nota^^notb)vv(a^^notb))^^notc)
$a*b=(nota^^notb)vv(a^^notb)$
$(a*b)*c=(not((nota^^notb)vv(a^^notb))^^notc)vv((nota^^notb)vv(a^^notb))^^notc)
E' l'operatore $*$ dell'esercizio, tale che $a*b=not a ^^ b$? Allora non mi torna...
No no è un altro operatore,è definito nella prima riga e la seconda riga fa l'associatività.
Allora va bene
Scusate, mi intrometto anche io con un esercizio simile:
Sia l'operatore $ A*B= neg A vv B $. Determinare se sono funzionalmente completi gli insiemi:
1. $ {*, neg } $
2. $ {*, _|_} $
Io vorrei sapere se ho risolto bene:
1. $ A*B= neg A vv B $ da cui ho trovato $neg$ e quindi ${*, neg}$ è funzionalmente equivalente a ${*,neg,vv}$ che è funzionalmente completo.
2. $A*_|_ = neg A vv _|_ = neg A$ da cui ho trovato $neg$ quindi ${*,_|_ }$ è funzionalmente equivalente a ${*, _|_, neg}$.
Qui sorge il mio dubbio: va bene se verifico quanto segue?
$A*B=A vv neg B$ da cui ho trovato $vv$ e quindi ${*,_|_}$ è funzionalmente equivalente a ${*,_|_, neg}$ che è funzionalmente equivalente a ${*, _|_, neg, vv}$ che è funzionalmente completo. Quindi ${*,_|_}$ è funzionalmente completo.
Sia l'operatore $ A*B= neg A vv B $. Determinare se sono funzionalmente completi gli insiemi:
1. $ {*, neg } $
2. $ {*, _|_} $
Io vorrei sapere se ho risolto bene:
1. $ A*B= neg A vv B $ da cui ho trovato $neg$ e quindi ${*, neg}$ è funzionalmente equivalente a ${*,neg,vv}$ che è funzionalmente completo.
2. $A*_|_ = neg A vv _|_ = neg A$ da cui ho trovato $neg$ quindi ${*,_|_ }$ è funzionalmente equivalente a ${*, _|_, neg}$.
Qui sorge il mio dubbio: va bene se verifico quanto segue?
$A*B=A vv neg B$ da cui ho trovato $vv$ e quindi ${*,_|_}$ è funzionalmente equivalente a ${*,_|_, neg}$ che è funzionalmente equivalente a ${*, _|_, neg, vv}$ che è funzionalmente completo. Quindi ${*,_|_}$ è funzionalmente completo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo