Logica di Base - UniPamath.unipa.it/~fbenanti/LogicaSISSIS.pdf · 2008-01-05 · Modulo Didattico:...

Logica Formale

Proposizioni

Principi Logici

Proposizioni Composte

Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica

Contronominale e . . .

Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

of 29

Go Back

Full Screen

Close

Quit

Logica di Base

Docente: Francesca Benanti

5 gennaio 2008

Modulo Didattico: Complementi di Algebra

http://math.unipa.it/~fbenanti/

Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

of 29

Go Back

Full Screen

Close

Quit

1. Logica Formale

La logica e la disciplina filosofica che studia le forme del ra-gionamento corretto. Da Aristotele al secolo scorso la logicae stata impiegata in campo filosofico nelle argomentazioni ditipo essenzialmente metafisico. A partire dalla seconda metadel XIX secolo la logica e andata progressivamente liberan-dosi dei legami con psicologia e metafisica per avvicinarsisempre piu alla matematica.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 2 of 29

Go Back

Full Screen

Close

Quit

1. Logica Formale


Il tentativo di ricondurre la logica a calcolo e stato un obi-ettivo di uno dei piu grandi logici e filosofi del XVII seco-lo, Leibniz (1646-1716), che cerco una formalizzazione deiragionamenti in modo da operare con essi come si fa inalgebra.



http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Leibniz.html

Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 2 of 29

Go Back

Full Screen

Close

Quit

1. Logica Formale


Il tentativo di ricondurre la logica a calcolo e stato un obi-ettivo di uno dei piu grandi logici e filosofi del XVII seco-lo, Leibniz (1646-1716), che cerco una formalizzazione deiragionamenti in modo da operare con essi come si fa inalgebra.

Leibniz affermo: ...le verita vengono de-dotte dalla mente umana in virtu di unmetodo di calcolo come nell’aritmetica enell’algebra e che quindi, quando sorger-anno controversie fra due filosofi, nonsara piu necessaria una discussione,come non lo e tra due persone

che effettuano calcoli. Sara sufficiente, infatti, che essi pren-

dano in mano le penne, si siedano di fronte agli abachi e sidicano l’un l’altro: calculemus!...



http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Leibniz.html

Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 3 of 29

Go Back

Full Screen

Close

Quit

La logica matematica nasce con Boole(1815-1864) e con la sua idea di appli-care alla vecchia logica aristotelica le re-gole e i procedimenti dell’algebra. Booleriprendeva su basi nuove le intuizionisvolte da Leibniz in questa direzionemolto tempo prima.

In seguito Frege (1848-1925) sviluppo genialmente il progettodi Boole e Peano (1858-1932) gli conferı quel rigore e quel-la chiarezza simbolica che ispiro i logici formali del secoloscorso:

ogni ragionamento poteva venir ridotto ad unpuro calcolo formale



http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Boole.html

http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Frege.html

http://www-groups.dcs.st-andrews.ac.uk/~history/Mathematicians/Peano.html

Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 4 of 29

Go Back

Full Screen

Close

Quit

La logica, dunque, ha come oggetto di studio la correttezzadei ragionamenti. Un ragionamento e logicamente correttoquando e formato da una catena di affermazioni ricavate leune dalle altre attraverso passaggi corretti.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 4 of 29

Go Back

Full Screen

Close

Quit


Ma come si puo valutare se e corretto un passaggio da un’af-fermazione ad un’altra? E, quindi, come possiamo valutarese un ragionamento e o meno corretto?



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 4 of 29

Go Back

Full Screen

Close

Quit



La logica si interessa del problema di stabilire un rigoroso mo-do di procedere nel passare da un’affermazione vera ad un’al-tra vera, nel ricavare da alcune premesse delle conseguen-ze. Analizza i passaggi che permettono di dedurre un’affer-mazione a partire da alcune ipotesi.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 4 of 29

Go Back

Full Screen

Close

Quit



La logica si interessa del problema di stabilire un rigoroso mo-do di procedere nel passare da un’affermazione vera ad un’al-tra vera, nel ricavare da alcune premesse delle conseguen-ze. Analizza i passaggi che permettono di dedurre un’affer-mazione a partire da alcune ipotesi.

L’interesse della logica non e percio rivolto al contenuto diun ragionamento, quanto alla forma con cui il ragionamentosi sviluppa. Si parla, pertanto, di

LOGICA FORMALE

Le regole della logica sono regole sintattiche, ossia regole cheriguardano lo schema di un ragionamento o lo schema diformazione di una frase, indipendentemente dal significatoche essi esprimono.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 5 of 29

Go Back

Full Screen

Close

Quit

2. Proposizioni

I primi oggetti di cui si occupa la logica sono gli enunciati oproposizioni.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 5 of 29

Go Back

Full Screen

Close

Quit

2. Proposizioni


Definizione:Una proposizione o enunciato e una frase acui e possibile attribuire un valore di verita, ossia per laquale si puo dire con certezza e senza ambiguita se esprimeun’affermazione vera o falsa.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 5 of 29

Go Back

Full Screen

Close

Quit

2. Proposizioni



Esempi:



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 5 of 29

Go Back

Full Screen

Close

Quit

2. Proposizioni



Esempi:

• A ≡ 3 e un numero primo; SI

• B ≡ Il gatto studia matematica; SI

• C ≡ La mosca e un insetto; SI

• D ≡ Attento a quel che fai! NO

• E ≡ Che ora e? NO

• F ≡ Carlo arrivo la casa. NO



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 5 of 29

Go Back

Full Screen

Close

Quit

2. Proposizioni



Esempi:

• A ≡ 3 e un numero primo; SI

• B ≡ Il gatto studia matematica; SI

• C ≡ La mosca e un insetto; SI

• D ≡ Attento a quel che fai! NO

• E ≡ Che ora e? NO

• F ≡ Carlo arrivo la casa. NO

Osservazione: Non sono proposizioni le domande, le escla-mazioni, le frasi non corrette sintatticamente.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 6 of 29

Go Back

Full Screen

Close

Quit

3. Principi Logici

I possibili valori di verita di una proposizione sono due:

V= Vero

F= Falso



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 6 of 29

Go Back

Full Screen

Close

Quit

3. Principi Logici


V= Vero

F= Falso

Si parla pertanto di

LOGICA BINARIA



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 6 of 29

Go Back

Full Screen

Close

Quit

3. Principi Logici


V= Vero

F= Falso


LOGICA BINARIA

I principi logici che regolano la verita delle proposizioni sono:

Principio di non contraddizione: Non e possibileche una proposizione sia vera e sia falsa.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 6 of 29

Go Back

Full Screen

Close

Quit

3. Principi Logici


V= Vero

F= Falso


LOGICA BINARIA

I principi logici che regolano la verita delle proposizioni sono:

Principio di non contraddizione: Non e possibileche una proposizione sia vera e sia falsa.

Principio del terzo escluso: Una proposizione o evera o e falsa, non esiste una terza possibilita.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 7 of 29

Go Back

Full Screen

Close

Quit

4. Proposizioni Composte

Le proposizioni semplici o atomiche sono quelle formate daun soggetto, un predicato e un oggetto. Nei ragionamenti,pero, spesso utilizziamo proposizioni piu complesse, ottenutea partire da altre piu semplici: Proposizioni Composte.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 7 of 29

Go Back

Full Screen

Close

Quit



Problema:

1. Come costruire una propo-sizione composta?

2. Come stabilire la verita di unaproposizione composta?



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 7 of 29

Go Back

Full Screen

Close

Quit



Problema:

1. Come costruire una propo-sizione composta?

2. Come stabilire la verita di unaproposizione composta?

Risposta:1. CONNETTIVI LOGICI

2. TAVOLE DI VERITA



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 8 of 29

Go Back

Full Screen

Close

Quit

5. Connettivi Logici

I tre connettivi logici principali:



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 8 of 29

Go Back

Full Screen

Close

Quit



1. Congiunzione: AND (∧);

2. Disgiunzione: OR (∨);

3. Negazione: NOT (¬).



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 8 of 29

