2
$\begingroup$

Translated as best I could the problem is stated as follows:

Over the set $A=\{\alpha,\beta,\gamma,\delta,\epsilon,\eta\}$ a model $\mathbb{A}$ of language $\mathcal{L}=\{q\}$ ($ar(q)=2$) is defined with the following graph ($q^A$ is represented with the arrows)

graph

Find the formula $F_a$ for each $a\in A$ such that $F_a(x)$ defines $a$.


I have only a rough understanding of formal languages, and would appreciate a detailed solution to this problem.

$\endgroup$
1
$\begingroup$

As this sounds like a textbook or homework exercise, a detailed solution would be out of place, but here is a hint:

Write $x \mathrel{q} y$ to mean $q$ relates $x$ to $y$ in the model $\Bbb{A}$ in your diagram (so, for example, $\varepsilon \mathrel{q} \alpha$ holds but $\alpha \mathrel{q} \varepsilon$ does not). Now use quantifiers to express a defining characteristic of each node in the diagram: e.g., $\gamma$ is the only node $x$ such that $y \mathrel{q} x$ never holds, $\beta$ is the only node $x$ such that $x \mathrel{q} x$, etc.

$\endgroup$
  • $\begingroup$ Thanks! I'll try the problem with this in mind. $\endgroup$ – Luka Aleksić Aug 26 '17 at 21:00
  • $\begingroup$ Could you please look at my own answer (which shows my attempt at solving this)? $\endgroup$ – Luka Aleksić Aug 27 '17 at 1:41
0
$\begingroup$

Following Rob Arthan's hint I got to this,

Alpha is the only element that is in relation with an element not in relation with any other element, with which there is an element in relation, that is not in relation with itself.

\begin{align} F_\alpha(x) =& \exists y\in A, \quad \nexists z\in A, \quad (y,z)\in q \quad \land \quad (x,y)\in q \quad \\&\land \exists m\in A, \quad (m,m)\notin q \quad \land (m,x)\in q \end{align}

Beta is simply the only element in relation with itself

$$ F_\beta(x) = (x,x) \in q $$

Gamma is the only element with which no other element is in relation

$$ F_\gamma(x) = \nexists y \in A, \quad (y,x) \in q $$

Delta is the only element not in relation with any other element, with which there is no element in relation that is also in relation to itself.

$$ F_\delta(x) = \nexists y\in A \quad (x,y) \in q \qquad \land \qquad \nexists z\in A, \quad (z,z)\in q \quad \land \quad (z,x) \in q $$

Epsilon is the only element not in relation with itself, that is in relation with some other element, and with which there is an element in relation, that is also in relation with itself

$$ F_\epsilon(x) = (x,x) \notin q \qquad \land \qquad \exists y\in A, \quad (x,y) \in q \qquad \land \qquad \exists z\in A, \quad (z,x) \in q, \quad (z,z) \in q $$

Eta is the only element not in relation with any other element, with which there is an element in relation, that is also in relation with itself

$$ F_\eta(x) = \nexists y\in A, \quad (x,y) \in q \qquad \land \qquad \exists z\in A, \quad (z,x)\in q \quad \land \quad (z,z) \in q $$


I believe this is correct, and I went over it a few times, though I felt a bit of an idiot doing this "by eye", so to speak. It simply took me too long, and I assume there is a way to quickly and systematically deduce this information from a table,

\begin{matrix} &\alpha & \beta & \gamma & \delta & \epsilon & \eta\\ \alpha & 0 & 0 & 0 & 1 & 0 & 0\\ \beta & 0 & 1 & 0 & 0 & 1 & 1 \\ \gamma & 0 & 0 & 0 & 0 & 0 & 1 \\ \delta & 0 & 0 & 0 & 0 & 0 & 0\\ \epsilon & 1 & 0 & 0 & 0 & 0 & 1 \\ \eta & 0 & 0 & 0 &0 & 0 & 0\\ \end{matrix}

like one would for a truth table of a boolean function?


Secondly, I'm still not sure from the text of the problem how I should have known to solve the problem thusly. Could someone elaborate or link to a helpful resource?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.