Riassunti per esame di logica + esercizi, prof. Abrusci, Università Roma tre,

├A,A

viene dimostrata attraverso la sua stessa refutazione. =

A A

La regola della a fortiori o dell’indebolimento afferma che avendo una dimostrazione di B allora

├B

abbiamo anche una dimostrazione di B da A. Dunque la proposizione B discende da A

CAPITOLO 3 A├B

Definizione dei connettivi classici

Date due proposizioni A e B possiamo formarne una nuova mediante l’uso dei connettivi

proposizionali quali: congiunzione “e”, disgiunzione “o,oppure”, l’implicazione “se..allora” e

l’equivalenza “…se e soltante se…”. La logica deve trovare la definizione di ogni connettivo,

ovvero quale proposizione tale connettivo produce; deve fissare qual è e come si esprime la sua

negazione e fissare quali sono le regole di dimostrazione per ogni connettivo. La concezione dei

connettivi e’ una concezione estensionale, ovvero si basa solo sul valore delle proposizioni e vero-

funzionale in quanto il valore di una proposizione derivata dipende unicamente dal valore delle due

proposizioni. I casi possibili in cui possono stare due proposizioni o bit sono 4.

Congiunzione classica

La congiunzione è un connettivo principale. Il valore della congiunzione “e” è vero quando

˄ la congiunzione classica.

entrambe le proposizioni sono vere(A=B=1). Denotiamo con il simbolo

Il comportamento della congiunzione classica è fissato dalla sua tabella.

Un circuito che dati due bit di ingresso, produce in uscita un bit e che si comporta secondo la tabella

˄

della congiunzione classica è detto circuito AND. La negazione della congiunzione, ovvero il suo

￢(A˄B) ￢A˅￢B.

duale, è la disgiunzione. =

Per dimostrare la congiunzione bisogna effettuare due dimostrazioni separate, una per la

proposizione A e una per la B. Dalla verità di A e dalla verità di B passiamo alla verità di A˄B e

dalla falsità di A˄B possiamo concludere che una delle due proposizioni è falsa. Nelle

dimostrazioni possiamo usare la congiunzione per scoprire che dalla verità di A˄B abbiamo la

verità di A o B e dalla falsità di A o B possiamo concludere la falsità di A˄B

Disgiunzione classica

La disgiunzione è un connettivo principale. Esistono due modi, in logica classica, per indicare la

disgiunzione: nel senso latino di vel o di aut (alternativa classica). Nel primo caso il valore di “o”

˅ la

sarà falso quando entrambe le proposizioni sono false (A=B=0). Denotiamo con il simbolo

disgiunzione classica

Un circuito con due bit di ingresso e un solo bit di uscita che si comporta secondo la tabella della

disgiunzione classica viene definito circuito OR. La negazione della disgiunzione è il suo duale,

￢(A˅B) ￢A˄￢B.

ovvero la congiunzione. =

Per dimostrare la disgiunzione bisogna conoscere che A oppure B sia vera. Quindi dimostrando che

A è 1 sappiamo conseguentemente che B è 0 e viceversa. Oppure possiamo ricavare la verità della

disgiunzione con una dimostrazione da ipotesi: dimostriamo che dalla falsità di una si arriva alla

verità dell’altra, senza però sapere quale delle due è vera o falsa.

Per usare la disgiunzione nelle dimostrazioni abbiamo bisogno di un’informazione dall’esterno,

e dalla falsità

ovvero dobbiamo per forza sapere se A o B sono false. Quindi dalla verità di A˅B di

e dalla falsità

A si ricava la verità di B e di conseguenza dalla verità di A˅B di B si ricava la verità

di A.

Esiste anche la regola della distinzione dei casi che afferma che dalla verità di una disgiunzione

si può

A˅B concludere la verità di una proposizione C quando essa discende sia da A che da B (se

sia A che B sono vere).

Alternativa classica

L’alternativa classica è un altro modo per definire la disgiunzione classica. Il valore dell’alternativa,

indicato con AUT, è falso quando A è uguale a B (A=B). ￢.

˄, ˅ e ˅

Possiamo indicare l’alternativa usando solo i connettivi AautB = (A˄￢B) (B˄￢A).

Quando abbiamo un circuito con due bit d’ingresso e un solo bit d’uscita che si comporta secondo

la tabella dell’alternativa classica abbiamo un circuito EXOR.

La negazione dell’alternativa è l’equivalenza classica.

Possiamo ricavare la dimostrazione dell’ alternativa classica dalla congiunzione e dalla

disgiunzione dal momento che l’alternativa è una disgiunzione classica di due congiunzioni

classiche

Implicazione classica

L’implicazione classica ha il significato di “se…allora” e si indica con il simbolo

Il valore dell’implicazione è falso quando l’antecedente è maggiore rispetto al conseguente (A=1 e

B=0).

L’implicazione classica si può anche scrivere usando solo la negazione classica e la disgiunzione:

A B =￢A˅B

La negazione dell’implicazione classica è A˄￢B.

La dimostrazione di un’implicazione è come una dimostrazione di una disgiunzione. Refutando A si

￢A

conclude che A B è vera; dimostrando B si conclude che A B; dimostrando B da A (o da

￢B) concludiamo la verità di A B.

Come nel caso della disgiunzione, possiamo usare un’implicazione classica nelle dimostrazioni

