0
$\begingroup$

To program a function that tests whether all elements in an array are greater than 5, the straightforward way will be:

bool test(std::vector<int> arr){
   int number = 0;
   for(auto i:arr){  // Iterate over all elements
       if(i>5){
         number++;
       }
   }
   return arr.size() == number;
}

However, we can also achieve the function in this way:

bool test2(std::vector<int> arr){
   for(auto i:arr){  // Iterate over all elements
      if(i<=5){
        return false;
      }
   }
   return true;
}

Why is test2 functionally equivalent to test? How to interpret them from a mathematical perspective?

test do the things like ∀x ∈ arr, if x > 5, the result is true while test2 do the things like ∃x ∈ arr, if x<=5, the result is false. How do such two propositions mutually exclusive? Or, they are not propositions?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This is called De Morgan's Laws. See: https://en.wikipedia.org/wiki/De_Morgan%27s_laws

The intuition behind it is that, if I said every rose is red, that is equivalent to !(there exists at least one rose that isn't red) where ! negates the meaning of the statement or operand. This is because when negating an AND you have to distribute the negation operator which "converts" the AND to an OR and vice versa.

EDIT: Thought it worth adding after OPs comment that the wikipedia page gives this exact formulation:

$\endgroup$
4
  • $\begingroup$ Specifically, do you mean !(∀x ∈ arr, if x > 5, the result is true) is equivalent to ∃x ∈ arr, if x<=5, the result is false, if so, which formulation in your mentioned link is used here? $\endgroup$
    – xmh0511
    Commented Aug 15, 2023 at 14:14
  • $\begingroup$ the formulation just clarifies that for all x in arr, if x >5, the result is true is equivalent to there is no x that is less or equal than 5 such that the result is not true. I still didn't understand why test and test2 can do the same things. test2 means there is x that is less or equal than 5 such that the result is true, which is not logically equivalent to test. $\endgroup$
    – xmh0511
    Commented Aug 16, 2023 at 1:20
  • 1
    $\begingroup$ @xmh0511 Sorry if I misunderstood you but my understanding is the statement does give you the equivalence of test 1 and 2 as follows: Let P(x) be true when x >= 5 and false when x < 5. Then the first statement says: If for all x in arr x>=5 return true, and the second statement reads: ! (If there exists x in arr x<5 return true). The negation at the front makes this: If there exists x in arr x<5 return false. The negation at the outside just flips the answer since the inside is either true or false and in either case negating it gives the expected result (there's an else return the other one) $\endgroup$
    – TheJack
    Commented Aug 16, 2023 at 7:38
  • $\begingroup$ I mean that there's an implied: if you don't find it return the other value in both tests (true or false). That's what allows you to flip just the true or false and not have to distribute to the rest of the statement. I hope this helps clarify things $\endgroup$
    – TheJack
    Commented Aug 16, 2023 at 7:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .