Ciao ragazzi, stavo provando a risolvere un esercizio che chiede:
"In una stanza ci sono due persone (che denoteremo $1$ e $2$) e due sedie (anch’esse denotate $1$ e $2$). Utilizzando le variabili $X_{1,1} X_{1,2} X_{2,1} X_{2,2}$, ove $X_{ij}$ dice "$i$ sta seduto sulla sedia $j$", esprimi in clausole il fatto che ciascuna persona è seduta esattamente su una sedia in forma CNF."
Volevo chiedervi se il mio svolgimento vi sembra corretto, e se vi è la possibilità di risolvere l'esercizio con un numero di clausole minore.
1) La persona $1$ è seduta sulla sedia $1$ e la persona $2$ è seduta sulla sedia $2$:
$(X_{11} \wedge X_{22} \wedge \neg X_{12} \wedge \neg X_{21})$
2) La persona $1$ è seduta sulla sedia $2$ e la persona $2$ è seduta sulla sedia $1$:
$(\neg X_{11} \wedge \neg X_{22} \wedge X_{12} \wedge X_{21})$
Adesso non rimane che unire tutto in un'unica clausola:
$(X_{11} \wedge X_{22} \wedge \neg X_{12} \wedge \neg X_{21}) \vee (\neg X_{11} \wedge \neg X_{22} \wedge X_{12} \wedge X_{21})$
Infine, per la trasformazione in CNF, applico il teorema di De Morgan, ottenendo:
$(\neg X_{11} \vee \neg X_{22} \vee X_{12} \vee X_{21}) \wedge (X_{11} \vee X_{22} \vee \neg X_{12} \vee \neg X_{21})$