The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+8 votes
Show that the formula $\left[(\sim p \vee q) \Rightarrow (q \Rightarrow p)\right]$ is not a tautology.

Let $A$ be a tautology and $B$ any other formula. Prove that $(A \vee B)$ is a tautology.
asked in Mathematical Logic by Veteran (52k points)
edited by | 441 views

2 Answers

+11 votes
Best answer
a.$\left[(\sim p \vee q) \Rightarrow (q \Rightarrow p)\right] \\ = \sim (\sim p \vee q)) \vee (q \Rightarrow p) \\= (p \wedge \sim q) \vee (\sim q \vee p) \\= p \vee \sim q$.

Hence not tautology.

b.$(A \vee B) = T \vee B = T$
answered by Veteran (407k points)
edited by
+2 votes

To prove that it is not a tautology, we need to show this proposition should result as FALSE.

To make it as FALSE in implication (ex : x->y) , we need to prove x as TRUE and y as FALSE. Here x = (not p ) OR q and y = q->p.

To make y as FALSE , we need to definitely have q = TRUE and p = FALSE.If we give that , the resulting truth value of this proposition is FALSE.

answered by Loyal (7.3k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,530 questions
54,139 answers
71,068 users