CSI/2627 - Exercise Sheet Nr. 2

➡️ Date: 5-Nov-2026

$ % LAST UPDATE: 18-Apr-2024 \def\start{&&} \def\more{\\&&} \def\sse#1#2{{#1}\subseteq{#2}} \def\iso{\cong} \newenvironment{lcbr}{\left\{\begin{array}{l}}{\end{array}\right.} \def\ana#1{(\hskip -1ex[#1]\hskip -1ex )} \def\cata#1{(\hskip -1.1pt[\hskip 0.1pt #1 \hskip 0.1pt]\hskip -1.1pt)} \def\Seq#1{{#1}^{\star}} \def\fB{\fun B} \def\mcond#1#2#3{#1 \rightarrow #2\;,\;#3} \newenvironment{lcbr}{\left\{\begin{array}{l}}{\end{array}\right.} \def\bang{{!}} \def\Nat{\mathbb{N}} \def\N{\Nat} \def\atmost{\subseteq} \def\alt#1#2{[#1,#2]} \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\from{\leftarrow} \def\fun#1{\mathsf{#1}} \def\i#1{\mathit{i}_{#1}} \def\inT{\mathsf{in}} \def\outT{\mathsf{out}} \def\implied{\Leftarrow} \def\implies{\Rightarrow} \def\just#1#2{\\&#1& \mathopen{\{}~\mbox{#2}~\mathclose{\}}\\&&} \def\ker#1{\mathbf{ker}\ {#1}} \def\img#1{\mathbf{img}\ {#1}} \def\kons#1{\underline{#1}} \def\larrow#1#2#3{#3\ \xleftarrow{#2}\ #1} \def\ldiv{\mathbin{/}} \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\sep{\rule{15em}{0.3pt}} \def\shrunkby{\mathbin{\upharpoonright}} \def\syd#1#2{\frac{#1}{#2}} \def\to{\rightarrow} \def\trans#1{\overline{#1}} \def\scata#1{⦅\, #1 \,⦆} \def\sep{\rule{15em}{0.3pt}} %-------- \def\Varid#1{\mathbin{#1}} \def\ensuremath#1{#1} \def\Conid#1{\mathbin{#1}} $


Q2.1 - We want to specify the Tokyo subway system, where (see figure) there are several lines ($L$), represented by different colours, whose stops ($P$) are numbered sequentially, and where stations ($E$) may include stops from different lines $-\!-$ e.g. the $\mathsf{Otemachi}$ station, which has stops $\fbox{$\frac C {11}$}$, $\fbox{$\frac M {18}$}$, etc. $-\!-$ allowing passengers to change lines.

Knowing that each stop is always associated with exactly one station, the simplified model

was defined, associating each stop with its line, number, and station. For example, if $p$ is the stop $\fbox{$\frac M {18}$}$ in the figure, then we have

$\begin{array}{l}st\ p = Otemachi\\\mathit{ln}\ p = M\\nr\ p = 18\end{array}$.

Clearly, the numbering system for stops on the lines requires the following invariant:

If $n+1$ is the number of a stop on a given line, then there is another stop on the same line numbered $n$.

Which of the following formulations of this invariant would you choose?

\begin{eqnarray} && \frac{nr}{succ \cdot nr} \subseteq \frac{ln}{ln} \label{eq:181128a} \\&& \nonumber\\&& \frac{nr}{succ} \subseteq nr \cdot \frac{ln}{ln} \end{eqnarray}

where $succ\ n = n+1$ is the successor function on $\Nat$?

Convert each "magic square" into the equivalent logical expression and decide, providing justification.

$\Box$


Q2.2 - $\tiny\sf\fbox{Alloy for fun}$ The following request was submitted to ChatGPT:

I would like to have an Alloy model for this simple problem:

(a) a bicycle always has two wheels, the front and the rear wheel;

(b) these wheels can never be the same;

(c) no two bicycles have a wheel in common.

The response was the following Alloy model, which did not report any errors:

// Signature for a Wheel
sig Wheel {}

// Each Bicycle has exactly two wheels: one front and one rear
sig Bicycle {
  front: one Wheel,
  rear: one Wheel
} {
  // (b) The front and rear wheels are distinct
  front != rear
}

// (c) No two bicycles share a wheel
fact NoSharedWheels {
  all disj b1, b2: Bicycle |
    no (b1.front + b1.rear) & (b2.front + b2.rear)
}

// A small scope example
run {} for 3 Bicycle, 6 Wheel

Analyse the proposed Alloy model and rewrite it using the pointfree (and diagrammatic) notation studied in this course. Evaluate its quality: what is wrong with it? What would you have done differently? Justify your answer.


Q2.3 - The figure represents the syntactic structure of a sentence written in Portuguese:

What is its formal meaning? Write it in the form of a "magic square",

\begin{eqnarray} R\ \cdot S \subseteq P \cdot Q \end{eqnarray}

in which you may use only the relation $\larrow {Person} L {Person}$ (where $L$ stands for likes) and the constant function $\larrow {1} {\kons{Mary}} {Person}$.


Q2.4 - The figure represents an elementary blockchain consisting of five blocks. Each block has its own $hash$ and the hash of the previous block ($\def\Phash{\mathit{Phash}}\Phash$), if one exists.

Identify which relations are:


Q2.5 - Represent, using a diagram with the types $Block$ and $\def\Word{\mathit{Word}}\Word$, the relational model suggested by the diagram in the previous question, and add the following invariants:


Q2.6 - $\tiny\sf\fbox{Alloy for fun}$ Complete the Alloy model below and verify it on the Alloy for fun platform:

sig Block { 
  Next  : lone Block, 
  hash  : one Word, 
  Phash : lone Word 
}

sig Word {}

fact {
   .....
}

run { # Next = 4} for 5 Block, 5 Word