Ad argvmentvm transi
Topos Uranos
Latine

Completvdo fvnctionalis

Svmmarivm

Omnis formvla tabvlam veritatis determinat; haec lectio sententiam conversam demonstrat: omnis tabvla, id est omnis attribvtio valorvm veritatis versibvs facta, tabvla est alicvivs formvlae. Fvnctiones veritatis definit, eas qvae nn argvmenta habent nvmerat (22n2^{2^{n}}) et accvrate statvit qvando formvla vnam ex eis repraesentet. Deinde theorema completvdinis fvnctionalis demonstrat per formvlam tabvlae, disivnctionem conivnctionvm litteralivm versv post versvm constrvctam, qva lectio de formis normalibvs vtetvr vt prima demonstratione exsistentiae formae normalis disivnctivae. Cvm omnis formvla cvrsvs catena sit circvlorvm et discorvm, inde sine vllo alio labore seqvitvr negationem conivnctam solam svfficere, et ostenditvr qvomodo qvaevis fvnctio ea scribatvr. Postremo inqvirit qvae classes connectivorvm svfficiant ad omnes fvnctiones repraesentandas: criterivm generale demonstrat, id ad {¬,∧}\{\neg, \wedge\}, {¬,∨}\{\neg, \vee\}, {¬,→}\{\neg, \rightarrow\}, {↓}\{\downarrow\} et ad negationem alternativam adhibet, et demonstrat {∧,∨,→,↔}\{\wedge, \vee, \rightarrow, \leftrightarrow\} non svfficere, qvia omnes eivs formvlae valorem 11 servant.

Proposita discendi

  1. Fvnctiones veritatis qvae nn argvmenta habent nvmerare et, per fvnctiones qvas repraesentant, decernere qvando dvae formvlae aeqvivalentes sint.
  2. Ex tabvla fvnctionis veritatis formvlam constrvere qvae eam repraesentet, et formvlam aeqvivalentem breviorem qvaerere cvm expediat.
  3. Exponere cvr in lingva cvrsvs negatio conivncta sola svfficiat, et ea sola formvlas scribere qvae fvnctiones datas repraesentent.
  4. Demonstrare classem connectivorvm idoneam esse, negationem conivnctam formvlis eivs exprimendo.
  5. Demonstrare classem connectivorvm idoneam non esse, per proprietatem qvam omnes eivs formvlae servant.

Fvnctiones veritatis

Lectio de semantica logicae propositionalis cviqve formvlae, svb qvaqve aestimatione, valorem veritatis tribvit, et ostendit evm valorem tantvm ex valoribvs variabilivm qvae in ea occvrrvnt pendere; vnde omnis formvla cvm nn variabilibvs tabvlam veritatis 2n2^{n} versvvm habet. Qvaestio hvivs lectionis est conversa. Data tabvla qvavis, id est colvmna valorvm verorvm et falsorvm ad libitvm ivxta 2n2^{n} versvs scripta, estne aliqva formvla qvae eam pro tabvla habeat? Si hoc in omni tabvla valet, lingva lacvnas exprimendi non habet: qvidqvid de valore veritatis nn envntiatorvm, ex eorvm valoribvs pendente, dici potest, formvla dicitvr. Et cvm in hoc cvrsv omnis formvla composita negatio conivncta sit, responsvm etiam dicet nvm vnvm connectivvm ad omnia dicenda svfficiat.

Qvae ex lectionibvs prioribvs adhibentvr

Aestimatio est fvnctio vv a classe variabilivm {v1,v2,…}\{v_1, v_2, \ldots\} in {0,1}\{0, 1\}, vbi 11 vervm est et 00 falsvm; eivs extensio ad omnes formvlas, qvae etiam vv scribitvr, per recvrsionem definitvr: v((φ↓ψ))=1v((\varphi \downarrow \psi)) = 1 si et solvm si v(φ)=0v(\varphi) = 0 et v(ψ)=0v(\psi) = 0. Ex abbreviationibvs statvtis eadem lectio, in theoremate de valoribvs connectivorvm derivatorvm, valorem cvivsqve connectivi compvtavit; svmmis et prodvctis scripti, hi svnt, pro omni aestimatione vv et omnibvs formvlis φ\varphi et ψ\psi:

v(¬φ)=1−v(φ),v((φ∧ψ))=v(φ) v(ψ),v((φ∨ψ))=v(φ)+v(ψ)−v(φ) v(ψ)v(\neg\varphi) = 1 - v(\varphi), \qquad v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi), \qquad v((\varphi \vee \psi)) = v(\varphi) + v(\psi) - v(\varphi)\,v(\psi)
v((φ→ψ))=1−v(φ)+v(φ) v(ψ),v((φ↓ψ))=(1−v(φ)) (1−v(ψ))v((\varphi \rightarrow \psi)) = 1 - v(\varphi) + v(\varphi)\,v(\psi), \qquad v((\varphi \downarrow \psi)) = (1 - v(\varphi))\,(1 - v(\psi))

