das Entscheidungsproblem – frågan om det går att avgöra ifall ett matematiskt eller logiskt påstående är sant eller falskt på ett mekaniskt sätt (alltså med en algoritm) som ger rätt svar för alla matematiska och logiska påståenden. – Problemet fick sitt namn av den tyska matematikern David Hilbert (1862—1942, se Wikipedia – se också Hilberts paradox), men andra filosofer och matematiker hade tänkt i samma banor tidigare. Ett annat sätt att se på saken är att fråga ifall det finns ett logiskt‑matematiskt språk som kan användas för att formulera varje tänkbart problem, och som också kan användas för att räkna ut lösningen. Kurt Gödels† ofullständighetssats från 1931 visade indirekt att det inte går att avgöra, och något senare visade Alan Turing† och Alonzo Church†, oberoende av varandra och på olika sätt, att svaret på frågan är nej. Turings bevis innehöll beskrivningen av det som numera kallas för Turingmaskiner. (Avgörbarhetsproblemet kallas också för avgörandeproblemet.)
– i programmering: ett logiskt villkor som betyder ”A eller B, men inte båda” – se exklusiv disjunktion;
– en enkel form av kryptering som bygger på det logiska villkoret XOR. Texten som ska kodas (klartexten) i binär form jämförs med en nyckel i binär form, bit för bit. Nyckeln är en serie ettor och nollor som vid behov repeteras tills den når slutet av texten. Om det finns samma tecken i klartexten och i nyckeln sätts en etta i kryptotexten, om det är olika tecken sätts en nolla. Detta räknas som en mycket enkel och riskabel form av kryptering.
eller sanningsvärdestabell, på engelska truth table – tabell som åskådliggör vad som krävs för att ett logiskt uttryck ska anses som sant eller falskt. Sant och falskt kallas för sanningsvärden. – En sanningsvärdetabell för en logisk konjunktion(OCH) ser ut så här:
– Båda påståendena A och B är sanna, alltså A och B (A∧B):
A
B
A ∧ B
sant
sant
sant
sant
falskt
falskt
falskt
sant
falskt
falskt
falskt
falskt
– Tabellen åskådliggör att, till exempel, ett påstående som ”Sverige är en monarki och Norge är en monarki” är sant bara om det är sant att Sverige är en monarki och sant att Norge är en monarki. Om något (eller båda) av påståendena skulle vara falskt är det sammansatta påståendet också falskt. – En sanningsvärdetabell kan sammanfattas genom att man tar värdena i spalten längst till höger, uppifrån och ner, och markerar sant med 1 och falskt med 0. För tabellen här ovanför, konjunktion, blir det alltså 1000, och om man ser 1ooo som binär notation motsvarar det 8.
i formell logik: motsvarighet till vardagsspråkets och. – Om man binder ihop två påståenden med OCH i formell logik och programmering måste båda vara sanna, annars anses det sammansatta påståendet som helhet vara falskt. I formell logik används tecknet ∧ för konjunktion, i programmering ofta engelska AND. Även tecknen · (upphöjd punkt) och & förekommer. – Sökvillkoret ”A AND B” tar, om man använder det i en sökmotor på webben, fram webbsidor som innehåller både A och B – men inte sidor som bara nämner ett av dem. Alltså: om man söker på ”sill AND brännvin” får man upp alla sidor som nämner både sill och brännvin (inte nödvändigtvis intill varandra), men inte sidor som nämner bara ett av orden. (Se och‑förval.) – Se också det omvända, NAND. – En sanningsvärdetabell för konjunktion ser ut så här:
(not AND) – inte båda, icke och – ett logiskt villkor som används i programmering. Det är motsatsen till villkoret AND, se konjunktion. – AND betyder att av två påståenden måste båda vara sanna; NAND betyder att minst ett av påståendena, eller båda, måste vara falskt. – Exempel: villkoret ”regn NAND snö” godkänner ”regn men inte snö”, ”snö men inte regn”, ”varken snö eller regn”, men inte ”regn och snö”. NAND‑villkoret kan också tillämpas på fler än två påståenden: ett eller flera av påståendena får då vara sanna, men inte alla. Alla andra logiska villkor kan skrivas som kombinationer av NAND‑villkor. – Jämför med NOR. – NAND flash memory, NAND‑minne, är en av huvudtyperna av flashminne. Det syftar på att transistorerna i minnescellerna är sammankopplade enligt det logiska villkoret NAND: bara om alla transistorerna i cellen får en hög ingående spänning (=sant) blir det en låg utgående spänning (=falskt). – En sanningsvärdetabell för NAND ser ut så här:
– Påståendena A och B får inte båda vara sanna” (A NAND B) :
(Boolean) – boolesk logik, boolesk algebra – ett sätt att uttrycka logiska problem som matematik. – Boolesk algebra är uppkallad efter George Boole (mer om honom längre ner). – Två saker gör att boolesk logik passar för datorteknik:
– boolesk algebra löser logiska problem med matematiska metoder. Om du kan beskriva ett problem med den booleska algebrans termer så kan du sedan lösa det mekaniskt, vilket innebär att du kan programmera en dator att lösa problemet;
– boolesk algebra representerar logikens två sanningsvärdensant och falskt med den binära matematikens två siffror 1 och 0. Det passar bra för datorer, eftersom datorernas logiska kretsar (processorerna) också arbetar med två lägen, på och av. Datorernas kretsar är komplicerade tillämpningar av boolesk algebra.
– Boolesk algebra är inget konstigt: det är ett sätt att beskriva vanlig matematik och logik som råkar passa in på hur datorer är konstruerade. I boolesk algebra används villkoren AND (konjunktion), OR (disjunktion) och NOT (negation). Det finns fler logiska villkor än AND, OR och NOT, till exempel IF THEN (implikation) och XOR (exklusiv disjunktion). Men de tre booleska termerna räcker. Alla andra logiska villkor kan nämligen uttryckas med kombinationer av AND, OR och NOT samt parenteser. – Boolesk algebra är uppkallad efter logikern George Boole (1815—1864). Han strävade efter att förena formell logik och matematik i ett gemensamt symbolspråk. Booles principer kom till användning när de första datorerna konstruerades. – Boolesk uttalas ”bolsk” med O som i sol. – Mer i Wikipedia.) – Det engelska ordet Boolean används ibland i betydelsen binär, alltså när svaret på en fråga är ja eller nej, sant eller falskt, ett eller noll – inga mellanvärden. – Språkligt: Benämningen booleansk förekommer också på svenska, men den är onödig, eftersom det inte finns något som heter booleanism.
logikensinte. – I boolesk algebra brukar det heta NOT. I formell logik används tecknet ¬ eller ~ (tilde) för negation. (Det förekommer också andra tecken för negation.) – Vardagsspråkets inte och logikens negation används inte alltid på samma sätt. Logikens negation kan ofta översättas med ”allt utom”. Skillnaden blir uppenbar när man använder NOT i en sökmotor på webben. (Sökmotorer brukar följa logikens regler.) Söker man på ”NOT Skanör” med en sökmotor så får man träff på alla de miljarder webbsidor som inte nämner Skanör. (Man skulle troligen skriva -Skanör med vanligt minustecken i en sökmotor.) Men i vardagsspråket betyder ”inte Skanör” antagligen Falsterbo. – En sanningsvärdetabell för negation är enkel: