Informatica - Matematica discreta

Logica

Divided by topic

BREVE CENNO DI LOGICA CLASSICA Lalogicapuo essere denita come la scienza che studia le condizioni in base alle quali un ragionamento risultacorrettoevero. Un ragionamento e corretto se segue uno schema logico valido. Per esempio: \se A e B e B e C allora A e C". L'esempio piu classico di questo tipo di ragionamento e:\ Socrate e un uomo, tutti gli uomini sono mortali, allora Socrate e mortale". In questo casoA: Socrate B: uomo C: mortale Si tratta di un ragionamento non solo corretto, ma anche vero nella sua conclusione. Il ragionamento: \l'asino e un animale, gli animali sono volatili, allora l'asino vola" e corretto come il primo, ma non e vero nella sua conclusione, perche si basa su un giudizio (\gli animali sono volatili") falso. Inne il ragionamento: \il canguro e un marsupiale, i marsupiali sono animali, dunque Socrate e mortale" non e corretto nel suo schema logico, ma il giudizio nale e corretto.Si pongono alcune denizioni. Denizione 1.Ilconcettoe la rappresentazione universale di qualcosa. Bisogna fare attenzione a non confondere il concetto e l'immagine: entrambi con- tengono un certo messaggio, ma si distinguono in quanto uno dipende dal \pensare" e l'altra dal \sentire". Le immagini rappresentano aspetti sensibili delle cose, i concetti ne rappresentano il contenuto intelligibile. Ad esempio, quando si parla del concetto di uomo, non si pensa ad un particolare essere umano, ma all'essere vivente che ha tutte le caratteristiche umane. Se si vede un oggetto di colore giallo, se ne riconosce il colore proprio perche si ha il concetto di giallo. Denizione 2.Ilgiudizioe l'operazione per la quale viene negato o aermato un concetto rispetto ad un'altro: in altre parole, il giudizio, rispettivamente, unisce o divide tra loro due concetti. Esempio 1.Dicendo: \l'informatico e un uomo", si uniscono i concetti \informatico" e \uomo"; dicendo \il serpente non e un mammifero", i concetti \serpente" e \mammifero" vengono separati. Denizione 3.I due concetti che vengono \uniti" o \divisi" nel giudizio costituiscono lamateriadel giudizio. In particolare la materia e formata da soggetto predicato. L'aermazionee lanegazione, che, rispettivamente uniscono o dividono soggetto e pre- dicato, costituiscono laformadel giudizio. Esempio 2.Nell'Esempio 1, nel giudizio \l'informatico e un uomo", naturalmente \in- formatico" e il soggetto, \uomo" e predicato e la forma del giudizio e un'aermazione; nel giudizio \il serpente non e un mammifero" il soggetto e \serpente", il predicato e \mammifero" e il giudizio e una negazione. La branca della logica dettalogica formalesi occupa della correttezza di un ragion- amento, che dipende esclusivamente dallaforma, ovvero dal fatto che il ragionamento si adatti a certe regole formali.D'altra parte, lalogica materialeriguarda lamateriadel ragionamento e studia la verita di un ragionamento.1 2 Denizione 4.Unaproposizionee una frase mediante la quale un soggetto viene legato mediante il verbo essere (copula) ad un predicato. Quindi la proposizione e formata dai seguenti elementi: soggetto predicato copula. Osservazione 1.Denita in questi termini, una proposizione potrebbe essere vera o falsa: questo puo essere stabilito tramite ilgiudizio, che e un'operazione dell'intelletto. Esempio 3."L'informatico e un uomo" e una proposizione ed e vera, mentre \il serpente e un mammifero" e una proposizione falsa. Bisogna dire che logica classica e riduttiva perche incapace di render conto nanche del linguaggio naturale. Inoltre ci sono aspetti di questo linguaggio, come il contesto o l'intonazione, che certamente la logica non riesce ad esprimere, ma spesso il signicato della frase dipende proprio da questi elementi.Invece, nel caso del linguaggio matematico, la logica e abbastanza appropriata. Anche in questo caso, pero non si usa rigorosamente la formalizzazione logica, perche il discorso ne risulterebbe eccessivamente appesantito. 3 CENNI DI LOGICA Alla base della logica (matematica) ci sono le cos detteproposizioni atomiche, odichia- rative, ovvero le proposizioni (nel senso della logica classica) delle quali (tramite giudizio) si possa aermare con certezza se sono vere o false. Se una proposizione atomica e vera, ad essa si attribuisce valore di verita V (o T o anche 1), se e falsa si attribuisce ad essa valore di verita F (o 0). Esempio 4.1.P: 8 e un numero primo 2.Q: il cane e un mammifero. Certamente la proposizionePe falsa, la proposizioneQe vera. Quindi il valore di verita diPe F, il valore di verita diQe V. Esempio 5.Le proposizioni 3.R: Marco e simpatico 4.S:xe pari non possono essere classicate come proposizioni atomiche:Rperche presenta un pre- dicato che non e di carattere oggettivo, per cui ciascuno puo attribuire valore di verita V o F secondo i propri sentimenti;Spresenta una variabile e quindi, come si vedra in seguito, e unafunizone proposizionale. Si puo assegnare aSvalore di verita se si denisce l'universo in cui variaxe inoltre si eettua una delle seguenti operazioni (1) si sostituisce axun determinato valore (2) si fa precedere laxda un quanticatore. I quanticatori sono:ilquanticatore universale8(si legge \per ogni") ilquanticatore esistenziale9(si legge \esiste") Se l'universo nel quale variaxe l'insiemeZdei numeri interi, sostituendo axi valori 6 e -3, per esempio,Sdiventa: \6 e positivo" che ha valore di verita V; \-3 e positivo" che ha valore di verita F. Se si usano i quanticatori, si ha: (8x) (xe positivo)" che ha valore di verita F; (9x) (xe positivo)" che ha valore di verita V. Le proposizioni atomiche possono essere combinate tramite i connettivi logici. Denizione 5.(NEGAZIONE) Data una proposizioneP, la negazione della proposizionePsi indica con  PoppureqP: SePe vera alloraqPe falsa. SePe falsa alloraqPe vera. Esempio 6.P: \Gli iscritti al primo anno di Informatica presso l'universita di Bari sono meno di 100" ha valore di verita F. AlloraqP: \Non e vero che gli iscritti al primo anno di Informatica presso l'universita di Bari sono meno di 100" ha valore di verita V.qPsi puo scrivere anche: \Gli iscritti al primo anno di Informatica presso l'universita di Bari sono piu di 100" (sempre con valore di verita V). Esempio 7.P: \L'Italia e una Repubblica" ha valore di verita V. AlloraqP: \L'Italia non e una Repubblica" ha valore di verita F. 4 Dalla denizione si deduce subito la tavola di verita della negazionePq PVF FV Denizione 6.(CONGIUNZIONE) SianoPeQdue proposizioni. La proposizione \PeQ"(congiunzione diPeQ) si denota con P^Q:  E vera quandoPeQsono entrambe vere ed e falsa altrimenti (ovvero falsa quando almeno una delle due e falsa). La tavola di verita della congiunzione e: PQP ^QVVV VFF FVF FFF Esempio 8.P: Torino e la capitale d'Italia. Q: 16 e un numero pari. Allora la congiunzione diPeQe: P^Q: Roma e la capitale d'Italia e 16 e un numero pari. CertamenteP^Qha valore di verita F percheQha valore di verita V maPha valore di verita F. Esempio 9. P: 12 e multiplo di 3 Q:12 non e un numero intero. Allora la congiunzione diPeQe: P^Q: 12 e multiplo di 3 e12 non e un numero intero. CertamenteP^Qha valore di verita V perchePeQhanno valore di verita V. Denizione 7.(DISGIUNZIONE) SianoPeQdue proposizioni. La proposizione \PoQ"(disgiunzione diPeQ) si denota con P_Q 5 ed e falsa quandoPeQsono entrambe false ed e vera altrimenti (ovvero vera quando almeno una delle due e vera). Si deduce la tavola di verita della disgiunzione: PQP _QVVV VFV FVV FFF Esempio 10. P: La macchina ha il motore diesel. Q: La macchina ha il motore a benzina. Allora la disgiunzione diPeQ: P_Q: La macchina ha il motore diesel o a benzina. NaturalmenteP_Qha valore di verita V. Denizione 8.(IMPLICAZIONE) SianoPeQdue proposizioni. La proposizione implicazione \PimplicaQ"si denota con P!Q:  E falsa quandoPe vera eQe falsa ed e vera altrimenti. Si puo scrivere la tavola di verita della implicazione PQP !QVVV VFF FVV FFV Quindi sePe veraQ, e vera, sePe falsa non si puo stabilire la verita diQ. Esempio 11. P: Il cellulare funziona. Q: La batteria del cellulare e carica. L'implicazione e: P!Q: Se il cellulare funziona, allora la batteria e carica. Se il cellulare non funziona, potrebbe essere scarica la batteria o potrebbe esserci qualche altro problema e quindi . 6 Denizione 9.(DOPPIA IMPLICAZIONE o EQUIVALENZA) Due proposizioniPeQsi dicono equivalenti e si scrive P !Q; se (P!Q)^(Q!P). La tavola di verita dell'equivalenza e: PQP !QQ !P( P!Q)^(Q!P)VVVVV VFFVF FVVFF FFVVV Denizione 1. SianoPeQformule della logica proposizionale. Si dice cheQe con- seguenza logica diPe si scrive P=)Q quandoQe vera ogni qualvolta e veraP. Dalla denizione segue subito cheQnon puo essere falsa quandoPe vera. Osservazione 1.Dire cheQe conseguenza logica diPvuol dire che certamenteQha valore di verita V quandoPha valore di verita V. Denizione 2.Si dice chePeQsono semanticamente equivalenti sePe conseguenza logica diQeQe conseguenza logica diP; ovvero seP=)QeQ=)P. Si scrive P()Q Osservazione 2.Si puo anche parlare di conseguenza logica di piu di una formula della logica proposizionale: vale a dire seP 1; : : : ; P k; Q sonok+ 1 formule e seQe vera quando sono vereP 1; : : : ; P k, si dice che Qe consegueza logica diP 1; : : : ; P ke si scrive: (P 1; : : : ; P k) = )Q Esempio 1.SianoPeQdue formule della logica proposizionale. AlloraQe con- seguenza logica diPe diP!Q. In simboli: (P; P!Q) =)Q: Infatti, considerata la tavola di verita: PQP !QQ VVVV VFFF FVVV FFVF si osserva che nell'unico caso (il primo) nel quale siaPcheP!Qhanno valore di verita V, ancheQha valore di verita V. Dalla tavola di verita si evince anche chePnon e conseguenza logica diQe diP!Q, perche nella terza rigaQeP!Qhanno valore di verita V, maPha valore di verita F. Esempio 2.SianoAeBdue formule. Si osserva facilmente cheA^Bnon e conseguenza logica diA_B, in quanto seAha valore di verita V eBha valore di veritaF, allora A_Bha valore di veritaV, maA^Bha valore di veritaF. Proposizione 1.SianoPeQdue formule del la logica proposizionale. Al loraPeQ sono semanticamente equivalenti se e solo se hanno la stessa tavola di verita. Dimostrazione.SePha valore di verita V, allora ancheQdeve avere valore di verita V, percheQe conseguenza logica diP. SePha valore di verita F, allora ancheQdeve avere valore di verita F, altrimentiPnon potrebbe essere conseguenza logica diQ. La dimostrazione si completa facilmente scambiando i ruoli diPeQfra loro. Osservazione 3.Si osserva facilmente, come conseguenza della precedente propo- sizione, che due formule sono semanticamente equivalenti se e soltanto seP !Q e una tautologia. Esempio 3.SianoPeQformule. Allora sono semanticamente equivalentiP!Qe qQ!qP, ovvero: (P!Q)()(qQ!qP): 1 2 Si prova utilizzando la proposizione precedente, con la seguente tavola di verita: PQq Pq QP !Qq Q!qPVVFFVV VFFVFF FVVFVV FFVVVV Esercizi 1.SianoPeQformule. Provare che valgono le seguenti equivalenze seman- tiche: (1)P!Q()q(P^qQ) (2)P!Q()qP_Q (3)q(P_Q)()qP^qQ (4)q(P^Q)()qP_qQ: Una teoria matematica si basa su un certo numero di assiomi assegnati su una certe struttura, a partire dai quali si dimostrano iTeoremi. Ma cos'e una dimostrazione? e la costruzione di una serie di argomentazioni consistenti che portino inne ad un'af-fermazione vera. Per dimostrare la validita di un argomento si potrebbe sempre far ricorso alle tavole di verita. Pero questo potrebbe essere un procedimento molto lungo e noioso: se ci sono molte variabili proposizionali, le relative tavole di verita possono diventare ingestibili. Per questo si utilizzano leregole di inferenzaometateoremi che forniscono dei modelli per costruire argomentazioni anche molto complicate. La piu usata delle regole di inferenza e (P^(P!Q)) =)QMODUS PONENS: Sostanzialmente: dalla validita in contemporanea diPe diP!Qsegue la validita di Q. Questa regola di inferenza da luogo al classico metodo di dimostrazione diretta. Un altra regola di inferenza e (P!Q)()(qQ!qP) MODUS TOLLENS; che permette di eseguire le dimostrazioni usando il metodo di dimostrazione indiretta o per contrapposizione.Si segnalano, inoltre: ((P!Q)^(Q!R))!(P!R) (P^Q)!P P!(P_Q): Un altro tipo di dimostrazioni sono quelle percontraddizioneoassurdo. Si procede nel modo seguente: si vuol provare chePe vero, allora si suppone cheqPnon sia vero e si ottiene una contraddizione di tipoQ^qQ. Predicati La logica proposizionale naturalmente non e in grado di comprendere tutti i possibili enunciati della matematica. Si pone la seguente: Denizione 3.Unpredicatoe un'aermazione che coinvolge una o piu variabili: x; y; z : : :, ciascuna delle quali sia variabile in undominioouniversoD x, D y, D z; : : : . 3 Ad un predicato, in generale, non si puo attribuire valore di verita: lo si puo a fare nel momento in cui si inseriscono opportunamente i quanticatori o si eettuano sostutuzioni al posto delle variabili. Per approfondimenti sulla logica, lo studente puo consultare il libro A. FACCHINI:ALGEBRA E MATEMATICA DISCRETA, ed. ZANICHELLI alle pagine 283-298 (capitolo 5)