Metodi matematici per l'informatica – Appunti logica, insiemi e induzione, appunti di logica matematica

Antonio Wang - PEU-Z

Metodi Matematici per l’Informatica

Logica Proposizionale (Parte 1)

Sentenze

Ci sono due tipi di sentenze:

• è una frase semplice costituita da un solo soggetto

Sentenza minimale:

e un solo predicato. Esempio: “Oggi piove.”

• è una frase costituita da più proposizioni collegate

Sentenza composta:

tra loro, che siano coordinate o subordinate. Esempio: “Oggi piove e fa

freddo.”

Linguaggio formale

Nel linguaggio che utilizziamo dobbiamo stabilire tendenzialmente alcune cose:

• i simboli che utilizzeremo per la rappresentazione;

Alfabeto:

• come si rappresentano gli oggetti del discorso;

Sintassi:

• cosa significano tali rappresentazioni.

Semantica:

Esempio Alfabeto A = area del rettangolo

l = lunghezza del rettangolo

w = larghezza del rettangolo

Sintassi ×

A l w

=

Semantica

A rappresenta il valore numerico dell’area del rettangolo

l rappresenta la lunghezza del rettangolo

w rappresenta la larghezza del rettangolo

× rappresenta l’operazione di moltiplicazione

= indica che l’area del rettangolo equivale al prodotto tra lunghezza e

larghezza del rettangolo

Proposizione

Una proposizione è una che è vera o falsa, ma non può

frase dichiarativa

assumere entrambi gli “stati” allo stesso tempo.

1

Antonio Wang - PEU-Z

Washington D.C. è la capitale degli Stati Uniti d’America =⇒ V.

Esempio F

2 + 2 = 5 =⇒ .

Quali problemi riscontriamo nell’uso della nostra lingua?

Le frasi che utilizziamo nel linguaggio comune sono

Linguaggio comune

spesso imprecise (perché la loro veridicità dipende dal contesto) o ambigue

(lasciano spazio a più interpretazioni).

Un americano muore di melanoma quasi ogni ora.

Esempio:

Esiste un americano che muore ogni ora (sempre lo stesso) o sono americani

diversi? Ecco qui che c’è ambiguità.

In la precisione è cruciale, per cui non si affida nulla al contesto o

matematica

a conoscenze pregresse.

Enunciati Matematici

Gli argomenti di cui si occupa la matematica sono enunciati che trattano oggetti

matematici.

√ 2 è un numero irrazionale.

Esempio:

Ogni enunciato della matematica può essere categorizzata in uno di questi 4 tipi

di proposizione: T P

• Proposizione ha la proprietà

semplice: T P

• Proposizione Ogni ha la proprietà

universale: T P

• Proposizione Esiste un che abbia la proprietà

esistenziale: ENUNCIATO A ENUNCIATO

Proposizione Se allora

• condizionale:

B

Oppure può essere una combinazione di più sotto-enunciati di questi tipi tramite

i connettivi AND, OR, NOT.

Variabili proposizionali

Ad ogni proposizione è assegnata una variabile proposizionale, per convenzione

p, q, r, s,

si usano le lettere . . . T F

Il valore di una variabile proposizionale è una tra: (true) o (false).

Proposizioni composte

Le proposizioni composte sono costituite da più proposizioni semplici collegate

da connettivi logici. 2

Antonio Wang - PEU-Z

Connettivi logici

• Congiunzione (AND)

• Disgiunzione (OR)

• Negazione (NOT)

• Implicazione

• Equivalenza o Bicondizione (il se e solo se visto in Matematica Discreta)

Il connettivo viene usato quando vogliamo dire che

Connettivo AND AND

entrambe le proposizioni semplici di una proposizione composta sono vere, cioè

vogliamo combinare due enunciati in uno che li afferma entrambi.

∧.

Il simbolo usato per questo connettivo è

∧

> <

(π 3) (π 4).

Esempio:

Logica proposizionale (seconda parte)

Connettivo o disgiunzione

OR A B

Ci sono enunciati in cui un enunciato è vero un enunciato è vero.

oppure

p, q p q

Siano proposizioni. La disgiunzione tra e è:

∨

p q

p q

ed è falsa se e sono false, è vera altrimenti.

Esempio: Salerno è una città della Campania o 3 + 2 = 5

Connettivo esclusivo

OR

In questo caso solo uno dei due enunciati deve essere vero, non entrambi veri e

non entrambi falsi.

p, q p q

Siano proposizioni. L’OR esclusivo di e è:

⊕

p q

Esempio: Infilo gli stivali o i mocassini.

3

Antonio Wang - PEU-Z

Connettivo o negazione

NOT p,

Data una proposizione la sua negazione può essere espressa in diversi modi.

p p

Dunque sia una proposizione, la negazione di è la proposizione “non è vero

p”.

che

La negazione si denota con: ¬p

Esempio

p = Maria ha superato almeno (non meno di) tre esami del corso di laurea

triennale in Informatica

¬p = Non è vero che Maria ha superato almeno 3 esami...

¬p = Maria ha superato meno di 3 esami...

¬p = Maria ha superato al più (non più di) 2 esami...

Connettivo implicazione o condizionale

p, q p q”

Siano proposizioni. La proposizione “se allora si chiama implicazione e

si denota con: p q

=⇒

p q

La proposizione è chiamata (o ipotesi) e è chiamata

antecedente con-

(o conclusione).

seguente

Equivalenze logiche ∧ ∧

p q p q

Le due proposizioni composte e hanno la stessa tabella di verità.

Accade spesso che si voglia dimostrare che ciò è vero (o falso) per una coppia

di proposizioni. Dunque è opportuno dare una definizione per introdurre una

terminologia.

p, q

Siano due proposizioni composte. Esse sono logicamente equivalenti se hanno

la stessa identica tabella di verità.

p q

L’equivalenza di e è denotata con: ≡

p q

Esempio: ¬(p ∨ ≡ ¬p ∧ ¬q

q) 4

Antonio Wang - PEU-Z

Tabelle di verità di proposizioni composte

Quando compariamo delle tabelle di verità è bene sapere anche il numero di righe

della tabella di verità. Se abbiamo 3 proposizioni elementari allora il numero di

3

righe sarà 2 . k

Dunque, date proposizioni elementari il numero di righe della

k

tabella di verità è 2 .

Inverso, opposto e contronominale

Ci sono tre particolari tipi di enunciati che possiamo formare a partire da

p q.

=⇒ p, q

Siano proposizioni.

q p

• =⇒

Inverso: ¬p ¬q

• =⇒

Opposto: ¬q ¬p

• =⇒

Contrononimale:

≡ ¬q ¬p.

p q

=⇒ =⇒

Attenzione:

Esempio n n n

Data la proposizione:“Se è maggiore di 2 ed è primo allora è dispari”

scriverne il contronominale, l’inverso e l’opposto.

p n>

= 2

q n

= primo

r n

= dispari

Proposizione

∧ q) r

(p =⇒

Contronominale

¬r ¬(p ∧ q)

=⇒

Inverso

∧

r q)

=⇒ (p

Opposto

¬(p ∧ ¬r

q) =⇒

Equivalenza o bicondizione

p, q

Siano due proposizioni. q”

La proposizione “p se e solo se è chiamata equivalenza.

Essa è denotata con: 5

Antonio Wang - PEU-Z ⇐⇒

p q

p q

ed è vera quando e hanno lo stesso valore.

⇐⇒ ∧

p q q) p)

Le proposizioni e (p =⇒ (q =⇒ sono logicamente equivalenti.

⇐⇒ ≡ ∧

q) q) p)

(p (p =⇒ (q =⇒

Regole di precedenza degli operatori

Abbiamo visto nelle espressioni composte che vengono usate le parentesi. Esse

ci indicano l’ordine secondo cui vanno applicati gli operatori logici.

Per ridurre il numero di parentesi si scelgono delle gerarchie secondo la quale

vengono applicati gli operatori:

Operatore Ordine

¬ Primo

∧ Secondo

∨ Terzo

=⇒ Quarto

⇐⇒ Quinto

Tautologie

Una è una proposizione composta che è indipenden-

tautologia sempre vera,

temente dal valore delle proposizioni che la compongono.

Esempio ∨ ¬p

p

Contraddizioni

Una è una proposizione composta che è indipen-

contraddizione sempre falsa,

dentemente dal valore delle proposizioni che la compongono.

Esempio ∧ ¬p

p

Contingenza

Una è una proposizione composta che è vera in alcuni casi e falsa

contingenza

in altri, dunque non è né una né una

tautologia contraddizione.

6

Antonio Wang - PEU-Z

Esempio ∧

p p

Logica proposizionale (terza parte)

Legge di De Morgan ¬(p ∨ ≡ ¬p ∧ ¬q

q)

Negazione OR: ¬(p ∧ ≡ ¬p ∨ ¬q

q)

Negazione AND:

Equivalenze logiche note

∧ ≡ ∨ ≡

p T p p F p

• Identità: ∨ ≡ ∧ ≡

p T T p F F

• Dominazione: ∨ ≡ ∧ ≡

p p p p p p

• Idempotenza: ¬(¬p) ≡ p

• Doppia negazione:

∧ ≡ ∧ ∨ ≡ ∨

p q q p p q q p

• Commutativa: ∧ ∧ ≡ ∧ ∧ ∨ ∨ ≡ ∨ ∨

p q r p r) p q r p r)

• (q (q

Associativa: ∧ ∨ ≡ ∧ ∨ ∧

p r) q) r)

