Analisi 1 - Logica

Logica

Definizione di proposizione logica

Si definisce proposizione logica un enunciato o una frase di cui si può stabilire con certezza se è vero o falso. Una proposizione logica porta con sé un valore di verità, cioè può essere vera o falsa.

Esempi

• Roma è la capitale dell'Olanda = è una proposizione logica propriamente perché dice un fatto che è erroneamente falso.
• Il Chimborazo è il monte più alto del mondo rispetto al livello del mare F (è l'Everest)
• Il Chimborazo è il monte più alto del mondo rispetto al centro della Terra V
• La vita è bella = non è una proposizione logica poiché è una questione soggettiva.

NB: Queste proposizioni sono dette proposizioni semplici.

Connettivi logici

A partire da proposizioni semplici possiamo ottenere nuove proposizioni utilizzando i connettivi logici.

"E" → Simbolo "∧"

Consideriamo due proposizioni semplici p e q. La tavola di verità del connettivo ∧ è data da:

→ È vero solo se entrambe vere.

"O" → Simbolo "∨"

→ È falso solo se entrambe false.

"Non" → Simbolo "¬"

Implicazione → Simbolo "→"

p→q si legge: p implica q.

• Se p allora q.
• p può essere chiamata: premessa o ipotesi.
• q può essere chiamata: conclusione o tesi.

P ⇒ q viene definita come ¬p ∨ q.

Tavola di verità

→ L'implicazione ⇒ è falsa solo se P è vera e Q è falsa.

→ Se la premessa è vera non si finisce in una conclusione falsa allora l'implicazione non è "corretta".

Equivalenze fra proposizioni

Definizione di proposizioni equivalenti

Due proposizioni si definiscono equivalenti se le verità dell’una implicano le verità dell’altra e viceversa. Per stabilire l’equivalenza si utilizzano le tavole di verità: se le tavole di verità coincidono allora le due proposizioni sono equivalenti.

• ∧ = ∧
• (p e q è equivalente a q e p) "∧" è commutativo
• possima scambiare l’ordine delle proposizioni e ottenere una proposizione equivalente
• ∨ = ∨
• "∨" è commutativo
• ∧(∧) = (∧)∧ (∧ e ∨ sono associativi)
• ∨(∨) = (∨)∨

Es. Dimostrare 2, 3, 4

Tabella a 3 proposizioni

1) L'implicazione non è commutativa. P ⇒ Q ≠ Q ⇒ P.

Andiamo a verificare:

NB: Q ⇒ P implica che è falsa solo se le premesse sono vere e la conclusione è falsa.

Es: P = "A è un quadrato" Q = "A è un rettangolo" P ⇒ Q = "Se A è un quadrato allora A è un rettangolo". Dico: "Se A è un quadrato allora A è un rettangolo" vero è la stessa cosa di dire "Se A è un rettangolo allora A è un quadrato".

2) Si ha invece l'equivalenza fra: P ⇒ Q = ¬Q ⇒ ¬P

Dico: Supponiamo che P ⇒ Q è definito come ¬P ∨ Q Quindi: P ⇒ Q = ¬P ∨ Q Andiamo adesso a vedere cosa succede a: ¬Q ⇒ ¬P

¬q ⇒ ¬p ≡ p ⇒ q ≡ s ≡ ¬p ∨ s ≡ ¬(p) ∨ (¬p) per come è definita l'implicazione

= ¬q ∨ p ≡ p ∨ ¬q per le commutative delle "v" quindi ¬p ∨ ¬q ≡ ¬q ⇒ ¬p :

Abbiamo allora: p ⇒ q = ¬p ∨ q ≡ ¬q ⇒ ¬p

NB: Grazie all'equivalenze: p ⇒ q ≡ ¬q ⇒ ¬p

Condizione necessaria e condizione sufficiente

Con l'operazione: p ➔ q

• p si dice condizione sufficiente affinché si realizzi q.
• q si dice condizione necessaria affinché si realizzi p.

