Question

Logic and Discrete Math Problem

I missed a Day of my discrete math class, and we covered proof by contrapositive.

-1. V => Y
-2. X
-3. W v ~Z
-4. X => Z
------------
(W => V) => Y

How would I go about proving that this is a valid proposition?

Answer 1

I dont even follow the levels tbqh hahaha

Answer 2

is that supposed to be -> like arrow?

Answer 3

-> is implies

Answer 4

yeah, i wasn't sure how to type it

Answer 5

just making sure there's some notation I still have to learn out there

Answer 6

contrapositive: if you have p=>q and you have ~q then you have ~p IIIRC

Answer 7

Ya but what are all those levels saying???

Answer 8

Each letter is a proposition of some kind (generic). The levels are more complex propositions containing the simple ones. They are basically just givens. The line separates the givens from the conclusion. If that makes any sense.

The objective is to prove through contrapositive that this is a valid statement.

Answer 9

so what if it is not valid statement?

Answer 10

I would assume you have to prove that as well? I missed the class, and I'm just not grasping how to work these problems out.

Answer 11

I am still trying to understand the statements
I just realized a few things
v would be ∨

Answer 12

Yeah in this problem V is not ∨, but instead a proposition. I probably should have just changed the letters

Answer 13

and the lower case v is ∨

Answer 14

order of operations
and then set up your truth table ?

Answer 15

We aren't supposed to use truth tables with these

Answer 16

Im having difficulties going about this maybe I am missing smth
This is how I am reading the various levels
#1 If V then Y
#2 There exists X
#3 W and ~Z
#4 If X then Z

And somehow using this information we deduce that If W then V then Y

I just dont seem to see the string pulling through all this

Answer 17

Maybe I am interpreting the levels/info given incorrectly

Answer 18

You are interpreting it correctly, except in #3 it is W or ~Z

Answer 19

-1. V => Y
-2. X
-3. W v ~Z
-4. X => Z

Answer 20

from 2) and 4) we can deduce :=

5) Z

Answer 21

from 3) and 5) we can deduce :=

6) W

Answer 22

see if that looks okay so far

Answer 23

next u just need to take the contrapositive of the statement u wanto prove and prove it using above hypothesis

Answer 24

statement : (W => V) => Y

if this statement is true, the contrapositive of this statement is also true :

contrapositive statement : ~Y => ~(W=>Y)

Answer 25

keep going..

Answer 26

@ganeshie8 contrapositive statement : ~Y => ~(W=>V)?

Answer 27

ahh typo thnks for correcting :)

Answer 28

contrapositive statement : ~Y => ~(W=>V)

Answer 29

show that this statements yields TRUE using the given/deduced 6 prior statements

Answer 30

Ohhh and ~(W=>V) can be written as W and ~V ( don't know how to type the symbol on here) correct?

Answer 31

oh u wanto simplify, nice :)

Answer 32

\(\neg (W \implies V)\)

\(\neg (\neg W \lor V)\)

\( W \wedge \neg V)\)

Answer 33

u may use below to show these in latex :-
\lnor
\wedge
\neg
\implies

Answer 34

Ok I actually get this now! Just one more question. When formatting these proofs, how do I make note that I simplified? do i write it as an assumption?

Answer 35

actually it depends on ur professor - if you havent worked w=>v <=> w' or v previously, then i feel its not a good idea to simplify

Answer 36

boolean simplification and truth table are same.
since you're saying truth tables are not allowed, i feel boolean simplification is also not allowed

Answer 37

u may try something like below :=

contrapositive statement : ~Y => ~(W=>V)

right hand side : ~(W => V)
~(TRUE => V) ----- from (6)
~V

that means ~Y => ~V

from (1), this is true
QED

Answer 38

see if that looks okay.. .

Answer 39

notice that we did not use any "boolean simplification" in the above argument