• (q (p (p

Distributiva:

∧ ¬p ≡ ∨ ¬p ≡

p F p T

• ⊕ ≡ ∧ ¬q) ∨ ∧

p q q)

• (p (¬p

≡ ¬p ∨

p q q

• =⇒

⇐⇒ ≡ ∧

p q p q q p

• =⇒ =⇒

Un’altra equivalenza nota è: ′ ′

≡ ≡

p p q q

Se: e ′ ′

∧ ≡ ∧

p q p q

Allora:

Questo lo possiamo dimostrare confrontando le tabelle di verità di entrambe le

proposizioni. il viceversa non è valido, dato che confrontando le

Attenzione:

tabelle di verità non lo possiamo dimostrare.

Soddisfacibilità

Una proposizione composta è se vi è un assegnamento di valore

soddisfacibile

alle variabili che possa renderla vera.

Esempio ∧ ¬p

p

Non è soddisfacibile, dato che è sempre falsa.

∨ ¬p

p 7

Antonio Wang - PEU-Z

È soddisfacibile.

Applicazioni della Logica Proposizionale

Rappresentazioni di T ed F in un computer (Rappresentazione binaria)

I computer per memorizzare dei dati utilizzano i bit 1 e 0. La logica utilizza vero

e falso, cioè ed Dunque un bit è sufficiente per rappresentare (1) ed (0).

T F. T F

Operazioni bit a bit

Dunque al posto di usare ed possiamo sostituire con 1 e 0.

T F

Circuiti logici

Un è un insieme di dispositivi elettronici che realizza

circuito logico operazioni

attraverso delle porte logiche (AND, ecc.). I circuiti logici

logiche OR, NOT,

elaborano dei segnali digitali che assumono il valore di 0 oppure 1 per eseguire

operazioni matematiche o di controllo (algebra binaria).

Progettazione di circuiti logici

I circuiti logici possono essere realizzati partendo da 3 porte logiche di base,

definite gates.

Queste 3 porte logiche sono l’AND gate, l’OR gate e il gate (o inverter).

NOT

Traduzione di frasi di un linguaggio comune in proposizioni logiche

Se hai più di 12 anni o sei accompagnato dai tuoi genitori allora puoi

salire su quella giostra.

Proposizioni elementari:

p:

• hai più di 12 anni

q:

• sei accompagnato dai tuoi genitori

r:

• puoi salire su quella giostra

∨

p q r

=⇒

Dunque, per poter tradurre le frasi di linguaggio comune in proposizioni logiche

bisogna:

1. Trovare i connettivi logici;

2. Identificare le proposizioni elementari;

3. Riscrivere la frase come una proposizione logica.

8

Antonio Wang - PEU-Z

Logica Proposizionale vs Logica Predicativa

La logica proposizionale è la forma più semplice della logica formale. Essa è

costituita da enunciati (proposizioni) che possono essere veri o falsi e da connettivi

logici.

Logica Predicativa (Prima Parte)

Limitazioni della logica proposizionale

La logica proposizionale non è sufficiente ad esprimere il significato di tutti gli

enunciati in matematica e del linguaggio naturale.

x

Per esempio, l’asserzione + 1 = 2 non è una proposizione, dato che non è né

x. x

vera né falsa, ma dipende dal valore della variabile Se = 1 allora l’asserzione

è vera, sennò è falsa.

Nella maggior parte delle proposizioni che abbiamo visto fino ad ora è stato

sempre semplice dedurre il loro valore (cioè se sono vere o false). Il peggiore dei

casi ci imponeva di utilizzare la tavola di verità. Ma non tutto è così semplice

perché ci sono situazioni in cui vengono coinvolti un numero infinito di casi.

Logica predicativa

Ed è per queste necessità che nasce la logica predicativa, anche conosciuta come

logica di primo ordine. Nella logica di primo ordine utilizziamo quelli che

Logica del primo ordine

∃)

sono i quantificatori (∀ e sui singoli oggetti del dominio di discorso, cioè

dell’insieme di tutti gli oggetti che stiamo considerando. Attenzione però, i

quantificatori possono fare affermazioni generali solo sui singoli oggetti di un

insieme di riferimento, ma non sui suoi sottoinsiemi.

La logica del secondo ordine è una generaliz-

Logica del secondo ordine

zazione della logica del primo ordine, in cui i quantificatori non solo possono

agire sui singoli termini dell’insieme di riferimento, ma in generale sull’insieme

delle parti del dominio di discorso, quindi anche su proprietà e sottoinsiemi

dell’insieme di riferimento. Ciò rende la logica del secondo ordine molto più

espressiva, ma al tempo stesso più complessa e meno formalmente trattabile.

Logica predicativa

Abbiamo quindi bisogno di, come detto prima, un tipo più potente di logica e

dobbiamo introdurre quindi i concetti di:

• predicato

• quantificatore universale

• quantificatore esistenziale 9

Antonio Wang - PEU-Z

Il predicato esprime una proprietà di un oggetto oppure una re-

Predicato

lazione tra due o più oggetti del dominio di discorso. Esso dipende da una o più

variabili.

Come per le proposizioni, anche i predicati sono denotati da una lettera. Per

P P(x) P x.

esempio, possiamo chiamare il nostro predicato e sarà il valore di su

Dunque diventa una vera e proposizione logica che ci restituisce o a seconda

T F

x.

del valore della variabile Bisogna fare attenzione, inoltre, a non confondere il

P P(x).

predicato con

Esempio: P = è un quadrato perfetto

P(4) = T

P(5) = F Nella logica

Elementi fondamentali della logica predicativa: Costante

predicativa, una è un simbolo che rappresenta un oggetto specifico e

costante

invariabile.

Esempio: x y

3 in = + 3 y"

Giovanna in "Giovanna è amata da Nella logica

Elementi fondamentali della logica predicativa: Variabile

predicativa, una rappresenta un oggetto di un tipo specificato. Questo

variabile

tipo è definito stabilendo un dominio di discorso.

x, y sono le variabili

x y

In = + 3 il dominio è un insieme di numeri

y"

In "Giovanna è amata da il dominio è un insieme di persone

Nella logica

Elementi fondamentali della logica predicativa: Predicato

predicativa, il rappresenta la proprietà o le relazioni tra oggetti.

predicato P è il predicato "> 3"

P(x)

x > 3 è denotato con

Il predicato può essere relativo a uno, due o più oggetti.

R≀∫ ∫ ≀(x), ∫ ⊔⊓⌈⌉\⊔⌉(x), ∫ √≀∫ ⊣⊔⟩(x, y)

10

Antonio Wang - PEU-Z Come già detto, quindi, per ogni

Predicato o funzione proposizionale

assegnamento di variabile, la proprietà diventa una proposizione che può essere

vera o falsa. P

Quindi associamo alla proprietà o alla relazione una funzione (funzione propo-

sizionale) che la rappresenta. S⊔⊓⌈⌉\⊔⌉(x),

Consideriamo il predicato dove l’universo del discorso

Esempio S⊔⊓⌈⌉\⊔⌉(x)

sono le persone. è il predicato “è uno studente”.

S⊔⊓⌈⌉\⊔⌉(G⟩≀⊑⊣\\⟩) T

ha valore se Giovanni è uno studente.

In programmazione la logica predicativa viene

Usi della logica predittiva

usata spesso in molte espressioni. Per esempio:

if (x > 0 || (x <= 0 && y > 100))

In questo caso possiamo notare che possiamo associare i predicati:

P(x) x >

: 0

Q(x) ≤

x

: 0

R(y) y >

: 100

Questa proposizione in realtà può essere anche pulita ed ottimizzata:

P(x) ∨ ∧ R(y)) ≡ P(x) ∨ R(y)

(¬P(x)

Nella logica predicativa spesso possiamo trovare delle

Asserzioni composte Vengono uniti più predicati, utilizzando i connettivi

asserzioni composte.

logici.

Esempio S⊔⊓⌈⌉\⊔⌉(x) ∧ E∫ ⊣⇕⌉(x, y)

x y.

è uno studente e ha superato l’esame

Possiamo identificare “quanto spesso” un predicato è vero

Quantificatori

tramite l’uso di quelli che sono i Le costruzioni linguistiche da

quantificatori.

tenere a mente sono tendenzialmente e

esiste per ogni.

11

Antonio Wang - PEU-Z La proprietà è soddisfatta per tutti gli oggetti

Quantificatore universale ∀.

del gruppo. Il simbolo per denotare questo quantificatore è

Esempio R

Dominio: 2

∀x(x ≥ 0)

Almeno un oggetto gode della proprietà.

Quantificatore esistenziale

Esempio R