26
$\begingroup$

How do I correctly represent the following pseudocode in math notation?

EDIT1: Formula expanded. EDIT2: Clarification.

(a,b) represents a line segment on a 1D line. a <= b for each segment. The division show below is done as per the following T-SQL code (which I suppose could be represented as a function in the formula?):

Input: @a1 real, @b1 real, @an real, @bn real

DECLARE @Result real

if @a1 <= @an begin
    SET @Result = @an - @b1

    if @Result <= 0 RETURN 0

    RETURN @Result / @an
end

SET @Result = @a1 - @bn

if @Result <= 0 RETURN 0

RETURN @Result / @a1

Formula:

if m = 1 then
  if (a,b)_1 intersects (a,b)_n then
    r = 1
  else if (a,b)_1 < (a,b)_n then
    r = (a,b)_1 / (a,b)_n
  else
    r = (a,b)_n / (a,b)_1
else if m = 2 then
  if (a,b)_1 intersects (a,b)_n then
    r = 1
  else if (a,b)_1 < (a,b)_n then
    r = (a,b)_1 / (a,b)_n
  else
    r = (a,b)_n / (a,b)_1

The m = 2 block is shown as being the same as the m = 1 one for simplicity's sake.

The divisions are against the two points that are closets to each other, unless the segments intersect, at which point r = 1.

  • 0
    If the cases for `m = 1` and `m = 2` are the same, why are you maintaining them as separate cases?2010-12-27
  • 0
    They aren't the same... I'm just keeping the equation here simple. I'm only interested in the formatting.2010-12-27
  • 0
    `(a,b)_1` and `(a,b)_n` are scalars?2010-12-27
  • 0
    (a,b)_1-n is an array of line segments on a 1D line where a <= b for a given line segment.2010-12-27
  • 0
    So the divisions and the comparisons are componentwise, then?2010-12-27
  • 0
    I'll edit the question to clarify.2010-12-27
  • 5
    There is no one "math notation" that is useful for every purpose. We use certain notation only when it makes communication easier. Most mathematics is conveyed in natural language (English, French, Chinese, etc.) rather than symbolically. There is not any special "mathematics" notation for pseudocode. When we want pseudocode we write it just like computer scientists. Given that, I don't think you question is precise enough for a ore specific answer.2010-12-27
  • 0
    @Carl I know this isn't a simple question. But I do believe it can be represented mathematically. I agree there is no one-size-fits-all notation. But I do believe that IF THEN ELSE is generic enough to easily be represented. I am not trying to represent the whole pseudocode in math. I only added it based on questions on my original question.2010-12-27
  • 0
    @IanC: The usual way that mathematicians express an "if/then" condition is in natural language. I'm sorry if that is not the answer you were hoping for.2010-12-27
  • 0
    @Carl The math symbols for "if then" are here: http://en.wikipedia.org/wiki/List_of_logic_symbols. They aren't written in plain natural language. It's the "else" part I was stuck with.2010-12-27
  • 0
    @IanC: mathematicians do not use those symbols in the way you are suggesting.2010-12-27
  • 0
    @Carl I see what you mean.2010-12-27

5 Answers 5

25

In general, if you have "If $\varphi$ then $\psi$, otherwise $\tau$" you can write this as the following formula (or sentence, depending on $\varphi,\psi,\tau$):

$\left(\varphi\rightarrow\psi\right)\wedge\left(\neg\varphi\rightarrow\tau\right)$

If you have several cases, you can either nest them (i.e. $\tau$ would be "if second condition then, else ...") or if you can express them as $\varphi_1$ meaning only the first case holds, and none of the others as $(\varphi_1\rightarrow\psi_1)\wedge(\varphi_2\rightarrow\psi_2)\wedge\ldots$

Addendum:

$(a=b\rightarrow x=1)\wedge(ab\rightarrow x=\frac{b}{a})$