quando riceviamo un input esterno. Dalla verità di un’ implicazione A B e dalla conoscenza

della verità di A si conclude che B è vera, tale regola viene chiamata regola del modus ponens

dell’implicazione. Se invece sappiamo che A B è vera e conosciamo che B è falsa possiamo

concludere la falsità di A, tale regola viene chiamata regola del modus tollens dell’implicazione.

Come nella disgiunzione anche nell’implicazione è presente la regola della distinzione dei casi:

￢A

dalla verità di A B conosciamo la verità di C quando questa discende da e da B

L’equivalenza classica

L’equivalenza si traduce letteralmente “…se e soltanto se…” o anche in maniera abbreviata “sse”.

Usiamo il simbolo per indicare l’equivalenza classica. Il valore di A B è 1 quando A=B.

￢.

˄, ˅ e ˄

Possiamo definire A B usando i connettivi A B = (￢A˅B) (￢B˅A)

La negazione dell’equivalenza classica è l’alternativa classica.

La dimostrazione dell’equivalenza classica non è altro che la dimostrazione della congiunzione e

della disgiunzione dal momento che l’equivalenza classica è una congiunzione di due disgiunzioni.

4° CAPITOLO

Cos’è una variabile?

E’ una casella che può essere riempita da qualunque oggetto di tipo T. Ogni oggetto di tipo T sarà

chiamato valore di ciascuna variabile di tipo T ed ogni riempimento della casella mediante un

oggetto di tipo T sarà detto “sostituzione della variabile con il suo valore”. Due variabili dello

stesso tipo, denominate con lo stesso simbolo si intende che quelle due variabili devono essere

sempre sostituite in maniera uguale.

Cos’è un Tipo?

L’attribuzione di un tipo è un attività libera che designa la classe di appartenenza di una

componente evidenziata. Genericamente indichiamo con A[a:T] una proposizione il cui

componente a è di tipo T. Possono esserci più tipi per diversi soggetti che indicheremo con

A[a :T …a :T ]. Ad una stessa componente possono essere attribuiti più tipi.

1 1 n n

Quantificatore universale

Una proposizione quantificata universalmente ha la forma per ogni x:T vale A[x] in cui “per ogni”

∀

in logica viene scritto mediante l’uso del simbolo . Ogni proposizione quantificata universalmente

è vera quando ogni valore a della variabile x della proposizione A[x:t] è vero, mentre è falsa quando

almeno un valore a vale 0.

La negazione di una proposizione quantificata universalmente, ovvero il suo duale è una

∀ ∃

proposizione quantificata particolarmente. ¬ x:T,A[x] = x:T,A[x]

∀

Per dimostrare x:T,A[x] bisogna dimostrare A[a:T] in cui a è un oggetto generico di tipo T

(ovvero bisogna usare solo ciò che compete ad a di tipo T) così da ottenere una dimostrazione di

∀x:T,A[x]. Dall’ipotesi che ogni proposizione quantificata è vera possiamo ricavare la verità di

ogni sua istanza è vera. Secondo la regola del dictum de omni ciò che è vero per tutti è vero per

ciascun componente di una proposizione quantificata universalmente.

Quantificatore particolare

Una proposizione quantificata particolarmente ha la forma per qualche x:T vale A[x] dove “per

∃.

qualche”, in logica classica, è sostituito con il simbolo Ogni proposizione quantificata

esistenzialmente è vera quando almeno un valore a della variabile x è vero e falsa quando tutti i

valori a della variabile x sono falsi.

La negazione di una proposizione quantificata particolarmente, ovvero il suo duale, è una

∃x:T,A[x] ∀x:T,A[x]

proposizione quantificata universalmente. ¬ =

Le regole di dimostrazione del quantificatore particolare sono due: dimostrare che almeno

∃x:T,A[x]

un’istanza è vera così da scoprire la verità di oppure attraverso la dimostrazione di

∃x:T,A[x]

A[a:T] da ¬A[a:T] così da avere una dimostrazione di senza conoscere quale sua istanza

sia vera ma sapendo semplicemente che una sua istanza è vera.

Proposizioni categoriche

Le proposizioni quantificate sono anche definite categoriche. Esse sono: Ogni S è P, Ogni S non è

P, Qualche S è P, qualche S non è P. AFFERMATIVE NEGATIVE

Ogni S è P Ogni S non è P

UNIVERSALI Qualche S è P Qualche S non

PARTICOLARI è P

Viene chiamato quadrato aristotelico. La p. universale affermativa è la contraddittoria della

particolare negativa e l’universale negativa è contraddittoria della particolare affermativa.

∀x:S

Oggi “ogni S è P”(SaP) viene letta come ,P[x]; “ogni S non è P”(SeP) viene letta con

∀x:S ∃x:S ∃x:S

, ¬P[x]; “qualche S è P” (SiP) con P[x] e “qualche S non è P” con ¬P[x].

Esiste un’altra lettura odierna delle proposizioni categoriche:

∀x:X

 → P(x))

Universale affermativa: (S (x)

∀x:X

 →

Universale negativa: (S (x) ¬P(x))

∃x:X

 ˄

Particolare affermativa: (S (x) P (x))

∃x:X

 ˄

Particolare negativa: (S (x) ¬P (x))

Sillogismi

I sillogismi divengono asserzioni di dimostrabilit&agr