Praeterea v((φ↔ψ))=v(φ) v(ψ)+(1−v(φ)) (1−v(ψ))v((\varphi \leftrightarrow \psi)) = v(\varphi)\,v(\psi) + (1 - v(\varphi))\,(1 - v(\psi)), qvod valet 11 si et solvm si v(φ)=v(ψ)v(\varphi) = v(\psi), et v((φ⊻ψ))=v(φ)+v(ψ)−2 v(φ) v(ψ)v((\varphi \veebar \psi)) = v(\varphi) + v(\psi) - 2\,v(\varphi)\,v(\psi), qvod valet 11 si et solvm si v(φ)≠v(ψ)v(\varphi) \neq v(\psi). Cvm valores sint 00 vel 11, qvadratvm valoris est ipse valor, v(φ) v(φ)=v(φ)v(\varphi)\,v(\varphi) = v(\varphi), et prodvctvm valorvm valet 11 si et solvm si qvisqve factor valet 11; ambae observationes sine repetitione adhibebvntvr. Adhibetvr etiam lemma coincidentiae: si dvae aestimationes in variabilibvs formvlae φ\varphi congrvvnt, id est in variabilibvs qvae svbformvlae svnt formvlae φ\varphi, evndem valorem formvlae φ\varphi dant. Ex lectione de conseqventia et aeqvivalentia semanticis svmitvr aeqvivalentia semantica: φ≡ψ\varphi \eqsem \psi cvm v(φ)=v(ψ)v(\varphi) = v(\psi) pro omni aestimatione vv. Deniqve valet conventio litterarvm lectionis de formalizatione: pp, qq et rr variabiles v1v_1, v2v_2 et v3v_3 designant.

Fvnctiones veritatis earvmqve nvmervs

Sit nn nvmervs natvralis. Versvs nn valorvm est series a=(a1,…,an)a = (a_1, \ldots, a_n) in qva qvodqve aia_i est 00 vel 11; classis omnivm talivm versvvm {0,1}n\{0, 1\}^{n} notatvr. Fvnctio veritatis nn argvmentorvm est fvnctio

f ⁣:{0,1}n→{0,1}f\colon \{0, 1\}^{n} \to \{0, 1\}

qvae cviqve versvi valorem veritatis tribvit. Vt tabvla exhibetvr: versvs ordine tabvlae scribvntvr, ab eo incipiendo in qvo omnes valores svnt 11 (pro dvobvs argvmentis, 1 11\,1, 1 01\,0, 0 10\,1, 0 00\,0), et ivxta qvemqve versvm eivs valor scribitvr. Fvnctio veritatis igitvr est tabvla veritatis sine formvla: colvmna dextra, nihil in eivs capite scripto.

PropositioSvnt 22n2^{2^{n}} fvnctiones veritatis nn argvmentorvm

Pro omni nvmero natvrali nn svnt exacte 2n2^{n} versvs nn valorvm et 22n2^{2^{n}} fvnctiones veritatis nn argvmentorvm.

Demonstratio

  1. 1 0 1    ⟼    ∙∘∙\dato{filas}{1\,0\,1 \;\; \longmapsto \;\; \sigI\sigO\sigI}

    Versvs est series nn signorvm, qvorvm qvodqve est 11 vel 00. Si discvs loco valoris 11 et circvlvs loco valoris 00 scribitvr, versvs singvli singvlis catenis longitvdinis nn svper alphabetvm dvorvm signorvm respondent, qvae svnt 2n2^{n} per primvm problema solvtvm lectionis de indvctione, ibi per indvctionem in nn demonstratvm.

  2. f    ⟼    f(1,…,1)    …    f(0,…,0)f \;\; \longmapsto \;\; f(1, \ldots, 1) \;\; \ldots \;\; f(0, \ldots, 0)

    Fvnctio veritatis valoribvs svis in versibvs determinatvr, et qvaevis electio horvm valorvm fvnctionem dat. Si valores ordine tabvlae scribvntvr, fvnctiones singvlae singvlis seriebvs 2n2^{n} signorvm respondent, qvorvm qvodqve est 11 vel 00.

  3. 22n2^{\resaltar{2^{n}}}

    Eadem nvmeratione, nvnc ad series longitvdinis 2n2^{n} adhibita, svnt 22 ad potentiam 2n2^{n} elatvm fvnctiones.

  4. 22=4,24=16,28=256,216=65 5362^{2} = 4, \quad 2^{4} = 16, \quad 2^{8} = 256, \quad 2^{16} = 65\,536

    Primi valores ostendvnt qvam celeriter nvmervs crescat: cvm qvinqve argvmentis iam plvs qvam qvadragies milies centena milia fvnctionvm svnt.

ExemplvmFvnctiones vnivs et dvorvm argvmentorvm

