Appunti riassuntivi di Logica

Logica e linguaggi: anno accademico 2016/2017

La logica è la base teorica di tutti gli studi informatici.

Linguaggio

• Naturale (molto espressivo ma ambiguo)
• Artificiale (povero e limitato ma univoco)

In cosa consiste la logica

• Traduzione da linguaggio naturale ad artificiale;
• Apprendimento del linguaggio artificiale (con la programmazione);
• Costruzione di dimostrazioni;
• Costruzione di modelli.

Modello: Descrizione formale di un mondo possibile in cui la formula è valida (un controesempio).

Logica proposizionale

Una variabile proposizionale può essere:

• Una frase, una parola o un simbolo ("2+2", piove, x);
• VERA (1) oppure FALSA (0).

Una formula sempre vera per ogni scelta delle variabili si dice tautologia.

Connettivi

La tavola di verità di un connettivo ne definisce la semantica. Il modello è l’assegnamento di valori alle variabili (le singole righe delle tavole di verità).

Variabili modelli

• 2 4
• 3 9
• 4 16

Congiunzione

(∧): Perché la congiunzione sia vera entrambi i congiunti devono essere veri.

Disgiunzione inclusiva

(∨): Anche se entrambi i disgiunti sono veri, la disgiunzione è vera (vel).

Disgiunzione esclusiva

(+): Se entrambi i disgiunti sono veri, la disgiunzione è falsa (aut).

Negazione

(¬): P si dice negato.

Implicazione

(→): Se l’antecedente è falso, l’implicazione è vera a vuoto, indipendentemente del conseguente.

Equivalenza logica

(≡) o biimplicazione.

Logica al primo ordine

Caratterizzata da un alfabeto di simboli.

Simboli di costante

• Rappresentano un solo oggetto nel dominio del discorso.
• Un oggetto può non essere raggiunto da alcuna costante: IRRAGGIUNGIBILE.
• Caratterizzato dalla lettera minuscola.

Esempi:

• aldo → un ragazzo
• felix → un gatto
• chiara → una ragazza
• flock → un cane

Simboli di predicato

• Denotano proprietà o relazioni.
• Caratterizzato dalla lettera maiuscola iniziale.
• Deve avere almeno un argomento (se 1 si dice UNARIO, 2 BINARIO, 3 TERZIARIO…).
• Il numero degli argomenti è fissato = ARIETÀ.
• L’ordine lo si decide a priori e deve essere rispettato sempre: È RILEVANTE.

Esempi:

• Ha(aldo, felix)
• Nero(felix)
• Dare(aldo, felix, chiara, 12.10.2016)

Formula atomica

• Forma più elementare del linguaggio.
• Composta da un predicato seguito dai suoi argomenti.
• Può essere vero/falso a seconda dei modelli.
• Un enunciato di eguaglianza è vero se e solo se i simboli rappresentano lo stesso individuo.
• Può trovarsi in notazione infissa (per i predicati matematici) o prefissa (per il linguaggio comune).

Esempi:

• a = b (notazione infissa)
• eg(a, b) (notazione prefissa)

Lista

Configurazione ordinata con ripetizione di argomenti.

Esempio di esercizio:

Quanti atomi sintatticamente corretti posso essere creati con n argomenti e predicati con k lunghezza di lista? kⁿ

Simboli di funzione

• L’applicazione di un simbolo di funzione ad argomenti forma un termine che denota un individuo/elemento/oggetto.
• Esprimono un individuo.
• Possiedono argomenti e arietà.
• È un’espressione, non una frase.

Esempi:

• funzionepadre(aldo) unaria con notazione prefissa
• funzione3+5 binaria con notazione infissa
• Possiede(padre(aldo), felix) frase atomica con un termine e un argomento

Nozione di termine

• Ogni simbolo di costante è un termine.
• Se f è un simbolo di arietà n e (t₁, t₂, …) sono termini allora f(t₁, t₂, …, t_n) è un termine.
• Un termine denota un solo individuo mentre un individuo può essere denotato da più termini.

Formula atomica / Atomo

Se P è un simbolo di predicato di arietà n e (t₁, t₂, …) sono termini, allora P(t₁, t₂, …, t_n) è un atomo.

Esempi:

• tabella m → prima riga (quinta colonna (m)) termine che individua una determinata posizione nella tabella con un numero contenuto di variabili
• genitori(aldo) termine che denota l’insieme degli individui che sono genitori dell’argomento.

Teorie

Adesso si parlerà di “teorie” perché il significato dei simboli logici è fissato.

Teoria degli insiemi

Due simboli di predicato:

Esempi:

• a → 2
• b → {2,4,6}
• c → 6
• d → {2;4;{2;4;6}}

Teoria dell’aritmetica

Simboli di costante

• 0
• 1

Simboli di funzione

• +
• *

Simboli di predicato

• =
• <
• >

Si può ottenere qualsiasi numero continuando a sommare 1 (n=1+1+1+1…n volte)

Se t₁=0 e t₂=1 allora anche t₁+t₂, t₁*t₂ sono termini.

Due categorie di simboli:

1. Simboli liberi (P, Q, f, h, ...)
2. Simboli definiti (∈ , = , 1, 0, +, *, …)

Esempi di formule atomiche:

• (1+1)+1=1+1+1 VERO
• 0>1 FALSO
• 1+1<1+1+1 VERO

Conseguenza logica / ragionamento / dimostrazione

Sequenza di formule/frasi dove ci sono una o più premesse e una conclusione. Un ragionamento è corretto se è valido, ma può non essere corretto anche se valido. La logica si interessa della validità dei ragionamenti.

Ragionamento

Connettivo di implicazione – Teorema di deduzione

Dimostrazioni di conseguenza

Costruzione di passi giustificati da regole (Premesse, altre frasi o formule, conclusione).

Dimostrazioni di non conseguenza

Esibire un controesempio che mostra la NON validità di un ragionamento.