Transcript
Di Emily Rinaldi
DI CHE COSA SI OCCUPA LA LOGICA La logica si occupa dell’esattezza dei ragionamenti
Nei tempi antichi solo verbale. Nell’epoca moderna la logica viene applicata per l’ordinamento sistemazione di numerose discipline (fisica, linguistica, biologia, economia…)
PROPOSIZIONI E VALORI DI VERITÁ Nella logica matematica si dice proposizione (o enunciato) un’espressione linguistica per la quale si possa dire che è vera oppure falsa. Esempio: p: Milano è una città del Piemonte
q: La Sicilia è un’isola
PROPOSIZIONI E VALORI DI VERITÁ Si parla pertanto di logica a due valori o binaria, in cui entrambe le proposizioni hanno lo stesso valore Esempio: v (p) = V
v (p) = F
DIVISIONE EUCLIDEA La divisione euclidea o divisione con resto è intuitivamente quell'operazione che si fa quando si suddivide un numero a di oggetti in gruppi di b oggetti ciascuno e quindi si conta quanti gruppi sono stati formati e quanti oggetti sono rimasti. Il numero a si chiama dividendo, il numero b è il divisore, il numero di gruppi formati è il quoziente e il numero di oggetti rimanenti il resto.
La possibilità di operare una tale suddivisione per ogni divisore e ogni dividendo diverso dallo zero è stabilita dal seguente
DIVISIONE EUCLIDEA Teorema Dati due interi a e b con b≠0 esiste un'unica coppia di interi q ed r detti quoziente e resto tali che: a=b×q+r 0≤r<|b| dove | b | indica il valore assoluto del divisore.
PROPOSIZIONI SEMPLICI E PROPOSIZIONI COMPOSTE Proposizioni semplici (atomiche): presentano un soggetto, un verbo e un complemento. Esempio: Giulio ascolta la musica
PROPOSIZIONI SEMPLICI E PROPOSIZIONI COMPOSTE Proposizioni composte (molecolari): si possono scomporre in proposizioni semplici. Esempio: r: Marisa canta e studia
p: Marisa canta r=peq
q: Marisa studia
PROPOSIZIONI SEMPLICI E PROPOSIZIONI COMPOSTE Viceversa date due proposizioni semplici: Esempio:
p: Piove
q: il mare è calmo
PROPOSIZIONI SEMPLICI E PROPOSIZIONI COMPOSTE Possiamo formare numerose proposizioni composte: Esempio:
Piove e il mare è calmo / Non piove e il mare è calmo Se piove, allora il mare non è calmo
Pertanto avremo la proposizione composta r = p e q: Piove e il mare è calmo
di cui dobbiamo dire il valore di verità di r.
PROPOSIZIONI SEMPLICI E PROPOSIZIONI COMPOSTE Per fare questo occorre conoscere : Il valore di verità di ciascuna delle proposizioni semplici p e q; Il significato della parola «e» con la quale abbiamo collegato p e q
CONNETTIVI LOGICI I connettivi logici fondamentali sono cinque:
non e o se… allora se e solo se
A) IL CONNETTIVO non Definizione: Il connettivo non opera su una proposizione p producendo una proposizione p̅, avente valore di verità opposto a quello di p. Il simbolo del connettivo non è un trattino soprasegnanto: non p = p̅ La negazione è un’operazione binaria.
A) IL CONNETTIVO non P: Roberta è stata promossa. Roberta è stata promossa.
non p: Non è vero che
Otteniamo una proposizione detta negazione L’uso del simbolo ¯ è reso più evidente dalla seguente tavola della verità: p V F
p̅ F V
A) IL CONNETTIVO non Esempio: Vi ricordate la definizione di differenza tra due insiemi: A-B= composto da elementi di A ed elementi che non stanno in B. Anche in questo esempio c’è il connettivo non.
A
1 2
4 3
4 6
5 3
B
A) IL CONNETTIVO non Il simbolo p̿ significa negazione di negazione di p, costruiamo la tavola di verità della proposizione: p
p̅
p̿
V
F
V
F
V
F
I valori di verità di p̅̅ sono gli stessi di p: questo ò il principio della doppia negazione, cioè due negazioni affermano.
B) IL CONNETTIVO e Definizione: Il connettivo e opera su due proposizioni p e q, producendo una proposizione p Ʌ q che è vera solo quando p e q sono entrambe vere e falsa in tutti gli altri casi. Il suo nome è congiunzione. Il simbolo del connettivo e è Ʌ. Alla congiunzione di due proposizioni logiche si dà anche il nome di prodotto logico e per esso si può usare il simbolo × invece di Ʌ. La congiunzione è un’operazione binaria.
B) IL CONNETTIVO e Esempio: p: Marisa canta. p Ʌ q: Marisa canta e studia. p V V F F
q V F V F
q: Marisa studia.
pɅq V F F F
C) IL CONNETTIVO o Definizione: Il connettivo o opera su due proposizioni p e q, producendo una proposizione p ᴠ q che è vera se è vera almeno una delle proposizioni p e q ed è falsa solo se p e q sono entrambe false. Il suo nome è disgiunzione. Il simbolo della disgiunzione è V (dal latino vel che significa o). Alla disgiunzione si dà anche il nome di somma logica e per essa si usa, a volte il simbolo + al posto di V.
C) IL CONNETTIVO o Esempio: p: Oggi piove. p ᴠ q: Oggi piove o fa freddo. p V V F F
q V F V F
q: Oggi fa freddo.
pɅq V F F F
B-C) I CONNETTIVI e-o Esempio: Le definizioni di unione e intersezione tra gli insiemi sono un esempio per i connettivi e-o. A V B = A unione B = A o B A Ʌ B = A intersezione B = A e B
A
B 1
2 3
3
4 5
CONNETTIVI E LINGUAGGIO COMUNE Vediamo se il significato dei connettivi è uguale nel linguaggio comune come nella logica. a) Anche nel linguaggio comune la parola non esprime una negazione. Esempio: LINGUAGGIO COMUNE «io non ho un libro di matematica.» LOGICA «Non è vero che io ho un libro di matematica.»
CONNETTIVI E LINGUAGGIO COMUNE b) La congiunzione e viene usata nel linguaggio comune per lo più con lo stesso significato che ha nella logica. Esempio: «Marisa canta e studia.» Con questa frase intendiamo affermare che Marisa fa simultaneamente le due cose. Talvolta però nel linguaggio comune la parola e viene utilizzata per indicare due azioni consecutive nel tempo e non simultanee; per esempio: «Prendo l’ombrello e vengo.» In logica, dobbiamo escludere questo significato per la e.
CONNETTIVI E LINGUAGGIO COMUNE c) Nel caso del connettivo o il confronto con il linguaggio comune diventa un po’ più complicato. Nel linguaggio comune la frase «Marisa studia o canta.» il suo solito significato è: o Marisa studia e non canta, o canta e non studia. Questo però non è il significato in logica; qui la proposizione ha tre significati: 1. Marisa studia e non canta. 2. Marisa canta e non studia. 3. Marisa canta e studia simultaneamente. In logica la o non è esclusiva e per esserlo bisognerebbe dire «Marisa o studia o canta.».
I CONNETTIVI SE… ALLORA E SE E SOLO SE Definizione: Il connettivo → opera su due proposizioni p e q, producendo una terza proposizione p → q che è falsa solo quando p è vera e q è falsa; in tutti gli altri casi è vera. Se… allora è una proposizione che viene utilizzata nelle proposizioni in cui è presente una condizione. La proposizione composta collegando due proposizioni p e q con se… allora si chiama implicazione materiale oppure condizionale. Il simbolo di questo connettivo è una freccia:
p→q
I CONNETTIVI SE… ALLORA E SE E SOLO SE Nella scrittura p → q, che si legge «se p allora q», oppure «p implica p», p prende il nome di antecedente e q il nome di conseguente. Anche questo connettivo è un’operazione binaria. Questo connettivo viene anche chiamato connettivo implicazione.
CONNETTIVI SE… ALLORA E SE E SOLO SE Esempio: «Se il tempo è bello, allora faccio una passeggiata.» Composta dalle proposizioni elementari (primarie): p: il tempo è bello q: faccio una passeggiata può essere scritta in questo modo: se p, allora q. p V V F F
q V F V F
P→q V F V V
CONNETTIVI SE… ALLORA E SE E SOLO SE Il connettivo implicazione è strettamente collegato al connettivo doppia implicazione o bicondizionale, il cui simbolo è la doppia freccia ↔. Definizione: Il connettivo ↔ opera su due proposizioni p e q, producendo una proposizione p ↔ q che è vera solo quando p e q sono entrambe vere o entrambe false. La proposizione p ↔ q si legge: p se e solo se q. p V V F F
q V F V F
p↔q V F F V
ESSPRESSIONI PROPOSIZIONALI Quello che ha noi importa di una proposizione composta è stabilire come varia il suo valore di verità al variare del valore di verità delle proposizioni semplici che lo compongono. Esempio: Nella proposizione composta p Ʌ q, p e q sono considerate variabili proposizionali, come in algebra le lettere sono variabili numeriche. L’insieme dei valori di una variabile proposizionale è costituito soltanto da due elementi, V e F. Se le variabili presenti in un’espressione proposizionale sono n, la relativa tavola di verità presenta 2ⁿ righe.
LE LEGGI DELLA LOGICA Le proposizioni che sono solamente vere si chiamano tautologie o leggi della logica, i valori di verità di quelle proposizioni sono indipendenti dai valori di verità delle proposizioni che le compongono. Per indicare che un’espressione proposizionale r è una tautologia si scrive: |= r
LE LEGGI DELLA LOGICA PRINCIPIO DEL TERZO ESCLUSO Per ogni proposizione p, o p è vera o p è falsa. Nella logica a due valori non esiste una terza possibilità. |= p V p̅
PRINCIPIO DI NON CONTRADDIZIONE Una proposizione non può essere contemporaneamente vera e falsa; è falso, cioè, che siano simultaneamente vere una proposizione p e la sua negazione p̅. |= sopra lineatura p Ʌ p̅
ESPRESSIONI LOGICAMENTE EQUIVALENTI Definizione: Due espressioni proposizionali r ed s si dicono logicamente equivalenti se l’espressione r ↔ s è sempre vera, ossia se risulta: |= r ↔ s Per indicare che r ed s sono logicamente equivalenti si scrive: r ˂=˃ s
o addirittura: r=s
ESPRESSIONI LOGICAMENTE EQUIVALENTI Definizione: Se due proposizioni sono logicamente equivalenti, allora esse hanno la stessa tavola di verità. Proposizioni che hanno la stessa tavola di verità sono logicamente equivalenti.
ESPRESSIONI LOGICAMENTE EQUIVALENTI Il valore di un’espressione proposizionale non si altera se al posto di una proposizione semplice o composta che vi compare si sostituisce una proposizione a essa logicamente equivalente .
r V V F F
s V F V F
r ˂=˃ s V F F V
PROPRIETÁ DEI CONNETTIVI Ʌ E V La proposizione p Ʌ q è logicamente equivalente alla proposizione q Ʌ p, quindi l’uguaglianza logica pɅq=qɅp esprime la proprietà commutativa del connettivo Ʌ. (p Ʌ q) Ʌ r = p Ʌ (q Ʌ r)
p Ʌ (q V r) = (p Ʌ q) V (p Ʌ r)
queste sono uguaglianze che esprimono la proprietà associativa del connettivo Ʌ e la proprietà distributiva del connettivo Ʌ rispetto al connettivo V.
PROPRIETÁ DEI CONNETTIVI Ʌ E V
pɅq=qɅp pVq=qVp (p Ʌ q) Ʌ r = p Ʌ (q Ʌ r) (p V q) V r = p V (q V r) p Ʌ (q V r) = (p Ʌ q) V (p Ʌ r) p V (q Ʌ r) = (p V q) Ʌ (p V r)
commutativa di Ʌ commutativa di V associativa di Ʌ associativa di V distributiva di Ʌ rispetto a V distributiva di V rispetto a Ʌ
ALTRE PROPRIETÁ DEI CONNETTIVI I connettivi Ʌ e V sono distributivi l’uno rispetto all’altro. p
p
pɅp
p
p
pVp
V
V
V
V
V
V
F
F
F
F
F
F
Le equivalenze logiche che si ricavano sono: pɅp=p pVp=p
legge di idempotenza di Ʌ legge di idempotenza di V
ALTRE PROPRIETÁ DEI CONNETTIVI Ci sono anche le leggi di assorbimento: p V (p Ʌ q) = p p Ʌ (p V q) = p Le leggi importanti di e, o e non: (sopra lineatura) p Ʌ q = p̅ V q̅ (sopra lineatura) p V q = p̅ Ʌ q̅
1^ legge di De Morgan 2^ legge di De Morgan
Esempio: p: Gino studia. q: Laura canta. (sopra lineatura) p V q: Non è vero che Gino studia o Laura canta
LEGGE DELLA CONTRINVERSA p→q Scambiando la p con la q, otteniamo la nuova proposizione q→p che si chiama inversa di quella di partenza, che chiameremo perciò diretta.
Se nell’implicazione diretta p → q neghiamo la p e la q otteniamo l’implicazione
LEGGE DELLA CONTRINVERSA p̅ → q̅ che si dice contraria a quella di partenza. Negando infine la p e la q nell’implicazione inversa q → p, otteniamo l’implicazione q̅ → p̅ che si dice contrinversa (cioè la contraria dell’inversa) dell’implicazione di partenza p→q
LEGGE DELLA CONTRINVERSA Riassumendo: p→q
diretta
q→p
inversa
p̅ → q̅
contraria
q̅ → p̅
controinversa
Sussiste l’uguaglianza logica tra l’implicazione diretta p → q p → q = q̅ → p̅
che esprime la legge della contrinversa. mentre non esiste alcuna uguaglianza logica tra l'implicazione diretta e la sua inversa, né tra la diretta e la sua contraria.
LEGGE DELLA CONTRINVERSA Esempio: p: Mario è italiano.
q: Mario è europeo.
L’implicazione p → q: Se Mario è italiano allora è europeo. È logicamente equivalente alla contrinversa q̅ → p̅: Se Mario non è europeo allora non è italiano. ma non è equivalente né all'inversa q → p: Se Mario è europeo allora è italiano.
Né alla contraria p̅ → q̅: Se Mario non è italiano allora non è europeo
L'IMPLICAZIONE LOGICA Definizione: date due espressioni proposizionali r ed s, si dice che r implica logicamente s, o che s è conseguenza logica di r, se risulta: |= r → s Per indicare che r implica logicamente s scriveremo: r =˃ s
L'IMPLICAZIONE LOGICA Ciò che deve invece sempre verificarsi è che ogni volta che è vera r dovrà essere necessariamente vera anche s; è proprio questo carattere di necessità che fa dell’implicazione logica il fondamento della deduzione. Ricordiamoci che se r ed s sono due espressioni proposizionali logicamente equivalenti, risulta: |= r ↔ s
Ossia: r ˂=˃ s questa scrittura significa che r implica logicamente s e che, simmetricamente, s implica logicamente r.
RIFLETTIAMO SUI SIMBOLI →, ↔, =˃, ˂=˃ I simboli → e ↔ rappresentano connettivi logici mediante i quali, partendo da proposizioni assegnate, si costruiscono altre proposizioni. I simboli =˃ e ˂=˃ esprimono relazioni logiche tra proposizioni e non conducono ad altre proposizioni. I primi, in quanto simboli di operazioni, sono interni al calcolo proposizionale; i secondi non fanno parte del calcolo proposizionale, ma hanno la funzione di descriverne, dall’esterno, aspetti e peculiarità.
RIFLETTIAMO SUI SIMBOLI →, ↔, =˃, ˂=˃ Date le due proposizioni p e q, la forma: p → q indica una proposizione vera o falsa secondo i casi ed è perciò interna al calcolo. La forma: p =˃ q non è una proposizione, ma descrive dall’esterno del calcolo proposizionale, la proposizione p → q, attribuendo la proprietà di essere vera in ogni caso, di essere cioè una tautologia: |= p → q Ne discende che anche il simbolo |= non fa parte del calcolo proposizionale ma, come =˃ e ˂=˃, appartiene al linguaggio che descrive, dall’esterno, il calcolo stesso.
REGOLE DI INFERENZA Definizione: Si dice che un ragionamento è valido quando la sua conclusione C è implicata logicamente dalla congiunzione p₁ Ʌ p₂ Ʌ … Ʌ p ̯delle sue premesse. In simboli, possiamo scrivere il seguente schema dimostrativo: (p₁ Ʌ p₂ Ʌ … Ʌ p ̯) =˃ C
Quando un ragionamento è valido, dalla verità di tutte le sue premesse si deduce la verità della conclusione. Un ragionamento non valido si chiama fallace.
REGOLE DI INFERENZA Ogni schema può essere considerato come una regola di inferenza. A) Regola di inferenza del modus ponens
Definizione: Se è vera l’implicazione a → b ed è vero l’antecedente a, allora è vero anche il conseguente b. [(a → b) Ʌ a] =˃ b
REGOLE DI INFERENZA Esempio: date le due proposizioni:
a: Piero studia.
b: Piero sarà promosso
la regola di deduzione del modus pones può essere cosi schematizzata: Se Piero studia allora sarà promosso. Piero studia. Piero sarà promosso.
REGOLE DI INFERENZA B) Regola di inferenza del modus tollens Definizione: Se è vera l’implicazione a → b ed è vera b̅ (cioè falsa b), allora è vera anche a̅ (cioè falsa a). [(a → b) Ʌ b̅] =˃ a̅
REGOLE DI INFERENZA Esempio: Date le due proposizioni: a: Sono stanco.
b: Smetto di studiare.
Lo schema dimostrativo del modus tollens può essere cosi espresso: Se sono stanco allora smetto di studiare. Non smetto di studiare. Non sono stanco.
REGOLE DI INFERENZA C) Legge di transitività del condizionale Definizione: Se è vera l’implicazione a → b ed è vera l’implicazione b → c, allora è vera l’implicazione a → c. [(a → b) Ʌ (b → c)] =˃ (a → c)
REGOLE DI INFERENZA Esempio: Date le tre proposizioni: a: Fa freddo.
b: Resto in casa
c: Guardo la TV
lo schema di transitività del condizionale assume la forma: Se fa freddo allora resto in casa. (premessa maggiore) Se resto in casa allora guardo la TV. (premessa minore) Se fa freddo allora guardo la TV.
IL RUOLO DELLE CONTRADDIZIONI Alle proposizioni sempre false si dà il nome di contraddizioni. Definizione: Se r è una tautologia allora r̅ è una contraddizione e, viceversa, se r è una contraddizione, allora r̅ è una tautologia. Il simbolo di contraddizione è V=. |= r r è una tautologia V= r |= r̅ r è una contraddizione V= r̅
r non è una tautologia r on è una contraddizione
IL RUOLO DELLE CONTRADDIZIONI (p Ʌ p̅) =˃ q questa espressione prende il nome di LEGGE DI LEWIS Definizione: essa afferma che da una contraddizione può essere logicamente dedotta qualunque proposizione.
IL RUOLO DELLE CONTRADDIZIONI La dimostrazione per assurdo è un procedimento dimostrativo mediante la quale si stabilisce la verità di una proposizione a come conseguenza logica del fatto che l’averla negata indica una contraddizione (b Ʌ b̅). [a̅ → (b Ʌ b̅)] =˃ a
Concludiamo dicendo che la matematica è la scienza logica per eccellenza perché è possibile dedurre tutto e il contrario di tutto.
DOMANDE ?
