LOGICA E ALGEBRA

Il volume ha l’obiettivo di fornire agli studenti dei primi anni di un corso di laurea in Informatica, Ingegneria informatica e, più in generale, del settore dell’informazione, un quadro ampio di nozioni fondamentali di logica e algebra.
Lo scopo viene raggiunto tramite una vasta raccolta di esercizi interamente svolti e accompagnati dagli opportuni richiami di teoria.
Il materiale presentato è stato ideato sulla base della pluriennale esperienza degli autori come docenti di corsi di Logica e algebra offerti agli studenti del Politecnico di Milano.
Gli autori sono, o sono stati, tutti docenti del corso di Logica e Algebra presso il Politecnico di Milano.
Notazioni

1 Relazioni e funzioni

1.1 Relazioni

1.1.1 Relazioni binarie

1.1.2 Relazioni binarie su un insieme

1.1.3 Relazioni di equivalenza

1.1.4 Relazioni d’ordine

1.2 Funzioni

1.2.1 Funzioni e relazioni di equivalenza

1.2.2 Cardinalit`a di un insieme

1.3 Esercizi

1.3.1 Relazioni binarie

1.3.2 Relazioni di equivalenza

1.3.3 Relazioni d’ordine

1.3.4 Funzioni

1.3.5 Cardinalità di insiemi

1.3.6 Esercizi vari

2 Logica proposizionale

2.1 Sintassi

2.1.1 Analisi sintattica

2.1.2 Precedenza degli operatori

2.2 Semantica

2.2.1 Tavole di verità

2.2.2 Soddisfacibilità e conseguenza semantica

2.2.3 Equivalenza semantica 78

2.3 Il legame tra sintassi e semantica

2.3.1 Sistemi formali

2.3.2 Il calcolo per risoluzione

2.3.3 Clausole di Horn

2.3.4 Risoluzione lineare per input e input-refutazione

2.4 Esercizi

2.4.1 Sintassi

2.4.2 Semantica

2.4.3 Risoluzione

2.4.4 Esercizi vari

3 Logica del primo ordine

3.1 Sintassi

3.1.1 Analisi sintattica

3.1.2 Precedenza degli operatori

3.1.3 Variabili libere e vincolate

3.2 Semantica

3.2.1 Soddisfacibilità e conseguenza semantica

3.2.2 Equivalenza semantica

3.2.3 Forma normale prenessa

3.2.4 Forma di Skolem

3.3 Il legame tra sintassi e semantica

3.3.1 Sistemi formali

3.3.2 Teorie del primo ordine con identità

3.3.3 Il calcolo per risoluzione

3.4 Esercizi

3.4.1 Sintassi

3.4.2 Semantica

3.4.3 Deduzione e risoluzione

3.4.4 Teorie con identità

3.4.5 Esercizi vari

4 Strutture algebriche

4.1 Leggi di composizione

4.2 Strutture algebriche

4.2.1 Semigruppi

4.2.2 Monoidi

4.2.3 Gruppi

4.2.4 Anelli

4.2.5 Reticoli

4.3 Esempi fondamentali di strutture algebriche

4.3.1 Gruppi di classi di resto

4.3.2 Gruppi simmetrici

4.3.3 Gruppi di movimenti rigidi e gruppi diedrali

4.3.4 Anelli di classi di resto

4.3.5 Anelli di matrici e gruppi generali lineari

4.3.6 Anelli di polinomi

4.4 Sottostrutture di una struttura algebrica

4.5 Congruenze e quozienti

4.6 Omomorfismi

4.7 Esercizi

4.7.1 Definizioni e proprietà

4.7.2 Sottostrutture

4.7.3 Congruenze e omomorfismi

4.7.4 Aritmetica modulare

4.7.5 Esercizi vari

5 Formalizzazione di problemi e dimostrazione automatica

5.1 Sintassi e funzionamento di SPASS

5.2 Linguaggio naturale

5.3 Insiemi

5.4 Insiemi ordinati

5.5 Semigruppi e gruppi

5.6 Anelli

Indice analitico