Es.

• p: "A è un quadrato"
• q: "A è un rettangolo"
• p ➔ q: "se A è un quadrato allora A è un rettangolo"
• Essere un quadrato è condizione sufficiente per essere un rettangolo perché se sono un quadrato sono anche un rettangolo.
• Essere un rettangolo è condizione necessaria per essere un quadrato perché se non sono un rettangolo allora non posso nemmeno essere un quadrato.

NB: Fate attenzione al fatto che dire che p ➔ q è vera non significa dire che q è vera ➔ affinché p sia vera deve infatti verificarsi il rapporto.

Abbiamo quindi che: se p è vera e sappiamo che p⇒q, allora q è vera.

questo in simboli diventa: P ∧ (P⇒Q) ↔ Q

Tavola di verità

Una proposizione che ha valore di verità sempre VERO si definisce TAUTOLOGIA

È equivalente logica il simbolo ⇔

P↔Q si legge “P se e solo se Q”

P↔Q = (P⇒Q) ∧ (Q⇒P)

Tavola di verità per la tautologia

Predicati

Definizione di predicato

Si definisce predicato una proposizione in cui compare una variabile. Es.

p(x): "x è un numero dispari"

NB: La veridicità o meno di un predicato dipende dal valore assunto dalle variabili. Es.

p(x): "x è un numero dispari"

• x = 3 allora p(3) è vero
• x = 2 allora p(2) è falso

I predicati vengono utilizzati nelle definizioni degli insiemi quando un insieme ha definizione mediata per tramite una formula. Infatti possono definire un insieme A come:

A = { x ∈ X | p(x) }

Es.

p(x): "x è un numero dispari"

A = { x ∈ X | x è un numero dispari } = { x ∈ X | p(x) }

Esiste una relazione fra i connettivi logici e le operazioni fra insiemi:

• Definiamo:
• A = { x ∈ X | p(x) }
• B = { x ∈ X | q(x) }
• A è l'insieme costituito degli x tali per cui p(x) è vero

* Consideriamo ora il complementare di A (A^c)

• Il complementare di A è costituito da tutti gli elementi che non stanno in A.
• ↓ quindi da tutti gli elementi per cui p(x) non è vero → non tutti gli elementi per cui p(x) è vero: ¬p(x) è vero:

A^c = {x ∈ X | ¬p(x)} → tutti gli x tali per cui ¬p(x) è vero

* Consideriamo ora l’intersezione fra A e B

• Nell’intersezione devono essere contenuti tutti quegli elementi che stanno sia in A che in B.
• ↓ cioè quegli elementi che contemporaneamente quindi → vuol dire che va bene la “e”

A∩B = {x ∈ X | p(x) ∧ q(x)}

* Consideriamo ora invece l’unione di A e B

• Nell’unione devono essere contenuti tutti quegli elementi che stanno in A o in B.
• Lo c’è la “o” → quindi quelli che rendono vera p(x) o q(x)

A∪B = {x ∈ X | p(x) ∨ q(x)}

Predicati in più di una variabile

Si possono definire anche predicati in più di una variabile. x, y sono studenti del Politecnico.

Definiamo:

p(x, y): “x e y sono compagni di corso”

p(x, y) è vera per esempio se i cognomi di x e y iniziano con [FER, GEM] mentre non è vera se uno inizia con A e l'altro con B.

Quantificatori

Dato un predicato p(x) è naturale chiedersi:

• ? : p(x) è vero per ogni x? (per tutte le x)
• ? : Esiste un valore di x che mi rende vero p(x)?

Quantificatori

• ∀ = “per ogni” → Quantificatore Universale
• ∀ x p(x) → questa scrittura si intende dire che per ogni valore di x mi che p(x) è vera.
• ∃ = “esiste” → Quantificatore Esistenziale
• ∃ x p(x) → questa scrittura si intende dire che esiste almeno un valore di x tale per cui p(x) è vera → potrebbero essere più di uno.
• ∃! = “esiste ed è unico”
• ∃! x p(x) → esiste un unico valore di x tale per cui p(x) è vera.

