Question

show that \(q \rightarrow p \equiv (p\rightarrow q)\rightarrow(q\rightarrow p)\) without using truth tables

Answer 1

Remember that \[p\rightarrow q\]Is just \[\neg p \vee q\]

Answer 2

so this becomes \[\neg(p \rightarrow q) \vee (q \rightarrow p)\]
then...
\[\neg (\neg p \vee q) \vee (\neg q \vee p)\]
then...
\[(p \wedge q) \vee (\neg q \vee p)\]
then...?

Answer 3

that, and some demorgan should do it

Answer 4

the third line should be
\[(p\land \lnot q)\lor (\lnot q \lor p)\]

Answer 5

oh yes

Answer 6

i still don't know what to do next though

Answer 7

i am thinking of how to do it with symbols
the first statement is evidently contained in the second, so visually you end up with \[\lnot q \lor p\] which is what you want

Answer 8

i cannot see how to achieve that...

Answer 9

i hate this crap, i think you have to distribute. let me see if i can do it with paper

Answer 10

on no, it is "absorption" law

Answer 11

seems i can use commutative here...
\[(\neg q \vee p) \vee (p \wedge \neg q)\]
then...

\[((\neg q \vee p) \vee p) \wedge ((\neg q \vee p)\wedge \neg q)\]

Answer 12

wait... it should be a wedge at the last part

Answer 13

\[((\neg q \vee p) \wedge ((\neg q \vee p) \vee \neg q)\]

Answer 14

hmm missed something again

Answer 15

\[((\neg q \vee p) \vee p) \wedge ((\neg q \vee p) \vee \neg q)\]
much better

Answer 16

so if i commute again...
\[(p \vee (\neg q \vee p)) \wedge (\neg q \vee (\neg q \vee p))\]
then...
\[(p \vee (\neg q \vee p)) \wedge ((\neg q \vee \neg q) \vee p)\]
then...
\[(p \vee (\neg q \vee p)) \wedge (\neg q \vee p)\]
hmm

Answer 17

ok i think i have it

Answer 18

then...
\[(p\vee(\neg q \vee p) \wedge \neg q) \vee (p\vee (\neg q \vee p) \vee p)\]
then...
\[(p\vee(\neg q \vee p) \wedge \neg q) \vee (p\vee p \vee(\neg q \vee p))\]
then...
\[(p\vee(\neg q \vee p) \wedge \neg q) \vee (p\vee (\neg q \vee p))\]
then...

Answer 19

what did you get?

Answer 20

this is what i did, and it took me a couple minutes to make the replacement
the distributive law say
\[p\lor (q\land r)\equiv (p\lor r)\land (p\lor q)\]
i wrote the first line as
\[(q\land r)\lor p\equiv (p\lor r)\land (p\lor q)\]
then i made the replacements \(p\) i replace by \(\lnot q \lor r\)
\(q\) i replace by \(p\) and \(r\) i replace by \(\lnot q\)

Answer 21

a direct substitution have me
\[(\lnot q \lor p \lnot q)\land (\lnot q \lor p \lor p)\]

Answer 22

crap i meant
\[(\lnot q \lor p\lor \lnot q)\land (\lnot q \lor p \lor p)\]

Answer 23

this is continued from what step?

Answer 24

nevermind

Answer 25

\[(p\land \lnot q)\lor (\lnot q \lor p)\]

Answer 26

\[(p\land \lnot q)\lor (\lnot q \lor p)\equiv (\lnot q \lor p\lor \lnot q)\land (\lnot q \lor p \lor p)\] by the substitutions i wrote above

Answer 27

ah i think im beginning to see what you mean

Answer 28

it took me a couple minutes to figure out the substitution to use, because i hate this crap
it is completely obvious that \(p\land \lnot q\) is entirely contained in \(\lnot q \lor p\) just like \(A\cap B\) is contained in \(A\cup B\)

Answer 29

the substitutions are always the hard part

Answer 30

try the substitution i wrote above, see if you get the same thing. i believe it will work, although i believe since it is so completely trivial that there is a snappier way to do it

Answer 31

yeah, that is the hard part