GATE CSE 1995 | Question: 2.19

Question

If the proposition $\lnot p \to q$ is true, then the truth value of the proposition $\lnot p \lor \left ( p \to q \right )$, where $\lnot$ is negation, $\lor$ is inclusive OR and $\to$ is implication, is

• A. True
• B. Multiple Values
• C. False
• D. Cannot be determined

Answer 1

Cannot be determined.

From the axiom $\lnot p \to q$, we can conclude that $p \vee q$.

So, either $p$ or $q$ must be TRUE.

$$\begin{align}
&\lnot p \lor (p \to q)\\[1em]
\equiv& \lnot p \lor ( \lnot p \lor q)\\[1em]
\equiv&\lnot p \lor q
\end{align}$$

Since nothing can be said about the Truth value of $p$, it implies that $\lnot p \lor q$ can also be True or False.

Hence, the value cannot be determined.

Comments

We never say that a proposition can take multiple truth values. We say that the truth value of the proposition is unknown, or cannot be determined.

Saying that the proposition takes multiple values would mean that the proposition can be both True and False at the same time in the same sense. Which is not allowed according to the Law of Non-Contradiction.

---

In reference to Pragy's comment just wanted to give an example : 

EDIT: My interpretation was wrong. Anyone who has started to read, kindly ignore it.

S: This statement S is False.

If we take S as True that means "This statement S is False" is true which says S is False. But this contradicts with our assumption that S is True.

If S is False that means "This statement S is False" is false which says that S is False is a false statement which makes the value of S=True. Again S is getting multiple values.

This type of statements are not propositions and are called "Liar's paradox".

---

@MiNiPanda: You're slightly incorrect. The example you've shown is that of a statement which leads to a contradiction no matter what truth value you try, leading to a paradox and the statement is neither true, nor false. The paradox isn't that it takes multiple truth values, the paradox is that it takes $0$ truth values!

 

The only way for a statement to be both true and false is to have an inconsistent set of axioms. A set of axioms is said to be inconsistent if it leads to both proving and disproving a statement, that is, if any statement S can be shown to be both true and false under the given set of axioms. The thing with inconsistent axioms is that you can prove anything in them! No matter what the statement P is, you can show that P is both true and false. This makes inconsistent axiomatic systems utterly useless.

Sidenote: We don't know if maths is consistent or not! There are several axiomatic systems that are used across maths. Different axioms lead us to different styles of maths. We've proved some axiomatic systems (let's say $X$, $Y$) to be consistent, but for the proof, we need to be doing our proofs under some different axiomatic system (let's say $Z$). An example would be: the consistency of "Peano Arithmetic axiomatic system" can be proven under the "ZFC axiomatic system".  But now we need to prove the consistency of the $Z$, because if $Z$ is inconsistent, our proofs for the consistency of $X, Y$ are useless as you can prove anything in $Z$. One way of resolving this would be if some axiomatic system $B$ could prove its own consistency! Sadly, that's impossible. Godel's incompleteness theorems show that given an axiomatic system $B$, if $B$ is infact consistent, then it cannot prove its own consistency. If it can, then it would mean that $B$ is inconsistent! (Some constraints on $B$ are applicable.)

---

@Pragy Agarwal Thank you for correcting me. I understood the mistake I made.

 

---

I get it that it can be either T or F, but I was wondering what is meant by multiple valued (option B)

---

It is for people like me who drew the truth table and thought as the truth table has multiple values, B must be the answer.

Answer 2

given that $ \lnot p \to q$ is true

A proposition can have only 2 possible values namely true or false. Here  I feel “cannot be determined”(option D) is a more suitable answer than “multiple values”(option B) because propositional variables are similar to variables in programming which can have only one value at a time.

Answer 3

We need to look only for the GREEN case as in that only P’ → Q is true .

And for these three (GREEN) cases we have truth value for some cases and false for some cases .

So the value can’t be determined .

Answer will be D.

Comments

I get it that it can be either T or F, but I was wondering what is meant by multiple valued (option B)