Systemata Deductiva Formalia in Logica Propositionali
Summarium:In hac lectione recensentur systemata deductiva formalia. Explicatur quomodo haec systemata adhibentur ad enodandas relationes quae inter diversas expressiones logicas exsistere possunt, atque elementa fundamentalia quibus hae demonstrationes construuntur: lingua, axiomatibus, regulisque inferendi. Memorantur axiomata Łukasiewicz et explicatur modus ponens ut motor deductionis calculi propositionis. Praeterea tractantur ratiocinia, theorema et praemissae, atque exponitur quomodo deductiones intra systemata deductiva perficiantur.
Proposita Discendi:
- Intelligere notionem systematum deductivorum formalium in logica propositionali.
- Agoscere partes elementares systematum deductivorum formalium.
- Noscere axiomata Łukasiewicz in calculo propositionis.
- Intellegere modum ponentem ut machinam deductionis calculi propositionis.
- Intelligere quomodo deductiones in systematibus deductivis fiant atque differentiam inter praemissas, ratiocinia et theoremata.
- Intelligere quomodo deductiones generentur per schemata axiomatum et regulas inferendi.
- Cognoscere potentiam logicae ad conectendas expressiones easque pro verbis linguae communis substituendas.
INDEX CONTENTORUM:
QUID EST SYSTEMA DEDUCTIVUM FORMALE?
AXIOMATA ŁUKASIEWICZ LOGICAE PROPOSITIONIS
MODUS PONENS: MACHINA DEDUCTIONIS CALCULI PROPOSITIONIS
RATIONES, THEOREMATA ET PRAEMISSAE
QUOMODO DEMONSTRATIO IN LOGICA PROPOSITIONALI PERFICITUR?
NOTIO AEQUIVALENTIAE PROBATAE
(META)THEOREMA DEDUCTIONIS
CONVERSUM THEOREMATIS DEDUCTIONIS
DEDUCTIONES DE EXPRESSIONIBUS ET DEDUCTIONES DE DEDUCTIONIBUS
REGULA MONOTONIAE
SYNTESIS ET REFLECTIONES DE SYSTEMATIBUS DEDUCTIVIS ET LOGICA PROPOSITIONALI
Pervenimus, in nostro studio logicae, ad punctum conversionis, nam hic initium sumimus recensendi Systemata Deductiva Logicae Propositionalis. Hic est locus ubi omnia quae antea vidimus effici incipiunt et lucem accipit verus spiritus logicae, quia studebimus essentiam demonstrationum. Hoc loco praesumitur te iam didicisse quomodo expressiones scribantur ac quid sit logica propositionalis intellegas; quodsi tibi nondum plene liquet, commendatur ut priores huius lectionis classes recognoscas.
His expletis, sequitur nunc ut perscrutemur modum quo expressiones logicae propositionis inter se connectuntur ad deductionem formandam. Mechanismus per quem istae relationes construuntur est systema deductivum formale.
Quid est Systema Deductivum Formale?
Systemata deductiva formalia, sive systemata calculi deductivi, tria elementa fundamentalia continent:
- Lingua Formali.
- Schema Axiomaticum.
- Regulae Inferendi Elementariae.
Iam omnia quae ad linguas formales spectant recognovimus. Nunc nobis introducenda sunt schemata axiomatum et regulae inferendi elementariae.
Ad construendum systema deductivum calculi propositionis incipiemus componendo systema deductivum ex Axiomatibus Łukasiewicz, et ut regula inferendi elementaria adhibebitur Modus Ponens.
Axiomata Łukasiewicz ad Logicam Propositionalem
Si \alpha, \beta et \gamma sunt expressiones calculi propositionis, tum sequentia sunt axiomata calculi propositionis:
| [A1] | (\alpha \rightarrow (\beta \rightarrow \alpha)) |
| [A2] | ((\alpha \rightarrow (\beta \rightarrow \gamma))\rightarrow ((\alpha\rightarrow \beta)\rightarrow(\alpha \rightarrow \gamma))) |
| [A3] | ((\neg\beta \rightarrow \neg\alpha)\rightarrow(\alpha\rightarrow \beta)) |
Modus Ponens: Machina Deductionis Calculi Propositionis
Si \alpha et \beta sunt expressiones validae calculi propositionis, tunc modus ponens statuit ex \alpha et (\alpha \rightarrow \beta) deduci \beta. In forma ratiocinii hoc scribitur hoc modo:
| (1) | \alpha | ; Praemissa |
| (2) | (\alpha \rightarrow \beta) | ; Praemissa |
| (3) | \beta | ; MP(1,2) |
Hic abbreviate repraesentatur Modus Ponens inter gradus (1) et (2) per scripturam “MP(1,2)”, et huius totius compendium exprimitur per notationem:
Ergo \{\alpha, (\alpha \rightarrow \beta)\}\vdash \beta
Mox videbimus ex axiomatis Łukasiewicz et Modo Ponente omnes technicas deductionis calculi propositionis extrahi posse, quae regulas fundamentales ratiocinii communis compendiunt atque fundamentum praebent logicae classicae.
Ratiocinia, Theoremata et Praemissae
In systematibus deductivis logicae propositionalis ratiocinia (sive deductiones) perficiuntur, quae sunt quaelibet series expressionum in qua unaquaeque est vel praemissa vel expressio ex praemissis orta utens solum axiomatibus Łukasiewicz et modo ponente. Theorema est exitus deductionis sine ullis praemissis. Praemissa esse potest quaelibet expressio quae neque est axioma neque ex axiomatibus deducitur. Generaliter, cum habeamus collectionem praemissarum \Gamma et expressionem \alpha quae ex aliquo elemento \Gamma, axiomatibus et modo ponente obtinetur, scribitur “\Gamma \vdash \alpha” et dicimus:
ex \Gamma deducitur \alpha
Si \Gamma est copia vacua, tum loco scripturae “\emptyset\vdash \alpha” scribitur “ \vdash \alpha “. Hoc legitur “\alpha est theorema”. Haec forma repraesentationis theorematum extendi potest ad repraesentationem axiomatum, ita ut si \alpha, \beta et \gamma sint expressiones, tunc axiomata Łukasiewicz scribi possint hoc modo:
| [A1] | \vdash (\alpha \rightarrow (\beta \rightarrow \alpha)) |
| [A2] | \vdash((\alpha \rightarrow (\beta \rightarrow \gamma))\rightarrow ((\alpha\rightarrow \beta)\rightarrow(\alpha \rightarrow \gamma))) |
| [A3] | \vdash((\neg\beta \rightarrow \neg\alpha)\rightarrow(\alpha\rightarrow \alpha)) |
Ex hoc dicitur axiomata esse enuntiata per se manifesta, vel theoremata esse expressiones quae ex vacuo inferuntur, vel axiomata et theoremata esse proprietates calculi propositionis.
Quomodo Demonstratio in Logica Propositionali Perficitur?
Nunc a tractatione theoretica ad praxim procedemus. Et quidem de exsecutione demonstrationis multa dici possunt; sed quamvis multa praeclara dicantur de systematibus deductivis et logica propositionali, et omnia intelligantur, hoc non necessario significabit competentiis ad demonstrationem perficiendam iam excultis esse. Quam ob rem, ut modum demonstrationum faciendarum doceamus, unam demonstrationem theorematis simplicis examinabimus.
Theorema
Si \alpha est expressio logicae propositionis, tunc valet quod
\vdash (\alpha\rightarrow \alpha)
Demonstratio
| (1) | (\alpha\rightarrow ( \alpha \rightarrow \alpha)) | ; A1 |
| (2) | (\alpha\rightarrow ((\alpha\rightarrow \alpha)\rightarrow\alpha)) | ; A1 |
| (3) | ( (\alpha\rightarrow((\alpha\rightarrow\alpha)\rightarrow\alpha)) \rightarrow ((\alpha\rightarrow (\alpha\rightarrow\alpha))\rightarrow( \alpha\rightarrow \alpha))) | ; A2 |
| (4) | ((\alpha\rightarrow (\alpha\rightarrow\alpha))\rightarrow( \alpha\rightarrow \alpha)) | ; MP(2,3) |
| (5) | ( \alpha\rightarrow \alpha) | ; MP(1,5) |
Ergo \vdash (\alpha\rightarrow\alpha)
Finis demonstrationis.
Ut videre licet, in systematibus deductivis et logica propositionali demonstrationes neutiquam triviales sunt, sed semel constructae facile replicari possunt.
Nunc autem, antequam nos totos in deductiones his technicis fiendas proiciamus, prius aliquas proprietates et definitiones evolvemus quae ad hanc rem perficiendam valde utiles erunt; nam si solis hisce rationibus utamur, gravissimos errores offendamus.
Notio aequivalentiae probatae
Si \alpha et \beta sunt expressiones quaelibet et simul verum est quod \{\alpha\}\vdash \beta et \{\beta\} \vdash \alpha, tunc dicitur \alpha et \beta aequivalere probatae, et scribitur \alpha \dashv \vdash \beta. Hoc symbolice compendiose exprimitur sic:
\left(\{\alpha\}\vdash\beta \wedge \{\beta\}\vdash\alpha \right) \Leftrightarrow \left(\alpha\dashv\vdash\beta\right)
Hoc legitur: ex \alpha infertur \beta, et ex \beta infertur \alpha si et tantum si \alpha et \beta sunt aequivalentes probatae.
Haec est meta-proprietas logicae propositionalis.
(Meta)Theorema Deductionis
Si \alpha et \beta sunt expressiones calculi propositionis, et \Gamma est collectio praemissarum; tunc habetur: si ex \Gamma \cup \{\alpha\} deducitur \beta, tum ex \Gamma deducitur (\alpha \rightarrow \beta). Symbolice hoc exprimitur sic:
\left(\Gamma \cup \{\alpha\}\vdash \beta \right) \Rightarrow \left( \Gamma\vdash(\alpha\rightarrow\beta)\right)
Demonstratio:
Ut verificetur \Gamma \cup \{\alpha\}\vdash \beta, necesse est habere deductionem huiusmodi:
| (1) | \gamma_1 | ; Prima praemissa e \Gamma |
| \vdots | \vdots | |
| (n) | \gamma_n | ; Praemissa n ex \Gamma |
| (n+1) | \overline{\gamma}_1 | ; Modus Ponens inter aliquas lineas superiores |
| \vdots | \vdots | |
| (n+m) | \overline{\gamma}_m | ; Modus Ponens inter aliquas lineas superiores |
| (n+m+1) | \alpha | ; Praemissa |
| (n+m+2) | \beta | ; Modus Ponens (n+m+1, una ex lineis superioribus, praeter (n+m+1)) |
Ergo \Gamma\cup\{\alpha\} \vdash \beta
Ut hoc fieri possit, necesse est ut saltem una ex expressionibus \gamma_1, \cdots \gamma_n,\overline{\gamma_1},\cdots,\overline{\gamma_m} sit formae (\alpha\rightarrow \beta); at omnes illae lineae solummodo involvunt elementa \Gamma et axiomata Łukasiewicz in deductione sua, unde sequitur \Gamma\vdash (\alpha \rightarrow \beta). Quare theorema demonstratum est.
Finis demonstrationis.
Reciproca Theorematis Deductionis
Iisdem condicionibus quibus theorema deductionis statuitur, sequitur
\left(\Gamma\vdash(\alpha \rightarrow \beta)\right) \Rightarrow \left( \Gamma \cup \{\alpha\}\vdash \beta \right)
Demonstratio:
Si ponitur \Gamma\vdash (\alpha\rightarrow \beta), tum habetur deductio huiusmodi formae
| (1) | \gamma_1 | ; Prima praemissa e \Gamma |
| \vdots | \vdots | |
| (n) | \gamma_n | ; Praemissa n e \Gamma |
| (n+1) | (\alpha \rightarrow \beta) | ; Modus Ponens (inter quasdam lineas superiores) |
Iam si \alpha addatur ut praemissa ad hoc ratiocinium, tunc habebuntur lineae sequentis formae
| (n+2) | \alpha | ; Praemissa addita |
| (n+3) | \beta | ; MP(n+1, n+2) |
Ergo \Gamma \cup \{\alpha\} \vdash \beta
Quod erat demonstrandum.
Deductiones de Expressionibus et Deductiones de Deductionibus
Demonstrationes sicut illa quae antea facta est ad obtinendum propositum \vdash (\alpha\rightarrow \alpha) sunt casus deductionum ex expressionibus, quia quisque gradus continet expressionem concretam. Similiter fieri potest deductiones ex aliis deductionibus conficere, ubi quisque gradus est ipsemet deductio. In praxi, utrumque modo simili efficitur, sed alterum nobis facultatem dat utamur theorema deductionis eiusque reciproco, quod magnam flexibilitatem rationandi tribuit. Ut hoc videamus, iterum demonstrabimus \vdash (\alpha \rightarrow \alpha), sed nunc utens deductionibus loco simplicium expressionum. Una ex possibilibus viis sequens est:
| (1) | \vdash (\alpha \rightarrow (\alpha \rightarrow \alpha)) | ; A1 |
| (2) | \{\alpha\}\vdash ( \alpha \rightarrow \alpha) | ; RTD(1) |
| (3) | \{\alpha\}\cup \{\alpha\}\vdash \alpha | ; RTD(2) |
| (4) | \{\alpha\}\vdash \alpha | ; Animadvertendum est \{\alpha\}\cup\{\alpha\}=\{\alpha\} |
| (5) | \vdash (\alpha\rightarrow \alpha) | ; TD(4) |
Animadvertendum est hanc ratiocinationem non esse breviorem quam priorem, sed multo simpliciorem ad efficiendum, cum solummodo theorema deductionis, eius reciprocam et axioma A1 adhibuerimus ad structuram demonstrationis perficiendam.
Apparet quidem in hoc processu nos usum fecisse tantum unius axioma Łukasiewicz et neglexisse tam ceteros axiomata quam modum ponentem. Significatne hoc quod hac ratione ratiocinandi caetera axiomata et modum ponentem omittamus? Responsio est simul ‘ita’ et ‘non’. Ex una parte, videmur eos ignorare, cum non explicite utamur; ex altera tamen, memorari oportet theorema deductionis et eius reciprocam ipsa ex axiomatibus Łukasiewicz et modo ponente derivari, unde fit ut eorum usu etiam implicite istis elementis innitamur.
Regula Monotoniae
Si \tau est theorema, tunc, data quaelibet expressio \beta, eveniet quod:
\{\beta\}\vdash\tau
Haec est revera regula facillime demonstranda, cum si \tau est theorema, tunc \vdash \tau. Id est, exsistit ratiocinatio quae, sine ulla praemissarum additione, ducit ad expressionem \tau; ergo additio alicuius expressi ad praemissas (vacuam copiam) nullam mutationem efficit.
Simili ratione sequens propositio proponi potest: si ex collectione praemissarum \Gamma infertur \gamma, tunc eveniet quod:
\Gamma\cup\{\alpha\}\vdash\gamma
Ubi \alpha est quaelibet expressio.
Synthesis et Meditationes de Systematibus Deductivis et Logica Propositionali
Cum linguam logicae propositionalis regula inferendi et expressionibus fundamentalibus instruximus: scilicet Modo Ponente et Axiomatis Łukasiewicz, id quod efficimus est simile machinamentum deductionis constituere et “machinam motoriam” quae eam in motum inducit. Ex hoc momento incipiunt naturaliter emergere omnes regulae fundamentales deductionis quas in lectionibus sequentibus examinabimus.
Adhuc unum observandum. Expressiones logicae propositionalis revera sunt meta-expressiones linguae binorum symbolorum quam antea inspeximus. Meminerimus gratiam harum meta-expressionum esse quod nobis permittunt metasymbolos eorum per quaslibet expressiones linguae substituere ad novam structuram eandem exprimendam obtinendam. Cum systemati deductivo schemata axiomatum et regulas inferendi addimus, systema logicum construitur quod deductiones inter expressiones connectendas gignit. Inde emergit structura deductiva quae infinitas deductiones complecti potest: omnes quae effici possunt per substitutionem meta-variabilium per quaslibet expressiones. Potentia logicae revera tunc explicatur, cum intellegimus nos posse, loco expressionum binorum symbolorum originum, uti expressionibus linguae nostrae usitatae, et spectare quid eveniat.