Appunti logica proposizionale e predicativa

LOGICA

Esistono tanti tipi di logica

Noi ci occupiamo di LOGICA CLASSICA

LOGICA CLASSICA

• PROPOSIZIONALE (è un'algebra booleana)
• PREDICATIVA (I ordine)

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

LOGICA

Esistono tanti tipi di logica

Noi ci occuperemo di LOGICA CLASSICA

• PROPOSIZIONALE (è un'algebra booleana)
• PREDICATIVA (I ordine)

LOGICA CLASSICA

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

Lo significato dei suoi costituenti

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

ALFABETO DELLA LOGICA PROPOSIZIONALE

1. T, ⊥

   SIMBOLI DI VERO/FALSO

2. A, B, C, ... , Z

   SIMBOLI PROPOSIZIONALI (lettere maiuscole)

3. ⊤, ∧, ∨, →, ↔

   non, o, e, implica, se e solo se CONNETTIVI LOGICI

4. ( )

   SIMBOLI E SEPARATORI

REGOLE PER DEFINIRE FORMULE BEN FORMATE

DEL LINGUAGGI PROPOSIZIONALI

1) ⊤, ⊥, A, B, ∈ F.B.F. _{caso base della dimostrazione per induzione delle F.B.F}

2) Se Ⓐ, B ∈ FBF allora (¬A), (A∧B), (A∨B), (A→B), (A↔B) ∈ FBF

Ⓐ NON FA PARTE DELL' ALFABETO _{è una metovariantle che stava a posto delle}

3) NIENTE ALTRO ∈ F.B.F.

cardinalità di F.B.F.

|| F.B.F.|| è finito o infinito?

|| F.B.F.|| = INFINITO

La lunghezza di una formula è finita? Sì, sempre

ESEMPI

• (⊥A) è una FBF Vedi clausola 2
• B ∈ F.B.F Vedi clausola 1
• (B) ∉ FBF
• ((A∧B)∨C) ∈ FBF
• ⊥(⊥A∧B)∨C) ∉ F.B.F

Precedenze

IN ORDINE: ¬, ∧, ∨, →, ↔

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

In generale le parentesi NON sono obbligatorie. 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)

CONVENZIONI:

• A → B → C

Se non ci sono parentesi, associamo a destra (A → (B → C))

Definizione:

(A → B) ↔ ((A → B) ∧ (B → A))

- il linguaggio proposizionale può essere ridotto anche a una sola costante

L'ideale sarebbe avere almeno 2

es

_¬, ∧

PRENDIAMO

¬, ∧ ↔ |

• A ∨ B = ¬(¬A ∧ ¬B)
• A → B = ¬A ∨ B

¬, ∨ ↔ |

• A ∧ B = ¬(¬A ∨ ¬B)
• A → B = ¬A ∨ B

CORRISPONDENZA TRA ALGEBRA DI BOOLE E LOGICA PROPOSIZIONALE

• 0 → ⊥
• 1 → ⊤
• ¯ → ¬
• × → ∧
• + → ∨
• D → A, B, C, ...

Assioni dell'algebra booleana scritta in logica proposizionale

• ¬¬A = A
• A ∨ ¬A = ⊤
• A ∧ ¬A = ⊥

Assiomi costantemente a valore

APPARATO DEDUTTIVO

Dato A, |- A dice che A è dimostrabile in logica proposizionale.

Esiste una sequenza finita che dimostra la F.B.F.

Cos'è una dimostrazione?

DIMOSTRAZIONE

• DIRETTA Attraverso un numero finito di passaggi, arrivo a dimostrare quello che voglio
• INDIRETTA Es. per assurdo

Γ = un qualsiasi insieme di assiomi

Apparato Deduttivo

Obiettivo: saper dimostrare una formula A dove A appartiene FBF

A solo se A è sintatticamente corretto

Proprietà

1. Per ogni FBF, il procedimento di dimostrazione termina sempre con SI o NO

DECIDIBILE

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