Formula con variabile libera
Non sò come risolvere questo problema:
Nel dominio dei numeri interi,indichiamo con $R$$(x,y)$ un segno di relazione binaria che si interpreta "y è un multiplo di x" e con la costante $"1"$ il numero $1$.Devo scrivere una formula $P$$(x)$ con una sola varibile libera $x$ che descriva la proprietà "x non è un numero primo".
Il problema di persè non è difficile,però non sò come fare a risolverlo avendo a disposizione solo il segno di relazione $R(x,y)$
Nel dominio dei numeri interi,indichiamo con $R$$(x,y)$ un segno di relazione binaria che si interpreta "y è un multiplo di x" e con la costante $"1"$ il numero $1$.Devo scrivere una formula $P$$(x)$ con una sola varibile libera $x$ che descriva la proprietà "x non è un numero primo".
Il problema di persè non è difficile,però non sò come fare a risolverlo avendo a disposizione solo il segno di relazione $R(x,y)$
Risposte
La definizione di primo può essere scritta così:
Per ogni \(\displaystyle y \) tale che \(\displaystyle R(y,x) \) risulta \(\displaystyle y=1 \)
Per ogni \(\displaystyle y \) tale che \(\displaystyle R(y,x) \) risulta \(\displaystyle y=1 \)
Ok,ho capito.
Grazie!
Grazie!
beh, ho dimenticato il caso x=y... comunque il senso è quello.
Approfiito per porre un'altro problema:
Avendo a disposizione oltre il segno di uguaglianza $=$ il segno di relazione $RR(x,y)$ che indica "x è figlio di y",con una sola varibile libera $x$ descrivere x non ha zii.
Mi servirebbe giusto capire come iniziare
Avendo a disposizione oltre il segno di uguaglianza $=$ il segno di relazione $RR(x,y)$ che indica "x è figlio di y",con una sola varibile libera $x$ descrivere x non ha zii.
Mi servirebbe giusto capire come iniziare
Scusa ma come definiresti uno zio? Un figlio di tuo nonno che non è un tuo genitore.
La mia difficoltà stà nel fatto che ho solo due variabili a disposizione $x,y$ e per come volevo svolgerlo ,mi servirebbe un'ulteriore variabile,dato che le utilizzerei una per il nonno,una per il padre/zio ed una per il figlio.
In realtà ne hai semplicemente una libera: \(x\). Le altre variabili devono essere quantificate.
Seguendo il tuo consiglio ho fatto così:
$EEy((R(y,z)^^(\neg R(x,y)))$
dove $z$ è il nonno,ora il problema è quello di dire che $x$ è nipote di $z$
P.S:
Aggiungendo una variabile $w$ per indicare il padre di $x$,mi risulta:
$AAxEEy(R(y,z)^^(\neg R(x,y))^^(R(w,z)^^R(x,w))$
E' corretto quello che ho fatto?
$EEy((R(y,z)^^(\neg R(x,y)))$
dove $z$ è il nonno,ora il problema è quello di dire che $x$ è nipote di $z$
P.S:
Aggiungendo una variabile $w$ per indicare il padre di $x$,mi risulta:
$AAxEEy(R(y,z)^^(\neg R(x,y))^^(R(w,z)^^R(x,w))$
E' corretto quello che ho fatto?
Direi che mancano pezzi e hai gestito male le variabili libere e non.
Vediamo quindi di scrivere \(\displaystyle \varphi(x) \) come "\(\displaystyle x \) non ha zii".
Per prima scriviamo \(\displaystyle z \) è nonno di \(\displaystyle x \). Si scriverebbe \(\displaystyle \exists y \left[R(x,y) \wedge R(y,z)\right] \).
D'altra parte noi vogliamo dire che per ogni nonno di \(\displaystyle x \) ha come figlio solo il genitore di \(\displaystyle x \) corrispondente.
Quindi \(\displaystyle \varphi(x) = \forall y, z, w \left[R(x,y) \wedge R(y,z) \rightarrow \left[R(w,z)\rightarrow (w=y) \right]\right] \)
Ovviamente in virtù della possibilità di esprimere l'implicazione con \(\displaystyle \vee \) e \(\displaystyle \neg \) posso scrivere anche le seguenti forme equivalenti:
\(\displaystyle \varphi(x) = \forall y, z, w \left[R(x,y) \wedge R(y,z) \rightarrow \left[\neg R(w,z) \vee (w=y) \right]\right] \)
\(\displaystyle \varphi(x) = \forall y, z, w \left[\neg \right[R(x,y) \wedge R(y,z)\left] \vee \left[R(w,z)\rightarrow (w=y) \right]\right] \)
\(\displaystyle \varphi(x) = \forall y, z, w \left[\neg R(x,y) \vee \neg R(y,z) \vee \left[R(w,z)\rightarrow (w=y) \right]\right] \)
\(\displaystyle \varphi(x) = \forall y, z, w \left[\neg R(x,y) \vee \neg R(y,z) \vee \neg R(w,z) \vee (w=y)\right] \)
e varie altre... Soprattutto perché il quantificatore può essere spostato. Alcune sono più intuitive di altre.
Vediamo quindi di scrivere \(\displaystyle \varphi(x) \) come "\(\displaystyle x \) non ha zii".
Per prima scriviamo \(\displaystyle z \) è nonno di \(\displaystyle x \). Si scriverebbe \(\displaystyle \exists y \left[R(x,y) \wedge R(y,z)\right] \).
D'altra parte noi vogliamo dire che per ogni nonno di \(\displaystyle x \) ha come figlio solo il genitore di \(\displaystyle x \) corrispondente.
Quindi \(\displaystyle \varphi(x) = \forall y, z, w \left[R(x,y) \wedge R(y,z) \rightarrow \left[R(w,z)\rightarrow (w=y) \right]\right] \)
Ovviamente in virtù della possibilità di esprimere l'implicazione con \(\displaystyle \vee \) e \(\displaystyle \neg \) posso scrivere anche le seguenti forme equivalenti:
\(\displaystyle \varphi(x) = \forall y, z, w \left[R(x,y) \wedge R(y,z) \rightarrow \left[\neg R(w,z) \vee (w=y) \right]\right] \)
\(\displaystyle \varphi(x) = \forall y, z, w \left[\neg \right[R(x,y) \wedge R(y,z)\left] \vee \left[R(w,z)\rightarrow (w=y) \right]\right] \)
\(\displaystyle \varphi(x) = \forall y, z, w \left[\neg R(x,y) \vee \neg R(y,z) \vee \left[R(w,z)\rightarrow (w=y) \right]\right] \)
\(\displaystyle \varphi(x) = \forall y, z, w \left[\neg R(x,y) \vee \neg R(y,z) \vee \neg R(w,z) \vee (w=y)\right] \)
e varie altre... Soprattutto perché il quantificatore può essere spostato. Alcune sono più intuitive di altre.
Ok,credo di aver capito dove sbagliavo....
Scrivo questo problema,di cui spero aver trovato una soluzione corretta:
Il testo è simile a quello precedente,però ora $R(x,y)$ indica x è un genitore di y,inoltre ho a disposizione oltre al segno $=$,due variabili libere $x,y$.Devo descrivere x e y sono cugini
io lo svolto così:
$\varphi(x,y)=AAz,w,k[R(z,w)^^(z,k)]rarr[(R(w,x)^^R(k,y))vvR((w,y)^^R(k,x))]$
dove $z$ è il nonno e $w,k$ gli zii.Nella prima parte della formula:$R(z,w)^^(z,k)$ dico che $w$ e $k$ sono fratelli,mentre nella seconda parte:$(R(w,x)^^R(k,y))vv(R(w,y)^^R(k,x))$ dico che $x$ ed $y$ sono figli di $w$ e $k$,quindi sono cugini.L'unico mio dubbio rimane quello di non aver mai utilizzato il simbolo $=$
Scrivo questo problema,di cui spero aver trovato una soluzione corretta:
Il testo è simile a quello precedente,però ora $R(x,y)$ indica x è un genitore di y,inoltre ho a disposizione oltre al segno $=$,due variabili libere $x,y$.Devo descrivere x e y sono cugini
io lo svolto così:
$\varphi(x,y)=AAz,w,k[R(z,w)^^(z,k)]rarr[(R(w,x)^^R(k,y))vvR((w,y)^^R(k,x))]$
dove $z$ è il nonno e $w,k$ gli zii.Nella prima parte della formula:$R(z,w)^^(z,k)$ dico che $w$ e $k$ sono fratelli,mentre nella seconda parte:$(R(w,x)^^R(k,y))vv(R(w,y)^^R(k,x))$ dico che $x$ ed $y$ sono figli di $w$ e $k$,quindi sono cugini.L'unico mio dubbio rimane quello di non aver mai utilizzato il simbolo $=$
Stai dicendo che per ogni \(\displaystyle z,w,k \) tali che \(\displaystyle w \) e \(\displaystyle k \) sono fratelli e \(\displaystyle k \) un loro genitore risulta che uno dei due è padre di \(\displaystyle x \) e l'altro di \(\displaystyle y \). Direi quindi che non va...
Sia \(\displaystyle x\prec y \) e \(\displaystyle y\succ x \) le relazioni "figlio di" e "genitore di".
Un cugino è il figlio del fratello di un genitore. Sto solo considerando il primo grado ovviamente.
Se \(\displaystyle x \) e \(\displaystyle y \) sono i cugini, \(\displaystyle \bar{x} \) e \(\displaystyle \bar{y} \) i rispettivi genitori fratelli e \(\displaystyle z \) un nonno di entrambi.
Risulterà
\(\displaystyle x\prec \bar{x} \prec z\)
\(\displaystyle y\prec \bar{y} \prec z\)
\(\displaystyle \bar{x}\neq \bar{y} \)
La relazione dei cugini quindi si scriverebbe come esiste un nonno comune ma non sono fratelli.
\(\displaystyle \exists\bar{x}, \bar{y}, z\left[ (x\prec \bar{x})\wedge (y\prec \bar{y})\wedge (\bar{x} \neq \bar{y}) \wedge (\bar{x} \prec z) \wedge (\bar{y} \prec z)\right] \)
Riscritto in formula logica più formale risulta:
\(\displaystyle \varphi(x,y) = \exists\bar{x}, \bar{y}, z\left[ R(\bar{x}, x)\wedge R(\bar{y}, y)\wedge \neg(\bar{x} = \bar{y}) \wedge R(z, \bar{x}) \wedge R(z, \bar{y})\right] \)
P.S.: La formula funziona a meno che non ci sia stano un incesto (fratello con sorella).
Sia \(\displaystyle x\prec y \) e \(\displaystyle y\succ x \) le relazioni "figlio di" e "genitore di".
Un cugino è il figlio del fratello di un genitore. Sto solo considerando il primo grado ovviamente.
Se \(\displaystyle x \) e \(\displaystyle y \) sono i cugini, \(\displaystyle \bar{x} \) e \(\displaystyle \bar{y} \) i rispettivi genitori fratelli e \(\displaystyle z \) un nonno di entrambi.
Risulterà
\(\displaystyle x\prec \bar{x} \prec z\)
\(\displaystyle y\prec \bar{y} \prec z\)
\(\displaystyle \bar{x}\neq \bar{y} \)
La relazione dei cugini quindi si scriverebbe come esiste un nonno comune ma non sono fratelli.
\(\displaystyle \exists\bar{x}, \bar{y}, z\left[ (x\prec \bar{x})\wedge (y\prec \bar{y})\wedge (\bar{x} \neq \bar{y}) \wedge (\bar{x} \prec z) \wedge (\bar{y} \prec z)\right] \)
Riscritto in formula logica più formale risulta:
\(\displaystyle \varphi(x,y) = \exists\bar{x}, \bar{y}, z\left[ R(\bar{x}, x)\wedge R(\bar{y}, y)\wedge \neg(\bar{x} = \bar{y}) \wedge R(z, \bar{x}) \wedge R(z, \bar{y})\right] \)
P.S.: La formula funziona a meno che non ci sia stano un incesto (fratello con sorella).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo