# Logica Monadica

## monadic first order logic

- monadic => i predicati sono solo unari (ammettono un solo argomento)
- uso: descrivere parole su un alfabeto $I$
#### sintassi
- $\phi := a(x) | x<y| \neg\phi | \phi \wedge \phi | \forall x(\phi)$
- $a \in I$, ogni lettera dell'alfabeto ha un predicato unario
#### interpretazione:
- $<$ è la relazione di minore
- il dominio delle variabile è $\mathbb{N}$
- data una parola $w \in I^+$ e un simbolo $a \in I$
- $a(x)$ è vero $\iff$ l'x-esimo simbolo di $w$ è $a$ (indici partono da zero)
#### Semantica
- siano $w \in I^+$ e $V_1$ l'insieme delle variabili
- Un **assegnamento** è una funzione $v_1 : V_1 \to [0,...,|w|-1]$ tale che
- $w,v_1 \models a(x) \iff w=u\textit{a}v \wedge |u|=v_1(x)$
- $w,v_1 \models x<y \iff v_1(x)< v_1 (y)$
- $w,v_1 \models \neg \phi \iff \text{non }w,v_1 \models \phi$
- $w,v_1 \models\phi_1 \wedge \phi_2 \iff w,v_1 \models\phi_1 \wedge w,v_1 \models\phi_2$
- $w,v_1 \models \forall x(\phi) \iff w,v_1' \models \phi \text{ per ogni } v_1' \text{ con }v_1'(y) = v_1(y), y\neq x$
#### proprietà
- chiusi rispetto a *unione*, *intersezione*, *complemento*
- non chiusi rispetto a * (stella di kleen)
- MFO definisce linguaggi *star-free*
- strettamente meno potenti dei FSA

## monadic second order logic
- posso quantificare su **insiemi di posizioni**
- posso fare formule $\exists X(\phi)$ dove $X$ è una variabile con dominio *l'insieme dei predicati monadici*
- convenzione:
- maiuscole -> variabili con dominio insieme di predicati monadici
- minuscole -> variabili con dominio numeri naturali
#### semantica
l'assegnamento delle variabili del II ordine ($V_2$) è una funzione $v_2 : V_2 \to \wp([0,...,|w|-1])$
- $w,v_1,v_2 \models X(x) \iff v_1(x) \in v_2(x)$
- $w,v_1,v_2 \models \exists X(x) \iff w,v_1,v_2' \models \phi \text{ per qualche } v_2' \text{ con } v_2' (Y) = v_2(Y), Y \neq X$
#### proprietà
- MSO sono equivalenti ai linguaggi regolari