[L03] Logica delle proposizioni

Esercizi sulla verità delle proposizioni e problemi che non sembrano rientrare in nessun'altra categoria.
Rispondi
Gizeta
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

[L03] Logica delle proposizioni

Messaggio da Gizeta »

La logica stessa può essere studiata col metodo deduttivo.
Limitandoci alla logica delle proposizioni, si possono accettare alcune tautologie come assiomi logici e cercare di dedurre da esse tutte le altre: ad esempio, si possono accettare le seguenti quattro:

[tex]\boxed{1}[/tex] [tex](P \lor P) \Rightarrow P[/tex];
[tex]\boxed{2}[/tex] [tex]P \Rightarrow (P \lor L)[/tex];
[tex]\boxed{3}[/tex] [tex](P \lor L) \Rightarrow (L \lor P)[/tex];
[tex]\boxed{4}[/tex] [tex](P \Rightarrow L) \Rightarrow ((R \lor P) \Rightarrow (R \lor L))[/tex];

Partendo da queste, e applicando sempre la regola di deduzione, si dimostrino le seguenti tautologie:

[tex]\boxed{5}[/tex] [tex](P \Rightarrow L) \Rightarrow ((C \Rightarrow P) \Rightarrow (C \Rightarrow L))[/tex];
[tex]\boxed{6}[/tex] [tex]P \Rightarrow P[/tex];
[tex]\boxed{7}[/tex] [tex]P \Rightarrow \lnot(\lnot P)[/tex];
[tex]\boxed{8}[/tex] [tex](P \Rightarrow L) \Rightarrow ((\lnot L) \Rightarrow (\lnot P))[/tex].

Nota[tex]_{1}[/tex]: La scrittura [tex]P \Rightarrow L[/tex] deve essere sempre ritenuta equivalente a [tex](\lnot P) \lor L[/tex];
Nota[tex]_{2}[/tex]: La regola di deduzione consiste nel fatto che se [tex]P \Rightarrow L[/tex] è vera e [tex]P[/tex] è vera, allora anche [tex]L[/tex] è vera.

Nota[tex]_{3}[/tex]: L'esercizio proposto è l'esercizio numero 3 del primo paragrafo del capitolo 0 [si potrebbe usare la notazione 0.1.3] (pagg. 19-20) del libro "Analisi Matematica" di Giovanni Prodi; esso è contrassegnato con un asterisco, che implica una certa difficoltà di risoluzione, ma procedendo sistematicamente non risulta eccessivamente ostico.
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: (L??) Logica delle proposizioni

Messaggio da afullo »

Come difficoltà potrebbe essere un L03? Non lo vedrei come accessibile con il solo intuito, quindi andrei oltre la classificazione di Archimede e Febbraio, ma come dici tu basta essere sistematici, non servono né grandi conoscenze teoriche né capacità di ragionamento che si acquisiscono per forza con esercizi simili. ;)
Gizeta
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: (L??) Logica delle proposizioni

Messaggio da Gizeta »

In un esercizio simile, probabilmente, la maggiore difficoltà potrebbe consistere nel non rendersi esattamente conto di cosa sia accettabile e cosa non lo sia.
In calce alla pagina 8 è possibile trovare il seguente testo:

AVVERTENZA Sono state contrassegnate con asterisco alcune osservazioni un po' difficili, che possono essere tralasciate in una prima lettura; così pure sono stati indicati con un asterisco gli esercizi più difficili [...].

Sono solo parzialmente d'accordo con la parte sottolineata, infatti da una parte il soffermarsi su questo esercizio non aggiunge niente alla comprensione dell'introduzione logica, ma dall'altra è estremamente utile per prendere confidenza con il formalismo matematico.

Un esempio pratico: si potrebbe convincersi che per dimostrare l'ultimo punto possa essere sufficiente partire da [tex]P \Rightarrow L[/tex], passare dall'equivalenza [tex](\lnot P) \lor L[/tex], sfruttare doppia negazione [[tex]L \iff (\lnot(\lnot L))[/tex]] e commutatività del connettivo or [[tex](P \lor Q) \iff (Q \lor P)[/tex]] e concludere che debba valere anche [tex]\lnot(\lnot L)) \lor (\lnot P)[/tex], ossia equivalentemente [tex](\lnot L) \Rightarrow (\lnot P)[/tex], ma ad un'occhiata più attenta si nota immediatamente che tale procedimento non sia da considerarsi valido, infatti tra i nostri assiomi non troviamo né la doppia negazione (che si trova in forma debole tra le tesi), né la commutatività (sebbene questa sia effettivamente presente in una forma debole da cui si può dedurre facilmente quella forte), peggio ancora gli unici metodi deduttivi accettati sono la regola di deduzione e la possibilità di sostituire il costrutto logico [tex]P \Rightarrow L[/tex] con [tex](\lnot P) \lor L[/tex].


È il classico esercizio in cui si corre il rischio di banalizzare, e quindi non comprendere, o al contrario estremizzare il lato formale e non riuscire ad ottenere alcun progresso; parte dell'esercizio consiste proprio nel trovare un buon equilibrio tra queste due tendenze, una contestualizzazione adeguata e un livello di formalismo tale da non incagliare e al contempo non privare completamente di contenuto.
In quest'ottica sono completamente d'accordo con l'indicazione data dall'asterisco; per questo ho optato per un non-livello, perché non credo sia facile vedere un simile esercizio spuntare in una gara di qualsivoglia livello; contemporaneamente, però, credo sia utile per chi abbia interesse nella matematica spendere parte del proprio tempo ragionando su esercizi simili, anche se si dovesse finire a fissare un foglio bianco per ore.

Personalmente, mettendo da parte l'idea che non sia un esercizio/problema da Olimpiadi e una volta trovato un contesto adeguato, direi che L03 potrebbe essere considerato un buon indicatore della difficoltà del problema.
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: [L03] Logica delle proposizioni

Messaggio da afullo »

Ok, vada per L03. Poi sì, abbiamo sempre detto che la difficoltà è indicativa, non di rado pure soggettiva, specie quando il problema non è di una tipologia tradizionalmente associata alle competizioni; ma sono il primo ad affermare che le gare troppo a misura di problem solver, quelle in cui è premiato eccessivamente l'uso dei cannoni a discapito dei maggiori sforzi in termini di ragionamento, non siano completamente indicatrici delle capacità dei concorrenti nel padroneggiare il pensiero matematico. 8-)
Rispondi