Vai al contenuto principale
Oggetto:

Logica

Oggetto:

Logic

Oggetto:

Anno accademico 2022/2023

Codice attività didattica
INF0291
Docenti
Alessandro Andretta (Corso A)
Luca Motto Ros (Corso B)
Matteo Viale (Corso C)
Corso di studio
[008707] Laurea in Informatica
Anno
1° anno
Periodo
Primo semestre
Tipologia
Di base
Crediti/Valenza
6 CFU - Numero di ore - Number of hours: 32 (in aula) + 20 (esercitazioni)
SSD attività didattica
MAT/01 - logica matematica
Erogazione
Tradizionale
Lingua
Italiano
Frequenza
Facoltativa
Tipologia esame
Scritto più orale obbligatorio
Prerequisiti
Conoscenza delle basi della matematica della scuola superiore: in particolare le operazioni aritmetiche di base, le proprietà delle potenze, le equazioni di primo e secondo grado. Conoscenza della terminologia di base relativa alle parti del discorso: nomi, verbi, proposizioni, aggettivi.
Insegnamenti propedeutici (forniscono le competenze attese in ingresso): nessuno
Acquaintance with basic high-school mathematics: arithmetic operations, properties of powers, first- and second-degree equations. Acquaintance with the basic terminology concerning parts of speech: nouns, verbs, adjectives and propositions.
Preparatory Courses (providing the expected entry skills): none
Oggetto:

Sommario insegnamento

Oggetto:

Avvisi

DSA o Disabilità: Sostegno e Accoglienza in UniTO e supporto in sede di Esame
Oggetto:

Obiettivi formativi

L’insegnamento si propone di fornire allo studente le basi della logica matematica, con particolare riguardo per i suoi aspetti più rilevanti per la formazione di base di un informatico, tra cui una adeguata familiarità con le strutture algebriche e le principali tecniche di dimostrazione. Questi contenuti fanno parte degli Obiettivi formativi specifici del CdS in Informatica (L31), in particolare sono tra quelli relativi all'area di Matematica di base.

Aim of the course is to provide student with mathematical logic basics, with particular attention to its most relevant aspects for basic training of a computer scientist, including adequate familiarity with algebraic structures and the main proof techniques. These contents are part of the specific educational objectives of the CdS in Computer Science (L31), in particular they are among those relating to the area “Matematica di base” 

Oggetto:

Risultati dell'apprendimento attesi

CONOSCENZA E CAPACITÀ DI COMPRENSIONE. Conoscenza delle principali tecniche di dimostrazione e delle formulazioni classiche del principio di induzione. Conoscenza della struttura delle formule del primo ordine. Conoscenza delle definizioni delle principali nozioni semantiche relative alla logica del primo ordine (validità, conseguenza logica)

CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE. Capacità di riconoscere le principali tecniche di dimostrazione (diretta, per assurdo, per contrapposizione, per casi) in semplici dimostrazioni di proposizioni relative a strutture algebriche e relazionali. Dovrà dimostrare di riconoscere l’esistenza o meno di biiezioni tra insiemi infiniti costruiti mediante le operazioni di unione disgiunta, prodotto cartesiano, insieme potenza, e insieme delle sequenze finite. Dovrà essere in grado di utilizzare le principali forme del principio di induzione (ordinaria, forte, principio del minimo) in semplici dimostrazioni aritmetiche o relative alla sintassi formale dei linguaggi proposizionali e del prim’ordine. Dovrà essere in grado di analizzare sia sintatticamente che semanticamente le formule proposizionali, anche mediante l'uso di tavole di verità. Dovrà dimostrare di essere in grado di formalizzare mediante formule logiche semplici asserzioni formulate in italiano. Dovrà essere in grado di valutare la validità o meno di semplici formule del prim'ordine in strutture algebriche in accordo con le regole della semantica di Tarski e dovrà essere in grado di stabilire quando una formula non è conseguenza logica di altre formule provvedendo semplici controesempi. Dovrà inoltre sapere determinare l'insieme di verità di una data formula del prim'ordine in una struttura assegnata.

AUTONOMIA DI GIUDIZIO. Acquisizione dei criteri di base per riconoscere la corretta impostazione di una semplice dimostrazione.

ABILITÀ COMUNICATIVE. Acquisizione degli elementi della terminologia logica di base.

CAPACITÀ DI APPRENDIMENTO. Acquisizione di capacità autonome di apprendimento e di autovalutazione della propria preparazione, teorica e pratica.

KNOWLEDGE AND UNDERSTANDING. Knowledge of the main proof techniques and the standard formulations of the induction principle. Knowledge of the structure of first-order formulas. Knowledge of the definitions of the main semantical notions of first-order logic.

