Log In
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
13 votes
Show that the conclusion $(r \to q)$ follows from the premises:

$p, (p \to q) \vee (p \wedge (r \to q))$
in Mathematical Logic
retagged by

6 Answers

15 votes
Best answer
$P_1 :p$

$P_2: (p → q) ∨ (p ∧ (r → q) )$

$P_1 \wedge P_2 \rightarrow   (r \rightarrow q)$

$\equiv [p \wedge [(\neg p \vee q) \vee (p\wedge \neg r \vee (p \wedge q))]  \rightarrow (r \rightarrow q)$
$\equiv [p \wedge [\neg p \vee q \vee  (p\wedge \neg r) \vee  (p\wedge q)]] \rightarrow (r \rightarrow q)$
$\equiv [ (p\wedge \neg r) \vee (p\wedge q)] \rightarrow (r \rightarrow q)$
$\equiv [ (\neg p\vee r )\wedge (\neg p\vee  \neg q)\vee \neg r \vee q] $
$\equiv [ \neg p\vee  (r\wedge \neg q) \vee \neg r \vee q]$
$\equiv [\neg p \vee \neg q \vee \neg r \vee q] $
$\equiv [\neg p \vee  (q \vee \neg q) \vee \neg r] $
$\equiv 1$ (Tautology)

Hence, proved.

edited by
Is it a correct solution ??
nice approach @ prashant


how did this become this [(P∧¬R)∨(PQ)]→(RQ) please explain me this step

As this part P∧[(¬PQ) is modus ponens and should reduce to Q but Q is not in the wff


if i solved this question by making  truth table then all are true only one value is going to false can you explain where i am going to wrong ???
you should post your table then anyone can help u

this is my solution.

in complete table it should have one more column i.e.

[p∧((p→q)∨(p∧(r→q)))]->(r->q) and u will get all T
12 votes

=> (~p V q ) V (p ∧ (~r V q))

=> (~p V q) V ( (p∧ ~r) V (p ∧ q) )

=> ( 0 V q ) V ( (1∧ ~r) V (1 ∧ q))

=> q V ( ~r V q )

=> ( ~r V q )

=> (r->q)
you have solved it by taking p=1, it is necessary to take p=0 and solve it again after that you can declare it is always true
9 votes
Using Distributive law, (p→q) ∨ (p ∧ (r→q)) = ((p→q) ∨ p) ∧ ((p→q) ∨ (r→q))

Using Simplification, (p→q) ∨ (r→q) is a conclusion.

(p→q) ∨ (r→q) = (¬p ∨ q) ∨ (¬r ∨ q) = ¬p ∨ q ∨ ¬r = ¬p ∨ (r→q)

Using premises p and ¬p ∨ (r→q) and applying Disjunction Syllogism, the conclusion is (r→q).
It is Modus Ponens and not disjunctive syllogism



$p\rightarrow \left ( r\rightarrow q \right )$


$r\rightarrow q$
1 vote
If we look at it carefully it is given that if premises are true then if r is true then q must be true.

We have data p is true and r is true(as we  want to prove it)

now we will try to prove that r implies q is not the solution. If you substitute p,r is true then truth value of second premise complete depend upon truth value of q. so it must be true and hence the conclusion.
1 vote
To derive the conclusion we must assume that the premises are true


0 votes
Some n number of premises implies a conclusion means that, If all the n premises are true then conclusion is true as well.
 p  and (p→q)∨(p∧(r→q)) both premises will be true only for below truth value assignments
(p=T,r=F,q=T), (p=T,r=T,q=T), (p=T,r=F,q=F)

none of the above truth value assignments has r=T,q=F  hence , If both the premises(p  and (p→q)∨(p∧(r→q)) ) are true then  (r→q) is true as well.( Note: (r→q) is false for only r=T,q=F truth value assignment)

Related questions

9 votes
3 answers
Show that proposition $C$ is a logical consequence of the formula$A\wedge \left(A \to \left(B \vee C\right)\right) \wedge \left( B \to \neg A\right)$using truth tables.
asked Sep 30, 2014 in Mathematical Logic Kathleen 1.4k views
8 votes
3 answers
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 Sep 24, 2014 in Mathematical Logic Kathleen 921 views
4 votes
1 answer
Give a minimal DFA that performs as a $\mod - 3,\;$ $1$'s counter, i.e. outputs a $1$ each time the number of $1$'s in the input sequence is a multiple of $3$.
asked Nov 15, 2016 in Digital Logic makhdoom ghaya 917 views
27 votes
6 answers
What is the generating function $G(z)$ for the sequence of Fibonacci numbers?
asked Nov 15, 2016 in Combinatory makhdoom ghaya 4.4k views