Note di Logica Matematica n.2

Claudia Malvenuto e Roberto Maieli ^{∗} canale E-O - a.a. 2002-2003

22 novembre 2002

L’insieme dei connettivi ¬, ∧, ∨ costituisce una base di connettivi, nel senso che sono sufficienti a definire da soli tutti gli altri connettivi. In realtà la coppia di connettivi ¬, ∧ (o rispettivamente, la coppia ¬, ∨) basta da sola a definire tutti gli altri connettivi. Questo è quanto esprime il prossimo teorema.

Teorema 1 (definibilità dei connettivi) Per ogni formula proposizionale A esiste una formula A′ tale che A ≡ A′ ed A′ usa solo i connettivi ¬, ∧ (rispettivamente ¬, ∨).

Dimostrazione: Dimostriamo che la coppia ¬, ∧ è una base di connettivi (il caso ¬, ∨ è analogo ed è lasciato come esercizio). Procediamo per induzione sul numero di connettivi che compaiono nella formula A.

1. A = p, in altre parole A è un atomo: in questo caso A′ = A, non occorre modificare A perché in A non compaiono connettivi.

2. A = ¬B: la formula B ha un connettivo in meno di A, dunque per ipotesi d’induzione esiste una formula B′ ≡ B in cui si usano solo i connettivi ¬ e ∧; per il lemma sulla sostituzione ^{1} concludiamo ¬B ≡ ¬B′. Chiaramente, ¬B′ è la formula A′ cercata, essa infatti non contiene altri connettivi se non ¬, ∧.

∗Dipartimento di Informatica, Università di Roma “La Sapienza”, Via Salaria, 113.

E-mail: claudia, maieli@dsi.uniroma1.it.

1Lemma della Sostituzione: Sia A una sottoformula di B, e sia A′ una formula tale che A ≡ A′. Allora la formula B′ ottenuta rimpiazzando in B il sottoalbero A con A′ è tale che B ≡ B′.

3. A = B ∧ C: per ipotesi d’induzione, avendo sia B che C un numero minore di connettivi che A, esistono B′, C′ definiti solo in termini dei connettivi ¬, ∧ logicamente equivalenti rispettivamente a B e C. Allora per il lemma sulla sostituzione concludiamo A ≡ B′ ∧ C′. Tale formula contiene solo i connettivi ¬, ∧.

4. A = B∨C: per la legge di De Morgan si ha B∨C ≡ ¬(¬B∧¬C); quindi procediamo come nel caso 2, prendendo come A la formula ¬(¬B∧¬C).

5. A = B → C: ricordiamo che si ha l’equivalenza logica B → C ≡ ¬B ∨C; possiamo quindi usare il caso 4 applicato alla formula ¬B ∨C.

6. A = B ↔ C: usando l’equivalenza logica B ↔ C ≡ (B → C) ∧ (C → B), si può procedere come nel caso 3.

Sia ↑, denotato anche come Nand (rispettivamente ↓, Nor), il connettivo definito nel seguente modo:

A ↑ B := ¬(A ∧ B)

(rispettivamente, A ↓ B := ¬(A ∨ B)), per A, B formule proposizionali.

Teorema 2 Per ogni formula proposizionale A esiste una formula A′ tale che A′ fa uso solo del connettivo ↑ (rispettivamente, ↓) e A ≡ A′.

Dimostrazione : Proveremo che ogni formula si può esprimere usando solamente Nand. La dimostrazione del fatto che si può scegliere solo il connettivo Nor per esprimere ogni formula è del tutto analoga ed è lasciata al lettore. Per il teorema 1, possiamo limitarci a considerare solo formule la cui base sia costituita dalla coppia di connettivi ¬, ∧. Procediamo per induzione sul numero di connettivi che compaiono nella formula A. Ci sono solo tre casi:

1. A è un atomo oppure una costante: il teorema in questo caso è banalmente vero, lasciamo A intatta.

2. A = ¬B: per l’idempotenza di ∧, abbiamo che A ≡ ¬(B ∧ B) = (B ↑ B). Poiché B ha un connettivo in meno di A = ¬B, possiamo applicare l’ipotesi induttiva a B: esiste una formula B′ ≡ B che usa solo il connettivo ↑. Applicando il lemma di sostituzione si ha A ≡ B′ ↑ B′. Chiaramente B′ ↑ B′ é definita solo tramite il connettivo ↑.

3. A = B ∧C: per la doppia negazione B ∧C ≡ ¬(¬(B ∧C)) = ¬(B ↑ C); procediamo quindi come nel caso 2, prendendo in considerazione la formula ¬(¬(B ∧ C)).