Welcome to our community

Be a part of something great, join today!

Propositions/ Logical Equivalences

Joystar1977

Active member
Jul 24, 2013
119
Let p and q be propositions. Use logical equivalences to show that

( p ^ ( ~ ( ~ p V q))) V ( p ^ q) = p
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
Do you know the equivalences you are supposed to use? If so, then you should see some subformulas that match one of the sides of an equivalence. For example, ~(~p V q) matches the left-hand side of the De Morgan's law ~(A ∨ B) = ~A ∧ ~B. Apply the equivalences until you are stuck, then post what you've got.
 

Joystar1977

Active member
Jul 24, 2013
119
Can I write this p and q propositions as follows and use this logical equivalence that involves the following:

p arrow q = slash bar q arrow slash bar p

Does this solve p and q being propositions and using logical equivalences to show that

( p ^ (~ (~ p V q))) V (p ^ q) = p
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
Can I write this p and q propositions as follows and use this logical equivalence that involves the following:

p arrow q = slash bar q arrow slash bar p
I assume by "slash bar" you mean negation. In plain text, you can use the following notations.

~ : negation (not)
/\ or ^ : conjunction (and)
\/ or v : disjunction (or)
-> : implication (if-then)

Or copy and paste characters from this page.

You probably mean contraposition: p -> q = ~q -> ~p.

Does this solve p and q being propositions and using logical equivalences to show that

( p ^ (~ (~ p V q))) V (p ^ q) = p
The phrase "solve p and q being propositions" makes no sense to me. You need to prove an equality (in this case, better called equivalence) using other equalities.

I would not use contraposition here because the left-hand side has no implications. Start by applying De Morgan's law to ~(~p \/ q); then remove double negation.
 

Joystar1977

Active member
Jul 24, 2013
119
What I mean by the slash bar is a line that looks like an L but its upside down and part of its cut off. Sorry it wasn't in my list of symbols so I could insert so I have typed out words of what it shows under logical equivalences where it involves conditional statements and biconditional statements.

Can I use the following logical equivalences where p and q are propositions where it shows I am using DeMorgan's Law?

1. p double arrow q = (p arrow q) ^ (q arrow p)

2. p double arrow q = slash bar p double arrow slash bar q

3. p double arrow q = (p ^q) V (slash bar p ^ slash bar q)

4. slash bar (p double arrow q) = p double arrow slash bar q
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
Can I use the following logical equivalences where p and q are propositions where it shows I am using DeMorgan's Law?
These equivalences, while correct, have nothing to do with De Morgan's law.

Could you say how many completed examples from your textbook or lecture notes that deal with proving equivalences like the one in post #1 have you seen and understood? Look specifically at applications of De Morgan's law. Then do the same for ~(~p \/ q), which is a subformula of (p ^ (~(~p V q))) V (p ^ q).

And please consider the notation suggestion in post #4 or use LaTeX because otherwise your formulas are hard to read.
 

soroban

Well-known member
Feb 2, 2012
409
Hello, Joystar1977!

[tex]\begin{array}{c}\text{Let }p\text{ and }q\text{ be propositions.} \\
\text{Use logical equivalences to show that:} \\ \bigg\{p \wedge \big[\sim(\sim\!p \vee q)\big]\bigg\} \vee (p \wedge q) \:\Leftrightarrow \: p \end{array}[/tex]


[tex]\begin{array}{cccccccc}
1. & \bigg\{p \wedge \big[\sim(\sim\!p \vee q)\big]\bigg\} \vee (p \wedge q) && 1. & \text{Given} \\
2. & \bigg\{p \wedge \big(p\: \wedge \sim\!q\big)\bigg\} \vee (p \wedge q) && 2. & \text{DeMorgan} \\
3. & \bigg\{(p \wedge p)\: \wedge \sim\! q\bigg\} \vee (p \wedge q) && 3. & \text{Assoc.} \\
4. & (p\: \wedge \sim\!q) \vee (p \wedge q) && 4. & s \wedge s \,=\,s \\ \\
5. & p \wedge (\sim\!q \vee q) && 5. & \text{Distr.} \\ \\
6. & p \wedge T && 6. & s \:\vee \sim\!s \,=\,T \\ \\
7. & p && 7. & s \wedge T \,=\,s \end{array}[/tex]
 

Joystar1977

Active member
Jul 24, 2013
119
Evgeny.Makarov in response to your question there aren't any logical equivalences that have to do with De Morgan's Laws in my textbook. In my textbook all it shows is a Truth Table proving De Morgan's second law and then these symbols in parentheses as follows:

( p ^ q) p V q

( p V q) p ^ q

There isn't anything else mentioning De Morgan's Laws. I will try to copy and paste from Microsoft Word so I can get the symbols correct when I write them down.

These equivalences, while correct, have nothing to do with De Morgan's law.

Could you say how many completed examples from your textbook or lecture notes that deal with proving equivalences like the one in post #1 have you seen and understood? Look specifically at applications of De Morgan's law. Then do the same for ~(~p \/ q), which is a subformula of (p ^ (~(~p V q))) V (p ^ q).

And please consider the notation suggestion in post #4 or use LaTeX because otherwise your formulas are hard to read.
- - - Updated - - -

Thanks Soroban for showing me this!

Hello, Joystar1977!



[tex]\begin{array}{cccccccc}
1. & \bigg\{p \wedge \big[\sim(\sim\!p \vee q)\big]\bigg\} \vee (p \wedge q) && 1. & \text{Given} \\
2. & \bigg\{p \wedge \big(p\: \wedge \sim\!q\big)\bigg\} \vee (p \wedge q) && 2. & \text{DeMorgan} \\
3. & \bigg\{(p \wedge p)\: \wedge \sim\! q\bigg\} \vee (p \wedge q) && 3. & \text{Assoc.} \\
4. & (p\: \wedge \sim\!q) \vee (p \wedge q) && 4. & s \wedge s \,=\,s \\ \\
5. & p \wedge (\sim\!q \vee q) && 5. & \text{Distr.} \\ \\
6. & p \wedge T && 6. & s \:\vee \sim\!s \,=\,T \\ \\
7. & p && 7. & s \wedge T \,=\,s \end{array}[/tex]
 

topsquark

Well-known member
MHB Math Helper
Aug 30, 2012
1,140

7. & p && 7. & s \wedge T \,=\,s \end{array}[/tex]
I know it's pretty obvious but I just want to make certain: [tex]\text{~} s \wedge s = T[/tex] represents "Tautology." Is this correct?

-Dan

Addendum: Whoops! I didn't see all of Joystar1977's last post. I didn't mean to butt in.
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,502
I know it's pretty obvious but I just want to make certain: [tex]\text{~} s \wedge s = T[/tex] represents "Tautology." Is this correct?
No, in step 6 Soroban has $s\lor\neg s=T$, which means that the truth value of $s\lor\neg s$ is T (Truth) regardless of the truth value of $s$. By definition, $s\lor\neg s$ is a tautology.