Quando abbiamo definito i predicati abbiamo detto che un predicato è la variabile di verità quando assegniamo a x un valore. Un altro modo di dare un valore di verità ad un predicato è quello di esprimere un quantificatore che gli fa assumere automaticamente un valore di verità.

X = ℕ, x ∈ ℕ₀, - ℕ₀ = numeri naturali escluso lo 0

p(x) = "x è un numero dispari"

Se scrivo:

∀x p(x) = intendiamo: per ogni x con: per ogni valore di x che è un numero dispari

A questo punto possiamo dire che:

∀x p(x) è FALSA

questo perché ovviamente non tutti i numeri sono dispari.

Ordine nei quantificatori

Fate attenzione all’ordine dei quantificatori quando li applicate ad un predicato cambia completamente il significato in alcuni casi:

• ∀x, ∀y p(x,y) => si intende per ogni x e y se p(x,y) è vera
• ∃x, ∃y p(x,y) => si intende, esistono x e y tali per cui p(x,y) è vera
• ∀x ∃y p(x,y) → mi intende "per ogni x esiste un y tale per cui p(x,y) è vera"

Coú significa che preso un x possiamo trovare un y che può come requisito affinché p(x,y) è vera → ai particolari dele x diverse può si potrà bene avere due y diverse con cuires le moscow (il responsabile è che wone).

∃y ∀x p(x,y) → mi interede; esome: valero di qualcuno; mi nl y tale che queiem mi il valero un x remide p(x,y) vera

∀x ∃y p(x,y) ≠ ∃y ∀x p(x,y) sono molto diversi

x, y ∈ N

p(x,y) = "x è numero ufficiale di y" = "x ≤ y"

Sc oanniano:

1. ∀x ∃y p(x, y) → mi interede per ogni x emmo un y tale per cui p(x, y) è vera

Nel nostro orso:

∀x ∃y p(x, y) = per ogni x emmo un y tale per cui x ≤ y

quere è ouave vero in felinci miosi un calg valero de x pesonelo guiper trerore un valere de y tali per cui x ≤ y

2. Se scriviamo invece: ∃y ∀x . p(x,y) = "in M un valore di y tale per cui qualsiasi x in M il valore di x è tale che x ≤ y”

questa non è vera perché non possiamo trovare un numero naturale che non è più grande di tutti gli altri.

Negazione dei quantificatori

La negazione scambia i quantificatori!!!

In particolare si ha che:

¬(∀x p(x)) = ∃x ¬p(x)

p(x): "lo studente x ha studiato”

∀x p(x) = "per ogni studente x in M che lo studente x ha studiato"

¬(∀x p(x)) = "non tutti gli studenti hanno studiato”

"non esiste uno studente x che non ha studiato"

¬(∀x p(x))L = ∃x ¬p(x)

*Allo stesso modo:

¬(∃x p(x)) = ∀x ¬p(x)

¬(∃x p(x)) = non esiste studente x che abbia studiato = tutti gli studenti non hanno studiato

Quest'ultima equivalenza è molto importante perché ci permette di dimostrare le non veridicità ad un'affermazione con un contro esempio. È necessario trovare quell' x che non realizza più.

Esercizi

Negare i seguenti predicati:

1. ∀m,m ∈ N ∃c | cm ≥ m

I step: negazione

¬(∀m,m ∈ N ∃c | cm ≥ m)

II step: individuare il predicato

¬(∀m,m ∈ N ∃c | cm ≥ m)

quindi:

∃m,m ∈ N ¬(∃c | cm ≥ m)

prima parte e passo ai numeri:

¬(∃c | cm ≥ m) = ¬(∃c q(x))

¬(∃x q(x)) = ∀x ¬q(x)

= ∀c ¬(∃cm ≥ m) = ∀c cm < m

= > quindi [ ∃m,m ∈ N ∀c cm < m ]