Appunti Elementi di informatica teorica

Inferenze logiche

Le inferenze logiche sono meccanismi mediante i quali una proposizione viene stabilita vera.

Induzione

• Ampliativa
• Non necessaria
• Caso
• Risultato
• Regola

Deduzione

• Non ampliativa
• Necessaria
• Regola
• Caso
• Risultato

Abduzione

• Risultato
• Regola
• Caso

Logica proposizionale

Ogni linguaggio ha due aspetti: sintassi e semantica.

Sintassi della logica proposizionale

Alfabeto di simboli:

• Connettivi: ¬, ∧, ∨, →, ↔
• Costanti: ⊤, ⊥
• Simboli atomici: A, B, ...
• Separatori: (, )

Formule ben formate:

• Costanti e atomi sono formule.
• Se α è una formula, allora (¬α) è una formula.
• Se α e β sono formule, allora: (α∧β), (α∨β), (α→β), (α↔β) sono formule.

È possibile eliminare alcune parentesi considerando la precedenza dei connettivi: ¬ < ∧ < ∨ < → < ↔.

Le sottoformule di una formula φ sono:

• Se φ è un atomo, allora φ è una sottoformula.
• Se φ è ¬β, allora le sottoformule sono φ e le sottoformule di β.
• Se φ è β o γ (dove o ∈ {∧, ∨, →, ↔}), allora le sottoformule sono φ e le sottoformule di β e γ.

Un albero sintattico è un albero binario dove i nodi diversi dalle foglie sono etichettati con connettivi e le foglie sono etichettate da costanti e atomi.

Semantica della logica proposizionale

La semantica si occupa del significato di un dato linguaggio. Il sistema di valutazione di una formula proposizionale è una tripla <B, T, O> dove:

• B = {0, 1} è l'insieme dei valori di verità.
• T = {1} è l'insieme dei valori che indicano il vero.
• O è un insieme di funzioni per i connettivi logici:

Una funzione di assegnazione o interpretazione V: P → {0, 1} è una funzione che associa agli atomi di una formula un valore di verità. Una valutazione di una formula è una funzione che associa alla proposizione un valore di verità: I_V: Prop → {0, 1}:

• I_V(a) = V(a) se a è un atomo.
• I_V(¬a) = O_¬(I_V(a)).
• I_V(a o β) = O_o(I_V(a), I_V(β)) dove o ∈ {∧, ∨, →, ↔}.

Per ogni assegnazione, la valutazione è unica. Una formula è soddisfatta da un'assegnazione v se v(α) = 1. Una formula è soddisfacibile se esiste v(α) = 1. Una formula è tautologia se per ogni v(α) = 1. Una formula è contraddizione se non esiste v(α) = 1. Una formula è tautologia se e solo se ¬α è contraddizione.

α implica logicamente v(α) = 1 allora v(β) = 1: α ⊧ β. α è logicamente equivalente a β se v(α) = 1 se e solo se v(β) = 1.

Equivalenze logiche:

• Idempotenza
• Associatività
• Leggi di De Morgan
• Commutatività
• Distributività
• Assorbimento
• Doppia negazione
• Terzo escluso
• Contrapposizione

Ad ogni proposizione d è possibile associare una funzione di verità f_d:{0,1}ⁿ → {0,1} che ad ogni assegnazione V associa la valutazione I_v di d. Se n è il numero di atomi distinti di d, esistono 2²ⁿ funzioni di verità. Anche i connettivi possono essere visti come funzioni di verità → esistono 2²ⁿ = 16 connettivi.

Posso scrivere alcuni connettivi mediante combinazioni di altri connettivi. Alcuni insiemi di connettivi si dicono completi se mediante i connettivi dell'insieme posso scrivere tutti gli altri. Un insieme di atomi veri si dice modello A ∈ M se e solo se V(A)=1.

Un modello modella una formula (M ⊧ d) se e solo se f_d(M) = 1:

• M ⊧ A sse A ∈ M
• M ⊧ ⊤ e M ¬⊧ ⊥
• M ⊧ ¬d sse M ¬⊧ d
• M ⊧ d ∧ β sse M ⊧ d e M ⊧ β
• M ⊧ d ∨ β sse M ⊧ d o M ⊧ β
• M ⊧ d → β sse M ¬⊧ d o M ⊧ β
• M ⊧ d ↔ β sse M ⊧ d e M ⊧ β o M ¬⊧ d e M ¬⊧ β

