Logical Equivalence

[JellyFish]

For this homework question we are given the following,

p ? (q ? r) ? (¬p ? ¬q ? r) and we are asked to negate it then simplify, then check with a truth table.

I assumed negating it meant ¬[p ? (q ? r) ? (¬p ? ¬q ? r)] and then apply the negation to each part. I did this and tried to simplify and then tried to check that the simplification was equivalent to ¬[p ? (q ? r) ? (¬p ? ¬q ? r)]using a truth table, but I was way off.

Any ideas or help is appreciated. Thank you.

 

[daon]

Logic isn't my forte, but it seems simple enough.

Start with something simple: ¬(p ? q) = ¬p ? ¬q. This is one of Demorgan's laws. I'm sure you know this so I will use it repeatedly:

We're looking for: ¬[p ? (q ? r) ? (¬p ? ¬q ? r)]

Start by breaking it into pieces: ¬[ ( p ? (q ? r) ) ? (¬p ? ¬q ? r) ] (Using the associative law for ? allows us to group as we please)

Using the above rule we get: ¬(p ? (q ? r)) ? ¬(¬p ? ¬q ? r)

Once again: (¬p ? ¬(q ? r)) ? (p ? q ? ¬r)

One more time: (¬p ? (¬q ? ¬r)) ? (p ? q ? ¬r)

From here you may use the distributive property. Can you finish?

 

[JellyFish]

After using the Distributive law I have: [(¬p v ¬q) ? (¬p v ¬r)]v [p ? q ? ¬r]

I'm assuming this can go further but yet again I'm not sure which rule would work next?

 

[DrMike]

(¬p ? (¬q ? ¬r)) ? (p ? q ? ¬r)

Rather than distributing the ¬p into the (¬q ? ¬r), you'd be better off getting rid of one set of brackets, giving ¬p ? (¬q ? ¬r) ? (p ? q ? ¬r), then distributing ¬p into (p ? q ? ¬r). Some things will cancel out, and then you can distribute (¬q ? ¬r) into what's left, then distribute the various remaining atoms into (¬q ? ¬r). A whole bunch of stuff will cancel, and you'll be left with something simpler.

If the truth tables don't match at the end, work out the truth tables for the various intermediate steps to see what went wrong where.