Formae normales · Topos Uranos

Svmmarivm

Eadem fvnctio veritatis infinitas formvlas admittit qvae eam repraesentent, nec vlla earvm, temere svmpta, qvid dicat perspicve ostendit. Haec lectio dvos typos fixos statvit in qvos omnis formvla salva aeqvivalentia intrat: formam normalem disivnctivam, disivnctionem conivnctionvm litteralivm, et formam normalem conivnctivam, conivnctionem disivnctionvm litteralivm. Litteralia, clavsvlae et conivnctiones elementares definivntvr; demonstratvr negationem alteram formam in alteram vertere cvm qvodqve litterale in svvm oppositvm vertitvr, qvae dvalitas inter eas est; ex tabvla veritatis formae canonicae constrvvntvr et vnicae esse demonstrantvr. Theorema exsistentiae dvas demonstrationes accipit: per tabvlam, vt corollarivm completvdinis fvnctionalis, et per indvctionem secvndvm complexitatem, cvm vnico casv negationis conivnctae et cvm hypothesi dvplici qvam ea demonstratio postvlat. Postremo videtvr cvr operae pretivm sint: validitas formae conivnctivae et satisfactibilitas disivnctivae primo aspectv decernvntvr.

Proposita discendi

Litteralia, clavsvlas, conivnctiones elementares et formvlas in forma normali disivnctiva vel conivnctiva agnoscere, formam, qvae proprietas catenae est, ab aeqvivalentia, qvae proprietas significationis est, distingvendo.
Ex tabvla veritatis formas canonicas disivnctivam et conivnctivam formvlae constrvere, et demonstrare formam canonicam vnicam esse et classem aeqvivalentiae formvlae determinare.
Per indvctionem secvndvm complexitatem demonstrare omnem formvlam formae normali disivnctivae et conivnctivae aeqvivalere, dvalitate, legibvs De Morgani et distribvtivis generalibvs et svbstitvtione semantica vtendo.
Validitatem formae normalis conivnctivae et satisfactibilitatem disivnctivae primo aspectv decernere, et formas normales ad conseqventiam semanticam et ad mensvram minimae magnitvdinis formae normalis adhibere.

In prioribvs hvivs vnitatis lectionibvs formvlis significatio data est: lectio de semantica logicae propositionalis omnem aestimationem ad omnes formvlas extendit; lectio de conseqventia et aeqvivalentia semanticis aeqvivalentiam $\varphi \eqsem \psi$ definivit et svbstitvtionem semanticam demonstravit; lectio de legibvs De Morgani et legibvs distribvtivis generalibvs eas leges ad conivnctiones et disivnctiones $n$ formvlarvm extendit; et lectio de completvdine fvnctionali ostendit omnem fvnctionem veritatis ab aliqva formvla repraesentari. Atqvi fvnctio veritatis ab infinitis formvlis repraesentatvr, qvae inter se valde differre possvnt: $(v_1 \rightarrow v_2)$ , $\neg(v_1 \wedge \neg v_2)$ et $(((v_1 \downarrow v_1) \downarrow v_2) \downarrow ((v_1 \downarrow v_1) \downarrow v_2))$ tria nomina eivsdem rei svnt. Qvod si ita est, expedit in qvaqve classe aeqvivalentiae repraesentantem formae fixae eligere, qvi sine labore legatvr et in qvo qvaedam qvaestiones aspiciendo respondeantvr. Id svnt formae normales.

Litteralia, clavsvlae et formae normales

Ex lectione de legibvs generalibvs memoretvr notatio conivnctionis et disivnctionis $n$ formvlarvm, per recvrsionem definita et ad sinistram consocians; ea vnivs formvlae est ipsa formvla.

\bigwedge_{i=1}^{1} \varphi_i = \varphi_1, \qquad \bigwedge_{i=1}^{n + 1} \varphi_i = \left( \bigwedge_{i=1}^{n} \varphi_i \wedge \varphi_{n + 1} \right)

\bigvee_{i=1}^{1} \varphi_i = \varphi_1, \qquad \bigvee_{i=1}^{n + 1} \varphi_i = \left( \bigvee_{i=1}^{n} \varphi_i \vee \varphi_{n + 1} \right)

In eadem lectione demonstratvm est ordinem et consociationem terminorvm formvlam salva aeqvivalentia non mvtare (associativitas generalis et independentia ab ordine et a repetitionibvs); ideo etiam $\varphi_1 \wedge \varphi_2 \wedge \cdots \wedge \varphi_n$ sine parenthesibvs scribemvs, consociationem ad sinistram intellegentes.

Litterale est variabilis $v_n$ , qvae litterale positivvm appellatvr, vel negatio $\neg v_n$ variabilis, qvae litterale negativvm appellatvr. Oppositvm litteralis $\ell$ , qvod $\ell^{*}$ scribimvs, est litterale eivsdem variabilis et alterivs signi:

\ell = v_n \;\Rightarrow\; \ell^{*} = \neg v_n, \qquad \ell = \neg v_n \;\Rightarrow\; \ell^{*} = v_n

Ex definitione seqvitvr $(\ell^{*})^{*} = \ell$ . Dvo litteralia par complementarivm facivnt si altervm alterivs oppositvm est, vt $v_3$ et $\neg v_3$ .

Clavsvla est disivnctio litteralivm, $\bigvee_{j=1}^{k} \ell_j$ , et conivnctio elementaris est conivnctio litteralivm, $\bigwedge_{j=1}^{k} \ell_j$ , cvm $k \geq 1$ in vtroqve casv; litterale igitvr solvm simvl clavsvla et conivnctio elementaris est. Litterale clavsvlae vel conivnctioni elementari inesse dicitvr si vnvm ex eivs $\ell_j$ est.

Formvla in forma normali disivnctiva est si disivnctio conivnctionvm elementarivm est, et in forma normali conivnctiva si conivnctio clavsvlarvm est; id est, si est, respective, alterivs ex dvabvs formis seqventibvs, vbi $m$ et $k_1, \ldots, k_m$ nvmeri natvrales svnt et qvodqve $\ell_{i,j}$ litterale est:

\bigvee_{i=1}^{m} \bigwedge_{j=1}^{k_i} \ell_{i,j}, \qquad \bigwedge_{i=1}^{m} \bigvee_{j=1}^{k_i} \ell_{i,j}

Dicemvs $\Phi$ formam normalem disivnctivam formvlae $\varphi$ esse si in forma normali disivnctiva est et $\varphi \eqsem \Phi$ , et idem de conivnctiva. Longitvdines $k_i$ ab vna conivnctione (vel clavsvla) ad aliam variare possvnt: idem nvmervm litteralivm in omnibvs postvlare cogeret vt repetitionibvs impleretvr nihilqve adderet.

ExemplvmQvid in forma normali sit et qvid non sit

Formvla $(v_1 \wedge \neg v_2) \vee \neg v_3$ in forma normali disivnctiva est, cvm $m = 2$ , $k_1 = 2$ et $k_2 = 1$ ; in forma conivnctiva non est, qvia conivnctio non est (dvo eivs membra distincta svnt, et conivnctio dvplex negatio est), neqve clavsvla est: vt disivnctio lecta, terminvm habet, $(v_1 \wedge \neg v_2)$ , qvi neqve litterale neqve disivnctio litteralivm est. Formvla $v_1 \wedge \neg v_2 \wedge v_3$ in vtraqve forma est: vt disivnctio vnivs conivnctionis elementaris ( $m = 1$ ) et vt conivnctio trivm clavsvlarvm singvlorvm litteralivm. Eodem modo $(\neg v_1 \vee v_2)$ simvl clavsvla est, id est forma conivnctiva cvm $m = 1$ , et forma disivnctiva dvarvm conivnctionvm singvlorvm litteralivm.

(v_1 \wedge \neg v_2) \vee \neg v_3, \qquad v_1 \wedge \neg v_2 \wedge v_3, \qquad \neg v_1 \vee v_2

Contra, $(v_1 \downarrow v_2)$ et $\neg(v_1 \rightarrow v_2)$ in nevtra forma svnt, qvamqvam prior aeqvivalet formvlae $(\neg v_1 \wedge \neg v_2)$ et posterior formvlae $(v_1 \wedge \neg v_2)$ , qvae in ea svnt.

(v_1 \downarrow v_2) \eqsem \neg v_1 \wedge \neg v_2, \qquad \neg(v_1 \rightarrow v_2) \eqsem v_1 \wedge \neg v_2

Operae pretivm est considerare qvid sit «in forma normali esse». Proprietas est catenae circvlorvm et discorvm, non eivs significationis: lectio de indvctione in nvmeris natvralibvs et in formvlis lectionem vnicam demonstravit, ita vt qvaestio vtrvm formvla disivnctio sit, et cvivs rei, vnvm tantvm responsvm habeat. Atqvi abbreviationes statvtae efficivnt vt qvaedam formvlae in forma normali sint qvamvis non videantvr. Implicatio $(v_1 \rightarrow v_2)$ vt $(\neg v_1 \vee v_2)$ definitvr: non aeqvivalet ei clavsvlae, sed est ea ipsa catena, et ideo iam in forma normali est. Mirabilior est dvplex negatio. Ex definitionibvs formvlarvm $\neg$ et $\vee$ , catena $(\varphi \vee \varphi)$ est $\neg(\varphi \downarrow \varphi)$ , id est $\neg\neg\varphi$ ; ergo $\neg\neg v_1$ litterale non est, sed est, signo post signvm, clavsvla $(v_1 \vee v_1)$ .

(\varphi \vee \varphi) = \neg(\varphi \downarrow \varphi) = \neg\neg\varphi

Valor conivnctionvm et disivnctionvm

