\documentclass[a4paper,11pt]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{dejavu} \usepackage[swedish]{babel} \usepackage{fullpage} \usepackage{hyperref} \usepackage{amsmath} \usepackage{amssymb} \usepackage{enumitem} \usepackage{algorithm} \usepackage{algpseudocode} \usepackage{algorithmicx} \usepackage{framed} \usepackage{mathtools} \usepackage{adjustbox} \selectlanguage{swedish} \include{swealgo} % babel-paket eller motsvarande %%%%%%%%%%%%%%%%%%%%%% FIX HREF \usepackage{xcolor} \definecolor{dark-red}{rgb}{0.4,0.15,0.15} \definecolor{dark-blue}{rgb}{0.15,0.15,0.4} \definecolor{medium-blue}{rgb}{0,0,0.5} \definecolor{dark-green}{rgb}{0,0.5,0} \hypersetup{ colorlinks, linkcolor={dark-red}, citecolor={dark-green}, urlcolor={dark-blue}, pdftitle={Logik och det Booleska}, % title pdfauthor={Gustav Hartvigsson}, % author pdfsubject={Computer Science}, pdfkeywords={Logic} {Logik} {Dator Vetenskap} {Computer Science}\ {Svenska} {Swedish} {Boole} {Boolean} {Boolesk}\ {Pseudo code} {Pseudokod} {Algorithm} {Algoritm} } %%%%%%%%%%%%%%%%%%%%%% END FIX HREF %%%% FIX DESCRIPTIONS % From: http://tex.stackexchange.com/a/33341 % Variant B with superior spacing -- thanks to Peter Grill \SetLabelAlign{parright}{\parbox[t]{\labelwidth}{\raggedleft#1}} \setlist[description]{style=multiline,topsep=10pt,leftmargin=2cm,% align=parright} %%%% END FIX DESCRIPTIONS %%%% FIX SWEDISH CAPTIONS ON ALGORITHMS % http://tex.stackexchange.com/a/169119 \makeatletter \renewcommand*{\ALG@name}{Algoritm} \makeatother %%%% \title{\Huge Logik och det Booleska\\ \Large Introduktion till Booleska Uttryck och Kontrollstrukturer för Blivande Programmerare} \author{Gustav Hartvigsson \\ \\Strömstad Gymnasium} \begin{document} \maketitle \begin{abstract} I detta dokument skall eleven lära sig den formella notationen för de booleska operatorer. Dokumentet går igenom operatorerna från en enkel nivå genom ekvationer och sanningstabeller. Eleven skall få en överblick över de operatorer som är mest relevanta för programmering: \texttt{och}, \texttt{eller}, \texttt{exklusiv eller}, \texttt{negering}, \texttt{implikation} och \texttt{omm}. Eleven presenteras därefter för övningar som \textit{bör} utföras som testar elevens förståelse för booleska operatorer, booleska uttryck och sanningstabeller. \bigskip I andra halvan av detta dokument skall eleven lära sig hur kontrollstrukturer ser ut, fungerar och någon form av pseudokod. Eleven skall lära sig hur det går att skriva och använder pseudokod och varför det är av fördel att använda den. \bigskip Målet med detta dokument är inte att vara ett substitut till de traditionella läromedlen, utan att vara ett komplement. Det är inte tänkt att eleven skall lära sig detta utantill -- det är inte en del av kursmålen -- utan att exponera eleven för hur det går att tänka i relation till booleska operatorer och logiska uttryck som förekommer inom programmering. Samt lära sig att läsa, skriva och resonera kring kod genom användningen av pseudokod. \end{abstract} \newpage \noindent Detta dokument finns tillgängligt under en \textbf{Creative Commons 3.0} licens, av typen \textbf{Creative Commons Erkännande} (CC-BY 3.0). Gå till \url{http://creativecommons.org/licenses/by/3.0/} för att se vad detta innebär. \bigskip\noindent Detta dokument finns att få tagpå på \url{https://launchpad.net/bok-logik} i form av \texttt{.tex} och \texttt{.pdf}. Förändringar och förbättringar är alltid välkomna. \vspace*{\fill} \noindent \Large Tack till:\\ \normalsize Teresia Lind (korrekturläsning),\\ Vincent Longo (förtydliganden),\\ Tobias Genberg (moraliskt stöd och idébollplank) \newpage \tableofcontents \newpage \section{Booleska Operatorer, Uttryck och Logik} Ordet boolesk (\textit{boolean} på engelska) kommer av den brittiske matematikern George Boole som introducerade konceptet i sina böcker \textit{The Mathematical Analysis of Logic (1847)} och \textit{An Investigation of the Laws of Thought (1854)}. Ordet lär ha myntats av Henry M. Sheffer enligt Edward Vermilye Huntington. Logik hjälper oss att förstå och resonera kring påståenden som ''Det finns ett heltal som inte är summan av kvadratroten ur två heltal''. %Att ringa ett samtal, lyssna på digital musik eller att surfa på nätet är alla %avhängiga den digitala tekniken vilken i sin tur är grundad i logiken. I logiken så används oftast $p, q, r, ...$ för att representera något påstående med ett visst sanningsvärde, ett sådant uttryck kan vara ''Pelle har en dator'', ''klockan är sexton fyrtiofem'' eller ''mitt hus är mindre än det där huset''. \bigskip\noindent I detta dokument användes -- generellt -- notationen $S$ för att representera ett \texttt{sant} sanningsvärde för ett uttryck och $F$ för ett \texttt{falskt} sanningsvärde för ett uttryck. \bigskip\noindent Den notationen som Boole använde i sina böcker var {\large $1$} för ett \texttt{sant} sanningsvärde och {\large $0$} för ett \texttt{falskt} sanningsvärde. Denna notation används inte här dels för att det skall vara lättare att läsa och för att skilja detta från digitala signaler, trots att de inte är så stor skillnad. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{''och'' Operatorn} \texttt{''och''} operatorn har den formella matematiska notationen $\wedge$. Denna operatorn kallas formellt för konjunktion. Om vi har sanningsuttrycken $p$ och $q$ och så kan vi skriva ett uttryck $ p \wedge q $ och sanningstabellen för detta uttryck kan ses i tabell \ref{tab:wedge}. \begin{table}[H] \caption{Sanningstabell för $p \wedge q$} \label{tab:wedge} \begin{center} \begin{tabular}{|c c||c|} \hline $p$ & $q$ & $p \wedge q$ \\ \hline $F$ & $F$ & $F$ \\ \hline $S$ & $F$ & $F$ \\ \hline $F$ & $S$ & $F$ \\ \hline $S$ & $S$ & $S$ \\ \hline \end{tabular} \end{center} \end{table} Ett sätt att se på hur $\wedge$ fungerar är att ta meningen ''Pelle \textbf{och} Nora håller om varandra'', detta uttryck håller endast om både Pelle och Nora håller om varandra. Om Pelle håller om Nora, men Nora inte håller om Pelle, och tvärt om, så håller inte det uttrycket som vi utgick ifrån. Ett annat exempel är ''klockan är fyra \textbf{och} solen går upp''. Om klockan inte är fyra eller om solen inte går upp så håller inte uttrycket, och är därmed \texttt{falkt}. Påståendena här är ''klockan är fyra'' och ''solen går upp''. \subsection{''eller'' Operatorn} \texttt{''eller''} operatorn har den formella notationen $\vee$ och har de formella namnen \textit{disjunktion} eller \textit{inklusive disjunktion}. Om vi har uttrycket $p \vee q$ där $p$ och $q$ är något logiskt uttryck som kan vara \texttt{sant} eller \texttt{falskt} så får vi sanningstabellen som kan ses i tabell \ref{tab:vee}. \begin{table}[H] \caption{Sanningstabell för $p \vee q$} \label{tab:vee} \begin{center} \begin{tabular}{|c c||c|} \hline $p$ & $q$ & $p \vee q$ \\ \hline $F$ & $F$ & $F$ \\ \hline $S$ & $F$ & $S$ \\ \hline $F$ & $S$ & $S$ \\ \hline $S$ & $S$ & $S$ \\ \hline \end{tabular} \end{center} \end{table} Ett sätt att se på hur $\vee$ fungerar är att ta uttrycket ''Pelle har en dator \textbf{eller} \newline Noras klocka visar fjorton femton'', detta uttryck består av två delar, båda delarna -- eller påståenden -- kan ha sanningsvärdena \texttt{sant} eller \texttt{falskt}, och de utesluter inte varandra när det gäller hela uttryckets sanningsvärde. Alltså om Pelle har en dator och Noras klocka visar fjorton femton så håller uttrycket, samma gäller om bara ett av dessa påståenden är \texttt{sant}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{''exklusivt eller'' Operatorn} Den matematiska notationen för \texttt{''exklusivt eller''} är $\oplus$ och har det formella namnet \textit{exklusiv disjunktion}. En sanningstabell över uttrycket $p \oplus q$ kan ses i tabell \ref{tab:oplus}. \begin{table}[H] \caption{Sanningstabell för $p \oplus q$} \label{tab:oplus} \begin{center} \begin{tabular}{|c c||c|} \hline $p$ & $q$ & $p \oplus q$ \\ \hline $F$ & $F$ & $F$ \\ \hline $S$ & $F$ & $S$ \\ \hline $F$ & $S$ & $S$ \\ \hline $S$ & $S$ & $F$ \\ \hline \end{tabular} \end{center} \end{table} Ett sätt att se på detta kan vara att använda uttrycket ''Pelle \textbf{eller} Nora använder datorterminalen'', detta utesluter varandra ty både Nora och Pelle kan inte använda samma datorterminal samtidigt. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection {''negering'' Operatorn} Negering är viktigt att förstå, det använd ofta tillsammans med deluttryck. Den matematiska notationen för negering är $\neg$. En sanningstabell över uttrycket $\neg p$ kan ses i tabell \ref{tab:neg}. \begin{table}[H] \caption{Sanningstabell för $\neg p$} \label{tab:neg} \begin{center} \begin{tabular}{|c||c|} \hline $p$ & $\neg p$ \\ \hline $F$ & $S$ \\ \hline $S$ & $F$ \\ \hline \end{tabular} \end{center} \end{table} Ett exempel på hur det går att använda $\neg$ är uttrycket $ p \wedge \neg q $, alltså $p$ och inte $q$. Ett exempel på detta kan vara meningen ''Nora hoppar bungyjump \textbf{och} Pelle kollar \textbf{inte} på sin mobiltelefon'', uttrycket håller inte om Nora inte hoppar bungyjump eller om Pelle kollar på sin mobiltelefon. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{''implikation'' Operatorn} \texttt{''implikaiton''} har operatorn $\rightarrow$. Om vi har ett uttryck $p$ och ett uttryck $q$ så kan det skrivas $ p \rightarrow q $ som betyder ''om $p$ så $q$''. En sanningstabell över $p \rightarrow q$ kan ses i \linebreak tabell \ref{tab:rarrow}. I $p \rightarrow q$ så kallas $p$ för \textit{hypotesen} och $q$ för \textit{slutsatsen} eller \textit{konsekvensen}. \begin{table}[H] \caption{Sanningstabell för $p \rightarrow q$} \label{tab:rarrow} \begin{center} \begin{tabular}{|c c||c|} \hline $p$ & $q$ & $p \rightarrow q$ \\ \hline $F$ & $F$ & $S$ \\ \hline $S$ & $F$ & $F$ \\ \hline $F$ & $S$ & $S$ \\ \hline $S$ & $S$ & $S$ \\ \hline \end{tabular} \end{center} \end{table} Uttrycket $ p \rightarrow q $ är falsk om $p$ är sant och $q$ är falsk, sant i övriga fall. Andra sätt att skriva $p \rightarrow q$ är som ''$p$ är tillräcklighet för $q$'', ''$q$ när $p$'' och ''$q$ är nödvändigt för $p$''. Notera att $p \rightarrow q$ är logiskt ekvivalent till $\neg(p \wedge \neg q)$, eller $ p \rightarrow q \equiv \neg (p \wedge \neg q) $. Ett sätt att se på hur $\rightarrow$ kan användas är ''\textbf{om} Nora vinner två miljoner \textbf{så} skall hon köpa en hålkortsläsare till Pelle'', detta uttryck håller om Nora inte vinner två miljoner och inte köper en hålkortsläsare till pelle, om Nora köper en hålkortsläsare till Pelle men inte har vunnit två miljoner, samt om Nora vinner två miljoner och köper en hålkortsläsare till Pelle. Uttrycket håller inte om och endast inte om Nora vinner två miljoner men inte köper en hålkortsläsare till Pelle. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{''omm'' Operatorn } \texttt{''omm''} betyder \textit{om och endast om} och har den formella notationen $ \leftrightarrow $. $ \leftrightarrow $ kallas på engelska \textit{iff} (\textit{if and only if}) eller \textit{bidirectional implication} vilket kan ge en indikation över vad operatorn gör. Notera att $ p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p) \equiv \neg (p \oplus q) $. En sanningstabell över $p \leftrightarrow q$ kan ses i tabell \ref{tab:lrarrow}. \begin{table}[H] \caption{Sanningstabell för $ \leftrightarrow $} \label{tab:lrarrow} \begin{center} \begin{tabular}{|c c||c|} \hline $p$ & $q$ & $ p \leftrightarrow q $ \\ \hline $F$ & $F$ & $S$ \\ \hline $S$ & $F$ & $F$ \\ \hline $F$ & $S$ & $F$ \\ \hline $S$ & $S$ & $S$ \\ \hline \end{tabular} \end{center} \end{table} Ett sätt att se på hur $\leftrightarrow$ fungerar är uttrycket ''solen går upp \textbf{om och endast om} jorden roterar kring sin axel'', uttrycket är inte \texttt{sant} om något av påståendena är \texttt{falskt} men håller i om båda är antingen \texttt{sant} eller \texttt{falskt}. Alltså om jorden inte roterar och solen inte går upp samt om jorden roterar och solen går upp så håller uttrycket, uttrycket håller inte om solen går upp trots att jorden inte roterar eller om jorden roterar men solen inte går upp. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Booleska Uttryck och Sanningstabeller} \label{subsec:statmentstruthtbl} Boolesk algebra är viktig att förstå och hur den relaterar till sanningsuttryck. Ovan sågs exempel på boolesk algebra där vi relaterade den till uttrycks sanningsvärde. I formel \ref{eq:complex} kan ses ett exempel på ett booleskt uttryck. \begin{equation} \label{eq:complex} (p \vee q) \oplus \neg (p \wedge q) \end{equation} Tabellen \ref{tab:complex} är en sanningstabellen för uttrycket \ref{eq:complex}. Uttrycket har bara två påståenden $p$ och $q$, dock kan uttryck vara mycket mer komplexa med många fler påståenden. \begin{table}[H] \caption{Sanningstabell för $(p \vee q) \oplus \neg (p \wedge q)$} \label{tab:complex} \begin{center} \begin{tabular}{|c c|| c | c || c ||c|} \hline $p$ & $q$ & $ p \vee q $ & $ p \wedge q $ & $ \neg(p \wedge q) $ & $(p \vee q) \oplus \neg (p \wedge q)$ \\ \hline $F$ & $F$ & $ F $ & $ F $ & $ S $ & $ S $ \\ \hline $S$ & $F$ & $ S $ & $ F $ & $ S $ & $ F $ \\ \hline $F$ & $S$ & $ S $ & $ F $ & $ S $ & $ F $ \\ \hline $S$ & $S$ & $ S $ & $ S $ & $ F $ & $ S $ \\ \hline \end{tabular} \end{center} \end{table} Vi ser att $ (p \vee q) \oplus \neg (p \wedge q) \equiv \neg (p \oplus q) $ (ekvivalent). \bigskip\noindent När vi ritar sanningstabeller för komplexa uttryck kan det vara till hjälp att kunna några grundläggande knep. \begin{itemize} \item Det finns \(2^n\) \textit{rader} i sanningstabellen där \(n\) är antalet påståenden ($p,q,r,...$). Alltså finns det två påståenden så skall det vara fyra rader, finns det fem påståenden skall det finnas 32 rader. \item Operator ordningen $\neg \wedge \vee \rightarrow \leftrightarrow$. \item Dela upp de minsta deluttrycken i var sin kolumn kombinera dem i i följande kolumner tills hela uttrycket finns att avläsa i sista kolumnen. \item Räkna binärt när påståendena fylls i. Alltså, har vi tre påståenden $p,q,r$ så fylls första raden i med $F,F,F$, andra raden med $S,F,F$ tredje raden med $F,S,F$ fjärde raden $S,S,F$ hela vägen till $S,S,S$. \end{itemize} Ett exempel är $(p \vee \neg q) \oplus (r \wedge q)$. Detta uttryck har tre påståenden ($p$,$q$ och $r$), detta medför att sanningstabellen skall ha sex rader. Det minsta deluttrycket är $\neg q$ och kommer i den första kolumnen efter påståendena, det näst minsta deluttrycken är $(p \vee \neg q)$ och $(r \wedge q)$ och följer på detta, och avslutas med en kolumn hela uttrycket. \begin{table}[H] \caption{Exempel tabell} \label{tab:exampelone} \begin{center} \begin{tabular}{|c c c||c||c|c||c|} \hline \multicolumn{3}{|c||}{Påståenden} & \multicolumn{3}{|c||}{Deluttryck} & Hela uttrycket. \\ \hline\hline $p$ & $q$ & $r$ & $\neg q$ & $(p \vee \neg q)$ & $(r \wedge q)$ & $(p \vee \neg q) \oplus (r \wedge q)$ \\ \hline ... & ... & ... & ... & ... & ... & ... \\ \hline ... & ... & ... & ... & ... & ... & ... \\ \end{tabular} \end{center} \end{table} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Kontradiktion och Tautologi} Programmerare kommer i kontakt med koncepten \textit{tautologi} och \textit{kontradiktion}, \linebreak detta för att det kan förekomma tautologiska och kontradiktoriska uttryck i kod som kan orsaka felaktigt beteende i mjukvara. Det är därför viktigt att ha en förståelse för vad en tautologi och en kontradiktion är. En tautologi är ett uttryck som är \texttt{sant} oavsett vad påståendena har för sanningsvärde. Ett exemplet på en tautologi är $A \vee \neg A$ ($A$ eller inte $A$), detta uttryck är alltid \texttt{sant} oberoende av vad $A$ har för sanningsvärde. En kontradiktion är ett uttryck som är \texttt{falskt} oberoende på vad påståendena har för sanningsvärde. Ett exempel är $A \wedge \neg A$ ($A$ och inte $A$), detta uttryck är \texttt{falskt} oberoende av vad $A$ har för sanningsvärde. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \subsection{Relation Mellan Uttryck} % När vi talar om logik så är det viktigt att förstå relationerna mellan uttryck. % En typ av relation mellan uttryck kan ses i undersektion \ref{subsec:equiv}. % % En annan relation mellan uttryck är de som vi har sett ovan, så som $p \rightarrow q$ % ($p$ medför $q$). % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Kvantifikatorer} Ibland så behöver vi kunna resonera kring existensen av något i en viss domän med en viss egenskap eller om ett påstående gäller för alla värden i en viss domän. I logiken så kan vi göra detta med hjälp av \textit{kvantorer} eller \textit{kvantifikatorer}. Det finns två primära sådana som vi använder inom logiken, \textit{allkvantifikatorn} \( \forall \) och \textit{existenskvantifikatorn} \( \exists \). Ni kommer här att introduceras till konceptet av kvantifikatorer, dock så kommer vi inte all lägga något krut på detta, det finns mycket som vi skulle kunna gå genom när det gäller regler för detta, dock är det utanför ramarna för detta dokument. Säg att vi har påståendet ''Det finns en fågel med blå fjädrar'', då kan man resonera kring detta med hjälp av \(\exists x P(x) \) där \(P(x)\) är ''\(x\) har blå fjädrar'' och \(x\) är en fågel i domänen av fåglar. Detta påståendet är sant om det finns minst en fågel med blå fjädrar. Om vi har påståendet ''alla böcker i biblioteket har en blank sida'' så kan vi skriva \( \forall x P(x) \) där \(P(x)\) är påståendet ''\(x\) har en tom sida'' och \(x\) är en bok i domänen böcker i biblioteket. Detta påstående är sant om och endast om det gäller för \textbf{all} böcker i biblioteket. \bigskip \noindent Kvantifikatorer kan bara användas på något i en viss domän eller i en mängd. Läs mer om detta om ni är intresserade i Matematik 5 eller Diskret Matematik. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Ekvivalenser}\label{subsec:equiv} \begin{table}[H] \caption{De logiska ekvivalenserna} \label{tab:logequiv} \begin{center} \begin{tabular}{|l|c|} \hline $ p \wedge S \equiv p $ & Identitetslagrna \\ $ p \vee F \equiv p $ & \\ \hline $ p \vee S \equiv S $ & Domänlagarna \\ $ p \wedge F \equiv F $ & \\ \hline $ p \vee p \equiv p $ & Idempotentlagarna \\ $ p \wedge p \equiv p $ & \\ \hline $ \neg (\neg p) \equiv p $ & Dubbelnegationslagen \\ \hline $ p \vee q \equiv q \vee p $ & Kommutativitetslagarna \\ $ p \wedge q \equiv q \wedge p $ & \\ \hline $ ( p \vee q ) \vee r \equiv p \vee ( q \vee r ) $ & Associationslagarna \\ $ ( p \wedge q ) \wedge r \equiv p \wedge ( q \wedge r ) $ & \\ \hline $ p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r) $ & Distributivalagarna \\ $ p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r) $ & \\ \hline $ \neg (p \wedge q) \equiv \neg p \vee \neg q $ & De Morgans lagar \\ $ \neg (p \vee q) \equiv \neg p \wedge \neg q $ & \\ \hline $ p \vee (p \wedge q) \equiv p $ & Absorptionslagarna \\ $ p \wedge (p \vee q) \equiv p $ & \\ \hline $ p \vee \neg p \equiv S $ & Negationslagarna \\ $ p \wedge \neg p \equiv F $ & \\ \hline \end{tabular} \end{center} \end{table} \begin{table}[H] \caption{Ekvivalenserna för implikation} \label{tab:qviimpl} \begin{center} \begin{tabular}{| l |} \hline $ p \rightarrow q \equiv \neg p \vee q $ \\ \hline $ p \rightarrow q \equiv \neg q \rightarrow \neg p $ \\ \hline $ p \vee q \equiv \neg p \rightarrow q $ \\ \hline $ p \wedge q \equiv \neg (p \rightarrow \neg q) $ \\ \hline $ \neg ( p \rightarrow q) \equiv q \vee q $ \\ \hline $ ( p \rightarrow q ) \wedge ( p \rightarrow r ) \equiv p \rightarrow ( p \wedge r ) $ \\ \hline $ ( p \rightarrow r ) \wedge ( q \rightarrow r ) \equiv (p \vee q) \rightarrow r $ \\ \hline $ ( p \rightarrow p ) \vee ( p \rightarrow r ) \equiv p \rightarrow (q \vee r) $ \\ \hline $ ( p \rightarrow r ) \vee ( q \rightarrow r ) \equiv (p \wedge q) \rightarrow r $ \\ \hline \end{tabular} \end{center} \end{table} \begin{table}[H] \caption{Ekvivalenserna för omm} \label{tab:qviiff} \begin{center} \begin{tabular}{| l |} \hline $ p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p) $ \\ \hline $ p \leftrightarrow q \equiv \neg q \leftrightarrow \neg p $ \\ \hline $ p \leftrightarrow q \equiv (p \wedge q) \vee (\neg q \wedge \neg p) $ \\ \hline $ \neg (p \leftrightarrow q) \equiv p \leftrightarrow \neg q $ \\ \hline \end{tabular} \end{center} \end{table} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newpage\subsection{Övningar} Dessa övningar skall göras individuellt och \textbf{för hand} med papper och penna. Det är \textbf{inte} viktigt att eleven skriver eller ritar snyggt, dock skall det vara läsbart och tydligt. När eleven ritar tabellerna kan de använda en linjal för att det skall bli snyggt och tydligt. Eleven \textbf{skall inte} rita, skriva eller fylla i något på detta dokument, de skall använda lösa papper. \paragraph{Övning 1} Vad skall stå istället för $\Box$ i uttrycket $ (p \vee q) \Box \neg r $ så att $r$ negerar deluttrycket $(p \vee q)$. \paragraph{Övning 2} Rita en sanningstabell för uttrycket $\neg (p \vee q) \wedge (p \oplus r)$. \paragraph{Övning 3} Bevisa att $ ( p \rightarrow q ) \wedge ( p \rightarrow r ) \equiv p \rightarrow ( p \wedge r ) $. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%% Från Logik till Kod %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newpage \section{Pseudokod, Kontrollstrukturer och Koppling till\\Logik} När vi skriver kod så kan det vara nödvändigt att den kod vi skriver kan kan göra något val under några omständigheter. En sådan omständighet är ''om variabel $i$ är mindre än $20$ så utför $x$ annars utför $y$'', detta mönster är mycket vanligt. Detta kallas för \textit{kontrollstrukturer} och styr \textit{programflödet}, alltså vad programmet gör, om det så är att läsa av styrspakarna på din Game Box Station handkontroll och få din karaktär på skärmen utföra något, eller att få en lampa att blinka i ett visst mönster. I denna sektion kommer vi att gå genom en vanlig notationen för pseudokod, denna notation är viktig att förstå för den hjälper oss att resonera kring programflöden och algoritmer på ett språkoberoende sätt. Här kommer vi att använda en variant av pseudokod som används av \LaTeX {} paketet \texttt{algorithmicx}, ett exempel på detta kan ses i algoritm \ref{alg:exp1}. Koden kommer att använda engelsk notering, men det går även att använda svenska ord i de som ni skriver. \begin{algorithm}[H] \caption{Ett exempel på pseudokod.} \label{alg:exp1} \begin{algorithmic}[1] \If {$i\geq maxval$} \State $i\gets 0$ \Else \If {$i+k\leq maxval$} \State $i\gets i+k$ \EndIf \EndIf \end{algorithmic} \end{algorithm} Algoritm \ref{alg:exp2} är ett exempel på hur algoritm \ref{alg:exp1} kan se ut på svenska. \begin{algorithm}[H] \caption{Hur algoritm \ref{alg:exp1} kan se ut på svenska.} \label{alg:exp2} \begin{algorithmic}[1] \Om {$i\geq maxval$} \State $i\gets 0$ \Annars \Om {$i+k\leq maxval$} \State $i\gets i+k$ \SlutOm \SlutOm \end{algorithmic} \end{algorithm} Pseudokod är har inte någon formell notation, dock så förekommer det vissa vanliga element: \begin{itemize} \item Börja ett kodblock med ett nyckelord och eventuella krav. \item Avsluta kodblock med ett \texttt{slut} eller \texttt{end} följt av namnet på nyckelordet som användes för att starta kod stycket. \item All pseudokod \textit{skall} vara indenterad så att det som är innanför kodblocket är lätt att urskilja från det utanför. Undantag finns. \item Skriv vad som skall häda, inte hur det skall utföras. \end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{\texttt{om} $p$ \texttt{så} $x$ \texttt{annars} $y$ } \label{sec:if} Inom programmering så är \texttt{om} satsen den mest basala kontrollstrukturen. Den -- tillsammans med \texttt{hopp} -- kan användas istället för alla andra kontrollstrukturer. \texttt{hopp} operationen används för att hoppa mellan olika ställen i koden. Denna operation anses generellt vara omodern, och finns inte i många språk. I algoritm \ref{alg:exp1} och \ref{alg:exp2} (som är ekvivalenta) så såg vi några exempel på hur \texttt{om} kontrollstrukturen kan användas. Vi kommer nu att gå genom hur det går att ta sig från ett logiskt uttryck till kontrollstrukturer. \bigskip\noindent Säg att vi har uttrycket ''Om och endast om Nora köper en häst så skall Pelle få rida den''. Detta uttrycks logiskt som: $n \Leftrightarrow p$ där $n$ är ''Nora köper en häst'' och $p$ är ''Pelle får rida på Noras häst'. Detta skulle uttryckas i kod som det som visas i algoritm \ref{alg:haest}. \begin{algorithm}[H] \caption{Får Pelle rida?} \label{alg:haest} \begin{algorithmic}[1] \Om{Nora köper en häst} \State Pelle får rida på Noras häst \SlutOm \end{algorithmic} \end{algorithm} Ett annat exempel kan vara ''Om Pelle har mer eller lika med tjugo euro så skall han bjuda Nora på en pizza annars får Nora en hamburgare'', detta uttrycks logiskt i ekvation \ref{eq:pizza} och uttrycks i pseudokod i algoritm \ref{alg:pizza}. \begin{align}\label{eq:pizza} \text{Nora får} \begin{cases} \text{Pizza} & p \leq 20\\ \text{hamburgare} & \text{annars} \end{cases} \end{align} \begin{center} Där $p$ är hur många euro Pelle har \end{center} \begin{algorithm}[H] \caption{Får Nora hamburgare eller pizza?} \label{alg:pizza} \begin{algorithmic}[1] \Om{$ p \geq 20 $} \Comment{Pelle har mer än 20 euro} \State Nora får Pizza \Annars \Comment{Pelle har inte mer än 20 euro} \State Nora får Hamburger \SlutOm \end{algorithmic} \end{algorithm} \bigskip\noindent Låt oss nu ta ett mer abstrakt exempel som är mer lik det som vi kan komma att se i riktig kod. I ekvation \ref{eq:theechoice} och uttrycks i kod i algoritm \ref{alg:threechoice}. \begin{minipage}{\textwidth} \begin{align}\label{eq:theechoice} x = \begin{cases} 1 & i \leq 1\\ 2 & 1 < i \leq 20\\ 3 & 20 < i \leq 50\\ 4 & \text{annars} \end{cases} \end{align} \begin{center} Där $i \in \mathbb{Z} $. \end{center} \end{minipage} \begin{algorithm}[H] \caption{Sett $x$ till något värde beroende på vad $i$ har för värde} \label{alg:threechoice} \begin{algorithmic}[1] \Require{$i \in \mathbb{Z} $ } \If{$ i \leq 1 $} \State $ x \gets 1 $ \ElsIf{$ 1 < i \leq 20 $} \State $ x \gets 2$ \ElsIf{$20 < i \leq 50$} \State $ x \gets 3$ \Else \State $ x \gets 4$ \EndIf \end{algorithmic} \end{algorithm} Notera att det går att skriva kontrollstrukturen på ett logiskt ekvivalet sätt som syns i algoritm \ref{alg:threechoicealt}. Att skriva på detta sätt är lite mer arbete och är inte väldigt snyggt. Dock kan det förekomma i äldre kod och i vissa språk som inte har \texttt{annars om}. \begin{algorithm}[H] \caption{Ett alternativt sätt att skirva samma kod som i algoritm \ref{alg:threechoice}} \label{alg:threechoicealt} \begin{algorithmic}[1] \Require{$i \in \mathbb{Z} $ } \If{$ i \leq 1 $} \State $ x \gets 1 $ \Else \If{$ 1 < i \leq 20 $} \State $ x \gets 2$ \Else \If{$20 < i \leq 50$} \State $ x \gets 3$ \Else \State $ x \gets 4$ \EndIf \EndIf \EndIf \end{algorithmic} \end{algorithm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{\texttt{medans} $p$ \texttt{utför} $x$} \label{sec:while} \texttt{medans} kontrollstationen utför det som finns innan för den medans dess krav är uppfyllda. Ett enkelt exempel på detta kan återfinnas i algoritm \ref{alg:while}. \begin{algorithm}[H] \caption{Medans $p$ är uppfyllt utför $i \gets i + 1$} \label{alg:while} \begin{algorithmic}[1] \State let $i \gets 0$ \Medans{$i \leq 20$} \State $i \gets i + 1$ \SlutMedans \end{algorithmic} \end{algorithm} Som ni kanske kommer ihåg från undersektion \ref{sec:if} så nändes att alla kontroll strukturer kan återskapas med bara \texttt{om} kontrollstrukturen och \texttt{hopp} operatorn, Detta demonstreras i algoritm \ref{alg:jumpwhile} och en alternativ skrivning kan ses i \ref{alg:jumpwhileagain}. \begin{algorithm}[H] \caption{Samma som i algoritm \ref{alg:while}, fast med hopp} \label{alg:jumpwhile} \begin{algorithmic}[1] \State låt $i \gets 0$ \\Loop: \label{line:jumpwhile:jumplbl} \Comment{Detta är ett märke eller en markör. Vi kan hoppa till den.} \Om{$i \leq 20$} \State $i \gets i + 1$ \Annars \State \textbf{hopp} Loop \Comment{Hoppa till markören ovan på rad \ref{line:jumpwhile:jumplbl}} \SlutOm \end{algorithmic} \end{algorithm} Den alternative skrivningen av algoritm \ref{alg:jumpwhile} som ses i algoritm \ref{alg:jumpwhileagain} är så som det kan utföras i datorer. Att använda \texttt{hopp} -- om det inte är maskinkod eller om du vet exakt vad du gör -- anses vara en osed och bör därmed undviks, använd istället de inbyggda kontrollstationerna som tillhandahålls av det programmeringsspråk som ni använder. \begin{algorithm}[H] \caption{Alternativ skrivning av \ref{alg:jumpwhile}.} \label{alg:jumpwhileagain} \begin{algorithmic}[1] \State let $i \gets 0$ \\Loop: \If{$i > 20$} \State \textbf{goto} JumpOut \EndIf \State $i \gets i + 1$ \State \textbf{goto} Loop \\JumpOut: \end{algorithmic} \end{algorithm} \subsection{upprepa $x$ tills $p$ -- utför $x$ medans $p$} \texttt{upprepa $x$ tills $p$} och \texttt{utför $x$ medans $p$} är kan se väldigt lika ut men har olika betydelse. Om vi skulle ta exemplet från undersektion \ref{sec:while} så kan det se ut som exemplena i algoritm \ref{alg:dowhile} och \ref{alg:repeatuntill}. \begin{algorithm}[H] \caption{Alternativ skrivning av \ref{alg:while}.} \label{alg:dowhile} \begin{algorithmic}[1] \State let $i \gets 0$ \Utfoer \State $i \gets i + 1$ \UtfoerMedans{$i \leq 20$} \end{algorithmic} \end{algorithm} \begin{algorithm}[H] \caption{Alternativ skrivning av \ref{alg:while}.} \label{alg:repeatuntill} \begin{algorithmic}[1] \State let $i \gets 0$ \Upprepa \State $i \gets i + 1$ \Tills{$i > 20$} \end{algorithmic} \end{algorithm} I algoritm \ref{alg:dowhile} så utförs allt inuti kodblocket om och endast om uttrycket i \texttt{medans} är uppfyllt, när uttrycket inte längre uppfylls så hoppar programmet ur kodblocket. Denna struktur är vanlig inom programmeringen. I algoritm \ref{alg:repeatuntill} så upprepas allt inuti kodblocket tills uttrycket i \texttt{tills} är uppfyllt. Detta uttryck är inte vanlig i programmeringsspråk, utan används nästan bara inom pseudokod och algoritmbeskrivningar. \subsection{för $i$ tills $j$ utför $x$} Säg att vi vill summera alla positiva heltal från och med $0$ till och med $200$. Detta skulle matematiskt uttryckas som i ekvation \ref{eq:sumzerototwohundrad}. \begin{align}\label{eq:sumzerototwohundrad} r = \sum\limits_{i=0}^{200} = 1 + 2 + 3 + ... + 198 + 199 + 200 \end{align} Detta kan uttryckat som i algoritm \ref{alg:fora} eller \ref{alg:forb} \begin{algorithm}[H] \caption{Addera ihop alla heltal mellan och inklusive $0$ och $200$} \label{alg:fora} \begin{algorithmic}[1] \State låt $r \gets 0$ %\Foer{$\overbrace{i \gets 0}^{\text{Värde}}; \overbrace{0 \leq i \leq 200}^{\text{Begränsare}}; \overbrace{i \gets i + 1}^{\text{iteration}}$} \Foer{$i \in \mathbb{Z}^{+}, i \leq 200; i \gets i + 1$} \State $r \gets r + i$ \SlutFoer \State Skriv ut $r$ \end{algorithmic} \end{algorithm} \begin{algorithm}[H] \caption{Alternativ skrivning av algoritm \ref{alg:fora}} \label{alg:forb} \begin{algorithmic}[1] \State let $r \gets 0$ %\For{$\overbrace{i :}^{\text{value}} \overbrace{\text{ between and including } 0 \text{ and } 200}^{\text{iteration and limitor}}$} \For{$i$ between and including $0$ and $200$ } \State $r \gets r + i$ \EndFor \State print $r$ \end{algorithmic} \end{algorithm} Här är det viktigt att förstå att det inte finns någon formel notation för pseudokod, dock så brukar den följa samma mönster som vi har använt här. I algoritm \ref{alg:fora} så uttrycks \texttt{för} på ett sätt som är mer likt det som vi återfinner i vissa programmeringsspråk. Algoritm \ref{alg:forb} är mer som när vi resonerar kring kod. Båda dessa är ekvivalenta, trots att de ser olika ut. Om vi ser på algoritm \ref{alg:fora} så ser vi att är det inte stor skillnad på en \texttt{för} och en \texttt{medans}. \subsection{för alla $a$ i $S$ utför $x$} När vi arbetar med \texttt{fält} (engelska \texttt{array}s) och \texttt{mängd}er (engelska \texttt{set}s) kan det vara viktigt att kunna utföra operationer på varje element i \texttt{fält}et eller \texttt{mängd}en. Säg att vi har en \texttt{mängd} med namn som vi vill skriva ut, hur skulle detta gå till? Hur det går till i riktig kod är inte viktigt när vi skriver pseudokod, vad som är viktigt är vad pseudokoden representerar. Ett exempel på det går att skriva pseudokod för att skriva ut alla namnen kan ses i algoritm \ref{alg:foralla}. \begin{algorithm}[H] \caption{Skriv ut alla namn i mängden $Namn$} \label{alg:foralla} \begin{algorithmic}[1] \Krav $Namn$ är en mängd med namn \FoerAlla{$n$ \textbf{i} $Namn$} \State Skriv ut $n$ \SlutFoerAlla \end{algorithmic} \end{algorithm} Ett annat sätt att skriva detta är med hjälp av $\in$ (element, är ett element av) operatorn, som i algoritm \ref{alg:forallb}. \begin{algorithm}[H] \caption{Alternativ skrivning av algoritm \ref{alg:foralla}} \label{alg:forallb} \begin{algorithmic}[1] \Require $Names$ is a set of names \ForAll{$n \in Names$} \State Print $n$ \EndFor \end{algorithmic} \end{algorithm} \subsection{Procedurer och Funktioner} \texttt{procedur}er och \texttt{funktion}er är så gott som ekvivalenta uttryck, dock så kan det sägas att en \texttt{procedur} -- i allmänhet -- inte returnerar något. Dessa strukturer är -- för att förklara det på ett enkelt sätt -- kodststycken som kan åkallas från andra ställen i koden. I datorer händer detta genom hopp och undanstoppade av värden på den så kallade \texttt{stack}en -- dock är detta utanför ramen för det här dokumentet. Vi kan börja med ett enkelt exempel. I algoritm \ref{alg:fact} så räknar vi ut fakulteten av ett $20$. \begin{center} \begin{align}\label{eq:fact} n! = fact(n) = \begin{cases} 1 & n \leq 1 \\ fact(n - 1) \times n & x > 1 \end{cases} \end{align} Den (simplifierade) formella definitionen av fakultet \end{center} \begin{algorithm}[H] \caption{Räkna ut fakulteten av $20$} \label{alg:fact} \begin{algorithmic}[1] \Funktion{$fact$}{$n$}\Comment {Definiera funktionen} \Om{$n \leq 1$} \State \Returnera {$1$} \AnnarsOm {$n > 1$} \State \Returnera {\Call{$fact$}{$n-1$}$\times n$ } \Comment{Detta är en rekursiv funktion} \SlutOm \SlutFunktion \State Skriv ut \Call{$fact $}{$20$} \Comment{Programmet skriver ut $!20$} \end{algorithmic} \end{algorithm} Låt oss nu ta ett lite mer komplett exempel. Låt säga att vi vill ta ett \texttt{associativ fält} (\texttt{map} på engelska) som mappar personnummer till namn ($ SsnName $) och ett \texttt{associativ fält} som mappar personnummer till telefon nummer ($SsnTel$), och så vill vi skriva ut namn och telefonnummer på var och en av personerna. Detta kan ses i algoritm \ref{alg:nametotel}. \begin{algorithm}[H] \caption{Skriv ut en lista med namn och telefon nummer} \label{alg:nametotel} \begin{algorithmic}[1] \Require $SsnName:Map(ssn,name)$ is a map that maps an SSN to a name \Require $SsnTel:Map(ssn,tel)$ is a map that maps an SSN to a telephone number \Function{$ createNameToTel $}{$ A:Map(name,ssn), B:Map(ssn,tel) $} \State create $outSet:Set(Pair(name,tel))$ \ForAll{$pairA:Pair(ssn,name) \in A$} \State create $pairB:Pair(name,tel)$ \State $pairB.name \gets pairA.name$ and $pairB.tel \gets B[pairA.ssn]$ \State add $pairB$ to $outSet$ \EndFor \State \Return $outMap$ \EndFunction \State \Comment {Only an empty line...} \Function{$printPairOfSet$}{$M:Set(Pair(name,tel))$} \ForAll{$pair:Pair(name,tel) \in M $} \State Print ``$pair.name$ has the telephone number $pair.tel$'' \EndFor \EndFunction \State \State let $NameTel$\ $\gets$\ \Call{$createNameToTel$}{$NameSsn, SsnTel$} \State \Call{$printPairOfSet$}{$NameTel$} \end{algorithmic} \end{algorithm} Koden i algoritm \ref{alg:nametotel} är är skriven på ett väldigt mångordig (verbose) sätt, den skulle nog kunna göras lite mer fåordig. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Kodramar - Kodomfattning} I kod talar vi om ramar (engelska \texttt{scope}) som håller variabler och/eller objekt. Det finns två primära ramar som vi använder: \texttt{lokal} och \texttt{global}. Den \texttt{global}a ramen innehåller variabler och objekt som är åtkomliga från hela programmet. De \texttt{lokal}a kodramarna kan ses som lådor. En låda som kan går att se ut genom, men inte se in i. Ett exempel på en sådan låda är en funktion: De variabler som deklareras i denna kodram kan inte ses från andra funktioner. Ett annat exempel på en lokal kodram är en \texttt{om}-satts, om variabel \(i\) deklareras i en sådan kodram så är den inte åtkomlig från ramen utanför. Om vi skulle beskriva vad den lokala kodramen är mer exakt är som följande: Den lokala kodramen, likt den globala kodramen, innehåller variabler och objekt vars tillgång är begränsad till ett lokalt exekverings sammanhang (execution context), så som inuti en funktion eller en loop. Den lokala kodramen har tillgång till allt i den globala kodramen, men en funktion har inte tillgång till variabler i en annan funktion för dess sammanhang är utanför ramen. % The local code scope, like the global code scope, contains variables and objects whose % access is restricted to a local execution context, ie (within a function or loop). % The local code scope can access items in the global code scope but one function may % not access the variable of another function as that other functions context is % now out of scope. -- Vincent Longo \bigskip\noindent Det finns fler sätt att dela upp kod än detta, så som klasser, object, design mönster (design patterns), men det är utanför ramen för detta dokument. \bigskip\noindent Ett exempel på hur detta fungerar kan ses i algoritm \ref{alg:scopeone}. Något att ha i åtanke är att författaren använder ordet ''kodram'', detta ord är helt påhittat av författaren för han inte kunde hitta ett bättre ord på svenska. \begin{algorithm}[H] \caption{Exempel på hur kodramar fungerar.} \label{alg:scopeone} \begin{algorithmic}[1] \State låt \( my\_global\_var \gets 12 \) \Comment En global variabel \Funktion{\(funk1\)}{} \State låt \(funk\_1\_var \gets \text{''Någon sträng''}\) \State \texttt{/* Det är tillåtet att använda globala} \State \texttt{ \ \ variabler i en funktion */} \State Skriv ut \( my\_global\_var\) \State \State \texttt{/* Det är tillåtet att använda vaiabler som } \State \texttt{ \ \ deklareras i denna kodram här */} \State Skriv ut \(funk\_1\_var\) \Om{\(foo\)} \State låt \(lokal\_var \gets 1337\) \Comment Deklarerad innuti om-satsen. \State \(my\_global\_var \gets lokal\_var \) \Comment OK! \SlutOm \State \(lokal\_var \gets 2\) \Comment Går inte att använda \(lokal\_var\) utanför kodramen. \SlutFunktion \State \Funktion{\(funk2\)}{} \State Skriv ut \( my\_global\_var\) \Comment Helt OK \State \State \texttt{/* Det går inte att använda denna variablen här, } \State \texttt{ \ \ den är deklarerad i en annan kodram */} \State Skriv ut \(funk\_1\_var\) \SlutFunktion \end{algorithmic} \end{algorithm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newpage\subsection{Övningar} Dessa övningar skall göras individuellt \textbf{eller} i grupp och \textbf{för hand} med papper och penna, \textbf{eller} på vita tavlan. Det är \textbf{inte} viktigt att eleven skriver eller ritar snyggt, dock skall det vara läsbart och tydligt. Eleven \textbf{skall inte} rita, skriva eller fylla i något på detta dokument, de skall använda lösa papper. \paragraph{Övning 1} Skriv en algoritm som adderar alla tal i en mängden \(N\) och skriv ut summan i slutet. \paragraph{Övning 2} Skriv en algoritm som adderar alla jämna tal i mängden \(M\) och skriv ut summan i slutet. \paragraph{Övning 3} Skriv en algoritm som skriver ut \begin{verbatim} - -- --- ---- ----- ------ \end{verbatim} Algoritmen skall använda en loop an något slag. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newpage \section{Svar} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Logik} \paragraph{Övning 1} $ (p \vee q) \wedge \neg r $. \paragraph{Övning 2} -- \begin{table}[H] \begin{center} \begin{tabular}{| c c c || c | c || c || c |} \hline $p$ & $q$ & $r$ & $ (p \vee q) $ & $ (p \oplus r) $ & $ \neg (p \vee r) $ & $\neg (p \vee q) \wedge (p \oplus r)$ \\ \hline $F$ & $F$ & $F$ & $F$ & $F$ & $S$ & $F$ \\ \hline $S$ & $F$ & $F$ & $S$ & $F$ & $F$ & $F$ \\ \hline $F$ & $S$ & $F$ & $S$ & $S$ & $F$ & $F$ \\ \hline $S$ & $S$ & $F$ & $S$ & $F$ & $S$ & $F$ \\ \hline $F$ & $F$ & $S$ & $F$ & $S$ & $S$ & $S$ \\ \hline $S$ & $F$ & $S$ & $S$ & $S$ & $F$ & $F$ \\ \hline $F$ & $S$ & $S$ & $S$ & $F$ & $F$ & $F$ \\ \hline $S$ & $S$ & $S$ & $S$ & $F$ & $F$ & $F$ \\ \hline \end{tabular} \end{center} \end{table} \subsection{Pseudokod} \paragraph{Övning 1} - \begin{algorithm}[H] \caption{Addera alla tal i en mängd.} \begin{algorithmic}[1] \Krav \(N\) är en mängd med tal. \State låt \(tmp \gets 0\) \FoerAlla{\(i\) i mängden \(N\)} \Comment för alla \(i \in N\) \State \(temp \gets temp + i\) \SlutFoerAlla \end{algorithmic} \end{algorithm} \paragraph{Övning 2} - \begin{algorithm}[H] \caption{Addera alla jämna tal i en mängd.} \begin{algorithmic}[1] \Krav \(N\) är en mängd med tal. \State låt \(tmp \gets 0\) \FoerAlla{\(i\) i mängden \(N\)} \Comment för alla \(i \in N\) \Om{\(i\) är jämt} \Comment \(i \mod 2 = 0\) alt. \(i | 2\) \State \(temp \gets temp + i\) \SlutOm \SlutFoerAlla \end{algorithmic} \end{algorithm} \newpage \paragraph{Övning 3} Visa lärare eller handledare. Ett exempel kan vara. \begin{algorithm}[H] \caption{Skriv ut ett streck.} \begin{algorithmic}[1] \State Skapa en tom textsträng \(S\) \State \(i \gets 0\) \Utfoer \State lägg till ett ''-'' till strängen \(S\) \State skriv ut \(S\) \State \(i \gets i + 1\) \UtfoerMedans{\(i \leq 5\)} \end{algorithmic} \end{algorithm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newpage \section{''Ordlista''} Här följer en liten ''ordlista'' över vanliga begrepp. Se \url{http://www.datatermgruppen.se/ordlista.html} för fler ord som har med datorer att göra. \begin{table}[H] \caption{Engelska $\Rightarrow$ Svenska} \begin{center} \begin{tabular}{l|l} iff & omm \\ if and only if & om och endast om \\ subset & delmängd \\ superset & övermängd \\ map, associative array & associativt fält \\ array & fält \\ set & mängd \\ while & medans \\ do & utför, gör \\ for & för \\ scope & ram, kodram, ramar, kodramar\\ execution context & exekverings sammanhang \\ \end{tabular} \end{center} \end{table} \begin{table}[H] \caption{Symboler} \begin{center} \begin{tabular}{l|l} $\subset$ & Strikt delmängd. \\ $\subseteq$ & Delmängd eller lika. \\ $\supset$ & Strikt övermängd. \\ $\supseteq$ & Övermängd eller lika. \\ $\forall$ & För alla - Allkvantifikatorn. \\ $\exists$ & Existerar - Existenskvantifikatorn. \\ $\in$ & I, inuti. \\ $\ni$ & Som $\in$ fast åt andra hållet. \end{tabular} \end{center} \end{table} Det finns motsatser till vissa av dessa, så som $\nsubseteq, \nsupseteq, \nexists, \notin$ finns även. \begin{table}[H] \caption{Vanliga mängder} \begin{center} \begin{tabular}{l|p{8cm}} $\mathbb{R}$ & Alla reella tal. \\ $\mathbb{Z}$ & Alla heltal, \(\mathbb{Z} = \left\{..., -3, -2, -1, 0, 1, 2, 3, ...\right\}\). \\ $\mathbb{N}$ & Alla naturliga tal. \(\mathbb{N}= \left\{i \in \mathbb{Z}, i > 0 \right\}\) eller \(\mathbb{N}= \left\{i \in \mathbb{Z}, i \geq 0 \right\} \) \\ $\mathbb{Q}$ & Alla bråktal eller rationella tal, \(\mathbb{Q} = \left\{ ^p/_q\ |\ p \in \mathbb{Z}, q \in \mathbb{Z}, q \neq 0 \right\} \).\\ $\mathbb{C}$ & Komplexa tal. \end{tabular} \end{center} \end{table} \end{document}