Go Back

Full Screen

Close

Quit






Esempi:



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 8 of 29

Go Back

Full Screen

Close

Quit






Esempi:

• A ≡ 3 e un numero primo,B ≡ 2 e un numero primo,A∧B ≡ 3 e un numero primo e 2 e un numero primo.

• A ≡ 8 e multiplo di 2,B ≡ 7 e multiplo di 2,A ∨B ≡ 8 e multiplo di 2 o 7 e multiplo di 2.

• A ≡ 3 e un numero primo,¬A ≡ 3 non e un numero primo.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 9 of 29

Go Back

Full Screen

Close

Quit

6. Tavole di Verita

Le tabelle della verita sono tabelle matematiche usate nellalogica per determinare se, attribuiti i valori di verita alleproposizioni che la compongono, una determinata propo-sizione e vera o falsa.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 9 of 29

Go Back

Full Screen

Close

Quit

6. Tavole di Verita

Le tabelle della verita sono tabelle matematiche usate nellalogica per determinare se, attribuiti i valori di verita alleproposizioni che la compongono, una determinata propo-sizione e vera o falsa.

1. Congiunzione AND (∧):

A ∧B e vera se e solo seA e B sono entrambe vere.

A B A ∧BV V VV F FF V FF F F

2. Disgiunzione OR (∨):

A ∨B e vera se e solo seA e vera oppure B e vera.

A B A ∨BV V VV F VF V VF F F

3. Negazione NOT (¬):

¬A e vera se e solo seA e falsa.

A ¬AV FF V



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 10 of 29

Go Back

Full Screen

Close

Quit

7. Tautologie, contraddizioni...

Definizione: Si definisce tautologia una proposizione chee sempre vera qualunque siano i valori di verita delle propo-sizioni che la compongono. (T )



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 10 of 29

Go Back

Full Screen

Close

Quit



Esempio:

A ∨ ¬A e una tautologia.A ¬A A ∨ ¬AV F VF V V



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 10 of 29

Go Back

Full Screen

Close

Quit



Esempio:


Definizione: Si definisce contraddizione una proposizioneche e sempre falsa qualunque siano i valori di verita delleproposizioni che la compongono. (C)



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 10 of 29

Go Back

Full Screen

Close

Quit



Esempio:



Esempio:

A ∧ ¬A e una contraddizione.

A ¬A A ∧ ¬AV F FF V F



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 10 of 29

Go Back

Full Screen

Close

Quit



Esempio:



Esempio:

A ∧ ¬A e una contraddizione.

A ¬A A ∧ ¬AV F FF V F

Definizione: Due proposizioni si dicono logicamente equiv-alenti se hanno la stessa tavola di verita. (=)



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 11 of 29

Go Back

Full Screen

Close

Quit

8. Proprieta dei Connettivi Logici

1. Idempotenza:A ∨ A = A, A ∧ A = A;



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 11 of 29

Go Back

Full Screen

Close

Quit



2. Associativa:(A ∨B) ∨ C = A ∨ (B ∨ C),(A ∧B) ∧ C = A ∧ (B ∧ C);



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 11 of 29

Go Back

Full Screen

Close

Quit




3. Commutativa:A ∨B = B ∨ A, A ∧B = B ∧ A;



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 11 of 29

Go Back

Full Screen

Close

Quit





4. Distributiva:A ∨ (B ∧ C) = (A ∨B) ∧ (A ∨ C),A ∧ (B ∨ C) = (A ∧B) ∨ (A ∧ C);



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 11 of 29

Go Back

Full Screen

Close

Quit






5. Legge dei neutri:A ∨ C = A, A ∨ T = T ,A ∧ C = C, A ∧ T = A;



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 11 of 29

Go Back

Full Screen

Close

Quit







6. Complemento:A ∨ ¬A = T , A ∧ ¬A = C,¬(¬A) = A, ¬(C) = T , ¬(T ) = C;



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 11 of 29

Go Back

Full Screen

Close

Quit







6. Complemento:A ∨ ¬A = T , A ∧ ¬A = C,¬(¬A) = A, ¬(C) = T , ¬(T ) = C;

7. Leggi di De Morgan:¬(A ∨B) = ¬A ∧ ¬B,¬(A ∧B) = ¬A ∨ ¬B.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 12 of 29

Go Back

Full Screen

Close

Quit

9. Leggi di De Morgan

Leggi di De Morgan:

¬(A ∨B) = ¬A ∧ ¬B

Tavola di verita di ¬(A ∨B):

A B A ∨B ¬(A ∨B)V V V FV F V FF V V FF F F V

Tavola di verita di ¬A∧¬B:

A B ¬A ¬B ¬A ∧ ¬BV V F F FV F F V FF V V F FF F V V V



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 13 of 29

Go Back

Full Screen

Close

Quit

Esercizi:

1. P ≡ 30 e multiplo di 7,Q ≡ 30 e multiplo di 6.

Costruite le seguenti proposizioni e stabilite quali sonovere e quali false:

• P ∧Q;

• ¬Q;

• ¬P ∧Q;

• P ∨ (¬Q).

2. Dimostrate le proprieta dei Connettivi Logici;

3. Negare le seguenti affermazioni:

a) Luca ama il mare ma non la barca;

b) Angela e Maria hanno gli occhi verdi.

ESERCIZI



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 14 of 29

Go Back

Full Screen

Close

Quit

10. Implicazione logica

Implicazione Logica (A ⇒ B):

A ⇒ B e falsa se e solo seA e vera e B e falsa,in tutti gli altri casi e vera.

A B A ⇒ BV V VV F FF V VF F V

A e detta antecedente o premessa,

B e detta conseguente o conseguenza.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 14 of 29

Go Back

Full Screen

Close

Quit







Osservazione: Se la premessa e falsa l’implicazione e sem-pre vera!



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 14 of 29

Go Back

Full Screen

Close

Quit







Osservazione: Se la premessa e falsa l’implicazione e sem-pre vera!

Osservazione: A ⇒ B = ¬A ∨B


A B ¬A ¬A ∨BV V F VV F F FF V V VF F V V



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 15 of 29

Go Back

Full Screen

Close

Quit

Osservazione: A ⇒ B puo essere espressa:

• Condizione sufficiente per B e A;

• Condizione necessaria per A e B.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 16 of 29

Go Back

Full Screen

Close

Quit

11. Contronominale e Inversa

Da una proposizione del tipo A ⇒ B ne possiamo ricavarealtre due

• la sua Contronominale: ¬B ⇒ ¬A;

• la sua Inversa: B ⇒ A.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 16 of 29

Go Back

Full Screen

Close

Quit





Osservazione: A ⇒ B = ¬B ⇒ ¬A


A B ¬A ¬B ¬B ⇒ ¬AV V F F VV F F V FF V V F VF F V V V



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 16 of 29

Go Back

Full Screen

Close

Quit





Osservazione: A ⇒ B = ¬B ⇒ ¬A


A B ¬A ¬B ¬B ⇒ ¬AV V F F VV F F V FF V V F VF F V V V

Esempi:

a) Se manca la corrente si ferma l’ascensore,Se non si ferma l’ascensore non manca la corrente;

b) Se un numero e negativo allora e minore di 1,Se un numero non e minore di 1 allora non e negativo;

c) Se hai un fratello allora non sei figlio unico,Se sei figlio unico allora non hai un fratello.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 16 of 29

Go Back

Full Screen

Close

Quit

Osservazione: Se A ⇒ B non e detto che B ⇒ A.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 16 of 29

Go Back

Full Screen

Close

Quit

Osservazione: Se A ⇒ B non e detto che B ⇒ A.

Esempio:A B A ⇒ B B ⇒ AF V V F



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 17 of 29

Go Back

Full Screen

Close

Quit

12. Doppia Implicazione

Doppia Implicazione (A ⇔ B):

A ⇔ B e vera se e solo seA e B son entrambe vere o false.

A B A ⇔ BV V VV F FF V FF F V



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 17 of 29

Go Back

Full Screen

Close

Quit

12. Doppia Implicazione

