For an Algorithms course we are studying propositional calculus. As an excercise we are given formal statements which we are to explain in natural language first and then evaluate with specific values. As a very simple example, which will serve us to clarify matters of notation, statements are of the form

$$\langle \sum i: 0 \leq i < \#xs : xs!i \rangle$$

Here (and from now on), $xs$ denotes a list of values, $\#xs$ denotes the length or cardinality of the list, and $!$ is the indexing operator. For example, if $xs = [1, 10, 20]$, then $xs!2 =20$ and $\#xs=3$. The statement above is understood to declare an operation ($\sum$), in the range ($0, 1, ..., \#xs$) of the variable $i$, for the values $xs!i$. For example, when asked to describe the proposition in natural language, we would reply

The sum of each element in the list $xs$

And its formal evaluation over a given list, say $xs = [1, 2, 3]$, would be given by \begin{align*} &\langle \sum i : 0 \leq i < \#xs : xs!i \rangle \\ \equiv &\{\text{By making the range explicit}\} \\ &\langle \sum i : i \in \{0, 1, 2\} : xs!i \rangle \\ \equiv &\{\text{Broadcasting the term $xs!i$ over the range}\} \\ &xs!0 + xs!1 + xs!2 \\ \equiv&~1 + 2 + 3 \\ =&6 .\end{align*}

So far so good. But I was requested to do this for the following expression, which is more complex:

\begin{align*} \langle \max i : 0 \leq i < \#xs : xs!i \rangle < \langle \min i : 0 \leq i < \#ys: ys!i \rangle .\end{align*}

where $xs = [-3, 9, 8], ys= [6, 7, 8]$. Of course, the statement reads: the maximum element of $xs$ is smaller than the mimimal element of $ys$. But I find it very difficult to apply the formal definition of $max, min$ to rigorously evaluate this expression. Such definition is given in my textbook as follows:

\begin{align*} z = \langle \max i: R.i : F.i \rangle \equiv \langle \exists i : R.i : z=F.i \rangle \land \langle \forall i : R.i : F.i \leq z \rangle \\ z = \langle \min i: R.i : F.i \rangle \equiv \langle \exists i : R.i : z=F.i \rangle \land \langle \forall i : R.i : F.i \geq z \rangle .\end{align*}

In truth, I don't entirely understand this definition at all, since the use of both $=$ and $\equiv$ confuses me. It seems to say we define the maximum (or minimum) $z$ as that value of the range where the conjunction is true. In our case,

\begin{align*} z = \langle \max i: i \in \{0, 1, 2\} : xs!i \rangle \equiv \langle \exists i : i \in \{0, 1, 2\} : z=xs!i \rangle \land \langle \forall i : i \in \{0, 1, 2\} : xs!i \leq z \rangle .\end{align*}

and similarly for the minimum. But how could I reduce the expression above so as to "boil it down" to $9$, the maximum of $xs$? What would be the correct, rigorous procedure, in terms of propositional calculus, to reduce the conjuction above to $9$?

  • $\begingroup$ I guess it ultimately depends on the set of rules you actually use for propositional calculus. There is no single system for that but a huge list of variants (all equivalent in power, of course). Anyway, maybe you could start by rephrasing the inequality between integers $A<B$ as the equivalent formula $\langle\exists a,b : a,b\in\mathbb Z : a=A \land b=B \land a<b \rangle$. That would allow $a=A$ and $b=B$ to be rewritten according to your definitions of $\min$ and $\max$. $\endgroup$
    – chi
    Mar 2, 2023 at 22:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.