Riassunto esame Programming for Data Science, prof. Ruggieri, libro consigliato Discrete mathematics and its applications, Rosen

Capitolo 11.1 Logica proposizionale

Una proposizione è un’affermazione che può essere vera o falsa ma non entrambe. Es: 1+1=2 true. Negazione: cambia il valore iniziale della variabile proposizionale. Congiunzione: restituisce vero solo se entrambe sono vere. Disgiunzione: è vero quando una delle due proposizioni è vera. Or esclusivo: restituisce vero quando è vera una delle due opzioni, non tutte e due. Ad esempio, se sul menù c’è scritto che si può prendere o la zuppa o l’insalata non possiamo chiedere al cameriere di portarcele entrambe.

Implicazione: si legge “se p allora q”. Il risultato è vero se tutte le volte che p è vero anche q è vero. Quando p è falso, quindi non vale l’ipotesi, l’implicazione è vera. (ad esempio, se in questo momento non sta piovendo e io affermo “sta piovendo” dico una cosa falsa e dopo posso dire qualsiasi altra cosa tanto non avrà importanza)

Contrario: q → p. Contrapositivo: ¬q → ¬p. Inverso: ¬p → ¬q.

Esempio: Frase da considerare “Se piove, non vado in città”.

• Contrario: Se non vado in città, allora piove.
• Contropositivo: Se vado in città, allora non sta piovendo.
• Inversa: Se non piove, allora vado in città.

Bicondizionale: “si legge p se e solo se q”. Risulta vero quando i valori di verità per p e q coincidono.

Tautologie: espressioni il cui valore di verità è sempre vero. Ad esempio, p (legge del terzo escluso) è una tautologia. Se dico sta piovendo o non sta piovendo l’affermazione sarà sempre vera. Due proposizioni sono equivalenti se hanno lo stesso valore di verità. Ad esempio, vorremmo dimostrare che un’implicazione e la contro positiva sono equivalenti.

Applicazioni della logica proposizionale

Come si può tradurre questa frase inglese in un'espressione logica? "Puoi accedere a Internet dal campus solo se sei un informatico o se non sei una matricola".

Soluzione: Ci sono molti modi per tradurre questa frase in un'espressione logica. Anche se è possibile rappresentare la frase con una singola variabile proposizionale, come p, questo non sarebbe utile per analizzarne il significato o ragionare con essa. Invece, useremo variabili proposizionali per rappresentare ogni parte di frase e determinare le connessioni logiche appropriate tra di loro. In particolare, lasciamo che a, c e f rappresentino "Puoi accedere a Internet dal campus", "Sei un informatico maggiore" e "Sei una matricola" rispettivamente. Notando che "solo se" è un modo in cui una dichiarazione condizionale può essere espressa; questa frase può essere rappresentata come a → (c ∨ ¬f).

La maggior parte dei motori di ricerca web supportano tecniche di ricerca booleane, che di solito possono aiutare a trovare pagine web su argomenti particolari. Per esempio, usando la ricerca booleana per trovare pagine web sulle università del New Mexico, possiamo cercare pagine che corrispondano a NUOVO EMESSICO E UNIVERSITÀ. I risultati di questa ricerca includeranno le pagine che contengono le tre parole NEW, MEXICO e UNIVERSITIES. Questo includerà tutte le pagine di interesse, insieme ad altre come una pagina sulle nuove università in Messico.

Equivalenze proposizionali

Una proposizione composta che è sempre falsa si chiama contraddizione. Una proposizione composta che non è né una tautologia né una contraddizione si chiama contingenza. Le proposizioni composte p e q sono chiamate logicamente equivalenti se p ↔ q è una tautologia. (La notazione è p ≡ q).

