Question

show that the statement (~p V q) ^ (p^~q) is a logical contradiction

Answer 1

Have you been taught how to do truth tables?

Answer 2

no

Answer 3

Well, they make the problem easier, but you can still do it without them. What we need to do, is break the problem up into 4 different cases.

Case 1: p=True, q=True.
Case 2: p=True, q=False.
Case 3: p=False, q=True.
Case 4: p=False, q=False.

I'll work through the first case.

Answer 4

ok

Answer 5

ive seen them in my text book but i am not sure how to do one

Answer 6

Suppose p=True, and q=True.

Then (~p V q) is the same as (False OR True), which is True, since q is True.
Also, (p ^ ~q) is the same as (True AND False), which is False, since q and p have different truth values (one is true, the other is false).

Thus, we end with True AND False, which by the same reasoning, is False. To do the rest, you need to go through each case, and show that you always end with False.

Can you try to do Case 2 by yourself?

Answer 7

if you were gong to use a truth table

set it up like this: \[\begin{array}{|c|c|c|c|c|}\hline p&\neg p&q&\neg q&\neg p\lor q&p\land \neg q&(\neg p\lor q)\land(p\land \neg q)\\\hline T&&T\\T&&F \\F&&T\\T&&F\\\hline\end{array}\]

Answer 8

@KingGeorge i am not even sure where to start...

Answer 9

Alright. So start with Case 2: p is True, and q is False. Now let's take it one step at a time. What is ~p?

Answer 10

false

Answer 11

right. Now, ~p is False, and q is true.

What is ~p OR q?

Answer 12

false

Answer 13

Not so fast. Remember that q is True, and since you only need one thing to be true in an OR statement, ~p OR q is actually True.

Answer 14

Let's go to the next step. What is ~q?

Answer 15

I dont get it..

Answer 16

true

Answer 17

Alright, let's take a step back, and look at ~p OR q again. For (~p OR q) to be true, either ~p is True, or q is True. Since q is True, (~p OR q) is True.

Does this make more sense?

Answer 18

i guess

Answer 19

Alright, stop me if you start to not understand anything.

Now, q is True. So what is ~q?

Answer 20

false

Answer 21

Precisely. Now, recall that p is True, and ~q is False. Can you tell me what (p AND ~q) is?

Answer 22

false

Answer 23

oops, I screwed up a bit.

Answer 24

Since we're assuming p is true, and q is False, ~q is True. So, (p AND ~q) is actually...?

Answer 25

trur

Answer 26

Oh wow. I screwed up earlier as well. You were correct in saying that (~p OR q) is False.

Anyways, then we only have (~p OR q) AND (p AND ~q) left. This simplifies to (False AND True). What is the truth value of this?

Answer 27

false true

Answer 28

Well, for (False AND True) to be True, either both need to be false, or both need to be true. Since neither is the case, (False AND True) is False. Now, I'm going to fill in the truth table that UnkleRhaukus kindly provided.

Answer 29

\[\begin{array}{|c|c|c|c|c|}\hline p&\neg p&q&\neg q&\neg p\lor q&p\land \neg q&(\neg p\lor q)\land(p\land \neg q)\\\hline T&F&T&F&T&F&F\\T&F&F&T&F&T&F \\F&T&T&F\\T&T&F&T\\\hline\end{array}\]
The first two lines correspond to Case 1 and Case 2 respectively.

Now we want to do Case 3. So p is False, and q is True. Can you tell me what (~p OR q) is?

Answer 30

true

Answer 31

right. what about (p AND ~q)?

Answer 32

false since q is true

Answer 33

Bingo. Then, what about (~p OR q) AND (p AND ~q)?

Answer 34

true

Answer 35

whops i set up the table with a mistake \[\begin{array}{|c|c|c|c|c|}\hline p&\neg p&q&\neg q&\neg p\lor q&p\land \neg q&(\neg p\lor q)\land(p\land \neg q)\\\hline T&F&T&F&T&F&F\\T&F&F&T&F&T&F \\F&T&T&F\\\color{red}F&T&F&T\\\hline\end{array}\]

Answer 36

Not quite. Remember that (~p OR q) is True, but (q AND ~q) is False. Since they're different truth values, (~p OR q) AND (p AND ~q) must be False.

Answer 37

Good catch^^

Answer 38

Now we just have the final case, where p is False, and q is False. Can you work through that, and tell me what you think (~p OR q) is, and what (p AND ~q) is?

Answer 39

false

Answer 40

@KingGeorge

Answer 41

What exactly are you saying is false?

Answer 42

~p or q

Answer 43

actually i mean that one is true since p is false

Answer 44

Right. what about (p AND ~q)?

Answer 45

true

Answer 46

Remember that p is False, and ~q is True, so (p AND ~q) would actually be False.

Answer 47

Now here's the very last step. What is (~p OR q) AND (p AND ~q)?

Answer 48

false and false?

Answer 49

Well the statement as a whole is False. Now, if we look at the truth table, we get a table that looks like this. \[\begin{array}{|c|c|c|c|c|}\hline p&\neg p&q&\neg q&\neg p\lor q&p\land \neg q&(\neg p\lor q)\land(p\land \neg q)\\\hline T&F&T&F&T&F&F\\T&F&F&T&F&T&F \\F&T&T&F&T&F&F\\F&T&F&T&T&F&F\\\hline\end{array}\]Since the entire last column is filled with F, we've shown that the original statement is a logical contradiction.

Answer 50

If you want to know some more about truth tables, and how to construct them, feel free to ask.

Answer 51

ok great so that truth table is the whole answer?

Answer 52

thanks so much! i have other questions but there not about truth tables

Answer 53

The truth table is a great way to show that you have a logical contradiction, and one of the easiest ways to see it directly.