Doppia Implicazione (A ⇔ B):

A ⇔ B e vera se e solo seA e B son entrambe vere o false.

A B A ⇔ BV V VV F FF V FF F V

Osservazione: La doppia implicazione e equivalente a:

• La premessa (A) e condizione necessaria e sufficienteper la conseguenza (B);

• La conseguenza (B) e condizione necessaria e suffi-ciente per la premessa (A).



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 18 of 29

Go Back

Full Screen

Close

Quit

Esercizi:

• Costruisci l’inversa e la contronominale delle seguentiproposizioni:

∗ Se un animale cammina allora e vivo;

∗ Se salti in alto piu di 1 metro e 90 cm sei ammessoalle Olimpiadi;

∗ Condizione necessaria affinche due poligoni siano sim-ili e che abbiano gli angoli di uguale ampiezza;

∗ Condizione sufficiente affinche due poligoni siano sim-ili e che abbiano gli angoli di uguale ampiezza;

∗ Condizione necessaria affinche due figure si corrispon-dano in una affinita e che segmenti paralleli cor-rispondano a segmenti paralleli;

∗ Se hai nazionalita italiana, sei maggiorenne e non seiinterdetto al voto, voterai domenica.

• Riscrivi le seguenti proposizioni utilizzando i termi-ni condizione necessaria, condizione sufficiente, con-dizione necessaria e sufficiente:

∗ Se un triangolo ha un asse di simmetria allora eisoscele e se e isoscele ha un asse di simmetria;

∗ Se un numero e intero allora e razionale;

∗ Sei iscritto alle liste di leva se e solo se sei maschio ehai diciotto anni.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 19 of 29

Go Back

Full Screen

Close

Quit

13. Teorema

Un teorema non e altro che una proposizione data sottoforma di implicazione logica:

TEOREMA: A ⇒ B

A = Ipotesi;

B = Tesi.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 20 of 29

Go Back

Full Screen

Close

Quit

14. Dimostrazione

Sono equivalenti le seguenti proposizioni:

1. A ⇒ B;

2. ¬B ⇒ ¬A;

3. ¬A ∨B;

4. ¬(A ∧ ¬B).



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 20 of 29

Go Back

Full Screen

Close

Quit

14. Dimostrazione

Sono equivalenti le seguenti proposizioni:

1. A ⇒ B;

2. ¬B ⇒ ¬A;

3. ¬A ∨B;

4. ¬(A ∧ ¬B).

L’equivalenza semantica delle formule 1, 2 e 4 e collegata a trediverse possibilita per dimostrare un teorema. Precisamente:

1. Dimostrazione diretta:A ⇒ B;

2. Dimostrazione indiretta o per contrapposizione:¬B ⇒ ¬A;

3. Dimostrazione per assurdo:¬(A ∧ ¬B).



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 20 of 29

Go Back

Full Screen

Close

Quit

Esempio:



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 20 of 29

Go Back

Full Screen

Close

Quit

Esempio:

TEOREMA: Se a e b sono due interi dispari, allora a · be un intero dispari.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 20 of 29

Go Back

Full Screen

Close

Quit

Esempio:


Dimostrazione:

1. (Diretta) a = 2q + 1 e b = 2k + 1, q, k ∈ Z. Alloraab = (2q + 1)(2k + 1) = 4qk + 2q + 2k + 1 = 2(2qk +q + k) + 1 = 2r + 1, r ∈ Z. Dunque ab e dispari.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 20 of 29

Go Back

Full Screen

Close

Quit

Esempio:


Dimostrazione:


2. (Indiretta) Sia ab pari. Allora 2|ab. Dunque, per laproprieta: se un primo divide un prodotto divide unodei due fattori, 2|a oppure 2|b. Possiamo concludereche a e b non sono entrambi dispari.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 20 of 29

Go Back

Full Screen

Close

Quit

Esempio:


Dimostrazione:


2. (Indiretta) Sia ab pari. Allora 2|ab. Dunque, per laproprieta: se un primo divide un prodotto divide unodei due fattori, 2|a oppure 2|b. Possiamo concludereche a e b non sono entrambi dispari.

3. (Per assurdo) Ragioniamo per assurdo e supponiamoche ab non sia dispari mentre a e b sono entrambi dis-pari. Allora si ha: ab = 2s, a = 2q + 1 e b = 2k + 1con s, q, k ∈ Z. Dunque 2s = ab = (2q + 1)(2k + 1) =4qk + 2q + 2k + 1 = 2(2qk + q + k) + 1 = 2r + 1, conr ∈ Z. Pertanto 2|1. ASSURDO!



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 21 of 29

Go Back

Full Screen

Close

Quit

15. Logica predicativa

Definizione: Un predicato o formula aperta e una frase checontiene almeno una variabile.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 21 of 29

Go Back

Full Screen

Close

Quit



Esempio: A(x) ≡ il numero naturale x e il doppio di 7.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 21 of 29

Go Back

Full Screen

Close

Quit




Osservazione: Ad un predicato non e possibile assegnareun valore di verita.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 21 of 29

Go Back

Full Screen

Close

Quit





Un predicato puo essere trasformato in una proposizione indue modi:

∗ sostituendo un valore alla variabile;

∗ quantificando una variabile, ossia facendo una asserzionesu quanti elementi, sostituiti alla variabile trasformanola formula in proposizione vera.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 21 of 29

Go Back

Full Screen

Close

Quit





Un predicato puo essere trasformato in una proposizione indue modi:

∗ sostituendo un valore alla variabile;

∗ quantificando una variabile, ossia facendo una asserzionesu quanti elementi, sostituiti alla variabile trasformanola formula in proposizione vera.

Esempi:

� A(10) ≡il numero naturale 10 e il doppio di 7;

� Esiste un numero naturale x che e il doppio di 7;

� Tutti i numeri naturali x sono il doppio di 7.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 22 of 29

Go Back

Full Screen

Close

Quit

16. Quantificatori

I quantificatori della Logica Matematica sono due:



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 22 of 29

Go Back

Full Screen

Close

Quit

16. Quantificatori


QuantificatoreUniversale:

Per ogni x vale la proprieta A(x):∀x, A(x).



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 22 of 29

Go Back

Full Screen

Close

Quit

16. Quantificatori




QuantificatoreEsistenziale:

Esiste un x per il quale vale laproprieta A(x): ∃x, A(x).



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 22 of 29

Go Back

Full Screen

Close

Quit

16. Quantificatori




QuantificatoreEsistenziale:

Esiste un x per il quale vale laproprieta A(x): ∃x, A(x).

Esempi:

� ∃x ∈ N tale che x = 2 · 7;

� ∀x ∈ N, x = 2 · 7.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 23 of 29

Go Back

Full Screen

Close

Quit

Osservazione: E possibile passare da un quantificatore adun altro utilizzando la negazione:

- Per ogni elemento x vale la proprieta P,- Non esiste un elemento x per cui non vale la proprieta P;

♦ Esiste un elemento x per cui non vale la proprieta P,♦ Non per ogni elemento x vale la proprieta P.

ESEMPI:

• Ogni gatto nero porta sfortuna,Non esiste un gatto nero che non porta sfortuna;

• Tutti sono usciti,Non esiste qualcuno che non e uscito;

• Non tutti sono entrati,Esiste qualcuno che non e entrato;

• Per ogni intero n se p|n e q|n allora pq|n,Non esiste un intero n tale che p|n, q|n e pq - n.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 24 of 29

Go Back

Full Screen

Close

Quit

Osservazione: Un quantificatore e la negazione dell’altro:

- Non per ogni elemento x vale la proprieta P,- Esiste un elemento x per cui non vale la proprieta P;

♦ Non esiste un elemento x per cui vale la proprieta P,♦ Per ogni elemento x non vale la proprieta P.

ESEMPI:

• La negazione dell’enunciato:

Per tutti i numeri naturali n, n + 2 > 8

e equivalente all’asserzione

Esiste un numero naturale n tale che n + 2 ≤ 8.

• La negazione dell’enunciato:

