Probationes per Inductionem: Regulae Generalizatae De Morgan et Distributio
SUMMARIUM
In hac lectione agitur de probationibus per inductionem in mathematica et logica propositionali. Exponuntur duo genera probationum: probationes internae sive deductivae, quae in regulis logicae nituntur, et probationes externae sive metamathematicae, quae necessariae sunt ad enuntiata probanda quae ad ipsam logicam spectant. Inductio Mathematica introducitur ut methodus demonstrationis, quae permittit demonstrare quaedam enuntiata valere pro omnibus numeris naturalibus. Exemplum cum demonstratione exhibetur, et exponuntur formae generalizatae legum De Morgan necnon legum distributivarum in logica propositionali, una cum earum demonstrationibus per inductionem. Haec lectio magni momenti est ad intellegendos fundamenta mathematicae et logicae, atque ad eos applicandos in variis cognitionis regionibus.
PROPOSITA DISCENDI:
Post hanc lectionem confectam, discipulus poterit:
- Agnoscere duo genera probationum distinguenda: probationes internas sive deductivas et probationes externas sive metamathematicas.
- Adhibere inductionem mathematicam ad demonstrationes faciendas de numeris naturalibus et in logica propositionali.
- Uti notationibus conjunctionum et disjunctionum ad enuntiata logicae propositionalis scribenda.
- Intellegere formas generalizatas legum De Morgan et Distributionis in Logica Propositionali.
- Intellegere notionem hypotheseos inductionis eiusque munus in demonstratione per inductionem.
INDEX
PROBATIONES INTERNAE ET EXTERNAE
PROBATIONES PER INDUCTIONEM MATHEMATICAM
PROBATIONES PER INDUCTIONEM IN LOGICA PROPOSITIONALI
FORMA GENERALIZATA LEGUM DE MORGAN
FORMA GENERALIZATA LEGUM DISTRIBUTIVARUM
Probationes internae et externae
Duo genera probationum distinguenda sunt. Hactenus multas probationes formales inspeximus. Huiusmodi probationes ex regulis logicae oriuntur. Taliae probationes dicuntur fieri “intra logicam”, atque ideo eas etiam “probationes internas” sive deductivas appellamus. Huiusmodi probationes formales ambitum limitatum habent, quia solum valent ad enuntiata probanda quae in sermone logico scribi possunt. Tamen aliquando volumus probare quaedam de ipsa logica. Vellemus probare omnia enuntiata logicae propositionalis propriam aliquam qualitatem implere. Huiusmodi enuntiata, quae ad ipsam logicam pertinent, neque intra logicam constitui neque probari possunt. Ad talia probanda utimur probatione externa. Probationes externae interdum “metamathematicae” vocantur, et iam huiusmodi exemplum vidimus, cum (meta)theorema deductionis tractavimus. Hic est locus in quo probationes inductivae collocantur.
Probationes per Inductionem Mathematicam
Inductio Mathematica est methodus demonstrationis quae nobis permittit demonstrare quaedam valere pro omnibus numeris naturalibus.
EXEMPLUM:
Probare possumus omnem numerum formae 11^n - 4^n, ubi n est quivis numerus naturalis, semper divisibilem esse per 7.
DEMONSTRATIO: Si inspiciamus quid accidat cum n=1, videbimus:
11^1 - 4^1 = 7
quod, ut manifestum est, divisibile est per 7.
Nunc supponamus 11^n - 4^n divisibile esse pro quodam n=k. Ex hoc probabimus hanc expressionem etiam valere pro n=k+1. Hoc fieri potest modo sequente:
Ergo, si 11^k - 4^k divisibile est per 7, consequenter erit etiam 11 ( 11^{k} - 4^{k} ) + 7\cdot 4^{k}, quod idem est ac dicere 11^{k+1} - 4^{k+1} divisibile esse per 7. Hinc habemus: si 11^k - 4^k est divisibile pro k=1, tum etiam pro k=2, k=3, k=4,\cdots et sic porro, atque proinde, divisibile pro quovis n\in\mathbb{N}. Cum hoc fit, dicimus inductionem esse completam. ■
Probationes per Inductionem in Logica Propositionali
Ad probationes per inductionem quas infra perficimus, necesse est prius introducere sequentem notationis conventionem.
NOTATIO: Sint F_1,\cdots, F_n finitium expressiones quaelibet logicae propositionalis. Coniunctiones et disiunctiones harum expressionum introducuntur hoc modo:
\displaystyle \bigwedge_{i=1}^n F_i := F_1\wedge \cdots \wedge F_n
\displaystyle \bigvee_{i=1}^n F_i := F_1\vee \cdots \vee F_n
His positis, nunc tractabimus duas formas generalizatas sequentis naturae.
Forma Generalizata Legum De Morgan
Dato quodam finito collectione expressionum logicae propositionalis F_1,\cdots, F_n, semper valent sequentes duae proprietates:
\displaystyle\neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
\displaystyle\neg\left(\bigvee_{i=1}^n F_i \right) \equiv \left( \bigwedge_{i=1}^n \neg F_i \right)
DEMONSTRATIO: Primum demonstrabimus per inductionem super n quod \neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
Primo inspiciendum est quid fiat in casu initiali n=1. Hoc in casu patet quod \neg F_1 \equiv \neg\left(\bigwedge_{i=1}^1F_i\right)\equiv \left(\bigvee_{i=1}^n \neg F_i \right) \equiv\neg F_1
Nunc supponamus hanc proprietatem valere pro quodam n=k; id est, data quadam finita collectione expressionum F_1, F_2, \cdots, F_k valet quod:
\displaystyle \neg\left(\bigwedge_{i=1}^k F_i\right) \equiv \left(\bigvee_{i=1}^k \neg F_i\right)
Tunc probabimus hinc sequi
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) \equiv \left(\bigvee_{i=1}^{k+1} \neg F_i\right)
Definita conjunctione habemus:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) := \neg\left[\left(\bigwedge_{i=1}^{k} F_i\right) \wedge F_{k+1}\right]
Ad hanc expressionem applicare possumus leges De Morgan (illam usualem pro duobus terminis) ut consequamur:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[\neg\left(\bigwedge_{i=1}^{k} F_i\right) \vee \neg F_{k+1}\right]
Nunc, si adhibeamus hypothesim inductionis, obtinebimus:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[ \left(\bigvee_{i=1}^k \neg F_i\right) \vee \neg F_{k+1}\right] := \left(\bigvee_{i=1}^{k+1}\neg F_i \right)
Quare inductio est completa, et proprietas valet pro omni n in genere. Secunda relatio similiter demonstrari potest modo prorsus analogo, quam ob rem lectori relinquitur exercenda, muajaja!
Forma Generalizata Legum Distributivarum
Similiter ac in legibus De Morgan, leges distributionis generalizari possunt hoc modo. Sint \{F_1, \cdots, F_n\} et \{G_1,\cdots, G_m\} duae collectiones finitae expressionum quarumlibet; tunc valent hae aequivalentiae:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]
\displaystyle \left[ \left(\bigvee_{i=1}^n F_i \right) \wedge \left(\bigvee_{j=1}^m G_j \right) \right] \equiv \left[\bigvee_{i=1}^n\left(\bigvee_{j=1}^m(F_i\wedge G_j) \right) \right]
DEMONSTRATIO: Ad hanc demonstrationem construendam oportet uti inductione duplici, super n et m. In sequentibus peragam inductionem primum super n, deinde super m, pro expressione \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]
Si ponamus m=1, tunc haec expressio scribitur ut:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^1 G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^1(F_i\vee G_j) \right) \right].
Quod idem est ac dicere:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^n\left( F_i\vee G_1 \right) \right].
Nunc demonstrabimus hanc expressionem per inductionem super n.
Si ponamus n=1, tunc expressio ad haec reducitur:
F_1 \vee G_1 \equiv F_1 \vee G_1.
Quod plane verum est. Nunc autem supponamus hoc valere pro quodam n=k; hoc est, hypothesi inductionis statuemus:
\displaystyle \left[ \left(\bigwedge_{i=1}^k F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right].
Ex hoc nunc probabimus id valere etiam pro n=k+1.
Definitio conjunctionis dat:
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] := \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\wedge F_{k+1} \right) \vee G_1 \right]
Nunc, adhibita \vee-distributione, habebimus:
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\vee G_{1} \right) \wedge \left(F_{k+1} \vee G_1 \right) \right]
Et hoc ipso loco uti possumus hypothesi inductionis ad obtinendum:
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right) \wedge \left(F_{k+1} \vee G_1 \right) \right] := \left[\bigwedge_{i=1}^{k+1}(F_{i}\vee G_1) \right]
Itaque, per inductionem probavimus quod pro omni n\in\mathbb{N} valet:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right)\vee G_1\right] \equiv \left[\bigwedge_{i=1}^n(F_i\vee G_1)\right]
Completa inductione super n, comprobavimus valere casum initialem pro m=1, nunc solum restat completa inductio super m. Ad hoc faciendum statuimus hypothesim inductionis pro quodam m=l, id est, valere sequentem aequivalentiam:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^l G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \right]
Et ex hoc demonstrabimus quod etiam valet pro m=l+1.
Ex definitione conjunctionis habemus:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] := \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\left(\bigwedge_{j=1}^{l} G_j \right) \wedge G_{l+1}\right) \right]
Deinde, adhibita \vee-distributione, consequitur:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \left( \left(\bigwedge_{i=1}^n F_i \right) \vee \left( \bigwedge_{j=1}^l G_j \right) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]
Quare, utens hypothesi inductionis, scribere potes:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]
Et nunc, si applicemus resultatum inductionis super n, habebimus:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \bigwedge_{i=1}^n (F_i \vee G_{l+1} )\right) \right]
Quod, tandem, ex definitione conjunctionis fit:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{l+1}(F_i\vee G_j) \right) \right]
Itaque, inductio super m est completa, et expressio
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{m} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{m}(F_i\vee G_j) \right) \right]
valet pro omni n,m\in\mathbb{N}.
Hoc iter per probationes per inductionem ostendit quomodo technicae rigidae demonstrationis mathematicae adhiberi possint non solum in ambitu numerorum naturalium, sed etiam in logica propositionali. Per inductionem, validitatem formarum generalizatarum legum De Morgan et legum distributivarum statuimus, ita corroborantes intellectum fundamentorum logicorum qui sub variis partibus scientiae mathematicae latent. Hic modus non solum est essentialis ad evolutionem facultatum cogitandi abstracte, sed etiam praebet instrumentum validum ad quaestiones complexas tractandas in mathematica et ultra eam.