/bok-logik/book-logik

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/bok-logik/book-logik

« back to all changes in this revision

Viewing changes to Booleska operatorer.tex

  • Committer: Gustav Hartvigsson
  • Date: 2016-02-23 12:12:45 UTC
  • Revision ID: gustav.hartvigsson@gmail.com-20160223121245-0m1861poe18v0uq3
Initial documents and such.

Show diffs side-by-side

added added

removed removed

Lines of Context:
Booleska operatorer.tex
 
1
\documentclass[a4paper,11pt]{article}
 
2
\usepackage[T1]{fontenc}
 
3
\usepackage[utf8]{inputenc}
 
4
\usepackage{dejavu}
 
5
\usepackage[swedish]{babel}
 
6
\usepackage{fullpage}
 
7
\usepackage{hyperref}
 
8
\usepackage{amsmath}
 
9
\usepackage{amssymb}
 
10
\usepackage{enumitem}
 
11
\usepackage{algorithm}
 
12
\usepackage{algpseudocode}
 
13
\usepackage{algorithmicx}
 
14
\usepackage{framed}
 
15
 
 
16
\usepackage[
 
17
    type={CC},
 
18
    imagemodifier={-eu},
 
19
    modifier={by-sa},
 
20
    version={3.0},
 
21
]{doclicense}
 
22
 
 
23
\selectlanguage{swedish} 
 
24
 
 
25
\include{swealgo}
 
26
 
 
27
% babel-paket eller motsvarande
 
28
 
 
29
%%%%%%%%%%%%%%%%%%%%%% FIX HREF
 
30
\usepackage{xcolor}
 
31
\definecolor{dark-red}{rgb}{0.4,0.15,0.15}
 
32
\definecolor{dark-blue}{rgb}{0.15,0.15,0.4}
 
33
\definecolor{medium-blue}{rgb}{0,0,0.5}
 
34
\definecolor{dark-green}{rgb}{0,0.5,0}
 
35
\hypersetup{
 
36
    colorlinks,
 
37
    linkcolor={dark-red},
 
38
    citecolor={dark-green},
 
39
    urlcolor={dark-blue},
 
40
    pdftitle={Logik och det Booleska},    % title
 
41
    pdfauthor={Gustav Hartvigsson},     % author
 
42
}
 
43
%%%%%%%%%%%%%%%%%%%%%% END FIX HREF
 
44
 
 
45
%%%% FIX DESCRIPTIONS
 
46
% From: http://tex.stackexchange.com/a/33341
 
47
% Variant B with superior spacing -- thanks to Peter Grill
 
48
\SetLabelAlign{parright}{\parbox[t]{\labelwidth}{\raggedleft#1}}
 
49
 
 
50
\setlist[description]{style=multiline,topsep=10pt,leftmargin=2cm,%
 
51
    align=parright}
 
52
 
 
53
%%%% END FIX DESCRIPTIONS
 
54
 
 
55
%%%% FIX SWEDISH CAPTIONS ON ALGORITHMS
 
56
% http://tex.stackexchange.com/a/169119
 
57
\makeatletter
 
58
\renewcommand*{\ALG@name}{Algoritm}
 
59
\makeatother
 
60
%%%%
 
61
 
 
62
\title{\Huge Logik och det Booleska\\
 
63
\Large Introduktion till Booleska Uttryck och Kontrollstrukturer för Blivande Programmerare}
 
64
\author{Gustav Hartvigsson \\
 
65
\\Strömstad Gymnasium}
 
66
 
 
67
\begin{document}
 
68
 
 
69
\maketitle
 
70
 
 
71
\begin{abstract}
 
72
I detta dokument skall eleven lära sig den formella notationen
 
73
för de booleska operatorer. Dokumentet går igenom operatorerna
 
74
från en enkel nivå genom ekvationer och sanningstabeller.
 
75
 
 
76
Eleven skall få en överblick över de operatorer som är mest relevanta för
 
77
programmering: \texttt{och}, \texttt{eller},
 
78
\texttt{exklusiv eller}, \texttt{negering}, \texttt{implikation} och \texttt{omm}.
 
79
 
 
80
Operatorerna och sanningsuttrycken relateras till schematisk programmerings kod som
 
81
beskriver kontrollstrukturer och programflöden.
 
82
 
 
83
Som avslutning presenteras övningar som eleven \textit{bör} utföra som testar elevens förståelse
 
84
för booleska operatorer, booleska uttryck och sanningstabeller.
 
85
 
 
86
\bigskip
 
87
I andra halvan av detta dokument skall eleven lära sig hur kontrollstrukturer ser ut,
 
88
fungerar och någon form av pseudokod. Eleven skall lära sig hur man skriver
 
89
och använder pseudokod och varför det är av fördel att använda den.
 
90
 
 
91
 
 
92
 
 
93
\bigskip
 
94
Målet med detta dokument är inte att eleven skall lära sig detta utantill --
 
95
det är inte en del av kursmålen -- utan att exponera eleven för hur man kan
 
96
tänka i relation till booleska operatorer och logiska uttryck som
 
97
förekommer inom programmering. Samt lära sig att läsa, skriva och resonera kring
 
98
kod genom användningen av pseudokod.
 
99
\end{abstract}
 
100
 
 
101
\newpage
 
102
\vspace*{\fill}
 
103
\noindent
 
104
\doclicenseThis
 
105
\vspace*{\fill}
 
106
 
 
107
\newpage
 
108
\tableofcontents
 
109
 
 
110
 
 
111
\newpage
 
112
\section{Booleska Operatorer, Uttryck och Logik}
 
113
Ordet boolesk (\textit{boolean} på engelska) kommer av den brittiske matematikern
 
114
George Boole som introducerade konceptet i sina böcker
 
115
\textit{The Mathematical Analysis of Logic (1847)} och
 
116
\textit{An Investigation of the Laws of Thought (1854)}.
 
117
Ordet lär ha myntats av Henry M. Sheffer enligt Edward Vermilye Huntington.
 
118
 
 
119
Logik hjälper oss att förstå och resonera kring uttryck som
 
120
''Det finns ett heltal som inte är summan av kvadratroten ur två heltal''.
 
121
Logik är grunden i all digital teknik, så som det som gör att du kan
 
122
ringa ett samtal och det kopplas fram, till att du kan surfa på nätet.
 
123
 
 
124
I logiken så används oftast $p, q, ...$ för att representera något
 
125
sanningsuttryck, ett sådant uttryck kan vara ''Pelle har en dator'',
 
126
''klockan är sexton fyrtiofem'' eller ''mitt hus är mindre än det där huset''.
 
127
 
 
128
\bigskip\noindent
 
129
I detta dokument användes -- generellt --
 
130
notationen $S$ för att representera ett \texttt{sant}
 
131
sanningsvärde för ett uttryck och $F$ för ett
 
132
\texttt{falskt} sanningsvärde för ett uttryck.
 
133
 
 
134
\bigskip\noindent
 
135
Den notationen som Boole använde i sina böcker var {\large $1$} för ett
 
136
\texttt{sant} sanningsvärde och {\large $0$} för ett \texttt{falskt} sanningsvärde.
 
137
 
 
138
Denna notation används inte här för att det skall vara lättare att läsa och för
 
139
att skilja detta från digitala signaler, trotts att de inte är mycket skillnad.
 
140
 
 
141
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
142
\subsection{''och'' Operatorn}
 
143
\texttt{''och''} operatorn har den formella matematiska notationen $\wedge$.
 
144
Denna operatorn kallas formellt för konjunktion.
 
145
 
 
146
Om vi har sanningsuttrycken $p$ och $q$ och så kan vi skriva ett uttryck $ p \wedge q $
 
147
och sanningstabellen för detta uttryck kan ses i tabell \ref{tab:wedge}.
 
148
 
 
149
\begin{table}[H]
 
150
  \caption{Sanningstabell för  $p \wedge q$}
 
151
  \label{tab:wedge}
 
152
  \begin{center}
 
153
    \begin{tabular}{|c c||c|}
 
154
      \hline
 
155
       $p$ & $q$ & $p \wedge q$ \\
 
156
      \hline
 
157
       $F$ & $F$ & $F$ \\
 
158
      \hline
 
159
       $S$ & $F$ & $F$ \\
 
160
      \hline
 
161
       $F$ & $S$ & $F$ \\
 
162
      \hline
 
163
       $S$ & $S$ & $S$ \\
 
164
      \hline
 
165
    \end{tabular}
 
166
  \end{center}
 
167
\end{table}
 
168
 
 
169
Ett sätt att se på hur $\wedge$ fungerar är att ta meningen ''Pelle \textbf{och} Nora håller om varandra'',
 
170
detta uttryck håller endast om både Pelle och Nora håller om varandra. Om Pelle håller om Nora, men Nora
 
171
inte håller om Pelle, och tvärt om, så håller inte det uttrycket som vi utgick ifrån.
 
172
 
 
173
Ett annat exempel är ''klockan är fyra \textbf{och} solen går upp''. Om klockan inte är fyra eller
 
174
om solen inte går upp så håller inte uttrycket, och är därmed \texttt{falkt}. Deluttrycken här är
 
175
''klockan är fyra'' och ''solen går upp''. 
 
176
 
 
177
\subsection{''eller'' Operatorn}
 
178
\texttt{''eller''} operatorn har den formella notationen $\vee$ och
 
179
har de formella namnen \textit{disjunktion} eller \textit{inklusive disjunktion}.
 
180
 
 
181
Om vi har uttrycket $p \vee q$ där $p$ och $q$ är något logiskt uttryck som
 
182
kan vara sant eller falskt så får vi sanningstabellen som kan ses i tabell \ref{tab:vee}
 
183
 
 
184
\begin{table}[H]
 
185
  \caption{Sanningstabell för $p \vee q$}
 
186
  \label{tab:vee}
 
187
  \begin{center}
 
188
    \begin{tabular}{|c c||c|}
 
189
      \hline
 
190
       $p$ & $q$ & $p \vee q$ \\
 
191
      \hline
 
192
       $F$ & $F$ & $F$ \\
 
193
      \hline
 
194
       $S$ & $F$ & $S$ \\
 
195
      \hline
 
196
       $F$ & $S$ & $S$ \\
 
197
      \hline
 
198
       $S$ & $S$ & $S$ \\
 
199
      \hline
 
200
    \end{tabular}
 
201
  \end{center}
 
202
\end{table}
 
203
 
 
204
Ett sätt att se på hur $\vee$ fungerar är att ta uttrycket ''Pelle har en dator \textbf{eller}
 
205
\newline Noras klocka visar kvart över fjorton'', detta uttryck består av två delar, båda
 
206
delarna -- eller deluttrycken -- kan ha sanningsvärdena \texttt{sant} eller \texttt{falskt}
 
207
och de utesluter inte varandra när det gäller hela uttryckets sanningsvärde.
 
208
Alltså om Pelle har en dator och Noras klocka visar kvart över fjorton så håller uttrycket,
 
209
samma gäller om bara ett av dessa deluttryck är \texttt{sant}.
 
210
 
 
211
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
212
\subsection{''exklusivt eller'' Operatorn}
 
213
Den matematiska notationen för \texttt{''exklusivt eller''} är $\oplus$ och
 
214
har det formella namnet \textit{exklusiv disjunktion}.
 
215
 
 
216
En sanningstabell över uttrycket $p \oplus q$ kan ses i tabell \ref{tab:oplus}.
 
217
 
 
218
\begin{table}[H]
 
219
  \caption{Sanningstabell för $p \oplus q$}
 
220
  \label{tab:oplus}
 
221
  \begin{center}
 
222
    \begin{tabular}{|c c||c|}
 
223
      \hline
 
224
       $p$ & $q$ & $p \oplus q$ \\
 
225
      \hline
 
226
       $F$ & $F$ & $F$ \\
 
227
      \hline
 
228
       $S$ & $F$ & $S$ \\
 
229
      \hline
 
230
       $F$ & $S$ & $S$ \\
 
231
      \hline
 
232
       $S$ & $S$ & $F$ \\
 
233
      \hline
 
234
    \end{tabular}
 
235
  \end{center}
 
236
\end{table}
 
237
 
 
238
Ett sätt att se på detta kan vara att använda uttrycket ''Pelle
 
239
\textbf{eller} Nora använder datorterminalen'', detta utesluter varandra ty
 
240
både Nora och Pelle kan inte använda samma datorterminal samtidigt.
 
241
 
 
242
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
243
\subsection {''negering'' Operatorn}
 
244
Negering är viktigt att förstå, det använd ofta tillsammans med
 
245
deluttryck. Den matematiska notationen för negering är $\neg$.
 
246
En sanningstabell över uttrycket $\neg p$ kan ses i tabell \ref{tab:neg}.
 
247
\begin{table}[H]
 
248
  \caption{Sanningstabell för $\neg p$}
 
249
  \label{tab:neg}
 
250
  \begin{center}
 
251
    \begin{tabular}{|c||c|}
 
252
      \hline
 
253
       $p$ & $\neg p$ \\
 
254
      \hline 
 
255
       $F$ & $S$ \\
 
256
      \hline
 
257
       $S$ & $F$ \\
 
258
      \hline
 
259
    \end{tabular}
 
260
  \end{center}
 
261
\end{table}
 
262
 
 
263
Ett exempel på hur man kan använda $\neg$ är uttrycket $ p \wedge \neg q $, alltså
 
264
$p$ och inte $q$. Ett exempel på detta kan vara meningen ''Nora hoppar bungyjump \textbf{och}
 
265
Pelle kollar \textbf{inte} på sin mobiltelefon'', uttrycket håller inte om Nora inte hoppar bungyjump
 
266
eller om Pelle kollar på sin mobiltelefon.
 
267
 
 
268
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
269
\subsection{''implikation'' Operatorn}
 
270
\texttt{''implikaiton''} har operatorn $\rightarrow$. Om vi har ett uttryck $p$ och
 
271
ett uttryck $q$ så kan man skriva $ p \rightarrow q $ som betyder ''om $p$ så $q$''.
 
272
En sanningstabell över $p \rightarrow q$ kan ses i \linebreak  tabell \ref{tab:rarrow}.
 
273
 
 
274
\begin{table}[H]
 
275
  \caption{Sanningstabell för  $p \rightarrow q$}
 
276
  \label{tab:rarrow}
 
277
  \begin{center}
 
278
    \begin{tabular}{|c c||c|}
 
279
      \hline
 
280
       $p$ & $q$ & $p \rightarrow q$ \\
 
281
      \hline
 
282
       $F$ & $F$ & $S$ \\
 
283
      \hline
 
284
       $S$ & $F$ & $F$ \\
 
285
      \hline
 
286
       $F$ & $S$ & $S$ \\
 
287
      \hline
 
288
       $S$ & $S$ & $S$ \\
 
289
      \hline
 
290
    \end{tabular}
 
291
  \end{center}
 
292
\end{table}
 
293
 
 
294
Uttrycket $ p \rightarrow q $ är falsk om $p$ är sant och $q$ är falsk, sant i övriga fall.
 
295
Andra sätt att skriva $p \rightarrow q$ är som ''$p$ är tillräcklighet för $q$'',
 
296
''$q$ när $p$'' och ''$q$ är nödvändigt för $p$''.
 
297
 
 
298
Notera att $p \rightarrow q$ är logiskt ekvivalent till $\neg(p \wedge \neg q)$, eller
 
299
$ p \rightarrow q \equiv \neg (p \wedge \neg q) $.
 
300
 
 
301
Ett sätt att se på hur $\rightarrow$ kan användas är ''\textbf{om} Nora vinner två miljoner \textbf{så}
 
302
skall hon köpa en hålkortsläsare till Pelle'', detta uttryck håller om Nora inte vinner två miljoner
 
303
och inte köper en hålkortsläsare till pelle, om Nora köper en hålkortsläsare till Pelle men inte har
 
304
vunnit två miljoner, samt om Nora vinner två miljoner och köper en hålkortsläsare till Pelle. Uttrycket
 
305
håller inte om och endast inte om Nora vinner två miljoner men inte köper en hålkortsläsare till Pelle.
 
306
 
 
307
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
308
\subsection{''omm'' Operatorn }
 
309
\texttt{''omm''} betyder \textit{\texttt{om och endast om}} och har den formella notationen $ \leftrightarrow  $.
 
310
$ \leftrightarrow  $ kallas på engelska \texttt{iff} eller \texttt{bidirectional implication}
 
311
vilket kan ge en indikation över vad operatorn gör.
 
312
 
 
313
Notera att $ p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p) $.
 
314
En sanningstabell över $p \leftrightarrow q$ kan ses i tabell \ref{tab:lrarrow}.
 
315
 
 
316
\begin{table}[H]
 
317
  \caption{Sanningstabell för $ \leftrightarrow $}
 
318
  \label{tab:lrarrow}
 
319
  \begin{center}
 
320
    \begin{tabular}{|c c||c|}
 
321
      \hline
 
322
       $p$ & $q$ & $ p \leftrightarrow q $ \\
 
323
      \hline
 
324
       $F$ & $F$ & $F$ \\
 
325
      \hline
 
326
       $S$ & $F$ & $S$ \\
 
327
      \hline
 
328
       $F$ & $F$ & $S$ \\
 
329
      \hline
 
330
       $F$ & $F$ & $F$ \\
 
331
      \hline
 
332
    \end{tabular}
 
333
  \end{center}
 
334
\end{table}
 
335
 
 
336
Ett sätt att se på hur $\leftrightarrow$ fungerar är uttrycket
 
337
''solen går upp \textbf{om och endast om} jorden roterar kring sin axel'',
 
338
uttrycket är inte sant om något av deluttrycken är \texttt{falskt} men
 
339
håller i om båda är antingen \texttt{sant} eller \texttt{falskt}.
 
340
Alltså om jorden inte roterar och solen inte går upp samt om jorden
 
341
roterar och solen går upp så håller uttrycket, uttrycket håller inte
 
342
om solen går upp trotts att jorden inte roterar eller om jorden roterar
 
343
men solen inte går upp.
 
344
 
 
345
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
346
\subsection{Booleska Uttryck och Sanningstabeller} \label{subsec:statmentstruthtbl}
 
347
Boolesk algebra är viktig att förstå och hur den relaterar till sannings uttryck.
 
348
Ovan sågs exempel på boolesk algebra där vi relaterade den till uttrycks sanningsvärde.
 
349
 
 
350
I formel \ref{eq:complex} kan ses ett exempel på ett booleskt uttryck. 
 
351
 
 
352
\begin{framed}
 
353
\begin{equation} \label{eq:complex}
 
354
 (p \vee q) \oplus (p \wedge q)
 
355
\end{equation}
 
356
\end{framed}
 
357
 
 
358
Tabellen \ref{tab:complex} är en sanningstabellen för uttrycket \ref{eq:complex}. Uttrycket har bara två
 
359
del{-}uttryck $p$ och $q$, men uttryck kan vara mycket mer komplexa med många fler deluttryck. 
 
360
 
 
361
\begin{table}[H]
 
362
  \caption{Sanningstabell för $(p \vee q) \oplus (p \wedge q)$}
 
363
  \label{tab:complex}
 
364
  \begin{center}
 
365
    \begin{tabular}{|c c|| c | c || c ||c|}
 
366
      \hline
 
367
       $p$ & $q$ & $ p \vee q $ & $ p \wedge q $ & $ \neg(p \wedge q) $ & $(p \vee q) \oplus \neg (p \wedge q)$ \\
 
368
      \hline
 
369
       $F$ & $F$ & $ F $ & $ F $ & $ S $ & $ S $ \\
 
370
      \hline
 
371
       $S$ & $F$ & $ S $ & $ F $ & $ S $ & $ F $ \\
 
372
      \hline
 
373
       $F$ & $S$ & $ S $ & $ F $ & $ S $ & $ F $ \\
 
374
      \hline
 
375
       $S$ & $S$ & $ S $ & $ S $ & $ F $ & $ S $ \\
 
376
      \hline
 
377
    \end{tabular}
 
378
  \end{center}
 
379
\end{table}
 
380
 
 
381
Vi ser att $ (p \vee q) \oplus \neg (p \wedge q) \equiv  \neg (p \oplus q) $ (ekvivalent).
 
382
 
 
383
 
 
384
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
385
\subsection{Kontradiktion och Tautologi}
 
386
Programmerare kommer i kontakt med koncepten  \textit{tautologi} och \textit{kontradiktion}, \linebreak
 
387
detta för att det kan förekomma tautologiska och kontradiktoriska uttryck i kod som
 
388
kan orsaka felaktigt beteende i mjukvara.
 
389
Det är därför viktigt att ni har en förståelse för vad en tautologi och en
 
390
kontradiktion är.
 
391
 
 
392
En tautologi är trycket som är sant oberoende på vad deluttrycken
 
393
har för sanningsvärde. Ett exemplet på en tautologi är $A \vee \neg A$
 
394
($A$ eller inte $A$), detta uttryck är alltid sant oberoende på vad
 
395
$A$ har för sanningsvärde.
 
396
 
 
397
En kontradiktion är ett uttryck som är sant oberoende på vad
 
398
deluttrycken har för sanningsvärde. Ett exempel på ett sanningsvärde
 
399
är $A \wedge \neg A$ ($A$ och inte $A$), detta uttryck är falskt oberoende
 
400
på vad $A$ har för sanningsvärde.
 
401
 
 
402
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
403
\subsection{Relation Mellan Uttryck}
 
404
När vi talar om logik så är det viktigt att förstå relationerna mellan uttryck.
 
405
En typ av relation mellan uttryck kan ses i undersektion \ref{subsec:equiv}.
 
406
 
 
407
En annan relation mellan uttryck är de som vi har sett ovan, så som $p \rightarrow q$
 
408
($p$ medför $q$).
 
409
 
 
410
%TODO
 
411
 
 
412
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
413
\subsection{Ekvivalenser}\label{subsec:equiv}
 
414
\begin{table}[H]
 
415
  \caption{De logiska ekvivalenserna}
 
416
  \label{tab:logequiv}
 
417
  \begin{center}
 
418
    \begin{tabular}{|l|c|}
 
419
      \hline
 
420
      $ p \wedge S \equiv p $ & Identitetslagrna \\
 
421
      $ p \vee F \equiv p $ & \\
 
422
      \hline
 
423
      $ p \vee S \equiv S $ & Domänlagarna \\
 
424
      $ p \wedge F \equiv F $ & \\
 
425
      \hline
 
426
      $ p \vee p \equiv p $ & Idempotentlagarna \\
 
427
      $ p \wedge p \equiv p $ & \\
 
428
      \hline
 
429
      $ \neg (\neg p) \equiv p $ & Dubbelnegationslagen \\
 
430
      \hline
 
431
      $ p \vee q \equiv q \vee p $ & Kommutativitetslagarna \\
 
432
      $ p \wedge q \equiv q \wedge p $ & \\
 
433
      \hline
 
434
      $ ( p \vee q ) \vee r \equiv p \vee ( q \vee r ) $ & Associationslagarna \\
 
435
      $ ( p \wedge q ) \wedge r \equiv p \wedge ( q \wedge r ) $ & \\
 
436
      \hline
 
437
      $ p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r) $ & Distributivalagarna \\
 
438
      $ p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)  $ & \\
 
439
      \hline
 
440
      $ \neg (p \wedge q) \equiv \neg p \vee \neg q $ & De Morgans lagar \\
 
441
      $ \neg (p \vee q) \equiv \neg p \wedge \neg q $ & \\
 
442
      \hline
 
443
      $ p \vee (p \wedge q) \equiv p $ & Absorptionslagarna \\
 
444
      $ p \wedge (p \vee q) \equiv p $ & \\
 
445
      \hline
 
446
      $ p \vee \neg p \equiv S $ & Negationslagarna  \\
 
447
      $ p \wedge \neg p \equiv F $ & \\
 
448
      \hline
 
449
    \end{tabular}
 
450
  \end{center}
 
451
\end{table}
 
452
 
 
453
\begin{table}[H]
 
454
  \caption{Ekvivalenserna för implikation}
 
455
  \label{tab:qviimpl}
 
456
  \begin{center}
 
457
    \begin{tabular}{| l |}
 
458
        \hline
 
459
       $ p \rightarrow q \equiv \neg p \vee q $ \\
 
460
        \hline
 
461
       $ p \rightarrow q \equiv \neg q \rightarrow \neg p $ \\ 
 
462
        \hline
 
463
       $ p \vee q \equiv  \neg p \rightarrow q  $  \\
 
464
       \hline
 
465
       $ p \wedge q \equiv \neg (p \rightarrow \neg q) $ \\
 
466
       \hline
 
467
       $ \neg ( p \rightarrow q) \equiv q \vee q $ \\
 
468
       \hline
 
469
       $ ( p \rightarrow q ) \wedge ( p \rightarrow r ) \equiv p \rightarrow ( p \wedge r ) $ \\
 
470
       \hline
 
471
       $ ( p \rightarrow r ) \wedge ( q \rightarrow r ) \equiv (p \vee q)  \rightarrow  r  $ \\
 
472
       \hline
 
473
       $ ( p \rightarrow p ) \vee ( p \rightarrow r ) \equiv p  \rightarrow  (q \vee r) $ \\
 
474
       \hline
 
475
       $ ( p \rightarrow r ) \vee ( q \rightarrow r ) \equiv (p \wedge q) \rightarrow  r $  \\
 
476
       \hline
 
477
    \end{tabular}
 
478
  \end{center}
 
479
\end{table}
 
480
 
 
481
\begin{table}[H]
 
482
  \caption{Ekvivalenserna för omm}
 
483
  \label{tab:qviiff}
 
484
  \begin{center}
 
485
    \begin{tabular}{| l |}
 
486
      \hline
 
487
      $ p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p) $ \\
 
488
      \hline
 
489
      $ p \leftrightarrow q \equiv \neg q \leftrightarrow \neg p $ \\
 
490
      \hline
 
491
      $ p \leftrightarrow q \equiv (p \wedge q) \vee (\neg q \wedge \neg p) $ \\
 
492
      \hline
 
493
      $ \neg (p \leftrightarrow q) \equiv p \leftrightarrow \neg q $ \\
 
494
      \hline
 
495
    \end{tabular}
 
496
  \end{center}
 
497
\end{table}
 
498
 
 
499
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
500
\newpage\subsection{Övningar}
 
501
Dessa övningar skall göras individuellt och \textbf{för hand}
 
502
med papper och penna.
 
503
Det är \textbf{inte} viktigt att eleven skriver eller ritar snyggt, dock
 
504
skall det vara läsbart och tydligt.
 
505
 
 
506
När eleven ritar tabellerna kan de använda en linjal för att det skall bli
 
507
snyggt och tydligt.
 
508
 
 
509
Eleven \textbf{skall inte} rita, skriva eller fylla i något på detta dokument, de
 
510
skall använda lösa papper.
 
511
 
 
512
\paragraph{Övning 1}
 
513
Fylli $\Box$ i uttrycket $ (p \vee q) \Box \neg r $ så att $r$ negerar deluttrycket $(p \vee q)$.
 
514
 
 
515
\paragraph{Övning 2}
 
516
Rita en sanningstabell för uttrycket $\neg (p \vee q) \wedge (p \oplus r)$.
 
517
 
 
518
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
519
\newpage \subsection{Svar}
 
520
\paragraph{övning 1}
 
521
$ (p \vee q) \wedge \neg r $.
 
522
 
 
523
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
524
%%%%%%%%%%%%%%%%% Från Logik till Kod %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
525
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
526
\newpage
 
527
\section{Pseudokod, Kontrollstrukturer och Koppling till\\Logik}
 
528
När vi skriver kod så kan det vara nödvändigt att den kod vi skriver kan
 
529
kan göra något val under några omständigheter. En sådan omständighet
 
530
är ''om variabel \texttt{i} är mindre än \texttt{20} så utför \texttt{x} annars utför \texttt{y}'', detta
 
531
mönster är mycket vanligt. Detta kallas för \textit{kontrollstrukturer} och
 
532
styr \textit{programflödet}, alltså vad programmet gör, om det så är att
 
533
läsa av styrspakarna på din Game Box Station handkontroll och få din karaktär
 
534
på skärmen utföra något, eller att få en lampa att blinka i ett visst mönster.
 
535
 
 
536
I denna sektion kommer vi att gå genom den formella notationen för pseudokod,
 
537
denna notation är viktig att förstå för den hjälper oss att resonera
 
538
kring programflöden och algoritmer på ett språkoberoende sätt.
 
539
 
 
540
Här kommer vi att använda en variant av pseudokod som används av \LaTeX {}
 
541
paketet \texttt{algorithmicx}, ett exempel på detta kan ses i algoritm \ref{alg:exp1}.
 
542
Koden kommer att använda engelsk notering, men det går även att använda svenska ord i de som ni skriver.
 
543
 
 
544
\begin{algorithm}[H]
 
545
\caption{Ett exempel på pseudokod.}
 
546
\label{alg:exp1}
 
547
\begin{algorithmic}[1]
 
548
\If {$i\geq maxval$}
 
549
  \State $i\gets 0$
 
550
\Else
 
551
  \If {$i+k\leq maxval$}
 
552
    \State $i\gets i+k$
 
553
  \EndIf
 
554
\EndIf
 
555
\end{algorithmic}
 
556
\end{algorithm}
 
557
 
 
558
Algoritm \ref{alg:exp2} är ett exempel på hur algoritm \ref{alg:exp1} kan se ut på svenska.
 
559
 
 
560
\begin{algorithm}[H]
 
561
\caption{Hur algoritm \ref{alg:exp1} kan se ut på svenska.}
 
562
\label{alg:exp2}
 
563
\begin{algorithmic}[1]
 
564
\Om {$i\geq maxval$}
 
565
  \State $i\gets 0$
 
566
\Annars
 
567
  \Om {$i+k\leq maxval$}
 
568
    \State $i\gets i+k$
 
569
  \SlutOm
 
570
\SlutOm
 
571
\end{algorithmic}
 
572
\end{algorithm}
 
573
 
 
574
\subsection{\texttt{om} $p$ \texttt{så} $x$ \texttt{annars} $y$ }
 
575
\label{sec:if}
 
576
Inom programmering så är \texttt{om} satsen den mest basala kontrollstrukturen.
 
577
Den -- tillsammans med \texttt{hopp} -- kan användas istället
 
578
för alla andra kontrollstrukturer.
 
579
 
 
580
\texttt{hopp} operationen används för att hoppa mellan olika ställen i koden. Denna
 
581
operation anses generellt vara omodern, och finns inte i många språk.
 
582
 
 
583
I algoritm \ref{alg:exp1} och \ref{alg:exp2} (som är ekvivalenta) så såg vi
 
584
några exempel på hur \texttt{om} kontrollstrukturen kan användas. Vi kommer
 
585
nu att gå genom hur man tar sig från ett logiskt uttryck till kontrollstrukturer.
 
586
 
 
587
\bigskip\noindent
 
588
Säg att vi har uttrycket ''Om och endast om Nora köper en häst så skall Pelle få rida den''.
 
589
Detta uttrycks logiskt som: $n \Leftrightarrow p$ där $n$ är ''Nora köper en häst'' och
 
590
$p$ är ''Pelle får rida på Noras häst'. Detta skulle uttryckas i kod som det som visas i
 
591
algoritm \ref{alg:haest}.
 
592
 
 
593
\begin{algorithm}[H]
 
594
\caption{Får Pelle rida?}
 
595
\label{alg:haest}
 
596
\begin{algorithmic}[1]
 
597
\Om{Nora köper en häst}
 
598
  \State Pelle får rida på Noras häst
 
599
\SlutOm
 
600
\end{algorithmic}
 
601
\end{algorithm}
 
602
 
 
603
Ett annat exempel kan vara ''Om Pelle har mer eller lika med tjugo euro så skall han
 
604
bjuda Nora på en pizza annars får Nora en hamburgare'', detta uttrycks logiskt
 
605
i ekvation \ref{eq:pizza} och uttrycks i pseudokod i algoritm \ref{alg:pizza}.
 
606
 
 
607
\begin{framed}
 
608
\begin{align}\label{eq:pizza}
 
609
  \text{Nora får}
 
610
  \begin{cases}
 
611
    \text{Pizza} & p \leq 20\\
 
612
    \text{hamburgare} & \text{annars}
 
613
  \end{cases}
 
614
\end{align}
 
615
\begin{center} där $p$ är hur många euro Pelle har \end{center}
 
616
\end{framed}
 
617
 
 
618
\begin{algorithm}[H]
 
619
\caption{Får Nora hamburgare eller pizza?}
 
620
\label{alg:pizza}
 
621
\begin{algorithmic}[1]
 
622
\Om{$ p \geq 20 $} \Comment{Pelle har mer än 20 euro}
 
623
  \State Nora får Pizza
 
624
\Annars \Comment{Pelle har inte mer än 20 euro}
 
625
  \State Nora får Hamburger
 
626
\SlutOm
 
627
\end{algorithmic}
 
628
\end{algorithm}
 
629
 
 
630
\bigskip\noindent
 
631
Låt oss nu ta ett mer abstrakt exempel som är mer lik det som vi kan komma att
 
632
se i riktig kod. I ekvation \ref{eq:theechoice} och uttrycks i kod i algoritm
 
633
\ref{alg:threechoice}.
 
634
 
 
635
\begin{framed}
 
636
\begin{align}\label{eq:theechoice}
 
637
  x
 
638
  \begin{cases}
 
639
    1 & i \leq  1\\
 
640
    2 & 1 < i \leq 20\\
 
641
    3 & 20 < i \leq 50\\
 
642
    4 & \text{annars}
 
643
  \end{cases}
 
644
\end{align}
 
645
\begin{center} Där $i \in \mathbb{Z} $.\\ \bigskip
 
646
Sätt $x$ till något värde beronde på vad $i$ har för värde.\end{center}
 
647
\end{framed}
 
648
 
 
649
\begin{algorithm}[H]
 
650
\caption{Sett $x$ till något värde beroende på vad $i$ har för värde}
 
651
\label{alg:threechoice}
 
652
\begin{algorithmic}[1]
 
653
\Require{$i \in \mathbb{Z} $ }
 
654
\If{$ i \leq 1 $} 
 
655
  \State $ x \gets 1 $
 
656
\ElsIf{$ 1 < i \leq 20 $}
 
657
  \State $ x \gets 2$
 
658
\ElsIf{$20 < i \leq 50$}
 
659
  \State $ x \gets 3$
 
660
\Else
 
661
  \State $ x \gets 4$
 
662
\EndIf
 
663
\end{algorithmic}
 
664
\end{algorithm}
 
665
 
 
666
Notera att man kan skriva kontrollstrukturen på ett logiskt ekvivalet
 
667
sätt som syns i algoritm \ref{alg:threechoicealt}. Att skriva på detta
 
668
sätt är lite mer arbete och är inte väldigt snyggt. Dock kan det
 
669
förekomma i äldre kod och i vissa språk som inte har \texttt{annars om}.
 
670
 
 
671
\begin{algorithm}[H]
 
672
\caption{Ett alternativt sätt att skirva samma kod som i algoritm \ref{alg:threechoice}}
 
673
\label{alg:threechoicealt}
 
674
\begin{algorithmic}[1]
 
675
\Require{$i \in \mathbb{Z} $ }
 
676
\If{$ i \leq 1 $} 
 
677
  \State $ x \gets 1 $
 
678
\Else
 
679
  \If{$ 1 < i \leq 20 $}
 
680
    \State $ x \gets 2$
 
681
  \Else
 
682
    \If{$20 < i \leq 50$}
 
683
      \State $ x \gets 3$
 
684
    \Else
 
685
      \State $ x \gets 4$
 
686
    \EndIf
 
687
  \EndIf
 
688
\EndIf
 
689
\end{algorithmic}
 
690
\end{algorithm}
 
691
 
 
692
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
693
\subsection{\texttt{medans} $p$ \texttt{utför} $x$}
 
694
\label{sec:while}
 
695
\texttt{medans} kontrollstationen utför det som finns innan för
 
696
den medans dess krav är uppfyllda. Ett enkelt exempel på detta
 
697
kan återfinnas i algoritm \ref{alg:while}.
 
698
 
 
699
\begin{algorithm}[H]
 
700
\caption{Medans $p$ är uppfyllt utför $i \gets i + 1$}
 
701
\label{alg:while}
 
702
\begin{algorithmic}[1]
 
703
\State let $i \gets 0$
 
704
\Medans{$i \leq 20$}
 
705
  \State $i \gets i + 1$
 
706
\SlutMedans
 
707
\end{algorithmic}
 
708
\end{algorithm}
 
709
 
 
710
Som ni kanske kommer ihåg från undersektion \ref{sec:if} så nändes
 
711
att alla kontroll strukturer kan återskapas med bara \texttt{om} kontrollstrukturen och
 
712
\texttt{hopp} operatorn, Detta demonstreras i algoritm \ref{alg:jumpwhile} och en alternativ
 
713
skrivning kan ses i \ref{alg:jumpwhileagain}.
 
714
 
 
715
\begin{algorithm}[H]
 
716
\caption{Samma som i algoritm \ref{alg:while}, fast med hopp}
 
717
\label{alg:jumpwhile}
 
718
\begin{algorithmic}[1]
 
719
\State låt $i \gets 0$
 
720
\\Loop: \label{line:jumpwhile:jumplbl} \Comment{Detta är ett märke eller en markör. Vi kan hoppa till den.}
 
721
\Om{$i \leq 20$}
 
722
  \State $i \gets i + 1$
 
723
\Annars
 
724
  \State \textbf{hopp} Loop \Comment{Hoppa till markören ovan på rad \ref{line:jumpwhile:jumplbl}}
 
725
\SlutOm
 
726
\end{algorithmic}
 
727
\end{algorithm}
 
728
 
 
729
Den alternative skrivningen av algoritm \ref{alg:jumpwhile} som ses i algoritm \ref{alg:jumpwhileagain}
 
730
är så som det kan utföras i datorer. Att använda \texttt{hopp} -- om det inte är maskinkod eller
 
731
om du vet exakt vad du gör -- anses vara en osed och bör därmed undviks, använd istället de
 
732
inbyggda kontrollstationerna som tillhandahålls av det programmeringsspråk som ni använder.
 
733
 
 
734
\begin{algorithm}[H]
 
735
\caption{Alternativ skrivning av \ref{alg:jumpwhile}.}
 
736
\label{alg:jumpwhileagain}
 
737
\begin{algorithmic}[1]
 
738
\State let $i \gets 0$
 
739
\\Loop:
 
740
\If{$i > 20$}
 
741
  \State \textbf{jump} JumpOut
 
742
\EndIf
 
743
\State $i \gets i + 1$
 
744
\State \textbf{jump} Loop
 
745
\\JumpOut: 
 
746
\end{algorithmic}
 
747
\end{algorithm}
 
748
 
 
749
\subsection{upprepa $x$ tills $p$ -- utför $x$ medans $p$}
 
750
\texttt{upprepa $x$ tills $p$} och \texttt{utför $x$ medans $p$} är
 
751
kan se väldigt lika ut men har olika betydelse. Om vi skulle
 
752
ta exemplet från undersektion \ref{sec:while} så kan det se ut som
 
753
exemplena i algoritm \ref{alg:dowhile} och \ref{alg:repeatuntill}.
 
754
 
 
755
\begin{algorithm}[H]
 
756
\caption{Alternativ skrivning av \ref{alg:while}.}
 
757
\label{alg:dowhile}
 
758
\begin{algorithmic}[1]
 
759
\State let $i \gets 0$
 
760
\Utfoer
 
761
  \State $i \gets i + 1$
 
762
\UtfoerMedans{$i \leq 20$}
 
763
\end{algorithmic}
 
764
\end{algorithm}
 
765
 
 
766
\begin{algorithm}[H]
 
767
\caption{Alternativ skrivning av \ref{alg:while}.}
 
768
\label{alg:repeatuntill}
 
769
\begin{algorithmic}[1]
 
770
\State let $i \gets 0$
 
771
\Upprepa
 
772
  \State $i \gets i + 1$
 
773
\Tills{$i < 20$}
 
774
\end{algorithmic}
 
775
\end{algorithm}
 
776
 
 
777
\subsection{\texttt{för} $i$ tills $j$ \texttt{utför} $y$}
 
778
Säg att vi vill summera alla positiva heltal från och med $0$ till och med
 
779
$200$. Detta skulle matematiskt uttryckas som i ekvation \ref{eq:sumzerototwohundrad}.
 
780
 
 
781
\begin{framed}
 
782
\begin{align}\label{eq:sumzerototwohundrad}
 
783
  r = \sum\limits_{i=0}^{200} = 1 + 2 + 3 + ... + 198 + 199 + 200
 
784
\end{align}
 
785
\end{framed}
 
786
 
 
787
 
 
788
 
 
789
\end{document}