Question about propositional logic

[Florence]

Homework Statement

I have to prove that ##(p \equiv q) \equiv ((p ∧ q) ∨ (¬p ∧ ¬q))##
With no premisses

In order to prove this, I first need to prove that:
##(p \equiv q) \to ((p ∧ q) ∨ (¬p ∧ ¬q))##

And:
##((p ∧ q) ∨ (¬p ∧ ¬q)) \to (p \equiv q)##

I was able to find the second implication, but I am still looking how I can prove the first one.

2. Homework Equations
I have the inference rules, contraposition, modus tollens ...

The Attempt at a Solution

I started with the hypothetical statement:
##(p \equiv q)##
But then I need to end the hypothetical statement with:
##((p ∧ q) ∨ (¬p ∧ ¬q))##

So I have tried to start a new hypothetical statement:
##¬((p ∧ q) ∨ (¬p ∧ ¬q))##
And to introduce a negation.
##¬((p ∧ q) ∨ (¬p ∧ ¬q)) \to (p \equiv q)## was easy to find, but I can't find a way to prove:
##¬((p ∧ q) ∨ (¬p ∧ ¬q)) \to ¬(p \equiv q)##
So that I could eliminate the negation afterwards.
I was looking to prove
##¬(p \equiv q)##
But I couldn't find a way to introduce the negation.

So I've tried to eliminate the disjuntion of:
##(p ∧ q) ∨ (¬p ∧ ¬q)##
By starting a new hypothetical statement, but this couldn't help me any futher.

Thank you in advance!

 

[nomadreid]

There are many ways you could prove this. The easiest way to prove both directions is with truth tables, but if you don't like that, then for example you can write out what p≡q means, that is (p→q)∧(q→p), then write A→B as A∨~B for each pair, then use the distributive law: (M∨N)∧(R∨S) ≡ (M∧R)∨(M∧S)∨(N∧R)∨(N∧S), and then simplify.

 

[Florence]

I think that we haven't seen the distributive law in logics. I've put all the rules that we have just below. For this exercise we are not allowed to use truth tables, so we have to use these rules to prove it.

##A, B / A∧B ##
##A∧B / A resp. A∧B / B##
##A / A∨B resp. B / A∨B##
##A∨B, A \to C, B \to C / C##
##A \to B, A \to ¬B / ¬A##
##¬¬A / A##
##A \to B, B \to A / A≡B ##
##A≡B / A \to B, B \to A##
##A, A \to B / B##
##A (Hyp), B / A \to B##
##A \to B, ¬B / ¬A ##
##¬A, A∨B / B##
##A \to B, B \to C / A \to C##
##A \to B / ¬B \to ¬A##
##¬(A∧B) / ¬A∨¬B##
##¬(A∨B) / ¬A∧¬B ##
## ¬(A \to B) / A∧¬B##

 

[nomadreid]

I find your statement that

¬((p∧q)∨(¬p∧¬q))→(p≡q)

was easy to prove a bit odd, since if the statement that you are trying to prove

(p≡q)≡((p∧q)∨(¬p∧¬q))

is correct (which it is if you think about what it is saying), then

¬((p∧q)∨(¬p∧¬q))→¬(p≡q)

by substitution (and a couple more easy steps).
This is not a solution, it is just pointing out that since the first and the third implication cannot both be correct, you apparently made a mistake in the derivation of the second implication above. If you find that mistake, you will probably be on your way to finding the correct derivation.
By the way, to find out if you have a mistake, although you are not allowed to use truth tables in your solution, you can use them to check a statement as being correct or not for your own peace of mind; you just don't hand that work in.

 

[Florence]

I think that I do understand what you mean and I see that introducing the negation on
##¬(p∧q)∨(¬p∧¬q)##
By doing
##¬((p∧q)∨(¬p∧¬q))→(p≡q)##
##¬((p∧q)∨(¬p∧¬q))→¬(p≡q)##
Is unnecessary because when I use the transposition rule on
##¬((p∧q)∨(¬p∧¬q))→¬(p≡q)##
I get
##(p \equiv q) \to ((p∧q)∨(¬p∧¬q))##
And that is what I need.

I just don't see what you mean by mistake, because I was trying to use the rule:
##A \to B, A \to ¬B / ¬A##

And I will try write the truth table down! (Thank you for the tip!)

 

[Florence]

By the way, to find out if you have a mistake, although you are not allowed to use truth tables in your solution, you can use them to check a statement as being correct or not for your own peace of mind; you just don't hand that work in.

So I've set up some truth tables and I was able to find out that I can prove them. But now I am trying an other way. I'm trying to prove
##¬((p∧q)∨(¬p∧¬q)) \to ¬(p \equiv q)##

