0

All in all, i wanted to know if if it's possible to mathematically simplify 'if expressions' in code, by replacing every condition by a set. Here's an example :

I have two 'if expressions', let's call them S1 & S2 respectively :

S1: ((x > 0) || ((x <= 0) && (y < 100))
S2: (x > 0) || (y < 100)

Now is it correct if i suppose that (x > 0) is basically some specific set A, generated by the actual rule x>0, and since x & y belong to the same domain (of natural numbers N), proving that the S1 and S2 are equal would also prove that the 'if expressions' are equivalent ?

If yes, would this be a valid proof :

Let A, B & C be the subsets generated by the following rules (x>0), (x<=0) & (y<100) respectively, using the domain of natural numbers N. I can then express S1 and S2 based on those sets, (using '+' for unions/ors and 'x' for intersections/ands) as such :

S1: A + (B x C)
S2: A + C

Hence, if S1 = S2 :
S1 = S2 <=> A + (B x C) = A x C
        <=> (A + B) x (A + C) = A + C

So if i prove that (A or B) is equal to the whole domain, then our initial assumption that S1 = S2 is correct ?

In our case : 

A or B = (x > 0) or (x <= 0) = N 
And since:  N or (A and C) = A and C 
and that would mean our initial assumption S1 = S2 is true

Would that ultimately prove that S1 = S2 ?

Asaf Karagila
  • 393,674
Lorenzo
  • 105
  • In general A || ((!A) && B) is logically equivalent to A || B (where !A refers to the negation of A, like how x <= 0 is the negation of x > 0 in your example). (Mathematically, we can write that $A\lor ((\sim A)\land B)$ is logically equivalent to $A\lor B$. You can prove this using rules of logic.) You can just use the latter in code. – Minus One-Twelfth Apr 03 '19 at 09:31

1 Answers1

1

There are different ways to prove the equivalence of logical expressions, such as algebraic manipulation and truth tables.

In your case, you want to prove

$$a\lor(\lnot a\land c)\equiv a\lor c.$$

The weird operators are or, not and and, in the order of appearance. You can also use the Boolean notation:

$$a+(\overline a\cdot c)=\overline a+c$$

Note that it is important to use $\lnot a$ rather than an extra condition, say $b$, otherwise the equations will not reflect the dependency between $a$ and $b$.

The above proof is straightforward, using the laws of logical arithmetic:

$$a\lor(\lnot a\land c)\equiv (a\lor\lnot a)\land(a\lor c)\equiv T\land(a\lor c)\equiv a\lor c.$$

$$a+(\overline a\cdot c)=(a+\overline a)\cdot(a+c)=1\cdot(a+c)=a+c$$

Using a truth table:

$$\begin{array}&a&c&\lnot a&\lnot a\land c&a\lor(\lnot a\land c)&a\lor c \\\hline F&F&T&F&F&F \\F&T&T&T&T&T \\T&F&F&F&T&T \\T&T&F&F&T&T \end{array}$$

you see that the last two columns are identical.

  • Thanks a lot for the reply, i was hoping for a more calculatory approach, rather than having to do a truth table (like i tried in my post above using the x>100 as some kind of subset of the natural numbers set [where only numbers above 100 are in the set]). If you have any further ideas on this i'm all ears hehe, otherwise, your post proves my original question good enough so thanks again! – Lorenzo Apr 17 '19 at 09:52
  • @Lorenzo: did you really read my post ? I am showing both, even using two different notations ! –  Apr 17 '19 at 09:56
  • I'm terribly, sorry, I completely misread, you're right, i somehow unintentionally skipped over those two lines and went straight for the truth table =v= Thanks a lot for the very detailed and diverse explanations ! I've asked for 1 and got 3 hehe, thank you for your time ! – Lorenzo May 21 '19 at 08:49
  • @jean Marie no worries hehe, the formula was exactly what i wanted but the typos confused me hana – Lorenzo Jul 09 '20 at 00:10