T denota la proposizione composta che è sempre vera. F denota la proposizione composta che è sempre falsa. Particolarmente importanti sono le due equivalenze logiche note come leggi di De Morgan. Ci dicono come ¬(p ∨ q) ≡ ¬p ∧ ¬q negare le congiunzioni e le disgiunzioni. In particolare, l'equivalenza ci dice che la negazione di una disgiunzione si forma prendendo la congiunzione delle negazioni delle proposizioni componenti. Allo stesso modo, l'equivalenza ci dice che la negazione di una congiunzione si forma prendendo la disgiunzione delle negazioni delle proposizioni componenti. (p ∧ q) → (p ∨ q) Ex. Mostra che è una tautologia. Soluzione: Per dimostrare che questa affermazione è una tautologia, useremo le equivalenze logiche per dimostrare che è logicamente equivalente a T. Questo potrebbe anche essere fatto utilizzando una tabella di verità.

Soddisfabilità proposizionale

Una proposta composta è soddisfacibile se esiste un'assegnazione di valori di verità alle sue variabili che la rende vera. Principio di sostituzione: Se due espressioni E1 e E2 sono equivalenti, posso sostituire all’interno di un’espressione F, la prima con la seconda. Questa legge vale anche per le proposizioni.

Predicati e quantificatori

Nella logica dei predicati, abbiamo dichiarazioni che coinvolgono variabili che variano su un dominio del discorso che indicheremo con U. Queste affermazioni non sono né vere né false quando i valori delle variabili non sono specificati. Es. P(x) che denota x>0 che ha come dominio gli interi. Allora P(-3) è falsa, P(0) è vera, P(3) è falsa. Nella foto, la terza non è una proposizione perché non ammette un unico valore di verità e quindi non posso dargli un’interpretazione booleana.

L'affermazione "x è maggiore di 3" ha due parti. La prima parte, la variabile x, è l'oggetto della dichiarazione. La seconda parte, il predicato, "è maggiore di 3", si riferisce ad una proprietà che l'oggetto della dichiarazione può avere. Possiamo indicare l'istruzione "x è maggiore di 3" con P(x), dove P denota il predicato "è maggiore di 3" e x è la variabile. L'istruzione P(x) è detta anche il valore della funzione proposizionale P a x. Una volta che un valore è stato assegnato alla variabile x, l'istruzione P(x) diventa una proposizione e ha un valore di verità.

I predicati sono anche usati per stabilire la correttezza dei programmi per computer, cioè per mostrare che producono sempre l'output desiderato quando viene dato un input valido.

Arità dei predicati: quanti argomenti hanno gli elementi. Si indica con il numero dopo la “/”. Ad esempio, la somma è binaria (+/2), il logaritmo è unario (log/1).

La quantificazione esprime la misura in cui un predicato è vero su una serie di elementi. Molte affermazioni matematiche affermano che una proprietà è vera per tutti i valori di una variabile in un particolare dominio, chiamato dominio del discorso (o universo del discorso), spesso chiamato semplicemente dominio. Tale affermazione è espressa utilizzando la quantificazione universale (∀xP(x)). La quantificazione universale di P(x) per un particolare dominio è la proposizione che afferma che P(x) è vero per tutti i valori di x in questo dominio. Si noti che il dominio specifica i possibili valori della variabile x. Il significato della quantificazione universale di P(x) cambia quando cambiamo il dominio.

Una dichiarazione è falsa, dove P(x) è una funzione proposizionale, se e solo se P(x) non è sempre vero quando x è nel dominio. Un modo per dimostrare che P(x) non è sempre vero quando x è nel dominio ∀xP(x) è quello di trovare un controesempio alla dichiarazione. Si noti che un singolo esempio di contatore ∀xP(x) è tutto ciò di cui abbiamo bisogno per stabilire che è falso.

Con la quantificazione esistenziale, formiamo una proposizione che è vera se e solo se P(x) è vero per almeno un valore di x nel dominio. Un dominio deve sempre essere specificato quando si usa una dichiarazione ∃xP(x). Inoltre, il significato di ∃xP(x) cambia quando il dominio cambia. Senza specificare il dominio, la dichiarazione non ha alcun significato. ∃() Si osservi che la dichiarazione è falsa se e solo se non c'è nessun elemento x nel dominio per il quale P(x) è vero.

