Enunciato soddisfacbile e valido

[MatteFra]

Ciao a tutti,
mi sto battendo su una tipologia di esercizi di logica che non riesco a capire.
Questo è un esempio. Mi potete spiegare come si risolvono, anche con una spiegazione perfavore?

Si consideri l'enunciato
$ varphi : AA xAA y(R(x,y)^^ f(x)=y rarr EE z(R(x,z)^^ f(y)=z)) $

Determinare se è soddisfacibile e se è valido

[megas_archon]

Inizia ricordando cosa significa "soddisfacibile" e cosa significa "valido".

[MatteFra]

soddisfacibile è una proposizione che soddisfa almeno un caso. Valido se soddisfa tutti i casi possibili

[Cannelloni]

Per vedere che è soddisfacibile basta costruire un esempio ad hoc
Per vedere che è valido basta dimostrarlo (beh)
Per vedere che NON è soddisfacibile basta vedere che è valida la sua negazione
Per vedere che NON è valido basta vedere che soddisfacibile la sua negazione

Come si fa a capire su che cavallo scommettere? Non saprei, andiamo sempre ad intuito più un pochino di esperienza. Guardando la proposizione che hai scritto mi viene da pensare che $R$ ed $f$ siano, rispettivamente, una relazione ed una funzione fissate, quindi non posso rispondere alla domanda senza sapere queste cose. Detto questo provo a rispondere in generale: secondo me $\phi$ è soffisfacibile ma non valida. Per mostrarlo scelgo lo spazio $A=\{1,2,3\}$, definisco $R=\emptyset$ e $f=\text{id}_A$ con questa costruzione la proprietà è vera a vuoto perché per ogni scelta di $x$ e di $y$ la "parte sinistra dell'implicazione" è sempre falsa, quindi l'implicazione è sempre vera. Per vedere che la proprietà non è valida basta usare $A$ come prima, $R=\{(1,2)\}$ e $f$ la definisco per casi ponendo
$f(1)=2$
$f(2)=1$
$f(3)=3$
In questo modo, prendendo $x=1$ e $y=2$ otteniamo che la "parte sinistra dell'implicazione" è vera ma non ci sono $z$ tali che $R(1,z)\wedge f(2)=z$

[MatteFra]

Per vedere che è soddisfacibile basta costruire un esempio ad hoc
Per vedere che è valido basta dimostrarlo (beh)
Per vedere che NON è soddisfacibile basta vedere che è valida la sua negazione
Per vedere che NON è valido basta vedere che soddisfacibile la sua negazione

Come si fa a capire su che cavallo scommettere? Non saprei, andiamo sempre ad intuito più un pochino di esperienza. Guardando la proposizione che hai scritto mi viene da pensare che $R$ ed $f$ siano, rispettivamente, una relazione ed una funzione fissate, quindi non posso rispondere alla domanda senza sapere queste cose. Detto questo provo a rispondere in generale: secondo me $\phi$ è soffisfacibile ma non valida. Per mostrarlo scelgo lo spazio $A=\{1,2,3\}$, definisco $R=\emptyset$ e $f=\text{id}_A$ con questa costruzione la proprietà è vera a vuoto perché per ogni scelta di $x$ e di $y$ la "parte sinistra dell'implicazione" è sempre falsa, quindi l'implicazione è sempre vera. Per vedere che la proprietà non è valida basta usare $A$ come prima, $R=\{(1,2)\}$ e $f$ la definisco per casi ponendo
$f(1)=2$
$f(2)=1$
$f(3)=3$
In questo modo, prendendo $x=1$ e $y=2$ otteniamo che la "parte sinistra dell'implicazione" è vera ma non ci sono $z$ tali che $R(1,z)\wedge f(2)=z$

Grazie mille, alla fine quindi, se ho capito bene, la non validità la vedo perché ogni valore che abbiamo preso, nel nostro caso f(1) e f(2) non condivide gli stessi?

[Cannelloni]

Non capisco la domanda: gli stessi cosa?

[MatteFra]

Non capisco la domanda: gli stessi cosa?

gli stessi valori