MaA 11 Algoritmer och talteori

1. Konnektiv och sanningsvärden

Vad betyder instruktionen på hissens vägg? Är det tillåtet för fem tyngdlyftare att använda hissen, om var och en av dem väger 130 kg? Hur är det med 12 magra gossar, som väger 50 kg? Hur är det med en ensam tyndlyftare?

För att undersöka problem som ovan använder vi oss av sanningsvärden och sanningsvärdetabeller. Varje påstående kan ha två värde, antingen är det sant, eller så är det falskt. Sanna värden betecknar vi med 1 och falska värden med 0.

Då vi jobbar med sanningsvärden och sanningsvärdetabeller utnyttjar vi oss också av konnektiv. Konnektiven är lite som räknesätten då vi räknar med siffor. Vi har konnektiven: negation, disjunktion, konjuktion, implikation och ekvivalen.

Negation

Negation betyder det motsatta. Vi får följande sanningsvärdetabell.

\( A \)\( \neg A \)
10
01

Disjunktion

Disjunktionen tolkas som eller, antingen skall \(A \) eller \( B \) vara sann för att disjunktionen är sann.

\( A \)\( B \) \( A \vee B \)
111
101
011
000

Konjunktion

Disjunktionen tolkas som och, då skall \(A \) och \( B \) vara sanna samtidigt för att konjuktionen är sann.

\( A \)\( B \) \( A \wedge B \)
111
100
010
000

Implikation

Implikationen tolkas som "om A så B". Av konnektiven är det den som ställer till med mest problem. För att implikationen gäller att sant leder till sant. Något falskt leder inte till något sant, medan falskt alltid leder till något sant.

\( A \)\( B \) \( A \Rightarrow B \)
111
100
011
001

Ekvivalens

Ekvivalens betyder att två uttryck är identiska. Vi tolkar ekvivalen som en dubbel implikation. Alltså \( A \Leftrightarrow B \) som \( (A \Rightarrow B) \wedge (B \Rightarrow A) \).

Vi får sanningstabellen

\( A \)\( B \) \( A \Rightarrow B \)\( B \Rightarrow A \) \( A \Leftrightarrow B \)
11111
10010
01100
00111

Exempel 1 Vi beteckar A: "det regnar", B: "det blåser" och C: "det är molnigt". Översätt till svenska

  1. \( A \wedge (B \vee C) \)
  2. \( (A \wedge B) \vee C \)

Lösning

Vi får

  1. \( A \wedge (B \vee C) \) ordagrant blir det "Det regnar och det blåser eller det är molnigt". På bättre svenska kunde vi säga: "Antingen blåser det eller är mulet då det regnar".
  2. \( (A \wedge B) \vee C \) ordagrant blir det "Det regnar och blåser eller det är molnigt". På bättre svenska kan vi säga: "Det regnar och blåser eller så är det mulet".

I exemplet ovan talar vi om att satsen är formaliserad, vi betecknar "det regnar" med ett A.

Sanningsvärden för en sats

Då vi bestämmer sanningsvärden för en sats utnyttjar vi sanningsvärdena för konnektiven och bildar en sanningsvärdetabell.

Exempel 2 Antag att satsen A lyder "det regnar" och satsen B "det blåser". Studera bilden. Är satsen sann?

  1. \( \neg A \)
  2. \( \neg B \)
  3. \( A \wedge B \)
  4. \( A \wedge \neg B \)
  5. \( A \vee B \)
  6. \( \neg A \vee B \)
  7. \( A \vee \neg B \)

Lösning

Vi översätter satserna till svenska och jämför med bilden.

  1. \( \neg A \), är "regnar inte". Satsen är falsk.
  2. \( \neg B \), är "det blåser inte". Satsen är sann.
  3. \( A \wedge B \), är "det regnar och blåser". Satsen är falsk.
  4. \( A \wedge \neg B \)är "det regnar och blåser inte". Satsen är sann.
  5. \( A \vee B \), är "det regnar eller blåser". Satsen är sann.
  6. \( \neg A \vee B \), är "det regnar inte eller blåser". Satsen är falsk.
  7. \( A \vee \neg B \), är "det regnar eller blåser inte". Satsen är sann.

Exempel 3 Ungkarlen Mannerström är intresserad av invecklade brottsfall och är på besök hos patronen i Lillby. Någon har knyckt silverfatet som tillhör husets vakthund. Misstankarna riktas mot Atte, Beata och Calle. Tack vare en pålitlig ledtråd vet Mannerström att endast en av dessa tre är misstänkta är skyldiga till brottet.

Mannerstöm lyssnar, då länsman Neovius förhör de misstänkta.

"Min minnesbild är dunkel, men jag är övertygad om att jag eller Calle är skyldig", bekänner Atte.

"Jag var med Atte hela kvällen på dans i grannsocknen", försäkrar Beata.

"Atte eller Beata ljuger", påstår Calle.

Mannerström vet att i Lillby talar de oskyldiga sanning och de skyldiga ljuger. Efter förhören berättade Mannerström åt Neovius vem den skyldiga var. Vad sade Mannerstörm?

Lösning

Vi betecknar A: Atte är skyldig, B: Beata är skyldig och C: Calle är skyldig.

Vi gör en sanningsvärdetabell. Vi betecknar erkännandena med D, E och F, för att spara utrymme. I den sista kolumnen har vi alla erkännanden med konjuktion, eftersom de skall gälla samtidigt.

\( \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline & & & D & & & E & F & \\ \hline A & B & C & A \vee C & \neg A & \neg B & \neg A \wedge \neg B & \neg(A \vee B) & D \wedge E \wedge F \\ \hline 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ \hline 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ \hline 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ \hline \end{array} \)

I sista kolumnen märker vi att vi har ett ställe med en 1:a. Då är Atte oskyldig, Beata oskyldig och Calle skyldig.

Alltså är Calle skyldig till att farit iväg med silverfatet. Det passar överrens med att de skyldiga ljuger.

Tautologi och logisk ekvivalens

Exempel 4 Nyhet från 3.4: "Genombrott i undersökningarna - Kasper är inte tjuv eller Jesper är oskyldig". Dagen efter låter rubriken som: "En ny vändning i skandalbrottet - Om Kasper är tjuv så är Jesper oskyldig". Är det någon skillnad på nyheterna från 3.4 och 4.4?

Lösning

Vi betecknar A: "Kasper skyldig" och B: "Jesper är oskyldig". Vi får sanningsvärdetabellen

\( \begin{array}{|c|c|c|c|c|c|c|c|} \hline A & B & \neg A & \neg A \vee B & A \Rightarrow B\\ \hline 1 & 1 & 0 & 1 & 1\\ \hline 1 & 0 & 0 & 0 & 0\\ \hline 0 & 1 & 1 & 1 & 1\\ \hline 0 & 0 & 1 & 1 & 1\\ \hline \end{array} \)

Vi märker att satserna betyder det samma. Det är ingen skillnad på rubrikerna till nyheterna.

Satser som ger samma resultat är ekvivalenta. De är satslogiskt samma sak.

Uppgifter

  1. Vi betecknar A: "Kasper är tjuv", B: "Jesper är tjuv" och C: "Jonatan är tjuv". Översätt till svenska.
    1. \( A \wedge B \)

      Kasper och Jesper är tjuvar.

    2. \( A \vee B \)

      Kasper eller Jesper är tjuv.

    3. \( A \wedge B \wedge \neg C \)

      Kasper och Jesper är tjuvar och Jonatan är inte en tjuv.

    4. \( \neg(A \wedge B) \)

      Kasper och Jesper är inte båda tjuvar.

    5. \( \neg(A \vee B) \)

      Varken Kasper eller Jonatan är tjuvar.

    6. \( A \to (B \vee C) \)

      Om Kasper är tjuv, så är Jesper eller Jonatan tjuv.

  2. Välj satserna P och Q så att satsen i formaliserad form är \( P \to \neg Q \).
    1. Om jag cyklar, så har jag inte bil.

      P: "jag cyklar", Q: "jag kör bil"

    2. Jag äter inte efterrätt, om jag har bråttom.

      P: "jag har bråttom", Q: "jag äter efterrätt"

    3. Om läraren inte skyndar på, så lär jag mig detta.

      P: "läraren skyndar inte på", Q: "jag lär mig inte detta"

    4. Jag lär mig detta endast om läraren inte skyndar på.

      P: "jag lär mig detta", Q: "läraren skyndar på"

  3. Sammanställ en sanningstabell för satserna \( \neg A \vee \neg B \) och \( \neg (A \wedge B) \). Jämför sanningstabellerna.

    Översätt satserna ovan till svenska, då satsen A lyder "Kasper är skyldig" och satsen B "Jesper är skyldig".

    Vi får

    \( \begin{array}{|c|c|c|c|c|} \hline A & B & \neg A & \neg B & \neg A \vee \neg B \\ \hline 1 & 1 & 0 & 0 & 0 \\ \hline 1 & 0 & 0 & 1 & 1 \\ \hline 0 & 1 & 1 & 0 & 1 \\ \hline 0 & 0 & 1 & 1 & 1 \\ \hline \end{array} \)

    Vi får

    \( \begin{array}{|c|c|c|c|} \hline A & B & A \wedge B & \neg (A \wedge B) \\ \hline 1 & 1 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 \\ \hline 0 & 1 & 0 & 1 \\ \hline 0 & 0 & 0 & 1 \\ \hline \end{array} \)

    Satserna ger samma sanningsvärdetabell.

    Vi får "Kasper eller Jesper är oskyliga" och "Kasper och Jesper är inte båda skyldiga".

  4. Är satsen en tautologi? Översätt satsen till svenska, då satsen A lyder "det regnar".
    1. \( A \vee A \)

      Nej

    2. \( A \wedge A \)

      Nej

    3. \( A \to A \)

      Ja

    4. \( A \leftrightarrow A \)

      Ja

    5. \( A \vee \neg A \)

      Ja

    6. \( \neg (A \wedge \neg A) \)

      Ja

  5. Är följande satser sanna?
    1. \( A \to (B \vee \neg B) \)

      Alltid sann.

    2. \( A \to (B \wedge \neg B) \)

      Då A är falsk.

    3. \( (A \vee \neg A) \to B \)

      Då B är sann.

    4. \( (A \wedge \neg A) \to B \)

      Alltid sann.

  6. I Kamomilla stad har någon knyckt rosor ur borgmästarens blomsterrabatt. Amatördetektiv Mannerström erhöll en lapp med texten: \( (A \wedge B \wedge \neg C) \vee (A \wedge \neg B \wedge \neg C) \). Senare fick han nyckeln till chifferskriften: A: "Kasper är skyldig", B: "Jesper är skyldig" och C: "Jonatan är skyldig".

    Mannerström hade från pålitliga källor fått veta att informationen på lappen var sann. Vilket budskap erhöll Mannerström?

    Gör en sanningsvärdetabell och kom fram till två rader: A har värdet 1, B har värdet 1 och C har värdet 0. Den andra raden är A har värdet 1, B har värdet 0 och C har värdet 0.

    Vi kan dra slutsatsen att Kasper är skyldig och Jonatan är oskyldig. Jesper kan vara skyldig eller oskyldig.

  7. I Kamomilla stad hade någon knyckt ventilgummit på rektorns cykel. Amatördetetkiv Mannerström erhöll igen ett hemlighetsfullt budskap. Budskapet innehöll följande text: \( (\neg A \vee (B \wedge \neg C)) \vee ((\neg A \vee \neg B) \wedge \neg C) \). Mannerström lyckades upptäcka chifferskriftens nyckel: A: "Kasper är skyldig", B: "Jesper är skyldig" och C: "Jonatan är skyldig".

    Mannerström var övertygad om att någon sänt ett falskt budskap för att vilseleda honom. Vilken slutsats drog han av budskapet?

    Kasper och Jonatan är skyldiga. Jesper kan vara skyldig eller oskyldig.

  8. Amatördetektiv Mannerström är åter gäst hos patronen i Lillby. Någon har med leriga gummistövlar gått över salens ljusa matta. Misstankarna riktas igen mot Atte, Beata och Calle. Mannerström är övertygad om att någon av dem är skyldig. Länsman Neovius förhör de misstänkta. I Lillby ljuger de skyldiga alltid och de oskyldiga talar sanning.

    "Calle är säkert skyldig", påstår Atte. "Atte är oskyldig och jag är oskyldig", tillägger Beata. "Atte är oskyldig eller jag är skyldig", tvekar Calle.

    Efter att ha funderat en stund avslöjade Mannerström den skyldiga. Vad sade Mannerström?

    Beata är skyldig.

    Vi kommer åt det via en sanningsvärde tabell. I de tre sista kolumnerna bildar vi värdena då alla tre vittnesmål skall gälla samtidigt och någon dera av dem ljuger.

    \( \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline A & B & C & \neg A & \neg B & \neq A \wedge \neg B & \neg A \vee C & \text{A ljuger} & \text{B ljuger} & \text{C ljuger} \\ \hline 1 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ \hline 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ \hline 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ \hline \end{array} \)

    På om Atte ljuger är alla oskyldiga. Om Calle ljuger stämmer inga vittnesmål. Det betyder att Beata är skyldig.

  9. Amatördetektiv Mannerström är på resa och en förtvivlad länsman Neovius är tvungen att förlita sig på en spåman: "Man har berättat för mig att om Jesper är oskyldig, så är Kasper oskyldig. Kan jag lita på denna information?"

    "Om Kasper är oskyldig håller informationen streck", svarar spåmannen. Vilken slutsats kan Neovius dra av svaret?

    Ingen. Spåmannens sats är alltid sann.

  10. Bilda med hjälp av konnektiv någon sats P av satserna A och B. Satsen P har följande sanningstabell.
    1. Den första sanningstabellen är

      \( \begin{array}{|c|c|c|} \hline A & B & P \\ \hline 1 & 1 & 0 \\ \hline 1 & 0 & 1 \\ \hline 0 & 1 & 0 \\ \hline 0 & 0 & 0 \\ \hline \end{array} \)

      Till exempel \( A \wedge \neg B \)

    2. Den andra är

      \( \begin{array}{|c|c|c|} \hline A & B & P \\ \hline 1 & 1 & 1 \\ \hline 1 & 0 & 0 \\ \hline 0 & 1 & 1 \\ \hline 0 & 0 & 1 \\ \hline \end{array} \)

      Till exempel \( (A \wedge B) \vee (\neg A \wedge B) \vee (\neg A \wedge \neg B) \) eller \( \neg(A \wedge B) \) eller \( \neg A \vee B \).

    11. Narrarnas och riddarnas ö

    Skådeplatsen får många logiska problem är den berömda Narrarnas och riddarnas ö. Varje invånare är på ön antingen narr eller riddare. Narrarna ljuger alltid och riddarna talar alltid sanning. Följande fyra uppgifter skildrar händelser på Narrarnas och riddarnas ö.

  11. Under min resa till Narrarnas och riddarnas ö mötte jag av två öbor, Anders och Bernhard. Under vår diskussion sade Anders: "Om jag är riddare, så är också Bernhard riddare". Är det möjligt att avgöra om Anders och Bernhard är narrar eller riddare?

    Ja, båda är riddare.

  12. Då jag diskuterade med två andra öbor, Anna och Bo, sade Anna: "Om Bo är riddare, så är jag en narr". Vad för något är Anna och Bo?

    Anna är riddare och Bo är narr.

  13. En gång tillbringade jag kvällen tillsammans med tre öbor; Atte, Börje och Cecilia. Vid ett visst skede berättade Atte: "Börje är riddare". Något senare nämnde Börje: "Om Atte är riddare, så är också Cecilia riddare". Vad för något är Atte, Börje och Cecilia?

    Alla är riddare.

  14. På ön spriddes ett rykte enligt man funnit guld i bergen på öns sydspets. En invånare på ön kommenterade ryktet och sade: "Det finns guld på ön sydspets om och endast om jag är riddare."
    1. Är invånaren narr eller riddare?

      Vilkendera som helst.

    2. Finns det guld på ön?

      Ja, det finns det.

  15. På Stollarnas ö talar man ett språk som har en invecklad satskonstruktion: "A lirum B larum C". Ön har besök av språkvetare och de har dragit slutsatsen att konstruktionen följer följande tabell.

    \( \begin{array}{|c|c|c|c|} \hline A & B & C & A \text{ lirum } B \text{ larum } C\\ \hline 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 0 & 0 \\ \hline 1 & 0 & 1 & 1 \\ \hline 1 & 0 & 0 & 1 \\ \hline 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 0 & 1 \\ \hline 0 & 0 & 1 & 1 \\ \hline 0 & 0 & 0 & 1 \\ \hline \end{array} \)

    Översätt till svenska satsen "bälä bää lirum bölö böö larum höbö höö", där "bälä bää" betyder "du äter morgongröten", "bölö böö" betyder "du slutar leka" och "höbö höö" betyder "vi går på cirkus".

    "Du äter inte morgongröten eller du slutar inte leka eller vi går på cirkus", som är logiskt ekvivalent med "om du äter morgongröten och slutar leka, så går vi på cirkus".