cvariablesexpressiondemorgans-law

Using De Morgans Law to write expressions in C

I'm having a hard time understanding De Morgans Law, and how it relates to Boolean Logic and expressions. Specifically rewriting equivalent expressions, using Boolean Logic and the &&, ||, and ! operators.

So I know that in C Programming, De Morgans Law is a way to re-state an expression differently (using NOT, OR, AND) while it remains equivalent.

Such as:

!(condition1 && condition2)

Also equals:

!condition1 || !condition two

And:

condition1 && !(condition2)

Also equals:

condition1 || !condition2

(are we just multiplying the parenthesis by the unary negation NOT operator here? Like in the good ole' algebra days?)

Where my brain starts to fry, is when I evaluate a bit more tricky of an expression, and how to re-write it with Boolean Logic. I have searched any past threads, with some help, but still cant wrap my head around this. I started writing out truth tables, but could not figure out how to make one based off an expression like the ones below. I'm giving it my best, so please excuse any errors or poor practice.

(PLEASE NOTE, THE BELOW CODE IS NOT TECHNICALLY COMPLETE C CODE, JUST EXAMPLE OF EXPRESSION I'M TRYING TO WRITE USING BOOLEAN LOGIC, TO INCORPORATE INTO C CODE.)

I'm not able to incorporate this into any of my C programs because I just cant get it.

for example:

!( a > 12 ) && !(b >= 3 )

essentially states (truth form before NOT):

a > 12 && b >= 3

meaning A is greater than 12, AND b is either greater than or equal to 3.

Take it to a truth table:

a   b   a&&b

1   0   false - a is greater than 12, but b is not greater than or equal to 3.

0   1   false - this time a is less than 12 while b >= 3.

0   0   false - a is not > 12 and b is not >= 3.

1   1   true -  a is greater than 12, and b is >= 3.

Now apply the NOT operator: (this is where I start getting lost)

!( a > 12 ) && !( b >= 3 )

and write (try to) the equivalent using De Morgans Law: so …

!( a > 12 ) && !( b >= 3 )

IS EQUIVALENT TO

a < 12 || b < 3

(is there a way to cross compare these in a truth table to see if they really are equivalent?)

Another one, this time a bit trickier...

!( a == b ) && !( c != 2 )

IS EQUIVALENT TO:

(a != b) || (c = 2)

lastly

!( (a < 9 ) || ( b <=3 ) )

IS EQUIVALENT TO:

a > 9 && b > 3

I'm not sure if any of those are right, but I figured the best thing to do was to stop reading about it and just go ahead and try it.

Solution

  • It seems like you're looking at the conditional parts and overthinking things.

    Let's take a look at the rules:

    not A AND not B = not (A OR B)
not A OR not B = not (A AND B)

    In plain english, this means you can distribute out a NOT and invert AND and OR. So given this expression:

    !( a > 12 ) && !(b >= 3 )

    This fits the first version of the rule. Leaving the > and >= as they are, you can distribute out the NOT from both sides and get this:

    !(( a > 12 ) || (b >= 3 ))

    The AND gets changes to an OR, and (this is the part you missed) the NOT gets pulled out. Similarly, this:

    !( a == b ) && !( c != 2 )

    Becomes:

    !(( a == b ) || ( c != 2 ))

    Then the last one:

    !( (a < 9 ) || ( b <=3 ) )

    Turns into this via DeMorgan's laws:

    !(a < 9 ) && !(b <=3 )

    Then switching the conditionals:

    (a >= 9 ) && (b > 3 )

    I think where you got confused is that you attempted to flip the conditionals and apply DeMorgan's laws at the same time. Don't do that. Perform each part separately as needed.