The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+9 votes

Which of the following propositions is a tautology?

  1. $(p \vee q) \rightarrow p$
  2. $p \vee (q \rightarrow p)$
  3. $p \vee (p \rightarrow q)$
  4. $p \rightarrow (p \rightarrow q)$
asked in Mathematical Logic by Veteran (52.1k points)
retagged by | 1k views

3 Answers

+6 votes
Best answer

$A. \ \ (p \vee q) \rightarrow p$
$\quad \quad \equiv \ \ \neg(p \vee q) \vee p$
$\quad \quad \equiv \ \ (\neg p \wedge \neg q) \vee p$
$\quad \quad \equiv \ \ (\neg p \vee p)\wedge(\neg q \vee p)$
$\quad \quad \equiv (p \vee\neg q)$

$B. \ \ p \vee (q \rightarrow p)$
$\quad \quad \equiv \ \ p \vee (\neg q \vee p)$
$\quad \quad \equiv \ \ (p \vee p)\vee\neg q$
$\quad \quad \equiv p \vee\neg q$

$C. \ \ p \vee (p \rightarrow q)$
$\quad \quad \equiv \ \ p \vee (\neg p \vee q)$
$\quad \quad \equiv \ \ ( p \vee \neg p) \vee q$
$\quad \quad \equiv \ \ T \vee q$
$\quad \quad \equiv \ \ T$

$D. \ \ p \rightarrow (p \rightarrow q)$
$\quad \quad \equiv \ \ p \rightarrow (\neg p \vee q)$
$\quad \quad \equiv \ \ \neg p \vee(\neg p \vee q)$
$\quad \quad \equiv \ \ (\neg p \vee\neg p) \vee q$
$\quad \quad \equiv \ \ \neg p \vee q$

Hence, Option(C) $p \vee (p \rightarrow q)$.

answered by Boss (40.9k points)
edited by
+15 votes
C) P OR (P -->Q) = P OR (NOT P OR Q)

                          =(P OR NOT P) OR Q                  Associativity rule

                          =T OR Q                                     

answered by Active (2.6k points)
Since only p and q are there, we can also give 1/0 to them and see that all other options can give F.
+3 votes

p v (p->q) can be written as

p+(p' + q)




hence  it's a tautology
answered by (67 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,811 questions
54,533 answers
75,585 users