Senter for Marxistiske og Matematiske Studium, Enschede (SMMSE)

I del II av teksten om logikkmaskina Jevons bygde hevda vi at ho ikkje gjev oss svar på dei problema vi er interesserte i. Som regel er gyldigheita til ei gjevi utsegn eller slutning det vi ønskje å undersøkje, ikkje kva som er dei moglege konklusjonane frå ei mengd premissar. Men at logikkmaskina ikkje kan hjelpe oss med dei interessante problema er ei sanning med modifikasjonar. I denne teksten skal vi sjå på korleis vi kan løyse dei problema vi er interesserte i ved å nytte logikkmaskina til Jevons på ein lur måte.

Vi hugsar at ei (gyldig) slutning er ei mengd premissar og ein konklusjon sånn at kvar gong alle premissane er sanne til same tid må òg konklusjonen sann. (Sidan ei utsegn er gyldig (alltid sann) om ho kan sluttast frå null premissar, skal vi halde oss til slutningar.) Vi skal kalle premissane for P₁, P₂,…,P_n og konklusjonen for K, og skrive ei slutning slik:

P1 P2 · · · Pn K

Kva skjer så om slutning ikkje er gyldig? Då finst det ein måte å gjere alle premissane sanne til same tid som samtidig gjer konklusjonen usann. Dette kallar vi eit moteksempel. Ta til dømes slutninga

A → B B A

Om vi set A = U and B = S ser vi at båe premissane vert sanne, medan konklusjonen vert usann. Vi har funni eit moteksempel, så slutninga kan ikkje vere gyldig. Så det vi skal gjere er å leite etter moteksempel til ei slutning, og om vi ikkje kan finne nokre tyder det at slutninga er gyldig. Enkelt og greitt, no treng vi berre ein måte å leite etter moteksempel på.

Vi hugsar at Jenons sitt logikkpiano gjev oss utsegner om er konsistente med ei mengd premissar, og det skal vi utnytte no. Tenk no at eit moteksempel gjer alle premissane sanne og konklusjonen usann; det er det same som å seie at det gjer alle premissane sanne og det motsette av konklusjonen (negasjonen av konklusjonen) sann til same tid. Tenk vidare at eit moteksempel kan uttrykkjast som ei utsegn. Moteksempelet over kan uttrykkjast som ¬A ∧ B. Det vil seie at vi finn igjen moteksempelet ved å gjere utsegna ¬A ∧ B sann.

No ser du sikkert kor vi vil hen. Lat oss seie vi har ei slutning frå P₁, P₂,…, P_n til K, og vi har funni eit moteksempel som vi kan representere med utsegna M. Sidan moteksempelet representert av M gjer premissane og negasjonen av konklusjonen sann, er M konsistent med mengda {P₁, P₂,…, P_n, ¬K} (det er mogleg å gjere P₁, P₂,…, P_n, ¬K og M sanne på ein gong)! Alt vi treng å gjere er å skrive inn mengda {P₁, P₂,…, P_n, ¬K}, og alle utsegnene vi får tilbake er moteksempel. Om vi ikkje får nokre utsegner tilbake tyder det at det ikkje finst nokre moteksempel og slutninga er gyldig.

Lat oss ta eit par eksempel. Fyrst eksempelet over. Vi skriv inn A → B, B og ¬A, og får tilbake

¬A ∧ B ∧ C ∧ D
¬A ∧ B ∧ C ∧ ¬D
¬A ∧ B ∧ ¬C ∧ D
¬A ∧ B ∧ ¬C ∧ ¬D

Med andre ord har vi A = U, B = S, og kva som helst for C og D som moteksempel, akkurat som vi hadde over. Lat oss no freiste slutninga

¬A → ¬B B A

No skriv vi ¬A → ¬B, B og ¬A, og denne gongen får vi inga utsegner tilbake. Vi veit då at slutninga er gyldig.

Dette er vel og bra. No vil vi sjå om (A ∧ (A → B)) → B er ei gyldig utsegn. Då treng vi berre å skrive ¬((A ∧ (A → B)) → B) på pianoet. Men det er ikkje berre berre, for utsegna er på feil form og kan ikkje skrivast inn. Kva skal vi då gjere? Det finst ei rekkje regler vi kan nytte til å skrive om utsegna til den ønskte forma. I tabellen under kan du sjå korleis vi gjer dette, med utsegna til venstre og reglane vi nyttar til høgre. (For å overtyde deg sjølv om at reglane stemmer kan du setje opp ein sanningstabell for kvar av dei.)

¬((A ∧ (A → B)) → B)	P → Q = ¬P ∨ Q
¬((A ∧ (¬A ∨ B)) → B)	P → Q = ¬P ∨ Q
¬(¬(A ∧ (¬A ∨ B)) ∨ B)	¬(P ∨ Q) = ¬P ∧ ¬Q
¬¬(A ∧ (¬A ∨ B)) ∧ ¬B	¬¬P = P
(A ∧ (¬A ∨ B)) ∧ ¬B	P ∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R)
((A ∧ ¬A) ∨ (A ∧ B)) ∧ ¬B	(P ∨ Q) ∧ R = (P ∧ R) ∨ (Q ∧ R)
((A ∧ ¬A) ∧ ¬B) ∨ ((A ∧ B) ∧ ¬B)	(P ∧ Q) ∧ R = P ∧ Q ∧ R
(A ∧ ¬A ∧ ¬B) ∨ (A ∧ B ∧ ¬B)	.

No, (A ∧ ¬A ∧ ¬B) ∨ (A ∧ B ∧ ¬B) kan vi skrive på pianoet. (Gjer det og sjå kva som skjer.) Denne forma kallest for disjunktiv normalform. Med bruk av desse og nokre reglar til kan faktisk alle utsegner skrivast om til disjunktiv normalform, så med pianoet kan vi skjekke alle utsegner (med inntil fire grunnutsegner) på denne måten.

Nytta så Jevons pianoet sitt på den måten? Det er vel lite truleg. For det fyrste ser vi at det kan vere ganske mykje jobb å skrive ei utsegn om til disjunktiv normalform, såpass mykje at vi like gjerne kunne gått rett på problemet. For det andre har vi sett at om ei utsegn er på disjunktiv normalform nyttar vi berre tangentane på høgresida av pianoet og då har Cop.IS-tangenten (for implikasjon) inga funksjon. Så viss dette var måten å nytte pianoet på kunne Jevons ha lage ein, om ikkje mykje enklare, så i alle høve mindre konstruksjon.

I ein seinare tekst skal vi sjå korleis ein kan nytte dei same prinsippa til å lage ein enkel utsegnskalkyle som er lett å mekanisere.