Riassunto esame Fondamenti di informatica, prof. Vittorini, libro consigliato Fondamenti di Informatica, Fadini Savy

Sistemi di logica e teorie formali

¬B →¬A").(vera- Modus Tollens = Se A→B e B è falso, allora anche A è falsa perchè è vera "A→B =- Deduzione per Assurdo = Se dall'ipotesi di A falso ne consegue un assurdo, allora A è vero.6. Sistemi di logica e teorie formaliSu un piano formale un Sistema di Logica è definita con la quadrupla <S, B, A, R> con:- S un insieme numerabile di Simboli.- B un insieme di Formule (sequenze finite di Simboli) ben formate.- A è un sottoinsieme di B detto di Assiomi.- R è un insieme di Regole di Inferenza (Relazioni tra Formule ben formate).Tra le altre logiche, la Logica Enunciativa può essere così introdotta:→, ⇔",- S = {Variabili booleane, Connettivi "And, Not, Or, Parentesi}.- Bf = {¬A, A→B, A∧B, A∨B, A⇔B} con A e B variabili booleane.→ (B → (A → (B → → ((A → → (A → (¬A → ¬B) →

(¬B → ¬A) = {A, C, B, C, A, B}.

R = {Modus Ponens}.

7. La dimostrazione automatica

Obiettivo della Logica Formale è quello di dimostrare a partire da certi Fatti (espressi in una forma simbolica) una Tesi (anch'essa formalizzata), applicando un certo Algoritmo e ricavando con qualche automatismo la conclusione, cioè Asserto vero o falso. Esistono vari Algoritmi che operano in questa direzione: essi sono detti Motori Inferenziali. Tra questi uno noto è il "Prolog" che a partire da Fatti (chiamati "Clausole") deriva una Tesi (chiamata "Obiettivo") passando per un Insieme di Obiettivi intermedio e aggiornabile, al cui esaurimento si ha la conclusione e l'Algoritmo termina. Il vero problema in questa operazione è l'Esistenza della Dimostrazione (che non in tutte le logiche esiste per ogni problema) e l'Efficienza dell'Algoritmo (dipendente dal numero di Fatti considerati e dalla strategia).

dell'Algoritmo nel visitare l'Albero delle Prove, prove con cui di volta in volta si considerano i Fatti in un ordine di priorità diverso).

8. Logica predicativa e quantificatori.

Mancano nella Logica Enunciativa i concetti di Individuo, Insieme di Individui, Proprietà dell'Individuo e Relazione. La Logica Predicativa supplisce a questa mancanza e rappresenta una evoluzione della Logica Enunciativa: essa introduce il concetto di Variabile (intesa come entità generica rappresentativa di un individuo) e i cosiddetti Quantificatori, ∀ e ∃ Universale e Esistenziale, che indicano "quanti" individui godono di una certa proprietà. Tra i "Predicati" si distinguono allora gli "Enunciati Quantificati" (riferiti ad una variabile e preceduti da un quantificatore), gli "Esemplari" (ottenuti dai "Quantificati" privati del quantificatore), i "Fatti Universali"

(espressioni di valore generale) e "Istanze" diessi (ottenuti sostituendo alle variabili alcune costanti). Ecco alcune note inerenti l'uso e il significato dei quantificatori: ⇔ ¬f(x)".- si ha l'equivalenza "¬∀x f(x)" "∃x ∧(f(x)- Qualche F è G si indica con "∃x g(x))"."∧ ¬g(x))".(f(x)- Qualche F non è G si indica con "∃x →(f(x)- Tutti gli F è G si indica con "∀x g(x))"."→ ¬g(x))".(f(x)- Nessun F è G si indica con "∀x9. Relazioni nAnalogamente alla Matematica, nella Logica dicesi Relazione -aria R fra gli insiemi I', I'', ... In il sottoinsieme R delprodotto cartesiano I' x I'' x ... x In.10. Logica dei predicati del primo ordineLa Logica Predicativa così estesa è detta "Logica dei Predicati di primo ordine" giacché in essa ciascuna

variabile rappresenta un singolo individuo, e non, come in altre logiche superiori, a sua volta un generico predicato.

Due importanti considerazioni vanno fatte sulla possibilità di porre un'interrogazione sulla base di certe premesse fatte: la prima è che un'eventuale risposta sarà coerente solo con l'Universo considerato (si baserà cioè solo sui dati inseriti) e la seconda è che la verità di un Predicato viene provata in termini esistenziali (cioè il Fatto è vero se può esserne considerata almeno una Istanza, cioè se esiste nell'Universo scelto almeno un'individuo che soddisfa quella proprietà).

11. Decidibilità e teorema di Church

Un sistema logico è "Decidibile" se esiste un algoritmo che possa classificare tutte le Argomentazioni in Valide e Non Valide, cioè, in altri termini, è "Decidibile" se è possibile automatizzare

attraverso un calcolatore un processo di dimostrazione di validità per ogni argomentazione. Il teorema di Church afferma che la Logica Predicativa non è Decidibile: il suo verdetto si basa sul fatto che in tale logica, in presenza dei quantificatori, non c'è un numero finito di modelli e quindi è impossibile costruire un algoritmo. Ciò pone delle enormi difficoltà di ordine pratico: si può dimostrare che se una Tesi è vera essa è dimostrabile, ma i limiti teorici accoppiati all'enorme numero di Prove non banali che si possono fare, lascia incerto il fatto che un algoritmo appositamente sviluppato termini o meno, e questo è un requisito minimale se si vuole che l'Algoritmo serva allo scopo (comunque è possibile definire Motori Inferenziali utili, anche se per piccoli e semplici problemi, e soprattutto posti in un certo modo, al fine di sfruttare utilmente la strategia di visita all'albero delle

Capitolo sesto = I linguaggi di programmazione

1. Le stringhe

Un linguaggio di programmazione è prima di tutto costituito (come è ovvio che sia un linguaggio in generale, tanto più se scritto) da "stringhe di caratteri" dove i caratteri di cui si parla appartengono ad uno specificato insieme V detto "vocabolario" o "alfabeto base". [vedere Parte II, Capitolo III, Paragrafo 9]

2. Definizione e riconoscimento dei linguaggi

I linguaggi di programmazione ad alto livello vengono definiti da:

• una Sintassi (che descrive le regole per scrivere un programma formalmente corretto).
• una Semantica (che definisce il Significato di ogni Frase).
• un Vocabolario (costituito da Caratteri, Segni di interpunzione, speciali Operatori e Parole chiave riservate).

Analizzando dunque un Programma riconosciamo in esso:

• componenti Lessicali o "token" (cioè Parole, Simboli, Operatori e Parole chiave).
• Fra

programma (cioè composizioni di token secondo precise regole) di tipo:

• Dichiarativo (per descrivere gli oggetti trattati).
• Esecutivo (per esprimere le azioni da eseguire).

Dunque, quando si scrive un Programma in un Linguaggio, vengono effettuate nell'ordine:

1. un'Analisi Sintattica della Frase (per verificare l'esistenza di token sconosciuti o errati).
2. un'Analisi Semantica della Frase (per vedere se i token, nella combinazione esposta, hanno nel Contesto esaminato un senso o costituiscono un'espressione priva di significato).

