Logical Equivalencies Homework Solutions

[emeraldskye177]

Homework Statement

[/B]

Homework Equations

[/B]

The Attempt at a Solution

[/B]

And I just don't know what to do from here... Any help will be greatly appreciated!

 

[Stephen Tashi]

I think you should use the distributive law on expressions like:
$(\lnot p \land \lnot q) \lor (q \lor \lnot r)$
to get:
$(\lnot p \lor ( q \lor \lnot r) ) \ \land \ (\lnot q \lor (q \lor \lnot r) )$

Then, in those propositions that involve only "$\lor$"'s, you can change the pattern $A \lor B \lor C$ to $\lnot( \lnot A \land \lnot B) \lor C$ and then get rid of the last $\lor$ by changing it to $(\lnot A \land \lnot B) \implies C$.

 

[emeraldskye177]

I think you should use the distributive law on expressions like:
$(\lnot p \land \lnot q) \lor (q \lor \lnot r)$
to get:
$(\lnot p \lor ( q \lor \lnot r) ) \ \land \ (\lnot q \lor (q \lor \lnot r) )$

Then, in those propositions that involve only "$\lor$"'s, you can change the pattern $A \lor B \lor C$ to $\lnot( \lnot A \land \lnot B) \lor C$ and then get rid of the last $\lor$ by changing it to $(\lnot A \land \lnot B) \implies C$.

Hi, thanks for taking the time to respond. Does this look correct to you?

Also, how would I prove that the original expression and the one I derived are equivalent using logical equivalencies? (I.e., I think I have to convert everything in the original and derived expressions to T's and F's (True's and False's), and they both have to reduce to the same.)

Again, thanks so much for your help!

 

[Stephen Tashi]

Does this look correct to you?

You are doing the double negations like changing $\lnot (\lnot p)$ to $p$ without showing it as a step. Some instructors may permit that.

The expression $\lnot q \lor (q \lor \lnot r)$ could be simplifed to $( \lnot q \lor q) \lor \lnot r$ and then to $T \lor \lnot r$ and then to $T$.

Also, how would I prove that the original expression and the one I derived are equivalent using logical equivalencies?

The rules you are using change expressions to logically equivalent expressions, so your steps are guaranteed to result in a logical equivalence.

Of course, you can check your work by using a truth table.

If you had a rule that was not a logical equivalence such as $p \lor q \lor r \implies p$ and you changed the expression $(p \lor q \lor r)$ to $(p)$ then you could not claim that such a step produced a new expression that was logically equivalent to the old expression. However, all the rules you listed use the relation $\equiv$.

 

[emeraldskye177]

You are doing the double negations like changing $\lnot (\lnot p)$ to $p$ without showing it as a step. Some instructors may permit that.

The expression $\lnot q \lor (q \lor \lnot r)$ could be simplifed to $( \lnot q \lor q) \lor \lnot r$ and then to $T \lor \lnot r$ and then to $T$.The rules you are using change expressions to logically equivalent expressions, so your steps are guaranteed to result in a logical equivalence.

Of course, you can check your work by using a truth table.

If you had a rule that was not a logical equivalence such as $p \lor q \lor r \implies p$ and you changed the expression $(p \lor q \lor r)$ to $(p)$ then you could not claim that such a step produced a new expression that was logically equivalent to the old expression. However, all the rules you listed use the relation $\equiv$.

Hi Stephen,

The next question in the assignment asks me to use a truth table, which should be easy enough. However, the preceding question asks for the use of logical equivalencies (reduction to T's and F's) to prove the original and derived expressions are logically equivalent. For this part, based on what you said, this is what I have so far (sorry if the snip resolution is suboptimal):

However, I'm not sure how to further reduce the last line... Can the original and derived expressions be further reduced?

Any help you can lend in this matter would be greatly appreciated. Thanks for all the help you've provided thus far.

 

[Stephen Tashi]

Can the original and derived expressions be further reduced?

It might be simpler to continue by using the associative and commutative laws after you reach the expression:
$( (\lnot p \lor ( q \lor \lnot r)) \land (\lnot q \lor (q \lor \lnot r)) ) \land ( (\lnot q \lor (p \lor q) )\land (r \lor (p \lor q)))$
by doing:
$\equiv ((\lnot p \lor ( q \lor \lnot r)) \land (( \lnot q \lor q) \lor \lnot r)) \land ((\lnot q \lor (p \lor q)) \land (r \lor (p \lor q)))$
$\equiv ((\lnot p \lor ( q \lor \lnot r)) \land (( \lnot q \lor q) \lor \lnot r)) \land ((\lnot q \lor q) \lor p) \land (r \lor (p \lor q)))$
The negation and domination laws are very useful in reducing logical expressions:
$\equiv ((\lnot p \lor ( q \lor \lnot r)) \land (T \lor \lnot r)) \land( (T \lor p) \land (r \lor (p \lor q)))$
$\equiv ((\lnot p \lor ( q \lor \lnot r)) \land T) \land ( T \land (r \lor (p \lor q)))$
$\equiv ((\lnot p \lor ( q \lor \lnot r))) \land ( (r \lor (p \lor q)))$