So I started my hypothetical statement with
##¬((p∧q)∨(¬p∧¬q))##
##¬(p∧q)∧¬(¬p∧¬q)##

Then I started a new hypothetical statement with
##(p \equiv q)##

I want to prove that
##(p \equiv q) \to ?## and
##(p \equiv q) \to ¬?##

So that I can conclude to
##¬(p \equiv q)##

But I don't see what I need to put on the question marks. I've looked for information that I have, which is:
##¬p∨¬q##
##p∨q##
##p \to q##
##q \to p##

 

[Delta2]

I think the idea behind this exercise is a lemma (##p \equiv q## is equivalent to ##A(p) \equiv A(q)## )where A(p) is any sentence that has p as variable and A(q) is the same sentence where we replace p with q. You can prove this lemma by induction in the form of A(p). Have you been taught this type of induction?

 

[Florence]

I think the idea behind this exercise is a lemma (##p \equiv q## is equivalent to ##A(p) \equiv A(q)## )where A(p) is any sentence that has p as variable and A(q) is the same sentence where we replace p with q. You can prove this lemma by induction in the form of A(p). Have you been taught this type of induction?

No we haven't seen that, I'm only in my first year psychology and I think we will only see the basics of logics

 

[nomadreid]

Sorry for the mess in the first sending of this post that arrived in your email inbox, and also for delay in responding, Florence, but I'm probably in a different time zone than you are, and sleep tends to interfere with one's schedule, and this morning my keyboard is acting up.
First, to your post asking where you had the mistake. This was my mistake in not reading your post carefully enough to see that you were attempting a proof by contradiction.
Let me recap.
So far you proved the second part of your task
((p∧q)∨(¬p∧¬q))→(p≡q)
and then you started on the first part, proving by contradiction:
¬((p∧q)∨(¬p∧¬q)) / (¬((p∧q)∨(¬p∧¬q))→(p≡q))
which did not get you very far.

Going back to your original statement, you want to prove
(p≡q)→((p∧q)∨(¬p∧¬q))
i.e.
(p∨¬q)∧(¬p∨q)→((p∧q)∨(¬p∧¬q))
Since you like proof by contradiction, let me restate this:
~((p∧q)∨(¬p∧¬q))→~((p∨¬q)∧(¬p∨q)) (*)
(I will now be lazy and use ~ as being the same thing as the crook symbol, and omit the obvious double negation elimination steps)
(Also I will omit the obvious step of double negation elimination
First apply deMorgan to the LHS to get

(~(p∧q)∧~(¬p∧¬q))
Apply deMorgan again

Apply deMorgan to the RHS of (*) to get
~(p∨¬q)∨~(¬p∨q))
deMorgan again
(~p∧q)∧ (p∧~q)
Using your rule

A∧B/Aresp.A∧B/B

several times, you get
(~p∨~q)
and again
(p∨q)
Then use your rule that allows you to join them with ∧
Now, do you suppose you can get a contradiction?
Sorry for the lack of detail, but I must run out for the rest of the day. I will be back online tomorrow.

 

[Florence]

Sorry for the mess in the first sending of this post that arrived in your email inbox, and also for delay in responding, Florence, but I'm probably in a different time zone than you are, and sleep tends to interfere with one's schedule, and this morning my keyboard is acting up.

No problem! I really appreciate all of your help!

But I don't really get what I need to do now
Do I need to start the hypothetical statement with
##(p \equiv q)##
Then start another hypothetical statement with
## ¬((p∧q)∨(¬p∧¬q))##
This? Or
##¬((p∨¬q)∧(¬p∨q))##
This?

 

[nomadreid]

Right, I was a little sketchy on how the proof proceeded after the last line. You can proceed either by proof by contradiction, or a straight proof without it. You seemed to be partial to proof by contradiction, so I first converted the original statement into something easier to prove by contradiction. I started with the statement you wanted to prove, converted ≡, took the contrapositive, used deMorgan, elimination of double negation, & the rules that I quoted about ∧,...so far, notice that I had not tried a proof by contradiction. But after you convert both sides, you end up with
(~p∨~q)∧(p v q))→(~p∨~q)∧(p∨q).
which is just A→A.
That was to show you what could go into the brackets if iI started with ~(original statement).
So, to do the proof, you can just start again but this time start with ~(original statement), and you will end up with
~ (A→A), which is (or can be turned into, according to your definition) a contradiction.
That is, you will have proven
~(original statement)→contradiction.
and thus you will have proven the original statement.

No guarantee that this is the shortest way; a direct proof would also be possible through the same types of conversions.

 

[Florence]

I think that I get it! I will try it out!

Thank you!