Propositional Equivalence Proof

83 Views Asked by At

I need some help getting to the next step of a problem I have been working on for about 2 hours now and can't solve. I would like to prove the following compound proposition: $(\neg q \wedge (p \vee p)) \rightarrow \neg q \equiv T$

So far I have not gotten past: $(\neg q \wedge p) \rightarrow \neg q\\ \neg(\neg q \wedge p) \vee \neg q\\ (q \vee \neg p) \vee \neg q\\$

From here I'm not quite sure what law to apply. I know I need to get the left side to probably be something like $q \vee \neg q \equiv T$ so I can apply the Complement Law.

As suggested I tried $q \vee \neg q \vee \neg p\\ T \vee \neg p\\$

But then I don't know what to do with the left over p. Here are the laws that I am using

2

There are 2 best solutions below

0
On BEST ANSWER

Let r be $(\neg q \wedge (p \vee p)) \rightarrow \neg q.$
Clearly r is true. Thus T -> r. As T is true, r -> T.
Both of those use the axiom p -> (q -> p).

0
On

Better to set up a truth table.

We know $p|p = p$

So $(!q \& (p | p)) = !q \& p$

p q  !q     !q & p  (!q & p) -> !q ≡ T
0 0   1        0          0  ->  1 = 1
0 1   0        0          0  ->  0 = 1
1 0   1        1          1  ->  1 = 1
1 1   0        0          0  ->  0 = 1