CODEWITHSUNDEEP
boolean-logic
Tanner
Tanner

Reputation: 477

Boolean negation

One of my exam questions reads:

! ( ! ( a != b)  &&  ( b > 7 ) )

The choices:

a) (a != b) || (b < 7)
b) (a != b) || (b <= 7)
c) (a == b) || (b <= 7)
d) (a != b) && (b <= 7)
e) (a == b) && (b > 7)

Initially, I thought it would be D. This is incorrect, and I realize why. I don't understand how the logical negation operator reverses && and greater than/less than. I believe I have narrowed it down to the first two. Is there any instance > would change to <= ?

Upvotes: 3

Views: 5127

Answers (5)

Hayden
Hayden

Reputation: 2988

First apply the inner bracket logical NOT (!):

!(!(a != b) && (b > 7)) becomes !((a == b) && (b > 7))

With De Morgan's Law we reverse the operators to their counterpart.

We change > to <= because the > operator does not include 7 itself or anything less, hence the <= is the only one that satisfies that condition.

Truth Table

Now the outer !:

When looking at truth tables (picture above), you'll notice that logical AND (&&) and logical OR (||) have opposite results when comparing 2 different boolean expressions (i.e. truth false, false true), hence when we apply the !, we reverse the && with ||. Finally we need to switch the == to != again.

All up, this produces:

((a != b) || (b <= 7))

Upvotes: 0

Rusheel Jain
Rusheel Jain

Reputation: 843

answer is B. to understand this : ! ( ! ( a != b) && ( b > 7 ) )

Lets break it into parts. Part dummy: (a!=b) Part X: !dummy Part Y: (b>7)

Now !X = double negate of dummy => dummy => (a!=b)

!Y = !(b>7) => b should not be greater than 7 => b should be less than or equal to 7 => (b<=7)

Now problem left is how && becomes ||

So original question is: !( X && Y ) => should not be (X and Y) => it should be either negate of X or it should be negate of Y, because if instead of X it is ~X, the condition (X and Y) becomes false and hence !(X and Y) becomes true and hence original condition is achieved. Similarly for Y.

Upvotes: 0

display name
display name

Reputation: 4185

! ( ! ( a != b)  &&  ( b > 7 ) )

= ! ( (a = b) && (b > 7))

= (a != b) || (b <= 7)

Upvotes: 1

Roddy of the Frozen Peas
Roddy of the Frozen Peas

Reputation: 15184

Is there any instance > would change to <= ?

Answer: every time you negate it.

Consider x > 1. The negation of this is clearly x <= 1. If you simply negate it as x < 1 then neither case covers the x == 1 case.

That being said, the given boolean ! ( ! ( a != b) && ( b > 7 ) ) can be decomposed as follows:

  1. Given:

    ! ( !(a != b) && (b > 7))

  2. Negate a != b:

    ! ((a == b) && (b > 7))

  3. Distribute the !:

    !(a == b) || !(b > 7)

  4. Negate a==b:

    (a != b) || !(b > 7)

  5. Negate b>7:

    (a != b) || (b <= 7)

The answer is, therefore, B.

Upvotes: 8

Evan Bechtol
Evan Bechtol

Reputation: 2865

The answer should be B. This is because the negation next to the (a != b) is evaluated first, then you distribute the outside negation to the entire proposition.

Using DeMorgan's Laws, the && will switch to ||. Similarly, != becomes ==, and > becomes <=.

!(!(a != b) && (b > 7))
!((a == b) && (b > 7))
 (a != b) || (b <= 7)

Upvotes: 2

Related Questions