28
$\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.

$\endgroup$
  • $\begingroup$ If the cases for m = 1 and m = 2 are the same, why are you maintaining them as separate cases? $\endgroup$ – J. M. is a poor mathematician Dec 27 '10 at 11:20
  • $\begingroup$ They aren't the same... I'm just keeping the equation here simple. I'm only interested in the formatting. $\endgroup$ – IamIC Dec 27 '10 at 11:21
  • $\begingroup$ (a,b)_1 and (a,b)_n are scalars? $\endgroup$ – J. M. is a poor mathematician Dec 27 '10 at 11:28
  • $\begingroup$ (a,b)_1-n is an array of line segments on a 1D line where a <= b for a given line segment. $\endgroup$ – IamIC Dec 27 '10 at 11:29
  • 5
    $\begingroup$ 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. $\endgroup$ – Carl Mummert Dec 27 '10 at 12:51
28
$\begingroup$

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(a<b\rightarrow x=\frac{a}{b})\wedge(a>b\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.

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – IamIC Dec 27 '10 at 13:15
  • $\begingroup$ I think I figured it out. It's "a=b"->(true)->(false)" - right? $\endgroup$ – IamIC Dec 27 '10 at 13:28
  • $\begingroup$ @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. $\endgroup$ – Carl Mummert Dec 27 '10 at 13:34
  • 1
    $\begingroup$ @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. $\endgroup$ – Asaf Karagila Dec 27 '10 at 13:35
  • 1
    $\begingroup$ @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. $\endgroup$ – Carl Mummert Dec 27 '10 at 13:40
6
$\begingroup$

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)

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ For some reason, neither Chrome nor Firefox will render that. Is there an error in the code? $\endgroup$ – IamIC Dec 28 '10 at 0:51
  • $\begingroup$ @Ianc: I think it did not render because it was in backquotes... I have corrected that. $\endgroup$ – Aryabhata Dec 28 '10 at 1:35
  • $\begingroup$ @Moron thanks. @user3141592 I don't get how this would represent "if (a < b) then c = 100..." $\endgroup$ – IamIC Dec 28 '10 at 17:15
4
$\begingroup$

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)$.

$\endgroup$
3
$\begingroup$

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)

$\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.