Forum Informatica Unict

LAUREA MAGISTRALE => Logica Computazionale, 9 CFU => Topic started by: bapu on 17-09-2012, 11:54:21



Title: Esercizio deduzione naturale
Post by: bapu on 17-09-2012, 11:54:21
Salve, qualcuno mi aiuterebbe a capire come risolvere questo esercizio?

((A implica B) or C) implica ((A and notB) implica C)

Grazie in anticipo


Title: Re:Esercizio deduzione naturale
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 17-09-2012, 13:42:28
Non so cosa si tratta in questa materia, ma provo a "semplificare" l'espressione booleana, evidenziandone i passaggi:

\fs{4}((A\Rightarrow B)+C)\Rightarrow((A\overline{B})\Rightarrow C)\;{\Longleftrightarrow}_1\;\\((\overline{A}+B)+C)\Rightarrow((A\overline{B})\Rightarrow C)\;{\Longleftrightarrow}_2\;\\(\overline{A}+B+C)\Rightarrow((A\overline{B})\Rightarrow C)\;{\Longleftrightarrow}_1\;\\\overline{(\overline{A}+B+C)}+((A\overline{B})\Rightarrow C)\;{\Longleftrightarrow}_1\;\\\overline{(\overline{A}+B+C)}+(\overline{(A\overline{B})}+C)\;{\Longleftrightarrow}_3\;\\\overline{(\overline{A}+B+C)}+((\overline{A}+B)+C)\;{\Longleftrightarrow}_2\;\\\overline{(\overline{A}+B+C)}+(\overline{A}+B+C)\;\Longleftrightarrow\;\\\overline{\alpha}+\alpha\;\Longleftrightarrow\;\text{true}

Sono state applicate
\fs{4}{\Longleftrightarrow}_1: equivalenza \fs{4}A\Rightarrow B\;\Longleftrightarrow\;\overline{A}+B
\fs{4}{\Longleftrightarrow}_2: rimozione parentesi eccessive
\fs{4}{\Longleftrightarrow}_3: regola di De Morgan
\fs{4}{\Longleftrightarrow}_4: posizione \fs{4}\alpha=(\overline{A}+B+C)

È quello che è richiesto in questa materia .smile?


Title: Re:Esercizio deduzione naturale
Post by: bapu on 17-09-2012, 14:45:16
Diciamo che dal punto di vista "logico" non fa una piega..però nello specifico del metodo è richiesta l'applicazione di alcune regole (beta-eliminazione,beta-introduzione,alfa-introduzione,....) tramite le quali si dovrebbe dedurre l'espressione iniziale  .bah

grazie cmq x aver risposto  .applausi


Title: Re:Esercizio deduzione naturale
Post by: fabio.rinnone on 20-09-2012, 18:46:16
La soluzione dovrebbe essere la seguente:

1) assumiamo (A implica B) or C
2) assumiamo (A and not B)
3) supponamo per assurdo not C
4) dalla (1) e dalla (3) otteniamo A implica B per beta-eliminazione
5) dalla (2) introduciamo A per alfa-eliminazione
6) dalla (4) e dalla (5) otteniamo B per beta-eliminazione
7) dalla (2) introduciamo not B per alfa-eliminazione
8) otteniamo una contraddizione dalla (6) e dalla (7)

Il resto della dimostrazione è standard.