$ % 20-Mai-2025 \def\Nat{\mathbb{N}} \def\N{\Nat} \def\B{Bool} \def\Seq#1{{#1}^{\star}} \def\alt#1#2{[#1,#2]} \def\ana#1{(\hskip -1ex[#1]\hskip -1ex )} \def\atmost{\subseteq} \def\bang{{!}} \def\cata#1{(\hskip -1.1pt[\hskip 0.1pt #1 \hskip 0.1pt]\hskip -1.1pt)} \def\comp{\mathbin\cdot} \def\conj#1#2{\mathopen{\langle} #1, #2\mathclose{\rangle}} \def\conv#1{#1^\circ} \def\crflx#1{\Phi_{#1}} \def\dom#1{\delta {#1}} \def\fB{\fun B} \def\from{\leftarrow} \def\fun#1{\mathsf{#1}} \def\i#1{\mathit{i}_{#1}} \def\img#1{\mathbf{img}\ {#1}} \def\implied{\Leftarrow} \def\implies{\Rightarrow} \def\inT{\mathsf{in}} \def\iso{\cong} \def\just#1#2{\\& \mathopen{\{}~\mbox{#2}~\mathclose{\}}\\&&} \def\cjust#1#2{\just{#1}{ ..................................................................... }} \def\ker#1{\mathbf{ker}\ {#1}} \def\kons#1{\underline{#1}} \def\larrow#1#2#3{#3\ \xleftarrow{#2}\ #1} \def\ldiv{\mathbin{/}} \def\mcond#1#2#3{#1 \rightarrow #2\;,\;#3} \def\more{\\&&} \def\outT{\mathsf{out}} \def\p#1{\pi_{#1}} \def\plus{\mathbin{\dagger}} \def\rarrow#1#2#3{#1\ \xrightarrow{#2}\ #3} \def\rcb#1#2#3#4{\mathopen{\langle}#1 #2 : #3 : #4\mathclose{\rangle}} \def\rdiv{\mathbin{\setminus}} \def\scata#1{⦅\, #1 \,⦆} \def\sep{\rule{15em}{0.3pt}} \def\sep{\rule{15em}{0.3pt}} \def\shrunkby{\mathbin{\upharpoonright}} \def\sse#1#2{{#1}\subseteq{#2}} \def\start{&&} \def\syd#1#2{\frac{#1}{#2}} \def\to{\rightarrow} \def\trans#1{\overline{#1}} \newenvironment{lcbr}{\left\{\begin{array}{l}}{\end{array}\right.} %-------- \def\Varid#1{\mathbin{#1}} \def\ensuremath#1{#1} \def\Conid#1{\mathbin{#1}} $
Q1.1 - Consider the relation $\larrow {Ocean} R {Continent}$ pictured below,
where $y\ R\ x$ means:
The continent $y$ is bathed by the ocean $x$
NB: the acronyms abbreviate continents (e.g. $NA$ = North America, $AF$ = Africa, etc.)
Classify the relation $R$ as to whether it is: (a) entire; (b) reflexive; (c) surjective; (d) simple; (e) injective. Justify your answer.
$\Box$
Q1.2 - Characterize the relations in the diagram. Suggestion: Represent each relation by a matrix of $0$s and $1$s, as seen in class, and classify it according to the rules of thumb given there.
$\Box$
Q1.3 - A railway line is made of two parallel rails where, at a given distance from its origin, measured in metres ($\Nat$), junctions or signals may appear. Suppose the line is represented by two relations:
Why is the following property, \begin{eqnarray} J \subseteq \top \comp S \comp (\leq) \end{eqnarray} desirable? Interpret it, i.e. state its meaning (e.g. pointwise).
How would you represent it in a "magic square"?
$\Box$
Q1.4 Assume that, in a file system ($\def\FS{\mathit{FS}}\FS$), each file ($\def\File{\mathit{File}}\File$) is accessed by a single $Path$. The "magic square" below
Every file belongs to a directory, which is a special file of type $Dir$.
It is easy to see that the empty file system, $\FS = \bot$, satisfies this invariant. But what can be said of a system with just one file, e.g. $\FS = \kons k \comp \conv{\kons p}$, where $k$ is the file descriptor and $p$ its path?
Replace $\FS$ by $\kons k \comp \conv{\kons p}$ in the square above, simplify and draw conclusions.
$\Box$
Q1.5 - Suppose that, based on the relations
A most important invariant of this model is the one guaranteeing that no process runs on memory cells belonging to other processes. To specify it, the relation \begin{eqnarray} \def\Owns{\mathit{Owns}} \Owns : \JobId \leftarrow Location \end{eqnarray} was defined, which indicates the "ownership" (or lack thereof) of an address $a$ by a process $k$:
\begin{eqnarray} k\ \Owns\ a\ &=& \langle \exists\ x\ :\ x\ S\ k\ :\ start\ x\ \leq\ a\ \leq start\ x + size\ x \rangle \end{eqnarray}What property (or properties) would you impose on the relation $\Owns$ to guarantee the desired invariant? Justify your answer appropriately.
$\Box$