Il modello è un altro modo di vedere la valutazione:

• se M ⊧ d, allora d è soddisfacibile
• se ¬⊧ d, allora d è tautologia
• se ⊧ ¬d, allora d è contraddizione

Se Γ è un insieme di proposizioni, Γ ⊧ d sse ⋃ {Γ ; ¬d} ⊧ ⊥. Teorema di compattezza: se Γ è un insieme di proposizioni, Γ è soddisfacibile se e solo se ogni suo sottoinsieme finito è soddisfacibile.

Sistemi di deduzione

Un sistema di deduzione è un sistema mediante il quale è possibile derivare un sottoinsieme delle formule ben formate utilizzando concetti esclusivamente sintattici.

Sistema assiomatico di Hilbert

Sistema in cui è possibile stabilire le formule rilevanti a partire da un certo insieme di assiomi e un certo insieme di regole di inferenza.

Per il sistema assiomatico di Hilbert:

1. (A → (B → A))
2. ((A → (B → C)) → ((A → B) → (A → C)))
3. ((¬B → ¬A) → ((¬B → A) → B))

Regole di inferenza

1. MP: modus ponens
   • α, α → β
   • β
2. SU: Sostituzione uniforme
   • Φ[P]
   • Φ[ψ, P]

Dove Φ[P] è una formula contenente P e Φ[ψ, P] è la stessa formula dove ogni occorrenza di P è stata sostituita da ψ.

Un insieme di proposizioni Γ si dice teoria. Una dimostrazione è una serie di proposizioni d₁,... dₙ dove d₁,... dₙ sono formule di una teoria, oppure sono ottenute dagli assiomi o dalle regole di inferenza. Ogni proposizione di una dimostrazione, tranne la prima, si dice teorema e si scrive: Γ ⊢ se Γ ≠ ∅ allora d è un teorema del calcolo proposizionale: ⊢ d.

Teorema di deduzione

Γ ∪ {B} ⊢ d se Γ ⊢ B → d.

Relazioni con la semantica

Un sistema di deduzione è vero (o corretto) se tutti i teoremi sono tautologie. È completo se tutte le tautologie sono teoremi. Teoremi di incompletezza di Gödel: ogni sistema contenente l'aritmetica è incompleto o incoerente, irriducibilità della semantica alla sintassi.

Decidibilità della logica proposizionale

Decidibilità = data una proposizione stabilire se è soddisfacibile, tautologia o no. Problema di complessità esponenziale. Si possono usare le tavole di verità o più efficientemente i tableau proposizionali.

Tableau proposizionali

Il sistema di deduzione mediante il quale è possibile stabilire se una formula è soddisfacibile, tautologia o no. Data una formula:

• È una α formula (congiuntiva) se è:
  • d₁ ∧ d₂
  • ¬β₁ ∧ ¬β₂ ≡ ¬(d₁ ∨ d₂)
  • d₁ ∧ ¬d₂ ≡ ¬(d₁ → d₂)
• È una β formula (disgiuntiva) se è:
  • d₁ ∨ d₂
  • ¬β₁ ∨ ¬β₂ ≡ ¬(β₁ ∧ β₂)
  • ¬β₁ ∨ β₂ ≡ β₁ → β₂

Le α-formule vengono scritte di seguito nello stesso ramo mentre le β-formule vengono scritte in rami separati. Inoltre:

• γγ ≡ γλ⇔β ≡ (λ→β)∧(β→λ)

Un ramo è chiuso se lungo quel ramo esiste una contraddizione, altrimenti è detto aperto. Un ramo è soddisfacibile se la congiunzione delle sue formule è soddisfacibile. Un tableau è chiuso se tutti i suoi rami sono chiusi. Un tableau è soddisfacibile se almeno un ramo è soddisfacibile. Il tableau è dimostrazione di λ se il tableau di ⊢λ è chiuso: ⊢_T λ. Anche per i tableau esistono correttezza e completezza. Rami aperti indicano i modelli.

Schema di decidibilità:

• Tableau di λ chiuso ↔ aperto
• Contraddizione tableau di λ chiuso ↔ aperto tautologia soddisfacibile

Linguaggi formali

Un insieme Σ di simboli è detto alfabeto. Una stringa è una sequenza finita di simboli di Σ. La stringa vuota si indica con ε. La lunghezza di una stringa s viene indicata con |s|.

Date due stringhe s e v, la stringa sv è la stringa che, mediante l'operatore di concatenazione, ha i simboli di s seguiti dai simboli di v. Esistono diversi insiemi di stringhe su un alfabeto Σ:

• Σ⁰ = {ε}
• Σ¹ = Σ = {a | a ∈ Σ}
• Σ² = {s | s = as¹, a ∈ Σ, s¹ ∈ Σ¹}
• Σ^m = {s | s = as¹, a ∈ Σ, s¹ ∈ Σ^m-1}

Σ^* = ∪_m≥0 Σ^m dove Σⁱ è l'insieme di tutte le stringhe di lunghezza i e Σ^* è l'insieme di tutte le stringhe. Un linguaggio è un sottoinsieme di Σ^*.

Operazioni sui linguaggi

• Unione: L₁ ∪ L₂ = {s| s ∈ L₁ o s ∈ L₂}
• Intersezione: L₁ ∩ L₂ = {s| s ∈ L₁ e s ∈ L₂}
• Concatenazione: L₁ ⋅ L₂ = {s₁s₂ | s₁ ∈ L₁, s₂ ∈ L₂}
• Complementazione: Ĺ = {s| s ∈ Σ*, s ∉ Ĺ }
• Star: L* = ∪_{m ≥ 0} L^m

Per definire i linguaggi usiamo 2 metodi:

• Generativo: spiegando come costruire il linguaggio (grammatiche)
• Riconoscitivo: riconoscendo le stringhe di un linguaggio (automi)

Non tutti i linguaggi possono essere definiti perché l'insieme dei linguaggi è un infinito non numerabile, l'insieme degli algoritmi è numerabile.

Grammatiche

Una grammatica è una quadrupla ⟨V_T, V_N, S, P⟩ dove:

• V_T è un alfabeto terminale
• V_N è un alfabeto non terminale
• S ∈ V_m è un assioma
• P è un insieme di regole di produzione

Attraverso le regole di produzione è possibile derivare direttamente (⇒) o indirettamente (⇒^*) stringhe di simboli ∈ (V_N ∪ V_T). L'insieme delle stringhe formate solo da simboli di V_T si dice linguaggio generato dalla grammatica. Partendo da un linguaggio esistono diverse grammatiche che lo generano.

Le grammatiche e i linguaggi generati da esse si dividono in:

• TIPO 3 o regolari:
  • S → aS | a ← lineari destre, sono quali S → Sa | a ← lineari sinistre
• Lineari:
  • S → aS | Sa | a
• TIPO 2 o non contestuali:
  • S → (V_N + V_T)⁺
• TIPO 1 o contestuali:
  • d → β dove d = (V_N + V_T)^* V_N (V_N + V_T)^* e |d| ≤ |β| e β = (V_N ∪ V_T)⁺
• TIPO 0 o generali:
  • Qualsiasi tipo di produzioni

Le ε-produzioni possono essere inserite rispettando alcuni criteri:

• TIPO 3 → possono essere inserite in posizione LINEARI → generale anche se poi possono essere riscritte grammaticali equivalenti con TIPO 2 → ε-produzioni solo sull'assioma
• TIPO 1 → se aggiungiamo le ε produzioni in posizione generale diventano equivalenti alle Tipo 0, quindi possono essere incluse solo sull'assioma

Le grammatiche così definite rispettano la gerarchia: TIPO 3 ⊂^C TIPO 2 ⊂^C TIPO 1 ⊂^C TIPO 0.

Dati: ∃ linguaggi regolari L₁, L₂ ⊆ Σ^* allora:

• ∅ e {ε} sono linguaggi regolari
• L₁, L₂, L₁ ∪ L₂, L₁^*, L₁L₂ sono linguaggi regolari

A partire da questi possiamo definire le espressioni regolari a partire da un alfabeto ∑. Infatti:

1. ∅ e a ∈ ∑ sono espressioni regolari
2. ∑ • F, ∑ + F, ∑^* sono espressioni regolari se E e F sono espressioni regolari

Attraverso le espressioni regolari è possibile generare linguaggi regolari:

• E → &Lscr;(E)
• E • F → &Lscr;(E) • &Lscr;(F)
• E + F → &Lscr;(E) ∪ &Lscr;(F)
• E^* → &Lscr;^*(E)

La precedenza degli operatori è * < • < +. Le espressioni regolari vengono rappresentate da cammini di un grafo.

Per vedere graficamente le produzioni della grammatica scriviamo gli alberi di derivazione. Esistono anche grammatiche ambigue, ovvero grammatiche che ammettono più alberi di derivazione per una stessa formula.

Automi a stati finiti

Un automa a stati finiti è una quintupola <Q, Σ, δ, q₀, F> dove:

• Q è un insieme di stati
• Σ è un alfabeto
• δ è la funzione di transizione Q × Σ → Q
• F ⊆ Q è un insieme di stati di accettazione

Una stringa è accettata da un automa a stati finiti se esso legge tutti i simboli e se una volta finita la computazione si trova in uno stato di accettazione. Il linguaggio riconosciuto da un automa è l'insieme delle stringhe accettate dall'automa.

Una configurazione di un automa a stati finiti è un elemento u q v dove u ∈ Σ, q ∈ Q, v ∈ Σ^* può essere:

• Iniziale se u = ε e q = q₀
• Intermedia se u ≠ ε, v ≠ ε
• Di accettazione se q ∈ F e v = ε

Siano c₁=q₁v₁ e c₂ q₂v₂. c₁ ⊢_A c₂ si dice passo di computazione se e solo se δ(q₁,v₂)=q₂ ⊤ v₁ = v₂v₂. Un insieme di passi di computazione si dice computazione. L(A) = {w ∈ Σ^* | ∃ q ∈ F : E q₀ w ⊢_A^* w_mq ε }.

Da un automa si può ottenere una grammatica traducendo δ in regole di produzione. La grammatica ottenuta è sempre regolare o equivalente. Gli automi a stati finiti riconoscono linguaggi regolari.

Automi a stati finiti non deterministici (AFN)

In contrapposizione a quelli deterministici (AFD). In un AFN, letto un simbolo si può passare in più di uno stato. Un AFN è una quintupla <Q, Σ, δ, q₀, F> dove:

• Q è un insieme di stati
• Σ è un alfabeto
• δ è la funzione di transizione δ : Q X Σ∪{ε}→P(Q)
• q₀ è lo stato iniziale
• F⊆Q è l'insieme degli stati di accettazione

La ε-chiusura eps(q) di uno stato q è definita induttivamente:

• q ∈ eps(q)
• se q₁ ∈ eps(q) e q₂ ∈ δ(q₁, ε) allora q₂ ∈ eps(q)

Ad ogni AFN corrisponde un AFD equivalente N = < Q, Σ, δ, q₀, F > A = < Q', Σ', δ, q₀', F' > dove:

• Q' = P(Q)
• δ' = P(Q) × Σ → P(Q)
• δ'^∩(S, a) = ∪ {eps(q) | q ∈ δ(s, a), s ∈ S}
• q₀' = eps(q₀)
• F' = { S ∈ Q' | S ∩ F ≠ Ø }

Inoltre, si può passare da espressioni regolari ad AFN:

• ε ⇒ _{0 ε} ⭕
• Ø ⇒ ➖ 0
• a ⇒ ➖a ➖ ⭕
• Unione R∪S ⇒ ➖0 ➖ ε_ε ➖ R ➖ ⭕ ε ε ⭕
• Concatenazione R-S ⇒ ➖0 ➖ R ➖ S ➖ ⭕ ⭕
• Chiusura R* ⇒ ➖0 ➖ ε ε ➖ R ➖ ⭕ ε ↑

Invece, per passare da un AFD ad un'espressione regolare bisogna prima trovare le equazioni relative ai suoi stati e poi risolvere il sistema negli stati di accettazione. Per farlo si usa il teorema di Arden:

X = B + XA => X = BA^*