Formula con variabile libera

[One]

Non sò come risolvere questo problema:
Nel dominio dei numeri interi,indichiamo con \( \displaystyle {R} \)\( \displaystyle {\left({x},{y}\right)} \) un segno di relazione binaria che si interpreta "y è un multiplo di x" e con la costante \( \displaystyle \text{1} \) il numero \( \displaystyle {1} \).Devo scrivere una formula \( \displaystyle {P} \)\( \displaystyle {\left({x}\right)} \) con una sola varibile libera \( \displaystyle {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 \( \displaystyle {R}{\left({x},{y}\right)} \)

[vict85]

La definizione di primo può essere scritta così:
Per ogni \(\displaystyle y \) tale che \(\displaystyle R(y,x) \) risulta \(\displaystyle y=1 \)

[One]

Ok,ho capito.
Grazie!

[vict85]

beh, ho dimenticato il caso x=y... comunque il senso è quello.

[One]

Approfiito per porre un'altro problema:
Avendo a disposizione oltre il segno di uguaglianza \( \displaystyle = \) il segno di relazione \( \displaystyle \mathbb{R}{\left({x},{y}\right)} \) che indica "x è figlio di y",con una sola varibile libera \( \displaystyle {x} \) descrivere x non ha zii.
Mi servirebbe giusto capire come iniziare

[vict85]

Scusa ma come definiresti uno zio? Un figlio di tuo nonno che non è un tuo genitore.

[One]

La mia difficoltà stà nel fatto che ho solo due variabili a disposizione \( \displaystyle {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.

[vict85]

In realtà ne hai semplicemente una libera: \(x\). Le altre variabili devono essere quantificate.

[One]

Seguendo il tuo consiglio ho fatto così:
\( \displaystyle \exists{y}{\left({\left({R}{\left({y},{z}\right)}\wedge{\left(\neg{R}{\left({x},{y}\right)}\right)}\right)}\right.} \)
dove \( \displaystyle {z} \) è il nonno,ora il problema è quello di dire che \( \displaystyle {x} \) è nipote di \( \displaystyle {z} \)
P.S:
Aggiungendo una variabile \( \displaystyle {w} \) per indicare il padre di \( \displaystyle {x} \),mi risulta:
\( \displaystyle \forall{x}\exists{y}{\left({R}{\left({y},{z}\right)}\wedge{\left(\neg{R}{\left({x},{y}\right)}\right)}\wedge{\left({R}{\left({w},{z}\right)}\wedge{R}{\left({x},{w}\right)}\right)}\right.} \)
E' corretto quello che ho fatto?

[vict85]

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.