Engineering-Mathematics
February 10, 2024Question 16659 – HCU PHD CS JUNE 2021
February 10, 2024GATE 1990
| Question 18 |
Choose the correct alternatives (More than one may be correct).
Indicate which of the following well-formed formulae are valid:
| (P⇒Q) ∧ (Q⇒R) ⇒ (P⇒R) | |
| (P⇒Q) ⇒ (¬P⇒¬Q) | |
| (P∧(¬P∨¬Q)) ⇒ Q
| |
| (P⇒R) ∨ (Q⇒R) ⇒ ((P∨Q)⇒R) |
Question 18 Explanation:
To prove any well formed formula 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 well formed formula is valid.
So, for option (A),
Substitute P=T and R=F
RHS:
P→R becomes 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 well formed formula given in option (A) is valid.
Similarly, try for (B), (C), (D). We get T → F in these options which says these well formed formula is invalid.
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 well formed formula is valid.
So, for option (A),
Substitute P=T and R=F
RHS:
P→R becomes 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 well formed formula given in option (A) is valid.
Similarly, try for (B), (C), (D). We get T → F in these options which says these well formed formula is invalid.
Correct Answer: A
Question 18 Explanation:
To prove any well formed formula 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 well formed formula is valid.
So, for option (A),
Substitute P=T and R=F
RHS:
P→R becomes 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 well formed formula given in option (A) is valid.
Similarly, try for (B), (C), (D). We get T → F in these options which says these well formed formula is invalid.
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 well formed formula is valid.
So, for option (A),
Substitute P=T and R=F
RHS:
P→R becomes 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 well formed formula given in option (A) is valid.
Similarly, try for (B), (C), (D). We get T → F in these options which says these well formed formula is invalid.