Qvattvor fvnctiones vnivs argvmenti svnt constans 11, identitas, ea qvae valorem mvtat et constans 00; formvlae ⊤\top, pp, ¬p\neg p et ⊥\bot, vbi ⊤:=(p→p)\top := (p \rightarrow p) et ⊥:=¬⊤\bot := \neg\top eae svnt qvae in lectione de semantica statvtae svnt, has tabvlas ordine habent. Inter sedecim fvnctiones dvorvm argvmentorvm svnt eae sex connectivorvm cvrsvs: negatio conivncta, disivnctio, conivnctio, implicatio, implicatio dvplex et disivnctio exclvsiva. Decem aliae restant, inter qvas dvae constantes, eae qvae vnvm tantvm argvmentorvm respicivnt et negatio alternativa, qvae valet 00 tantvm cvm ambo argvmenta valent 11; problema solvtvm 1 omnes eas digerit.

Formvlae qvae fvnctiones repraesentant

Formvla et fvnctio veritatis hoc modo inter se refervntvr. Si φ\varphi est formvla cvivs variabiles svnt inter v1,…,vnv_1, \ldots, v_n, dicitvr φ\varphi fvnctionem veritatis ff nn argvmentorvm repraesentare cvm, pro omni aestimatione vv,

v(φ)=f(v(v1),…,v(vn))v(\varphi) = f(v(v_1), \ldots, v(v_n))

id est cvm tabvla formvlae φ\varphi, variabilibvs v1,…,vnv_1, \ldots, v_n scripta, tabvla fvnctionis ff est. Condicio de variabilibvs non est res minvta: formvla (p∧q)(p \wedge q) nvllam fvnctionem vnivs argvmenti repraesentat, qvia eivs valor non ex solo valore variabilis pp pendet.

PropositioFvnctio formvlae

Sit φ\varphi formvla cvivs variabiles svnt inter v1,…,vnv_1, \ldots, v_n. Tvm φ\varphi exacte vnam fvnctionem veritatis nn argvmentorvm repraesentat, qvae fφf_\varphi notatvr. Si ψ\psi est alia formvla cvivs variabiles svnt inter v1,…,vnv_1, \ldots, v_n, tvm φ≡ψ\varphi \eqsem \psi si et solvm si fφ=fψf_\varphi = f_\psi.

Demonstratio

  1. va(vi)=ai(i≤n),va(vk)=0(k>n)\dato{va}{v_a(v_i) = a_i \quad (i \leq n), \qquad v_a(v_k) = 0 \quad (k > n)}

    Pro qvoqve versv aa est aestimatio qvae cviqve variabili viv_i valorem aia_i dat: satis est ceteris variabilibvs valorem 00 dare.

  2. v(vi)=v′(vi)=ai(i≤n)    ⇒    v(φ)=v′(φ)=fφ(a)v(v_i) = v'(v_i) = a_i \quad (i \leq n) \;\; \Rightarrow \;\; v(\varphi) = v'(\varphi) = \resaltar{f_\varphi(a)}

    Si dvae aestimationes variabilibvs v1,…,vnv_1, \ldots, v_n valores versvs aa dant, in variabilibvs formvlae φ\varphi congrvvnt, et per lemma coincidentiae evndem valorem formvlae φ\varphi dant. Is valor commvnis pro fφ(a)f_\varphi(a) svmitvr; ex constrvctione φ\varphi fvnctionem fφf_\varphi repraesentat.

  3. g(a)=va(φ)=fφ(a)g(a) = v_a(\varphi) = f_\varphi(a)

    Si φ\varphi etiam fvnctionem gg repraesentat, in qvoqve versv aa habetvr g(a)=va(φ)=fφ(a)g(a) = v_a(\varphi) = f_\varphi(a): fvnctio repraesentata vnica est.

  4. v(φ)=fφ(v(v1),…,v(vn))=fψ(v(v1),…,v(vn))=v(ψ)v(\varphi) = f_\varphi(v(v_1), \ldots, v(v_n)) = f_\psi(v(v_1), \ldots, v(v_n)) = v(\psi)

    Si fφ=fψf_\varphi = f_\psi, pro omni aestimatione vv valores formvlarvm φ\varphi et ψ\psi svnt valor eivsdem fvnctionis in eodem versv; vnde φ≡ψ\varphi \eqsem \psi.

  5. fφ(a)=va(φ)=va(ψ)=fψ(a)f_\varphi(a) = v_a(\varphi) = v_a(\psi) = f_\psi(a)

    Vicissim, si φ≡ψ\varphi \eqsem \psi, in qvoqve versv aa aestimatio vav_a evndem valorem ambabvs formvlis dat, et ideo fφ(a)=fψ(a)f_\varphi(a) = f_\psi(a).

Infinitae svnt formvlae cvm variabilibvs inter v1,…,vnv_1, \ldots, v_n et tantvm 22n2^{2^{n}} fvnctiones; ideo mvltae formvlae eandem fvnctionem repraesentant, et propositio dicit eas esse exacte formvlas inter se aeqvivalentes. Restat vt sciatvr vtrvm omnis fvnctio ab aliqva formvla repraesentetvr, an qvaedam tabvlae sine formvla maneant qvae eas habeat.