I have added $x$ as a variable, because writing just $\rightarrow 1$ seems very meaningless to me, you can of course replace $x$ by anything you'd like. The idea, essentially is that you express "IF ... THEN ... ELSE" structures using the $\rightarrow$ (or $\implies$ sometimes) and I gave you in my original post the method of doing so.

  • 0
    @Asaf Thanks. Ok, we're getting there. The first example is slightly confusing because of the and nots and double if. Could you write it out for me r = if a = b then 1 else if a < b then a/b else b/a.2010-12-27
  • 0
    I think I figured it out. It's "a=b"->(true)->(false)" - right?2010-12-27
  • 0
    @IanC: There is no straightforward way to do that in first-order logic because it doesn't have either of the following concepts: (1) assigning a value to a variable with an operator like =, and (2) a formula that returns an object, rather than True or False, as output. Those things are two of the main differences between pseudocode in imperative languages and formulas in first-order logic. It would be possible to use lambda calculus, which is more like pseudocode; but you could use any other actual programming language to get away from pseudocode, too; lambda calculus is not unique for that.2010-12-27
  • 1
    @Carl: I usually think about it as informal predicate calculus, I allow myself to write vague/undefined things in order to keep the idea clear mathematically. I usually do note when I'm "cheating" and explain why I am cheating.2010-12-27
  • 0
    @Carl, ah, I see where you are coming from. This is one of those cases where I need to post the whole problem, but then no one will answer. It's simply part of a summation. I'm just showing the code equivalent. But I get your point.2010-12-27
  • 1
    @Asaf Karigila: that's fine, as long as everyone realizes that a "formula" such as "$((a = b) \to 4) \land ((a \not = b) \to 7)$" is not actually a formula, because it has terms (4 and 7) where it ought to have subformulas. One thing that we do not have in first-order logic is a way for a formula to have a term as its value, rather than a truth value. Of course you can use your own personal shorthand whenever you like.2010-12-27
  • 0
    @Carl I knew there was a way :-) @Asaf thanks much.2010-12-27
  • 0
    @Carl, by (true) and (false), I means the formula when true and when false, not a boolean return.2010-12-27
  • 0
    @Carl: of course. This is why I added $x=1$ :-)2010-12-27
6

You could potentially convert it to a mathematical formula too.

For example say we had the following:

if (a < b) then c = 100 
else if (a > b) then c = 200
else c = 300.

This can be rewritten as

$$c = 300 \ (1 - \text{sgn}^2(a-b)) + \text{sgn}^2(a-b)(50 \ \text{sgn}(a-b) + 150)$$

Where $\text{sgn}(x)$ is the sign of $x$, as defined here; http://en.wikipedia.org/wiki/Sign_function.

(It is defined as: 1 for positive, 0 for 0, and -1 for negative)

5

Or just $\begin{cases} a & b \\ c & d \end{cases}$

  • 0
    For some reason, neither Chrome nor Firefox will render that. Is there an error in the code?2010-12-28
  • 0
    @Ianc: I think it did not render because it was in backquotes... I have corrected that.2010-12-28
  • 0
    @Moron thanks. @user3141592 I don't get how this would represent "if (a < b) then c = 100..."2010-12-28
4

This was a rejected edit on the accepted answer so I'm posting it as a new answer instead. I just wanted to point out that "If $\varphi$ then $\psi$, else $\tau$" is equivalent to $(\varphi\wedge\psi)\vee(\neg\varphi\wedge\tau)$. Since $P \to Q$ is equivalent to $\neg P \vee Q$, we can expand $(\varphi\rightarrow\psi)\wedge(\neg\varphi\rightarrow\tau)$ as follows:

$\begin{align*} (\varphi\rightarrow\psi)\wedge(\neg\varphi\rightarrow\tau) &\iff (\neg\varphi\vee\psi)\wedge(\varphi\vee\tau) \\ &\iff \left((\neg\varphi\vee\psi)\wedge\varphi\right)\vee\left((\neg\varphi\vee\psi)\wedge\tau\right) \\ &\iff (\varphi\wedge\psi)\vee(\neg\varphi\wedge\tau)\vee(\psi\wedge\tau) \end{align*}$

The last term, $(\psi\wedge\tau)$, is redundant. This can be corroborated with a truth table but it should be intuitive as the first two terms cover all cases due to the presence of $\varphi$ and $\neg\varphi$. Thus, the concept of "If $\varphi$ then $\psi$, else $\tau$" is mathematically equivalent to the sentential logic formula $(\varphi\wedge\psi)\vee(\neg\varphi\wedge\tau)$.

3

How to implement If-then-else structures in propositional logic:

Example 1

If P then
  Q
else
  R
end if

(P -> Q) & (~P -> R)

Example 2

If P then
  Q
else if R then
  S
else
  T
end if

(P -> Q) & (~P & R -> S) & (~P & ~R -> T)