I Metodi e Modelli Teorici adoperati per la definizione dei Linguaggi di Programmazione sono:

• le Espressioni Regolari (per la definizione del Lessico).
• le Grammatiche non contestuali (per la definizione della Sintassi).
• la Semantica Operazionale o quella Denotazionale (per la definizione della Semantica).
• modelli di Automi a Stati Finiti e Automi a Pila (come strumenti usati, rispettivamente, per l'analisi Lessicale e Sintattica).

3.

Definizione formale di un linguaggio Intuitivamente si intende per Linguaggio "L" l'insieme delle frasi che con esso si possono costruire: un Linguaggio di Programmazione può dunque essere definito come l'insieme dei suoi possibili (infiniti) programmi. In realtà, se V* è l'insieme completo delle possibili stringhe di simboli appartenenti al vocabolario V del Linguaggio in questione, allora diremo che il Linguaggio di Programmazione è (nel senso sopra-indicato) è un sottoinsieme di V* secondo delle "Regole di produzione" a fondamento delle quali c'è la Sintassi del Linguaggio. Su un piano strettamente formale, la Sintassi S di un Linguaggio di Programmazione L si costituisce di: - un Vocabolario V dei "simboli terminali". - un Vocabolario U dei "simboli non terminali" o "variabili metalinguistiche". - un Simbolo Iniziale I appartenente ad U. - delle Regole di Produzione P. E si affermache: <>. 4. La forma normale di Backus Per descrivere formalmente le regole di produzione P bisogna usare un nuovo linguaggio, distinto dal linguaggio da definire, chiamato Metalinguaggio: uno tra i più noti è il cosiddetto "Linguaggio di Backus" o "Backus Normal Form (BNF)". Esso adopera i "simboli metalinguistici" (<, >, ::=, |) e le "variabili metalinguistiche" (lettera, cifra, identificatore, assegnazione, ...) che indicate tra parentesi angolari rappresentano ciascuna il nome dato ad una classe di oggetti del linguaggio. Essa ammette inoltre anche la notazione Ricorsiva, utile a rendere una definizione più intuitiva e facilmente leggibile (ciò risulta evidente dal secondo esempio, laddove "identificatore" èdefinito in termini di se stesso). Il simbolo "::=" serve a definire una variabile metalinguistica tramite altre variabili metalinguistiche o simboli del linguaggio, e si legge "è definito come": tutti gli "elementi" che lo seguono a destra susseguendosi danno proprio l'idea della concatenazione delle varie stringhe nelle Frasi del Programma... per esempio: <assegnazione> ::= <variabile> = <espressione> Il simbolo " | " significa "oppure" e si usa quando non c'è un'unica definizione possibile... per esempio: <identificatore> ::= <lettera> | <identificatore> <lettera> | <identificatore> <cifra> Più semplici rispetto alle notazioni in forma BNF, sono quelle in EBFN (detta "forma estesa di Backus"), totalmente equivalenti alle prime ma con qualche utile formalismo in più: 1) [ t] = indica che "il simbolo o sequenza di simboli" t

1) {t} indica che "il simbolo o sequenza di simboli" t può apparire da 0 a 1 volta.

2) {t}^n indica che "il simbolo o sequenza di simboli" t può apparire da 0 a n volte.