Homework Help: Logical equivalencies

1. Jan 12, 2017

emeraldskye177

1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

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

2. Jan 12, 2017

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$.

3. Jan 13, 2017

emeraldskye177

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!

Last edited: Jan 13, 2017
4. Jan 13, 2017

Stephen Tashi

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$.

5. Jan 13, 2017

emeraldskye177

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?

Last edited: Jan 13, 2017
6. Jan 29, 2017

Stephen Tashi

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)))$