MHB Propositions/ Logical Equivalences

[Joystar77]

Let p and q be propositions. Use logical equivalences to show that

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

 

[Evgeny.Makarov]

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.

 

[Joystar77]

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]

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.

 

[Joystar77]

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]

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]

Hello, Joystar1977!

\begin{array}{c}\text{Let }p\text{ and }q\text{ be propositions.} \\<br /> \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}

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

 

[Joystar77]

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!



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

 

[topsquark]

7. & p && 7. & s \wedge T \,=\,s \end{array}[/tex]

I know it's pretty obvious but I just want to make certain: \text{~} s \wedge s = T 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]

I know it's pretty obvious but I just want to make certain: \text{~} s \wedge s = T 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.