Esiste un pianeta abitabile

e equivalente all’asserzione

Tutti i pianeti sono inabitabili.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 25 of 29

Go Back

Full Screen

Close

Quit

Osservazione: Siano A(x) e B(x) due predicati. ScriviamoA(x) ⇒ B(x) se ogniqualvolta A(x) e vera allora e vera ancheB(x).



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 25 of 29

Go Back

Full Screen

Close

Quit


Esempio:A(x) ≡x e un intero relativo diverso da zero;B(x) ≡x2 e un intero positivo;

Allora A(x) ⇒ B(x).



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 25 of 29

Go Back

Full Screen

Close

Quit




Scriviamo A(x) 6⇒ B(x) se esiste un x per il quale A(x) evera ma B(x) e falsa.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 25 of 29

Go Back

Full Screen

Close

Quit




Scriviamo A(x) 6⇒ B(x) se esiste un x per il quale A(x) evera ma B(x) e falsa.

Esempio:A(x) ≡x e un intero positivo minore di 4;B(x) ≡x2 e un intero minore di 8;

Per x = 1: A(x) vera, B(x) vera;

Per x = 2: A(x) vera, B(x) vera;

Per x = 3: A(x) vera, B(x) falsa;

Conclusione A(x) 6⇒ B(x).



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 26 of 29

Go Back

Full Screen

Close

Quit

Esercizi:

• Quali quantificatori sono sottointesi in queste frasi?

? L’uomo e mortale;

? Il cane e un animale fedele;

? C’e chi sa chi e l’assassino;

? Nel triangolo un lato e sempre minore della sommadegli altri due.

• Esprimi formalmente queste due frasi:

? A qualsiasi ora c’e un medico di guardia all’ospedale;

? C’e un medico che a qualsiasi ora e di guardia al-l’ospedale.

• Quantifica le seguenti formule aperte con un quantifi-catore che ritieni opportuno:

? x e il quadrato di 4;

? x e un giorno di quest’anno;

? x e il Presidente del Consiglio;

? x e la radice quadrata di 9.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 27 of 29

Go Back

Full Screen

Close

Quit

• Quali delle seguenti proposizioni sono vere?

? per ogni x vivente, x e femmina;? per ogni x vivente, x e femmina o maschio;? per ogni x triangolo, se x ha i lati uguali allora ha

gli angoli uguali;? esiste un x triangolo tale che se x ha i lati uguali

allora ha gli angoli uguali;? esiste x naturale divisibile per 3 e per 5;? per ogni x naturale x e divisibile per 3 e per 5.

• Esprimere ciascuna delle seguenti frasi con il quantifi-catore diverso da quello che compare in essa:

? Tutti sono usciti;? Esiste qualcuno che ha preso la sufficienza;? Ogni persona le ha portato un regalo;? Non tutti sono entrati;? Non esiste qualcuno che non ha letto questo libro.

• Negare le seguenti asserzioni:

? Esiste un x naturale tale che x + 3 = 10;? Esiste un x naturale tale che x + 3 < 5;? Per ogni x naturale x + 3 < 10;? Per ogni x naturale x + 3 ≤ 7.



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 28 of 29

Go Back

Full Screen

Close

Quit

17. Circuiti di Commutazione

File sui Circuiti di Commutazione



Logica Formale

Proposizioni

Principi Logici


Connettivi Logici

Tavole di Verita

Tautologie, . . .

Proprieta dei . . .

Leggi di De Morgan

Implicazione logica


Doppia Implicazione

Teorema

Dimostrazione

Logica predicativa

Quantificatori

Circuiti di . . .

Stampa

Home Page

Title Page

JJ II

J I

Page 29 of 29

Go Back

Full Screen

Close

Quit

18. Stampa

Versione di Stampa



Logica di Base - UniPamath.unipa.it/~fbenanti/LogicaSISSIS.pdf · 2008-01-05 · Modulo Didattico:...

Documents

Transcript of Logica di Base - UniPamath.unipa.it/~fbenanti/LogicaSISSIS.pdf · 2008-01-05 · Modulo Didattico:...