Semantica Logicae Propositionalis
SUMMARIUM
In hac lectione tractatur semantica logicae propositionalis, speciatim de attributione valorum veritatis expressionibus et de modo quo hi valores propagantur ab una expressione ad aliam per nexus logicos. Introducitur notio tabularum veritatis et exhibentur tabulae veritatis nexuum derivatorum, quales sunt negatio, disiunctio, coniunctio, implicatio, implicatio reciproca atque disiunctio exclusiva. Praeterea, exhibetur definitio attributionis super coetu expressionum atomicarum et explicatur quomodo illa naturaliter extendatur super omnes expressiones quae ex hoc coetu construi possunt. Postremo, definiuntur expressiones validae, satisfacibiles et insatisfacibiles, et afferuntur exempla tautologiarum et contradictionum. Attamen, agnoscitur calculum tabularum veritatis pro expressionibus complexis posse esse inefficax, unde commemoratur inquisitio de methodis alternativis ad quaestiones de validitate vel satisfacibilitate solvendas.
METAE DISCENDI:
Post hanc lectionem discipulus poterit
- Explicare semanticam logicae propositionalis
- Adhibere tabulas veritatis ad repraesentandas attributiones valorum veritatis expressionibus in logica propositionali
- Formulare expressionem per attributionem in logica propositionali
- Applicare regulas semanticas logicae propositionalis ad determinandum utrum expressio sit tautologia, contradictio vel contingentia
INDEX
DE ATTRIBUTIONIBUS VALORUM VERITATIS
SEMANTICA NEXUUM LOGICAE PROPOSITIONALIS
ATTRIBUTIONES IN LOGICA PROPOSITIONALI
EXEMPLARIA IN LOGICA PROPOSITIONALI
PROBLEMA EFFICIENTIAE SEMANTICAE LOGICAE PROPOSITIONALIS
De Attributionibus Valoribus Veritatis
Priori tempore perlustramus syntaxim et systemata deductiva logicae propositionalis. Quamquam hoc nobis profuit ad perpendendum quomodo una expressio ex alia derivari possit, tamen nihil adhuc diximus de attributione valorum veritatis. Cum iam exposuimus omnia quae ad technicas deductionis logicae propositionalis spectant, incipiemus nunc tractatum de semantica logicae propositionalis, ubi consideratur quomodo attributiones valorum veritatis ab una expressione ad aliam propagantur.
Semantica Nexuum Logicae Propositionalis
Semantica nexuum introducitur per tabulas veritatis, quae modum simplicem et ordinatum praebent ad omnes attributiones possibiles super expressionem repraesentandas.
Tabula Veritatis Negationis Coniunctae
Primum incipiemus a nexu omnium fundamentaliore, nempe negatione coniuncta. Huius tabula veritatis talis est:
| \alpha | \beta | (\alpha\downarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Valores “1” et “0” respondent “Verum” et “Falsum”, respective. Quaeque linea in tabula veritatis repraesentat attributionem possibilis super variabiles (vel expressiones atomicas) ex quibus expressio (vel expressiones) examinanda constat. Similiter, quaeque columna in qua expressio ex his variabilibus composita reperitur, ostendit eventus possibiles harum attributionum. Sic, interpretatio huius tabulae declarat \alpha\downarrow\beta verum esse tantum cum \alpha et \beta simul falsae sint, et falsum in ceteris casibus. Quamobrem, connector \downarrow appellatur negatio coniuncta.
Tabulae Veritatis Nexuum Derivatorum
Ex semantica negationis coniunctae, semantica aliorum nexuum obtineri potest per definitiones eorum. Hae sunt:
| Negatio: | \neg \alpha | := | (\alpha\downarrow\alpha) |
| Disiunctio Inclusiva: | (\alpha \vee \beta) | := | \neg(\alpha\downarrow\beta) |
| Coniunctio: | (\alpha \wedge \beta) | := | \neg(\neg\alpha\vee \neg\beta) |
| Implicatio: | (\alpha \rightarrow \beta) | := | (\neg\alpha\vee \beta) |
| Implicatio Duplex: | (\alpha \leftrightarrow \beta) | := | ((\alpha\rightarrow \beta)\wedge(\beta \rightarrow \alpha)) |
| Disiunctio Exclusiva: | (\alpha \underline{\vee} \beta) | := | \neg(\alpha\leftrightarrow \beta) |
Ex his definitionibus licet tabulas veritatis aliorum nexuum computare:
Negatio
| \alpha | \neg \alpha |
| 0 | 1 |
| 1 | 0 |
Hinc oritur proprietas connectoris negationis, qui valorem veritatis expressionis cui applicatur invertere potest.
Disiunctio Inclusiva
| \alpha | \beta | (\alpha\vee\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Quam ob rem disiunctio inclusiva (vel simpliciter “disiunctio”) inter duas expressiones vera est si saltem una ex expressionibus vera est, et falsa est si ambae expressiones simul falsae sunt.
Coniunctio
| \alpha | \beta | (\alpha\wedge\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Ex quo sequitur, coniunctio inter duas expressiones vera est tantum si ambae expressiones simul verae sunt, et falsa est alioquin. Propter hoc, nomen aptum pro hoc connectore etiam esse potest affirmatio coniuncta.
Implicatio
| \alpha | \beta | (\alpha\rightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Itaque tabula veritatis implicationis breviter exprimit notionem quod expressio vera tantum expressionem veram implicare potest, dum expressio falsa potest quidlibet implicare.
Implicatio Duplex
| \alpha | \beta | (\alpha\leftrightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Implicatio duplex expressionem veram format quoties ambae expressiones eiusdem valoris veritatis sunt, et est falsa aliter.
Disiunctio Exclusiva
| \alpha | \beta | (\alpha\underline{\vee}\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Disiunctio exclusiva inter duas expressiones vera est cum una, et tantum una earum vera est, et falsa aliter.
Attributiones in Logica Propositionali
Ex ante dictis habemus notionem simplicem attributionis; attamen, ad progressus postea considerandos opus erit definitione accuratiore. Si S=\{A_1, A_2, \cdots, A_n\} coetus expressionum atomicarum est et \mathcal{F}(S) coetus omnium expressionum quae ex elementis S constitui possunt, tunc habetur sequens definitio:
DEFINITIO: Attributio super S est functio \mathcal{A}: S \longrightarrow \{0,1\}
Id est, attributio super S unicuique expressioni atomicae in S valorem veritatis tribuit. Attributio \mathcal{A} ex S naturaliter extenditur ad omnes elementos \mathcal{F}(S). Si expressio F\in \mathcal{F}(S) est, tunc attributio \mathcal{A} super S respondet unicae lineae in tabula veritatis F, et dicitur \mathcal{A}(F) esse valor veritatis F in illa linea.
Attributio \mathcal{A} ex S extendi etiam potest ad quasdam expressiones quae non sunt in \mathcal{F}(S). Si F_0 expressio est quae non est in \mathcal{F}(S), et S_0 est coetus subformulis atomicarum F_0, tunc si omnes extensiones \mathcal{A} ad S\cup S_0 eundem valorem praebent pro F_0, tunc definitur \mathcal{A}(F_0) esse illum valorem.
EXEMPLUM: Si A et B sunt expressiones atomicae et \mathcal{A} attributio est super \{A,B\} definita per \mathcal{A}(A)=1 et \mathcal{A}(B)=0, tunc habetur:
\mathcal{A}(A\wedge B)=0 et \mathcal{A}(A\vee B)=1
Et quamquam nulla attributio definita est pro variabili C, dici potest:
\mathcal{A}(A\wedge (C\vee \neg C))=1 et \mathcal{A}(B\vee (C\wedge \neg C))=0
Hoc fit in his duabus expressionibus finalibus, quia, cuiuscumque sit valor attributus C, semper erit verum quod
\mathcal{A}(C\vee\neg C)=1 et \mathcal{A}(C\wedge\neg C)=0
Quod facile inspici potest per computationem tabularum veritatis.
| C | \neg C | (C\wedge \neg C) | (C \vee \neg C) |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
■ Finis Exempli
Exemplaria in Logica Propositionali
Consideremus attributionem \mathcal{A} super coetum expressionum S. Si F\in S est talis ut \mathcal{A}(F)=1, tunc dicitur attributionem \mathcal{A} exemplar esse pro F, sive F sustineri per attributionem \mathcal{A}, et id repraesentamus scripto
\mathcal{A}\models F.
Ex hoc statuuntur definitiones sequentes:
DEFINITIO: Expressio valida dicitur cum sub qualibet attributione sustinetur. Si F valida est, tunc scribitur \models F . Expressionum validarum alium nomen est tautologia.
EXEMPLUM: Expressio (C\vee \neg C), quam iam vidimus, est tautologia.
■ Finis Exempli
DEFINITIO: Expressio satisfacibilis dicitur si est ab aliqua attributione sustentata. Expressiones satisfacibiles quae non sunt tautologiae vocantur contingentes.
DEFINITIO: Expressio insatisfacibilis dicitur si nulla attributione sustentatur. Tales expressiones vocantur contradictiones. Si F contradictio est, tunc scribitur \not\models F .
EXEMPLUM: Expressio (C\wedge \neg C), quam iam vidimus, est contradictio.
■ Finis Exempli
Exempla Tautologiarum et Contradictionum
Ponamus nos velle scire utrum expressio sit valida necne. Hoc ipsum est quaestio decisionis in ambitu Semanticae Logicae Propositionalis. Quaestio decisionis est quaelibet quaestio cui, data quaedam inputatio, respondetur per “ita” aut “non”. Si expressio F proposita est et quaeritur an sit valida, versamur in quaestione validitatis. Similiter, si quaeritur an sit satisfacibilis, versamur in quaestione satisfacibilitatis. In logica propositionali, tabulae veritatis methodum systematicam praebent ad has quaestiones solvendas: si omnes valores veritatis F sunt “1”, tunc F est valida; si quidam tantum sunt “1”, est satisfacibilis; et si omnes sunt “0”, est insatisfacibilis.
EXEMPLUM: Consideremus expressionem ((A\wedge (A \rightarrow B)) \rightarrow B). Ad cognoscendum utrum haec expressio sit valida, satisfacibilis an contradictoria, conficienda est eius tabula veritatis.
| A | B | (A\rightarrow B) | (A\wedge(A\rightarrow B)) | ((A\wedge(A\rightarrow B))\rightarrow B) |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Ex hoc videmus ((A\wedge(A\rightarrow B))\rightarrow B) habere valorem veritatis “1” pro omnibus attributionibus possibilibus, unde sequitur expressionem esse tautologiam.
■ Finis Exempli
EXEMPLUM: Consideremus nunc expressionem (((A\rightarrow B)\rightarrow A)\wedge \neg A). Calculus tabulae veritatis dat quod sequitur infra:
| A | B | (A\rightarrow B) | ((A\rightarrow B)\rightarrow A) | \neg A | (((A\rightarrow B)\rightarrow A)\wedge \neg A) |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Itaque eventus est contradictio.
Quaestio Efficientiae Semanticae Logicae Propositionalis Substat
Theoretice, possumus determinare utrum expressio sit valida, contingens vel insatisfacibilis simpliciter computando eius tabulam veritatis, quod non est per se difficile; sed, proh dolor, facilitas exsecutionis pretio efficaciae redimitur. Si habemus expressionem F compositam ex n expressionibus atomicis, tunc conficienda est tabula veritatis cum 2^n lineis; ita, exempli gratia, si F constat ex 23 expressionibus atomicis, eius tabula veritatis habebit 8.388.608 lineas computandas. Hoc modo procedendo, licet mechanicum et facile ad perficiendum sit, calculus celeriter incipit esse non exsecutabilis dum complexitas expressionum augetur. Quam ob rem, unum ex nostris propositis futuris erit modum reperire quaestiones de validitate vel satisfacibilitate solvendi sine necessitate computandi tabulas veritatis. Investigatio talium methodorum est una ex quaestionibus fundamentalibus in qualibet logica.