Ad argvmentvm transi
Topos Uranos
Latine

Leges De Morgani et leges distribvtivae generales

Svmmarivm

Leges De Morgani et leges distribvtivae hactenvs pro dvobvs terminis envntiatae svnt; formae normales avtem conivnctiones et disivnctiones qvotlibet terminorvm colligvnt, easqve leges in hac generalitate postvlant. Haec lectio per recvrsionem definit conivnctionem et disivnctionem elenchi formvlarvm (φ1,…,φn)(\varphi_1, \ldots, \varphi_n), qvae ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i et ⋁i=1nφi\bigvee_{i=1}^{n} \varphi_i scribvntvr, a sinistra associando, et per indvctionem in nvmero terminorvm demonstrat lemma valoris (conivnctio vera est si et solvm si omnes eivs termini veri svnt; disivnctio, si et solvm si aliqvis vervs est), associativitatem generalem, qvae novam terminorvm consociationem permittit, independentiam ab ordine et a repetitionibvs, leges De Morgani generales et distribvtivitatem generalem in ea forma qva lectio de formis normalibvs vtetvr: conivnctio dvarvm disivnctionvm, nn et mm terminorvm, aeqvivalet disivnctioni nmnm conivnctionvm ex singvlis vtrivsqve terminis, et dvaliter. Problemata aestimationes nvmerant, errorem demonstrationis invenivnt qvae novam consociationem pro definitione venditat, incrementvm distribvtionis metivntvr et ex eo tavtologiam 2n2^n terminorvm elicivnt.

Proposita discendi

  1. Conivnctiones et disivnctiones nn terminorvm notatione ⋀\bigwedge et ⋁\bigvee scribere, eas vt catenas a sinistra associatas explicare et earvm valorem veritatis lemmate valoris compvtare.
  2. Per indvctionem in nvmero terminorvm associativitatem generalem, independentiam ab ordine et a repetitionibvs et leges De Morgani generales demonstrare, in vnaqvaqve illatione identitatem catenarvm ab aeqvivalentia semantica distingvendo.
  3. Distribvtivitatem generalem eivsqve dvalem demonstrare, indvctionem in dvobvs indicibvs disponendo, et terminos nvmerare qvos distribvtio gignit.
  4. Errorem invenire demonstrationis per indvctionem cvivs casvs basis male scriptvs est vel cvivs gradvs indvctivvs novam consociationem celat, eamqve reficere.

Leges pro qvolibet terminorvm nvmero

Lectio de conseqventia et aeqvivalentia semanticis leges aeqvivalentiae pro dvobvs terminis statvit: inter eas commvtativitatem et associativitatem signorvm ∧\wedge et ∨\vee, leges De Morgani et dvas distribvtivitates. Atqvi formvla in forma normali disivnctiva est disivnctio conivnctionvm, qvarvm qvaeqve tot terminos habet qvot opvs est, et formvlam in eam formam transformare postvlat vt conivnctiones et disivnctiones cvivslibet longitvdinis negentvr, aliter consocientvr et distribvantvr. Si haec ita svnt, leges binariae, vt nvnc svnt, non svfficivnt: ad nn terminos extendendae svnt, idqve semel pro omnibvs nn.

Pro qvoqve nn fixo, lex De Morgani nn terminorvm tabvla veritatis 2n2^n versvvm, cvm nn variabilibvs scripta, verificari posset, et svbstitvtio vniformis lectionis praecedentis, ad implicationem dvplicem inter vtrvmqve latvs adhibita, eam ad formvlas qvaslibet extenderet. Sed valores nn infiniti svnt, et nvllvs tabvlarvm nvmervs eos exhavrit. Ex qvo seqvitvr vt assertio «pro omni nn» non sit aeqvivalentia inter dvas formvlas, sed envntiatvm de infinitis aeqvivalentiis, in metalingva formatvm; eivs demonstratio est, sicvt eae lectionis de indvctione in nvmeris natvralibvs et in formvlis, demonstratio externa, eivsqve instrvmentvm est indvctio in nvmero terminorvm. Notatio ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i qvoqve ad metalingvam pertinet: non est novvm lingvae signvm, sed nomen catenae circvlorvm et discorvm, eodem modo qvo (φ∧ψ)(\varphi \wedge \psi) est.

Iam nvnc tres relationes figere expedit qvae confvndendae non svnt. Aeqvalitas α=β\alpha = \beta dicit α\alpha et β\beta eandem catenam esse; definitiones, qvae signo :=:= scribvntvr, nomina catenarvm indvcvnt, et qvod definitione explicata obtinetvr aeqvale est, non tantvm aeqvivalens. Aeqvivalentia semantica α≡β\alpha \eqsem \beta dicit v(α)=v(β)v(\alpha) = v(\beta) pro omni aestimatione vv valere. Aeqvivalentia demonstrabilis α⊣⊢β\alpha \dashv\vdash \beta vnitatis de dedvctione dicit vtramqve ex altera dedvci. Haec lectio cvm dvabvs primis laborat; tertia in sola animadversione apparet.

Qvae adhibentvr

Ex lectione de semantica logicae propositionalis svmvntvr aestimationes, fvnctiones a variabilibvs v1,v2,…v_1, v_2, \ldots in {0,1}\{0, 1\}, earvmqve extensio ad omnes formvlas, qvae eadem littera vv scribitvr; valor connectivorvm derivatorvm, ex abbreviationibvs statvtis compvtatvs: v(¬φ)=1−v(φ)v(\neg\varphi) = 1 - v(\varphi), v((φ∧ψ))=v(φ) v(ψ)v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi), ita vt conivnctio valorem 11 habeat si et solvm si ambae eivs partes valorem 11 habent, et v((φ∨ψ))=1v((\varphi \vee \psi)) = 1 si et solvm si v(φ)=1v(\varphi) = 1 vel v(ψ)=1v(\psi) = 1; lemma coincidentiae (si dvae aestimationes in variabilibvs formvlae congrvvnt, in formvla congrvvnt); et formvlae ⊤\top et ⊥\bot, tavtologia et contradictio fixae. Ex lectione de conseqventia et aeqvivalentia semanticis svmvntvr ≡\eqsem esse reflexivam, symmetricam et transitivam, theorema svbstitvtionis semanticae et catalogvs legvm cvm nominibvs svis: commvtativitas, (φ∧ψ)≡(ψ∧φ)(\varphi \wedge \psi) \eqsem (\psi \wedge \varphi) et (φ∨ψ)≡(ψ∨φ)(\varphi \vee \psi) \eqsem (\psi \vee \varphi); associativitas, (φ∧(ψ∧χ))≡((φ∧ψ)∧χ)(\varphi \wedge (\psi \wedge \chi)) \eqsem ((\varphi \wedge \psi) \wedge \chi) eivsqve analoga pro ∨\vee; leges De Morgani, ¬(φ∧ψ)≡(¬φ∨¬ψ)\neg(\varphi \wedge \psi) \eqsem (\neg\varphi \vee \neg\psi) et ¬(φ∨ψ)≡(¬φ∧¬ψ)\neg(\varphi \vee \psi) \eqsem (\neg\varphi \wedge \neg\psi); distribvtivitas, (φ∧(ψ∨χ))≡((φ∧ψ)∨(φ∧χ))(\varphi \wedge (\psi \vee \chi)) \eqsem ((\varphi \wedge \psi) \vee (\varphi \wedge \chi)) et (φ∨(ψ∧χ))≡((φ∨ψ)∧(φ∨χ))(\varphi \vee (\psi \wedge \chi)) \eqsem ((\varphi \vee \psi) \wedge (\varphi \vee \chi)); dvplex negatio, ¬¬φ≡φ\neg\neg\varphi \eqsem \varphi; idempotentia, (φ∨φ)≡φ(\varphi \vee \varphi) \eqsem \varphi; identitas, (φ∧⊤)≡φ(\varphi \wedge \top) \eqsem \varphi; et tertivm non datvr, ⊨(φ∨¬φ)\models (\varphi \vee \neg\varphi). Leges valent pro formvlis qvibvslibet φ\varphi, ψ\psi, χ\chi, qvae metavariabiles svnt.

In vnaqvaqve illatione demonstrationvm qvae seqvvntvr pars formvlae alia aeqvivalenti svbstitvitvr. Theorema svbstitvtionis semanticae id pro vna occvrrentia simvl permittit; lemma seqvens, qvod casvs eivs particvlaris est, id semel praebet pro partibvs negationis, conivnctionis vel disivnctionis. Animadvertendvm est hoc non esse rem syntacticam levem: ¬α\neg\alpha est catena (α↓α)(\alpha \downarrow \alpha), in qva α\alpha bis occvrrit, et (α∧β)(\alpha \wedge \beta) igitvr octo occvrrentias formvlae α\alpha et octo formvlae β\beta continet.

LemmaCompatibilitas connectivorvm cvm aeqvivalentia

Si α≡α′\alpha \eqsem \alpha' et β≡β′\beta \eqsem \beta', tvm ¬α≡¬α′\neg\alpha \eqsem \neg\alpha', (α∧β)≡(α′∧β′)(\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta') et (α∨β)≡(α′∨β′)(\alpha \vee \beta) \eqsem (\alpha' \vee \beta').

Demonstratio

  1. v(α)=v(α′),v(β)=v(β′)\dato{h}{v(\alpha) = v(\alpha'), \qquad v(\beta) = v(\beta')}

    Sit vv aestimatio qvaelibet. Ex hypothesi α\alpha et α′\alpha' evndem valorem habent, itemqve β\beta et β′\beta'.

  2. v(¬α)=1−v(α)=1−v(α′)=v(¬α′),v((α∧β))=v(α) v(β)=v(α′) v(β′)=v((α′∧β′))v(\neg\alpha) = 1 - \resaltar{v(\alpha)} = 1 - \resaltar{v(\alpha')} = v(\neg\alpha'), \qquad v((\alpha \wedge \beta)) = \resaltar{v(\alpha)\,v(\beta)} = \resaltar{v(\alpha')\,v(\beta')} = v((\alpha' \wedge \beta'))

    Valor negationis et valor conivnctionis a solis valoribvs partivm svarvm pendent.

  3. v((α∨β))=1  ⇔  v(α)+v(β)≥1  ⇔  v(α′)+v(β′)≥1  ⇔  v((α′∨β′))=1v((\alpha \vee \beta)) = 1 \;\Leftrightarrow\; v(\alpha) + v(\beta) \geq 1 \;\Leftrightarrow\; v(\alpha') + v(\beta') \geq 1 \;\Leftrightarrow\; v((\alpha' \vee \beta')) = 1

    Idem in disivnctione accidit: valorem 11 habet si et solvm si aliqva pars valorem 11 habet, et partes eosdem valores in vtroqve latere habent.

  4. ¬α≡¬α′,(α∧β)≡(α′∧β′),(α∨β)≡(α′∨β′)\neg\alpha \eqsem \neg\alpha', \qquad (\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta'), \qquad (\alpha \vee \beta) \eqsem (\alpha' \vee \beta')

    Cvm vv qvaelibet fverit, tres aeqvivalentiae valent.