Appunti logica proposizionale e predicativa

LOGICA

• Esistono tanti tipi di logica

Noi ci occupiamo di logica classica

LOGICA CLASSICA

• PROPDSIZIONALE (È un'algebra booleana)
• PREDICATIVA (I ordine)

Una logica è definita da un apparato sintattico e da una semantica

Il significato dei suoi costrutti

APPARATO SINTATTICO

• solitamente si parte da dall'alfabeto
  • I simboli di partenza

  es. JAVA - lettere, simboli, numeri

• Regole (sono in numero finito e permettono di stabilire quando un costrutto gode di tali regole)
  • NON VALE NEI LINGUAGGI NATURALI
    • es. italiano
• Apparato deduttivo
  • L'insieme delle regole che ci consentono di passare da un'istruzione all'altra

Precedenze

IN ORDINE: ¬ ∧ ∨ → ↔

es.

¬A ∧ B ∨ C → LA POSSO INTERPRETARE: (((¬A)∧B)∨C)

In generale le parentesi NON sono obbligatori. Siamo obbligati a metterle se la formula non rispecchia le precedenze o se ci sono problemi di ambiguità.

es.

¬A ∧ B ∨ C = (((¬A)∧B)∨C) ≠ ((¬(A∨B))∧C)

caso estremo

A → B → C

CONVENZIONI:

Se non ci sono parentesi, associamo a destra

(A → (B → C))

vedremo che implica non è né: commutativa né associativa a differenza di ∧ e ∨

Teorema della logica proposizionale

Devo stabilire un apparato deduttivo

per dimostrare una certa formula

per assurdo

(faccio il falso)

Apparato deduttivo manipola FBF utilizzando segni e regole

Metodi di dimostrazione

• Assiomi + regole (Hilbert)
• Regole dirette (ded. naturale di Gentzen)
• Regole indirette (Tableaux)

Lavorano su FBF con polarità

Metodo che vedremo

esempio

├ ¬(A ∧ B) → (¬A ∨ ¬B) è dimostrabile? SÌ

F(¬(A ∧ B) → (¬A ∨ ¬B))

1. Applico F → : T ¬(A ∧ B), F(¬A ∨ ¬B)
2. Applico T ¬ : F(A ∧ B), F(¬A ∨ ¬B)
3. Applico F ∨ : F(A ∧ B), F ¬A, F ¬B
4. Applico F ∧ : F A, F B, F ¬A, F ¬B
5. Applico F ¬ : F A, T A, F B, F ¬B
6. Applico F ¬ : F A, T B, F B, T A, T B

DIMOSTRABILE

Dimostrazione con il metodo deduttivo

F (A → B) ⊢ (ƬB → Ƭ A)

Ƭ A → B , Ƒ ⊢ Ƭ B → Ƭ A

Ƭ A → B , Ƭ ⊢ B , Ƒ → Ƭ A

Ƭ A → B , Ƒ B , Ƒ ⊢ Ƭ A

Ƭ A → B , Ƒ B , Ƭ A ⊢ Ƭ B , Ƒ B ⊢ Sub A

⊢ Ƒ A , Ƒ B , Ƭ A ⊢ Sub B , Ƒ B ⊢ Ƭ A → OK

dimostrazione delle parte 1

Teorema fondamentale

Teorema di completezza e validità

⊢ A   ↔   ⊨ A

Se una formula è dimostrabile è una tautologia e viceversa

1) c'è una sola costante: 0

2) + ², * ², S ¹ il Successore

2 FUNZIONI DI ARIETÀ 21 " " 1

3) = ² IDENTITÁ

considerazioni

1. ∀x (P(x) → Q(x))
   1. per ogni si applica a tutta la formula
   2. è chiusa cioè non esiste nessuna variabile libera
2. ∀x P(x) → Q(x)
   1. il primo connettivo da applicare è implica
   2. è aperta cioè x compare sia vincolata sia libera

(∃x P(ax) ∧ ∃x ¬Q(ax)) → ∃x (P(ax) ∧ R(ax))

F →

┬ (∃x P(ax) ∧ ∃x Q(ax)), F ∃x (P(ax) ∧ R(ax))

───────────

┬₁ ¬∃x P(ax), ┬ ∃x ¬Q(ax), F ∃x (P(ax) ∧ R(ax))

───────────

┬ P(ax), ┬ ∃x ¬Q(ax), F ∃x (P(ax) ∧ R(ax))

─────────────────

┬ P(ax), ┬ Q(bx), F P(ax) ∧ R(bx)

─────────────── Ω

┬ P(ax), ┬ Q(bx), F

───────────────

⌊

┬ P(ax), ┬ Q(bx), ┬ P(ax), ┬ R(bx), F

… e

NON CHIUDI

POSSO CONTINUARE ALL’INFINITO

3. SARA HA ALMENO UN AMICO CHE E' SPOSATO CON UNA SUA AMICA

∃x ∃y (SARA (x) ∧ AMICA (SARA (y)) → SPOSATO (x,y))

un altro predicato

4. OGNI MOTO HA UNA TARGA

PREDICATI: MOTO (x) , TARGA (x)

COSTANTI:

∀x (MOTO (x) → TARGA (x))

In questo caso la targa non si dice che targa è. Una moto può avere 2 targhe

L'unicità la vedremo più avanti

Prendiamo

∃x (∀x A(x) ∨ ∀ T A(x))

F ∀x A(x) ∨ T A(a), A

F ∀x A(x), F T A(a), A

F ∀x A(x), T A(a), A

F A(b), T A(a), A

F A(b), T A(a), F ∀x A(x) ∨ T A(b), F U

F A(b), T A(a), F ∀x A(x), F A(b), A

F A(b), T A(a), F ∀x A(x), T A(b), A

CHIUDE!

SIGNORE NON CHIUDERE