Pages: [1]   Go Down
Print
Author Topic: Eserciziettinino logica proposizionale  (Read 275 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.896



WWW
« on: 06-12-2017, 14:53:34 »

Dimostare che in deduzione naturale,
per A,B e C arbitrari, non vale che
A v B, B v C |- (A ^ B) v C

Trovare invece A, B e C per cui
A v B, B v C |- (A ^ B) v C
Logged
giorgio_buzzanca
Matricola
*
Offline Offline

Gender: Male
Posts: 22



« Reply #1 on: 07-12-2017, 23:51:28 »

Dimostrarlo ricorrendo alla definizione semantica dei connettivi logici AND e OR, e dunque alla tabella di verità, è abbastanza semplice, basta infatti prendere il seguente caso di riferimento:
A B C  AvB  BvC  A^B      (A^B) v C
0 1 0    1      1      0                0
E di conseguenza possiamo rispondere alla seconda domanda che gli A, B e C per cui vale l'ipotesi sono le combinazioni di 0 e 1 che producono i termini minimi 3,5,6 e 7 della funzione logica (A^B)vC  [011, 101, 110, 111].

Ho provato ad effettuare una dimostrazione in DN che non faccia ricorso alla tabella di verità, ma non sono sicuro della sua correttezza.

Sia Γ = {(AvB), (BvC)}, e sia Γ |- (A^B)vC.
Allora ciò mi assicura che ovunque figuri (A^B)vC come ipotesi io possa sostituirla con la sua deduzione a partire da Γ.
Pertanto qualunque deduzione a partire da {(A^B)vC} può essere sostituita da una equivalente a partire da Γ = {(AvB), (BvC)}.
Prendiamo allora la deduzione (A^B)vC |- AvC :

                  [A^B]1
                 --------^E
                     A            [C]2
(A^B)vC    --------vI  --------vI
                   AvC         AvC
------------------------------------vE(1)(2)
                   AvC

Ciò mi porta ad affermare, stando a quanto detto fino ad ora, che  AvB, BvC |- AvC.
Se esiste una tale deduzione essa allora sarà ottenuta ragionevolmente a partire dalla regola vI o dalla regola RAA avendo supposto prima ¬(AvC).
Se è ottenuta a partire dalla regola vI ciò significa che posso ottenere indifferentemente almeno una tra le deduzioni di A e C.
Ma a partire dall'insieme di ipotesi Γ = {(AvB), (BvC)} ciò non è possibile in alcun modo a meno di introdurre ipotesi che poi non verranno scaricate. Infatti non ho nemmeno la possibilità di utilizzare la regola vE perchè supporre B non mi permette di inferire nulla su A o su C.
Se invece fosse ottenuta dalla regola RAA partendo dall'ipotesi ¬(AvC) ed arrivando a dedurre l'assurdo, allora, sapendo che ¬(AvC)≡(¬A^¬C), dovrei avere una deduzione di A o C a partire dall'insieme di ipotesi Γ = {(AvB), (BvC), ¬A, ¬C}. Ancora una volta però introdurre le ipotesi ¬A e ¬C non mi aiuta ad applicare la regola di vE e a dedurre A o C(potendo poi applicare la regola ¬E per giungere all'assurdo); questo perchè mi ritrovo nella stessa situazione del caso precedente, cioè ancora una volta rimango con una supposizione di B in entrambi i possibili alberi di deduzione che non è utilizzabile per inferire alcunchè su A o C.
Con questo siamo arrivati ad una contraddizione, nata dall'aver supposto che AvB, BvC |- (A^B)vC, quindi, per assurdo, abbiamo dimostrato ciò non è vero.
Logged

Indirizzo email: giorgiobuzzanca@outlook.it
Public Key Id: 68BB499B
Public Key Fingerprint: FD792C4AAC7067DEDE54B070040F6AF568BB499B
Chiave su keyserver.pgp.com e pgp.mit.edu.
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.896



WWW
« Reply #2 on: 08-12-2017, 01:27:43 »

Quote
Dimostrarlo ricorrendo alla definizione semantica dei connettivi logici AND e OR, e dunque alla tabella di verità, è abbastanza semplice, basta infatti prendere il seguente caso di riferimento:
A B C  AvB  BvC  A^B      (A^B) v C
0 1 0    1      1      0                0

Poco chiaro.
Meglio dirlo nel modo seguente:
supponiamo per assurdo che per ogni A, B, e C valga
A v B, B v C |- (A ^ B) v C
Allora varrebbe anche se come A, B e C consideriamo delle variabili proposizionali.
Dovrebbe quindi valere
p v q, q v r |- (p ^ q) v r
Per la proprieta' di correttezza della logica proposizionale dovrebbe quindi valere che
p v q, q v r |= (p ^ q) v r
Il che e' impossibile per definizione di consequenza tautologica.
Infatti per l'assegnamento proposizionale B tale che
B(p)=0, B(q)=1, B(r)=0
avremmo che B-(p v q)=B-(q v r)=1, ma B-((p ^ q) v r)=0.
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.896



WWW
« Reply #3 on: 08-12-2017, 01:34:47 »

Quote
E di conseguenza possiamo rispondere alla seconda domanda che gli A, B e C per cui vale l'ipotesi sono le combinazioni di 0 e 1 che producono i termini minimi 3,5,6 e 7 della funzione logica (A^B)vC  [011, 101, 110, 111].

Diciamolo in modo meno compatto.

Basta prendere come B e come C una tautologia.
Questo implica immediatamente che
A v B, B v C |= (A ^ B) v C
e quindi A v B, B v C |- (A ^ B) v C
per completezza della logica proposizionale.
Logged
Franco Barbanera
Moderator
Forumista Eroico
*****
Offline Offline

Posts: 2.896



WWW
« Reply #4 on: 08-12-2017, 01:39:52 »

La complessita' dell'approccio diretto proposto da Giorgio fa capire come
sia utile poter utilizzare le proprieta' di correttezza e completezza della logica proposizionale.
Un approccio diretto infatti comporta necessariamente dei tipi di ragionamento
sullo stile di quello di Giorgio.
Logged
Pages: [1]   Go Up
Print
Jump to: