edited by
9,204 views
29 votes
29 votes

Indicate which of the following well-formed formulae are valid:

  1. $\left(P\Rightarrow Q\right) {\wedge} \left(Q \Rightarrow R\right) \Rightarrow \left(P \Rightarrow R\right)$
  2. $\left(P\Rightarrow Q\right) \Rightarrow \left( \neg P \Rightarrow \neg Q\right)$
  3. $\left(P{\wedge} \left(\neg P \vee  \neg Q\right)\right) \Rightarrow Q$
  4. $\left(P \Rightarrow R\right) \vee \left(Q \Rightarrow R\right) \Rightarrow \left(\left(P \vee Q \right)  \Rightarrow R\right)$
edited by

6 Answers

Best answer
44 votes
44 votes

Ans is (A)

$\Rightarrow$ To make a formula valid it must be true for all cases (Tautology)


  1. $\underbrace{(P\implies Q)\wedge (Q\implies R)}_{T}\implies \underbrace{(P\implies R)}_{F}$ :To make it invalid
    assume:
    $\underbrace{P}_{T}\implies \underbrace{R}_{F} :\;F$
    Now,
    $\underbrace{\underbrace{(P\implies Q)}_{T}\wedge\underbrace{ (Q\implies R)}_{T}}_{T}$

    We know,
    $\hspace{2 cm} P=T; \;R=F$

    ${\underbrace{(T\implies Q)}_{T}}_{\large\color{Red}\searrow}\wedge\; {\underbrace{(Q\implies F)}_{T}}_{\large\color{RED}\searrow}$
    ${\qquad\qquad Q\ne F;\\ \qquad\text{it should be T.}}{\qquad\qquad Q\ne T;\\ \qquad\text{it should be F.}}$

    Since ,value of Q is ambiguous. it tells that our original assumption of $P=T ;R=F$ and $P\implies R:F ;\text{ is wrong.}$
    $T\implies F$ is not possible. Hence its valid.
     
  2. $\underbrace{(P\implies Q)}_{T}\implies \underbrace{(\neg P\implies \neg Q)}_{F}$ ; to make it invalid the case must hold.
    So,  $\underbrace{\neg P}_{T}\implies \underbrace{\neg Q}_{F}$; for this to be false.
    $\therefore P=F;Q=T$ which makes $P\implies Q:T$
    So,  $T\implies F$ does hold. Hence invalid.
     
  3. ${\quad \underbrace{(P\implies R)\vee (Q\implies R)}_{T}}\implies {\underbrace{((P\vee Q)\implies R)}_{F}}$
        $\hspace{3 cm}{\large\color{Red}\downarrow} \hspace{5 cm}  {\large\color{Red}\downarrow}$
        $\underbrace{(P\implies R)}_{T}\vee \underbrace{(Q\implies R)}_{T} \hspace{2 cm} \underbrace{(P\vee Q)}_{T}\implies \underbrace{R}_{F}$
    or,
    $(P\implies F)\vee (Q\implies F)\quad [\because R=F]$
    assume  $P=T$ and $Q=F$ which makes the above $T$ (LHS) and $F$ (RHS)
    So, again $T\implies F$ hold. Hence invalid.
edited by
20 votes
20 votes
To prove any wff valid or tautology try to use this analogy.

Since implication A->B is FALSE only when A=T and B=F.So to prove any implication is valid or not try to get TRUE->FALSE if we succeed then it is not valid,if we not then wff is valid.

So for option A

substitute P=T and R=F

RHS P->R become FALSE

LHS (P->Q)^(P->R)

To get true here we need T^T so substitute Q=T which makes P->Q TRUE and P->R FALSE so T^F=F which makes LHS=FALSE.

Hence we are unable to get T->F which proves wff given in OPTION A is valid.

NOTE: we can use similar kind of logic to prove contradiction.
1 votes
1 votes
Create a logic table for each of the given formula and check if we are getting true everywhere.
Answer:

Related questions

20 votes
20 votes
3 answers
2
makhdoom ghaya asked Nov 22, 2016
9,026 views
Let $R_{1}$ and $R_{2}$ be regular sets defined over the alphabet $\Sigma$ Then:$R_{1} \cap R_{2}$ is not regular.$R_{1} \cup R_{2}$ is regular.$\Sigma^{*}-R_{1}$ is regu...
46 votes
46 votes
2 answers
3
makhdoom ghaya asked Nov 22, 2016
12,497 views
It is undecidable whether:An arbitrary Turing machine halts after $100$ steps.A Turing machine prints a specific letter.A Turing machine computes the products of two numb...
27 votes
27 votes
2 answers
4
makhdoom ghaya asked Nov 22, 2016
16,674 views
Recursive languages are:A proper superset of context free languages.Always recognizable by pushdown automata.Also called type $0$ languages.Recognizable by Turing machine...