Predicati e quantificatori
Obiettivo (corso Analisi Matematica 1)
- La logica dei predicati
- Quantificatore universale
- Quantificatore esistenziale
- Regola generale per la negazione dei qualificatori
La logica dei predicati
Definizione
Predicato: una proposizione che contiene una o più variabili
Il predicato fissate le variabili diventa una proposizione
Esempio
- $P(x)=$ "$x$ è un numero pari"
- $P(2)$ è vera
- $P(3)$ è falsa
- $P(x,y)=$ "$x \geqslant y$" (esempi di predicato con due variabili)
Nota
- Il valore di verità del predicato $P(x)$ dipende dal valore assunto dalla variabile $x$
- Fissare $x$ in $P(x)$ significa trasformare il predicato in una proposizione
Quantificatori
Quantificatori: utili allo studio del predicato $P(x)$ al variare di $x$ in un dato insieme
Quantificatori:
- $\forall$: Per ogni (quantificatore universale)
- $\exists$: Esiste (quantificatore esistenziale)
- $\exists!$: Esiste ed è unico
Nota
- Attenzione all'ordine dei quantificatori!
- Nel linguaggio comune si ha
- "nessuno ..." che è equivalente a "tutti non ..." i.e "per ogni non ..."
- "ci sono ..." che è equivalente a "esiste almeno un ..."
Esempio 1
Dato $P(x)$ si ha
- $\forall x \colon P(x)$ significa per ogni $x$, $P(x)$ è vera
- $\exists x \colon P(x)$ significa esiste (almeno) un $x$ per cui $P(x)$ è vera
- $\exists! x \colon P(x)$ significa esiste un unico $x$ per cui $P(x)$ è vera
Esempio 2: quantificatori nel caso di due variabili
Sia $P(x,y)$ l'espressione "$x+y=0$" con $x,y\in\mathbb{R}$, allora:
- $\forall x, \forall y \colon P(x,y)$: significa per ogni $x$ e $y$ si ha $x+y=0$ (falsa)
- $\exists x, \exists y \colon P(x,y)$: significa che esistono due numeri $x$ e $y$ tali che $x+y=0$ (vera)
- $\forall x, \exists y \colon P(x,y)$: significa per ogni $x$, esiste un $y$ tale che $x+y=0$ (vera)
- $\exists y, \forall x \colon P(x,y)$: significa esiste un numero $y$ tale che, tutti gli $x$ sono tali che $x+y=0$ (falsa)
Esempio 3: quantificatori nel caso di due variabili
Sia $P(x,y)$ l'espressione "${1\over x}\leqslant y$" con $x\geqslant1$ e $y$ qualunque allora:
- $\exists y, \forall x \colon P(x,y)$ significa esiste un numero $y$ tale che, tutti gli $x$ sono tali che ${1\over x}\leqslant y$ (vera)
Ad esempio $y=1$ (anche $2$), perché la divisione di un numero positivo maggiore di 1 è compreso tra 0 e 1
Regola generale per la negazione dei qualificatori
Per negare una proposizione della forma $n$ qualificatori e predicato finale con $n$ variabili, si scambiano i qualificatori $\forall$ e $\exists$ e si nega il predicato finale
Ad esempio nel caso di una variabile:
- $\neg (\forall x \colon P(x))$ è equivalente a $\exists x \colon \neg P(x)$
- $\neg (\exists x \colon P(x))$ è equivalente a $\forall x \colon \neg P(x)$
Ad esempio nel caso di due variabili:
- $\neg \left(\forall x, \exists y \colon P(x,y)\right) \quad \iff \quad \exists x, \forall y \colon \neg P(x,y)$
- $\neg \left(\exists x, \forall y \colon P(x,y)\right) \quad \iff \quad \forall x, \exists y \colon \neg P(x,y)$
Esempio 1
Sia
- $P(x)$: $x$ è un numero naturale pari
allora si ha che
- $\neg \forall x \colon P(x)$: non tutti i numeri naturali sono pari
è equivalente a
- $\exists x \colon \neg P(x)$: esiste un numero naturale che non è pari
Esempio 2
Sia $P(x,y)=y\geqslant x$ allora si ha che
- $\forall x, \exists y \colon y\geqslant x$ ovvero fissato un qualunque numero $x$ esiste un numero $y$ maggiore del numero dato
equivale a
- $\exists x, \forall y \colon y< x$ esiste un numero $x$ maggiore di ogni numero $y$.
Esempio 3
$$\neg \forall x, \exists y \colon P(x,y) \quad \iff \quad \exists x, \forall y \colon \neg P(x,y)$$
Sia $P(x,y)$ l'espressione "$x\leqslant y^2$", allora:
- $\neg \forall x, \exists y \colon P(x,y)$ significa negare che per ogni numero $x$ esiste un numero $y$ tale che $x\leqslant y^2$ è equivalente a
- $\exists x, \forall y \colon \neg P(x,y)$ che significa che esiste un numero $x$ che per ogni numero $y$ si ha $x > y$
Ruolo del controesempio
Dimostrare che $\forall x \colon P(x)\implies Q(x)$ è falso equivale a mostrare che:
- $\neg( \forall x \colon P(x)\implies Q(x))$ è vero,
- $\exists x \colon P(x)\land \neg Q(x)$ è vero (il controesempio),
- i.e. ovvero $P(x)$ è vero e $Q(x)$ è falso
cioé devo fornire un esempio in cui le ipotesi sono vere e la tesi è falsa!
Nota: Il valore di verità di $P \implies Q$ è lo stesso di $\neg P \lor Q$ (equivalenza dell'implicazione)
Esempio
Teorema: Dimostrare che $$\text{ogni equazione polinomiale di secondo grado ha almeno una soluzione reale}$$ è una preposizione falsa
Soluzione
Basta fornire un controesempio
Si consideri l'equazione $x^2+1=0$ che non ha radici reali ($x^2=-1$)
Curiosità
Tutto il monodo è vero o falso?
No: esiste la Logica Fuzzy
In cui un predicato può assumere un valore di verità compreso tra 0 e 1
Ricorda di sostenere questo progetto con una donazione (PayPal.Me/ManoloVenturin).