Istituzioni di logica - riassunto

Istituzioni di logica (riassunto)

Enunciato, connettivi e formula

• Enunciato = proposizione per la quale sia sensato chiedersi se sia vera o falsa.
  • Enunciato semplice (o atomico): non contiene nessun altro enunciato.
  • Enunciato composto: è possibile scomporlo in enunciati più semplici.
• Connettivi = permettono di ottenere enunciati composti da enunciati semplici (“e”, “o”, “se”).
• Formula = espressione ottenuta da un insieme di simboli, chiamati lettere proposizionali, mediante l’applicazione dei connettivi.

Rappresentazione, in un linguaggio artificiale, del contenuto concettuale degli enunciati del linguaggio naturale.

• p ∧ q.
• p → enunciato, “piove”.
• ∧ → connettivo, “e”.
• q → enunciato, “c’è vento”.

Linguaggio proposizionale

• Linguaggio proposizionale: insieme i cui elementi si dicono lettere proposizionali.
  • Con l’eventuale aggiunta di apici o indici.
• Formule = stringhe di simboli ottenute applicando un numero finito di volte le seguenti regole di formazione:
  • p∈ L.
  • Ogni è una formula, detta formula atomica.
  • A₁ A₂.
  • Se A₁ e A₂ sono formule, tali sono:
  • A₁ ∧ A₂.
  • A₁ ∨ A₂.
  • A₁ → A₂.
  • ¬ A₁.

Caratteri dei connettivi

• ∧ = e.
• ∨ = o.
• → = se… allora.
• ¬ = non.

Le formule vengono indicate con lettere maiuscole dette metavariabili, con indici e apici F. L’insieme di tutte le formule è indicato L.

Convenzioni di notazione

• Si utilizzano molte parentesi → per unicità di lettura.
  • Che serve a stabilire il connettivo principale in formule non atomiche.
• Per alleggerire la scrittura, l’uso delle parentesi non viene rispettato alla lettera:
  • Le parentesi esterne → omesse.
  • p₁ … p_n sta per: (p₁ ∧ (p₂ ∧ … (p_n−1 ∧ p_n))).
  • ¬ lega più strettamente di ∧ e ∨, che stringono più strettamente di →.
  • Quindi, in lettura, si parte dall’esterno.
  • Prima →.
  • Poi ∨, ∧.
  • Ed infine ¬.
  • A ↔ B sta per (A → B) ∧ (B → A).
  • ↔ = connettivo chiamato bi-implicazione o equivalenza materiale.

Valore di verità e ottica vero-funzionale

• Una formula denota un’asserzione → che può essere vera o falsa.
• Noto il valore di verità dei suoi costrutti si può determinare il valore di verità della formula stessa.

• Ottica vero-funzionale: definire il significato di un connettivo = specificare sotto quali condizioni è vero o falso un enunciato che lo contiene come connettivo principale.
• Semantica bivalente: i valori di verità sono due:
  • Vero T.
  • Falso F.
• Tavola di verità per il connettivo:
  • Verifica di veridicità di un enunciato.

Tavole di verità dei connettivi

• Tavola di verità per il connettivo ∧ (congiunzione):
  • A ∧ B è vera se e solo se sia A che B sono vere.
• Tavola di verità per il connettivo ∨ (disgiunzione):
  • A ∨ B è vera quando almeno uno degli enunciati è vero.

• Tavola di verità per il connettivo ¬ (negazione):
  • ¬ A è vera se e solo se A è falsa.

• Tavola di verità per il connettivo → (implicazione):
  • A → B è falsa solamente quando A è vera e B è falsa.

• Nell’implicazione (→), l’enunciato è falso solo se:
  • La conclusione è falsa e la premessa vera.
  • È invece vero anche se la premessa è falsa.

Stabilire la verità di una formula proposizionale

• Fissiamo innanzitutto il fatto di accettare di avere solo 2 possibili valori di verità (T e F).
  • 2 ≔ {1,0} → insieme dei valori di verità.
• Si procede per gradi → partendo dalle formule atomiche, fino a quelle più complesse.
  • Atto di assegnamento → funzione matematica.
  • Che va dall’insieme delle formule atomiche → all’insieme di valori di verità.
  • V : L → 2.
  • Ovvero: prende in entrata formule atomiche.
  • E dà in uscita un valore di verità.
  • V → funzione di valutazione.
  • L → insieme del linguaggio proposizionale.
  • 2 {1,0} → insieme dei valori di verità.
• Assegnato il valore di verità alle formule atomiche, il valore di verità delle formule composte è fissato automaticamente con le tavole di verità per i connettivi.

Valori di verità dei connettivi

• Valore di verità della negazione:
  • V(¬ A) ≔ 1 − V(A).
  • L’assegnamento di valore di verità di ¬ A si ottiene togliendo 1 al valore di verità di A.
• Valore di verità della disgiunzione:
  • V(A ∨ B) ≔ max (V(A), V(B)).
  • L’assegnamento di valore di verità di A ∨ B si ottiene scegliendo il maggiore dei valori di verità attribuiti ad A e B.
• Valore di verità della congiunzione:
  • V(A ∧ B) ≔ min (V(A), V(B)).
  • L’assegnamento di valore di verità di A ∧ B si ottiene scegliendo il minore dei valori di verità attribuiti ad A e B.
• Valore di verità della implicazione:
  • V(A → B) ≔ max (1 − V(A), V(B)).
  • L’assegnamento di valore di verità di A → B si ottiene scegliendo il massimo tra:
  • (1 − V(A)), ciò che si ottiene sottraendo 1 dal valore di verità di A.
  • E il valore di verità di B.
• Valore di verità della bi-implicazione:
  • V(A ↔ B) = 1 se e solo se V(A) = V(B).
  • Quindi, A ↔ B è vero se e solo se V(A) è uguale a V(B).

Possibili definizioni relative ad una formula in base al valore di verità

• Tautologia (o verità logica):
  • Una formula A è una tautologia qualora si abbia V(A) = 1 per ogni possibile V.
  • Se quindi è vera secondo ogni V.
• Contraddizione (o formula refutabile):
  • Una formula A è refutabile qualora valga V(A) = 0 per ogni possibile V.
  • Se quindi è falsa secondo ogni V.
• Formula soddisfacibile:
  • Una formula A è soddisfacibile se e solo se V(A) = 1 per almeno un V.
  • Se quindi è vera per almeno 1 V.

Tavola di verità e interpretazioni possibili

• Tavola di verità che calcoli V(A) per tutti i V.
• Sono rilevanti solamente i valori di V sulle lettere proposizionali che compaiono in A.
• Se A contiene n lettere proposizionali:
  • Saranno prese in considerazione solo 2ⁿ interpretazioni possibili.

Costruzione della tavola di verità

• Inserire prima gli enunciati atomici.
• Poi i connettivi.
• Infine inserire l’enunciato composto.

Applicando via via le tavole di verità per ciascun connettivo di ogni sotto-formula, si ottiene il valore di verità della formula nel suo complesso.

• Esempio: p ∨ q → ¬ r.
• Abbiamo 3 lettere proposizionali → quindi 2³ interpretazioni possibili.

• Ad ogni assegnamento di verità alle lettere proposizionali:
  • Corrisponde un valore di verità della formula nel suo complesso.
• La formula è soddisfacibile → esiste almeno un assegnamento che la rende vera.
  • Non è una tautologia perché non è vera per ogni V.

Studio della correttezza delle inferenze

• Studio della correttezza delle inferenze (= schemi di ragionamento).
• La congiunzione ha:
  • Come antecedente le premesse dell’inferenza.
  • Come conseguente, la conclusione dell’inferenza.
• Vi sono inferenze intuitivamente corrette ma non giustificabili con il calcolo proposizionale.
• È necessario considerare più a fondo la struttura interna delle proposizioni.

Ai connettivi ∧, ∨, →, ¬ aggiungiamo due nuovi operatori, i quantificatori.

• ∀ → quantificatore universale “per ogni”.
• ∃ → quantificatore esistenziale “esiste”.

Costanti e predicati

• Costanti = elementi del dominio del discorso.
• Predicati = proprietà di questi oggetti, o relazioni che posso intercorrere tra questi.
• In sostanza → i predicati permettono di esprimere proprietà e relazioni su insiemi di oggetti.

Quindi:

• x P → la costante x gode di una proprietà P.
• ∀x P(x) → per ogni x vale la proprietà P.
• ∃x P(x) → esiste un x che gode della proprietà P.
• U sta per il predicato “essere uomo”.
• M sta per il predicato “essere mortale”.
• a invece sta per “Socrate”.
• U sta per “essere uomo”.
• M sta per “essere mortale”.
• A sta per “essere animale”.

Linguaggio elementare o di primo ordine

• Linguaggio elementare (o di primo ordine) è composto di:
  • Connettivi proposizionali → ∧, ∨, →, ¬.
  • 2 quantificatori → ∀, ∃.
  • Le variabili individuali → x₀, x₁, …
  • Le costanti individuali → a₀, a₁, …
  • Le lettere predicative → P, Q, …
  • Le lettere funzionali → f, g, …

Definizioni del linguaggio elementare

• Linguaggio elementare L → è una quadrupla ⟨P, F, α, β⟩.
• È quindi costituito da 4 elementi:
  • P è l’insieme dei simboli di predicato.
  • α è una funzione che assegna ad ogni P la sua arietà.
  • α : P → N.
  • F è l’insieme dei simboli di funzione.
  • β è una funzione che assegna ad ogni F la sua arietà.
  • β : F → N.

Cos’è l’arietà?

• Nel caso dei predicati (P):
  • Se si tratta di predicato nominale:
    • Il suo simbolo avrà arietà 1.
    • Perché per ottenere un enunciato è sufficiente 1 sola specificazione.
  • Se si tratta di predicato verbale, il suo simbolo potrà avere:
    • Arietà 2 → predicati che richiedono 2 specificazioni per divenire enunciati.
    • Arietà 3 → predicati che richiedono 3 specificazioni per divenire enunciati.
  • Le lettere proposizionali:
    • Rappresentano di per sé un enunciato.
    • Hanno quindi arietà 0.
  • Simboli di predicato secondo l’arietà:
    • Arietà 0:
      • Sono le lettere proposizionali.
      • Usati per formalizzare frasi composte da verbi impersonali.
    • Arietà 1:
      • Rappresentano proprietà d