Ex lectione de semantica valores connectivorvm derivatorvm svmvntvr: $v(\neg\varphi) = 1 - v(\varphi)$ ; $v(\varphi \wedge \psi) = v(\varphi)\,v(\psi)$ , qvae valet $1$ si et solvm si ambae valent $1$ ; et $v(\varphi \vee \psi) = 0$ si et solvm si ambae valent $0$ . Lectio de legibvs De Morgani et legibvs distribvtivis generalibvs eos ad $n$ formvlas extendit, per indvctionem secvndvm nvmervm terminorvm, in lemmate valoris: pro omni aestimatione $v$ , conivnctio $\bigwedge_{i=1}^{n} \varphi_i$ valet $1$ in $v$ si et solvm si qvaeqve $\varphi_i$ valet $1$ in $v$ , et disivnctio $\bigvee_{i=1}^{n} \varphi_i$ valet $1$ in $v$ si et solvm si aliqva $\varphi_i$ valet $1$ in $v$ . Hoc lemma, qvod hic sine demonstratione repetita citatvr, instrvmentvm est qvo valor cvivsvis formae normalis compvtatvr.

LemmaNegatio litteralis

Pro omni litterali $\ell$ , negatio formvlae $\ell$ eivs opposito aeqvivalet, $\neg\ell \eqsem \ell^{*}$ ; praesertim $v(\ell^{*}) = 1 - v(\ell)$ pro omni aestimatione $v$ .

Demonstratio

$\ell = v_n \;\Rightarrow\; \neg\ell = \neg v_n = \ell^{*}$
Si $\ell$ variabilis $v_n$ est, eivs oppositvm est $\neg v_n$ , qvod est accvrate catena $\neg\ell$ : nihil demonstrandvm est.
$\ell = \neg v_n \;\Rightarrow\; \neg\ell = \resaltar{\neg\neg v_n} \eqsem v_n = \ell^{*}$
Si $\ell$ est $\neg v_n$ , eivs negatio est $\neg\neg v_n$ , qvae litterale non est; ex lege dvplicis negationis (lectio de conseqventia et aeqvivalentia semanticis), aeqvivalet formvlae $v_n$ , qvae oppositvm litteralis $\ell$ est.
$v(\ell^{*}) = v(\neg\ell) = 1 - v(\ell)$
In vtroqve casv $\ell^{*}$ et $\neg\ell$ evndem valorem in omni aestimatione habent, et valor formvlae $\neg\ell$ ex valore negationis datvr.

Secvndvs casvs facile neglegitvr: forma normali negata, scribere solemvs $\neg\ell_{i,j}$ pro litterali, et $\neg\neg v_n$ litterale non est. Dvplex negatio est qvae effectvm in typvm redvcit.

LemmaConivnctiones elementares et clavsvlae

Conivnctio elementaris satisfactibilis est si et solvm si nvllvm par complementarivm continet. Clavsvla valida est si et solvm si aliqvod par complementarivm continet.

Demonstratio

$v(\ell)\,v(\ell^{*}) = v(\ell)\,(1 - v(\ell)) = 0$
Si conivnctio elementaris $\ell$ et $\ell^{*}$ continet, in omni aestimatione altervm eorvm valet $0$ , ex lemmate praecedenti; ex lemmate valoris, conivnctio valet $0$ in omni aestimatione.
$\dato{val}{v_n = \ell_j \;\Rightarrow\; v(v_n) = 1, \qquad \neg v_n = \ell_j \;\Rightarrow\; v(v_n) = 0}$
Si nvllvm par complementarivm continet, aestimatio definitvr qvae $1$ tribvit cviqve variabili qvae ei vt litterale positivvm inest et $0$ cviqve variabili qvae ei vt litterale negativvm inest (ceteris, $0$ ). Definitio sibi non repvgnat, qvia nvlla variabilis vtroqve modo inest.
$v\left( \bigwedge_{j=1}^{k} \ell_j \right) = 1$
In ea aestimatione omnia eivs litteralia valent $1$ , et ex lemmate valoris conivnctio valet $1$ : satisfactibilis est.
$v(\ell) + v(\ell^{*}) = 1$
Si clavsvla $\ell$ et $\ell^{*}$ continet, in omni aestimatione altervm eorvm valet $1$ , et clavsvla valet $1$ : valida est.
$v\left( \bigvee_{j=1}^{k} \ell_j \right) = 0$
Si nvllvm par complementarivm continet, aestimatio qvae $0$ eivs variabilibvs positivis et $1$ eivs variabilibvs negatis tribvit omnia eivs litteralia $0$ valere facit; ex lemmate valoris, clavsvla in ea valet $0$ et valida non est.

In reliqva parte hvivs lectionis

Dvalitas inter dvas formas
Formae canonicae, ex tabvla
Exsistentia per indvctionem secvndvm complexitatem
Qvae primo aspectv videntvr
Problemata solvta
Variabilis qvae altervtram ex ceteris dvabvs comitatvr
Formae normales dvplicis negationis conivnctae
Syllogismvs hypotheticvs, per formas normales
Paritas formas breves non admittit
Formvlae monotonae
Problemata proposita
Forma canonica variabili addita
Conseqventia primo aspectv
Forma disivnctiva valida
Paritas in forma conivnctiva
Variabiles a qvibvs formvla non pendet