Es. L'affermazione afferma che per ogni numero reale x con x <0, x > 0. Cioè, afferma "Il quadrato di un numero reale negativo è positivo".

Equivalenze nella logica dei predicati

Gli stati che coinvolgono i predicati e i quantificatori sono logicamente equivalenti se e solo se hanno lo stesso valore di verità indipendentemente dal dominio dei valori e indipendentemente dal significato dei predicati.

∀((P(x) ∧ Q(x) ∧ R(x)) ≡ ∀P(x) ∧ ∀Q(x))

Esercizio: Dimostrare che e sono logicamente equivalenti. Per dimostrare che queste affermazioni sono logicamente equivalenti, dobbiamo dimostrare che prendono sempre lo stesso valore di verità, indipendentemente da quali siano i predicati P e Q, e indipendentemente dal dominio utilizzato. È necessario dimostrare che:

• ∀(P(x) ∧ Q(x) ∧ R(x)) ≡ ∀P(x) ∧ ∀Q(x) - se è vero, allora è vero.
• ¬∀(P(x) → Q(x)) ≡ ∃(P(x) ∧ ¬Q(x))

Dimostrare che e sono logicamente equivalenti.¬∀(P(x) → Q(x)) Soluzione: Secondo la legge di De Morgan per i quantificatori universali, sappiamo che ∃(¬(P(x) → Q(x))) e sono logicamente equivalenti. Con la quinta equivalenza logica, sappiamo che ¬(P(x) → Q(x)) e sono logicamente equivalenti per ogni x. Dato che possiamo sostituire un'espressione logicamente equivalente con un'altra, ne consegue che ¬∀(P(x) → Q(x)) e ∃(P(x) ∧ ¬Q(x)) sono logicamente equivalenti.

Precedenza dei quantificatori

I quantificatori ∀ e ∃ hanno una precedenza più alta di tutti gli operatori logici da parte degli operatori proposizionali. Per esempio, ∀P(x) ∨ Q(x) è la disgiunzione di ∀P(x) e Q(x). In altre parole, significa (∀P(x)) ∨ Q(x) anziché ∀(P(x) ∨ Q(x)). L’esempio 2 della foto è da tenere in considerazione perché quando i quantificatori sono diversi l’ordine è importante. La prima formula significa che per ogni numero reale esiste un numero inverso la cui somma da zero. Se invece scambio i quantificatori, la formula significa esiste un numero reale per cui comunque ne prenda un altro la loro somma è zero: questo è falso. Infatti, dovrei trovare un numero che sommato a tutti gli altri da zero. Ad esempio, se al posto di x ci metto -y+1 ottengo -y+1+y=1. Avendo l’esiste prima del per ogni significa che questo numero è fissato una volta sola e per tutti gli altri deve valere.

1. È vero che dati due numeri x e y il loro prodotto è zero qualsiasi siano questi x e y? Chiaramente no. 2x1 non da zero.

2. È vero che per ogni numero riesco a trovarne un altro per cui il loro prodotto è zero? Si, un numero moltiplicato per 0 da sempre 0.

3. È vero che esiste un numero per cui per qualsiasi altro numero il loro prodotto è zero? Si perché 0*x mi dà sempre zero.

4. È vero che esistono due numeri il cui il loro prodotto mi dà sempre 0? Si.

Quantificatori annidati

1. Per tutti gli studenti, o lo studente ha un computer oppure esiste un altro studente che ha un computer ed è un amico di questo studente.

2. Esiste uno studente per cui presi altri due studenti, se x è amico di y e x è amico di z e y e z sono amici diversi non è vero che questi due sono amici tra di loro. Ossia esiste uno studente per cui nessuno dei suoi amici sono amici tra di loro.

Regole di inferenza