APPLYING KNOWLEDGE AND UNDERSTANDING. Ability to recognize the main proof techniques (direct, reductio ad absurdum, contraposition, proof by cases) in the proof of simple propositions about algebraic and relational structures. Ability to recognize the existence or non-existence of bijections among infinite sets built by disjoint union, cartesian product, power set and formation of finite sequences. Ability to apply the main forms of the induction principle (ordinary induction, strong induction and least number principle) in simple proofs concerning properties of natural nmumbers and propositional and first-order formulas. Ability to analyze syntactically and semantically propositional formulas, also by means of truth tables. Ability to translate simple natural language statements into first-order formulas. Ability to assess the validity of simple first-order formulas in algebraic structures according to the clause of Tarski's semantic definition, and to prove that a given formula is not a logical consequence of other formulas by means of counterexamples. Finally, the student is assumed to be able to establish the truth-set of a first-order formula in a given structure.

MAKING JUDGMENTS. Acquisition of the basic criteria to assess the soundness of a simple proof.

COMMUNICATION SKILLS. Acquisition of the elements of the basic logical terminology.

LEARNING SKILLS. Acquisition of autonomous learning and auto-evaluation skills of their own compentences, theoretical and practical.

Oggetto:

Programma

Tecniche di dimostrazione (8 ore circa) • Dimostrazione diretta, per assurdo, per contrapposizione; • Connettivi logici e loro significato in termini di condizioni di verità; • Tavole di verità e conseguenza logica tra proposizioni. Insiemistica di base (8 ore circa) • Insiemi • Relazioni • Funzioni Cardinalità (10 ore circa) • Insiemi numerabili e più che numerabili: esempi; • Operazioni infinitarie: unioni e intersezioni, prodotti e somme, con le principali proprietà. Il principio di induzione (6 ore circa) • Forma ordinaria e forte del principio di induzione; • Principio del minimo; • Equivalenza tra forme del principio di induzione; • Induzione strutturale; • Ricorsione. Formalizzazione (6 ore circa) • Linguaggi proposizionali e del prim’ordine: termini, quantificatori, alfabeto non logico, formule; • Schemi di traduzione da linguaggio naturale in linguaggi del prim’ordine (condizione sufficiente, necessaria, per tutti gli n abbastanza grandi, ci sono n arbitrariamente grandi,…) Semantica della Logica del primo ordine (14 ore circa) • Regole della semantica di Tarski per formule del primo ordine: esempi, e definizioni; • Conseguenza logica tra formule del primo ordine: definizioni e costruzione di contro-esempi.
Proof techniques (8 hours) • Direct proof, proof by contradiction and by contraposition. • Logical constants and their meanings in terms of truth tables. • Logical consequence. Basic set theory (8 hours) • Sets • Relations • Functions Cardinality (10 hours) • Countable and uncountable sets: examples; • Infinitary set operations: union and intersections, sums and products, and their main properties. The principle of induction (6 hours) • Ordinary and strong forms of the induction principle.The least number principle. • Equivalence of the forms of the induction principle. • Structural induction. • Recursion. Formalization (6 hours) • Propositional and first order languages: terms, quantifiers, non-logic alphabet, formulas; • Patterns of translation from natural language to first order languages (sufficient condition, necessary condition, for all n large enough…, there are arbitrarily large n…) Semantics of first order logic (14 hours) • Tarski semantics for first order formulae: examples and definitions; • Logical consequence between first order formulae: definitions and construction of counterexamples. .

Oggetto:

Modalità di insegnamento

Il corso sarà svolto esclusivamente in presenza, con lezioni frontali nelle aule e orari indicati sul sito del Dipartimento di Informatica. A qualche settimana dall'inizio del corso, verranno parallelamente attivati i tutorati.

The course will be carried out exclusively in presence, with lectures in the classrooms and times indicated on the website of the Department of Computer Science. Tutoring will be activated in parallel a few weeks before the start of the course.

Oggetto:

Modalità di verifica dell'apprendimento

Le prove di esame sono scritte a meno di motivata richiesta di esame orale da parte dei docenti come integrazione della prova scritta. Le domande dello scritto e dell'eventuale orale possono riguardare sia la teoria che lo svolgimento di esercizi. L’esito dell’esame è espresso in trentesimi.
 The exams are written unless the teachers request an oral exam as a supplement to the written exam. The questions of the written and possible oral can involve both the theory and the carrying out of exercises. The result of the exam is expressed in thirtieths.

Testi consigliati e bibliografia

Oggetto:

Andretta, Cardone, Motto Ros, Viale: Dispense di logica matematica, 2017.



Oggetto:

Insegnamenti che mutuano questo insegnamento

Oggetto:
Ultimo aggiornamento: 11/09/2023 08:41
Location: https://laurea.informatica.unito.it/robots.html
Non cliccare qui!