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

Let $p, q, r$ and $s$ be four primitive statements. Consider the following arguments:

$P:  [(¬p\vee  q) ∧ (r → s) ∧ (p \vee  r)] → (¬s → q)$
$Q:  [(¬p ∧q) ∧ [q → (p → r)]] → ¬r$
$R:  [[(q ∧ r) → p] ∧ (¬q \vee  p)] → r$
$S:  [p ∧ (p → r) ∧ (q \vee  ¬ r)] → q$

Which of the above arguments are valid?

  1. $P$ and $Q$ only
  2. $P$ and $R$ only
  3. $P$ and $S$ only
  4. $P, Q, R$ and $S$
in Mathematical Logic by Boss (16.3k points)
edited by | 2.4k views
Admins, please change the or symbol in expression P look like an OR symbol.It looks more like literal 'v'

6 Answers

+30 votes
Best answer

An argument form is valid if no matter what propositions are substituted for the propositional
variables in its premises, the conclusion is true if the premises are all true.
i.e. $\left( p_1 \wedge p_2 \wedge \ldots \wedge p_n \right ) \rightarrow q$ is a tautology.

$$\begin{array}{l|l}\hline \text{$P:\large{\neg\color{Red}\not {p}\vee q}$}  & \text{$Q:\large{\neg{p}}$}\\ \text{$\quad \large{\neg\color{Red}\not {r}\vee s}$} & \text{$\large{\quad \quad\color{Red}\not {q}}$}\\ \text{$ \large{\quad  \underline{\color{Red}\not {p}\vee \color{Red}\not {r}}}$}& \text{$\large \quad {\underline {\neg\color{Red}\not {q}\vee(\neg {p}\vee r)}}$}\\ \text{$\large\qquad\;\; s\vee q$   also, $\large\neg s\to q$ $\large\color{Green}\checkmark$} & \text{$\qquad\quad\large\ \neg {p}\vee r$}\\ & \text{$\color{Red} {\large \neq \neg r}$} \\\hline
\text{$R: \large{\neg(q\wedge r)\vee p\\ \neg{q}\vee p}$$\large{ \;\;=\underline{\neg{q}\vee \neg{r}\vee {p}\\ \;\neg {q}\vee p}\\ \qquad  {p}\vee\neg{q}\vee \neg {r}}$} & \text{$S:\large{\color{Red}\not {p}\\\neg\color{Red}\not {p}\;\vee \color{Red}\not {r}\\ \underline{q \vee \neg\color{Red}\not {r}}}$}\\ & \text{$\large\qquad\;\; q$  $\qquad\large\color{Green}\checkmark$}\\ \text{$\color{Red} {\large \neq  r}$}\\\hline   \end{array}$$

Correct Answer: $C$

by Boss (30.5k points)
edited by
can u explain how we cut the terms. i am not knowing this method. either explain or give me a link. it will be thnkful.
what i learned from this . whenwver there is a and , change the line. in the same line only or terms are allowed.

cut down everything that is in complemented from also. and then just rite the common remaining terms. ,.

any other thing to keep in mind.
please give detailed explanation
it uses resolution principle
how to cut the term... plzz explain anyone
@ Billy,It uses resolution principle-

If you have disjunction of literals given in the premises you can cut out the literals which are in true as well as complemented form in two different premises.

example- the various premises are:




q and r can be cancelled and p is the conclusion.

Refer Keneth Rosen.
need to change best answer
I don't think this approach is right because even though we get one valid conclusion by using the resolution principle, there can be other valid conclusions too. For example, in S option, r can also be a conclusion. But, if you go by only the resolution principle, you will get q and mark S as wrong option. Correct me if I'm wrong.
@Vishal How can you say that r can also be a conclusion in S option ?
Can you solve this same using rules of inferences
Can P⟹(Q∨R))⟹((P∧Q)⟹R) be solved using resolution?
If you don't found it easy to solve using resolution. Then use boolean logic minimization and try to get 1(TRUE) for validation.

eg:- $P:[(\neg P \vee Q)\wedge (r\rightarrow S)\wedge (P\vee R)] \Rightarrow (\neg S \rightarrow Q)$

$\equiv \overline{(\bar P+Q)(\bar R+S)(P+R)}\;+(\bar{\bar S}+Q)$

$\equiv (P\bar Q)+(R\bar S)+(\bar P \bar Q)+(S+Q)$

$\equiv \bar Q(P+\bar P)+(R \bar S)+(S+Q)$

$\equiv \bar Q + R\bar S + S+Q$

$\equiv TRUE \;(1)$
Why to complicate things by boolean logic and all. Just try to derive T-> F case using assignment of truth values. One value is already known of the RHS (F) To prove T->F .If you cannot generate such case then statement is valid.
+17 votes

P:  [(¬p v q) ∧ (r → s) ∧ (p v r)] → (¬s → q)

This must be valid ( All options contains P) No need to evaluate.

R:  [[(q ∧ r) → p] ∧ (¬q v p)] → r ->

This is invalid, Put q = False, P= True, R = False to derive "False" result !

S:  [p ∧ (p → r] ∧ (q v ¬ r)] → q This is valid !



P-> r



q v ¬ r



So Answer ->

3) P and S only
by Boss (41.1k points)
Good approach of option elimination..?
+3 votes
According to me, using the rules of inference like resolution principle to come up with valid conclusions is tricky since there can be multiple valid conclusions. Instead, using proof by contradiction would be the most accurate way to tackle this question. To prove that a given statement is valid (i.e. a tautology), assume that it is not a tautology. It can only be possible if the right side is false and left side is true. Using this assumption, try to put truth values of proposition variables so as to make the left side true. If it is impossible to make left side true, then the statement is invalid. Otherwise, it's valid.

Another way is to convert the statement into a combination of negation, conjunction and disjunction operators and then simplify the statement as much as possible so that the end result is no more minimisable. If the result is a T, then it is valid. Else, it is invalid.

One more way is to draw the truth table of the statement. If all the values are true, then the statement is valid. Otherwise, it is not.

The last two methods are time-taking. The first method is the best.
by Active (1.7k points)
In simple terms assume conclusion to be false.

Case 1(valid): if conclusion is true and you have assumed it false then atleast one premises will be false.

Case 2 (invalid): If conclusion if false and you assume it's opposite, and still you are able to make all premises true, then it is invalid

 If it is impossible to make left side true, then the statement is invalid. Otherwise, it's valid.

this one is wrong  

+2 votes
let p->q is conditional proposition here p and q are compound propositions itself
Arguments to be valid if all combinations have to be tautology ( like T->T, F->T, F->F ) and its invalid if it have fallacy ( T->F )
if we somehow get this fallacy (T->F) then an argument is invalid
for options P and S u don't get any such combinations for T->F so P and S are VALID.
for option Q : if we put p=F,q=T,r=T then we get T->F so it is INVALID
for option R : if we put p=F,q=F,r=F then we get T->F so it is INVALID

so Ans is C.
by Active (2.6k points)
+1 vote
Option 3

Both P and S are valid... I used truth table
by Active (2.6k points)
0 votes

Answer is option C.


by Active (1.9k 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,807 questions
54,727 answers
79,845 users