Un argomento è una sequenza di affermazioni (proposizioni) che terminano con una conclusione. Un argomento è valido se e solo se la verità di tutte le sue premesse implica che la conclusione è vera. Una forma di argomento nella logica proposizionale è una sequenza di proposizioni composte che coinvolgono variabili proposizionali. Una forma di argomento è valida indipendentemente da quali particolari proposizioni siano sostituite alle variabili proposizionali nelle sue premesse, la conclusione è vera se le premesse sono tutte vere. Dalla definizione di una forma argomentativa valida vediamo che la forma argomentativa con premesse 1, 2, ... , n (1 ∧ 2 ∧ ... ∧ n) → e la conclusione q è valida, quando è una tautologia. La chiave per dimostrare che un argomento nella logica proposizionale è valido è dimostrare che la sua forma di argomento è valida.

Risoluzione: Regola d'inferenza che si basa sulla tautologia ((P ∨ Q) ∧ (¬P ∨ R)) → (Q ∨ R). La risoluzione svolge un ruolo importante nei linguaggi di programmazione basati sulle regole della logica. Per costruire prove nella logica proposizionale utilizzando la risoluzione come unica regola d'inferenza, le ipotesi e la conclusione devono essere espresse come clausole, dove una clausola è una disgiunzione di variabili o una negazione di queste variabili.

Regole di inferenza sui quantificatori

• L'istanziazione universale è la regola d'inferenza utilizzata per concludere che P(c) è vera, dove c è un particolare membro del dominio, data la premessa ∀xP(x).
• La generalizzazione universale è la regola d'inferenza che afferma che ∀xP(x) è vero, data la premessa che P(c) è vero per tutti gli elementi c nel dominio. L'elemento c deve essere un elemento arbitrario del dominio.
• L'istanziazione esistenziale è la regola che ci permette di concludere che esiste un elemento c nel dominio per il quale P(c) è vero se sappiamo che ∃xP(x) è vero. Non possiamo selezionare qui un valore arbitrario di c, ma piuttosto deve essere un c per il quale P(c) è vero.
• La generalizzazione esistenziale è la regola d'inferenza che si usa per concludere che ∃xP(x) è vera quando si conosce un particolare elemento c con P(c) vero.

Esempi:

1. Il nostro dominio è costituito da tutti i cani e Fido è un cane. "Tutti i cani sono coccoloni". "Quindi, Fido è coccolone". (UI). 1 ≥ 0.

2. C può essere zero, quindi è verificata. C può essere il successore di un c (c = c +1) con 1 ≥ 0c quindi il successore è ancora maggiore o uguale di 0. Questo ragionamento viene fatto per un generico c, senza dimostrarne nessuna particolare proprietà. Dimostro che se posso farlo per un c generico posso farlo anche per tutti gli altri. (UG).

3. "C'è qualcuno che ha preso una A nel corso", "Chiamiamo e diciamo che una ha preso una A (EI).

4. "Michelle ha preso una A nella classe" "Quindi, qualcuno ha preso una A nella classe". (EG).

Dimostrare che le premesse "Tutti in questa classe di matematica discreta hanno fatto un corso di informatica" e "Marla è una studentessa in questa classe" implicano la conclusione "Marla ha fatto un corso di informatica".

Soluzione: Lasciate che D(x) denoti "x è in questa classe di matematica discreta" e che C(x) denoti "x ha frequentato un corso di informatica". Poi le premesse sono ∀x(D(x) → C(x)) e D(Marla). La conclusione è C(Marla). Le seguenti fasi possono essere utilizzate per stabilire la conclusione partendo dalle premesse.

Passi:

• ∀x(D(x) → C(x)). Premessa.
• Istanziazione universale da (1): D(Marla) → C(Marla).
• Premessa D(Marla).
• Modus ponens da (2) e (3) C(Marla).

Capitolo 22.1 Insiemi

Un insieme è una collezione non ordinata di oggetti, chiamati elementi o membri dell'insieme. ∈ Si dice che un insieme contiene i suoi elementi. Scriviamo a ∈ A per indicare che a è un elemento dell'insieme A.