edited by
8,619 views
40 votes
40 votes

If $F_1$, $F_2$ and $F_3$ are propositional formulae such that $F_1 \land F_2 \rightarrow F_3$ and $F_1 \land F_2 \rightarrow \sim  F_3$ are both tautologies, then which of the following is true:

  1. Both $F_1$ and $F_2$ are tautologies
  2. The conjunction $F_1 \land F_2$ is not satisfiable
  3. Neither is tautologous
  4. Neither is satisfiable
  5. None of the above
edited by

9 Answers

Best answer
31 votes
31 votes

The mistake many make for this question is to consider $F_i$ as a propositional variable But it is actually a propositional formula.

For example, $F_1 $ can be $p \wedge q$, where $p,q$ are propositional variables.

To understand the difference between propositional variable and propositional formula, watch the following video:

https://youtu.be/PT7yn-k-wiU

Note that $F_1,F_2,F_3$ are propositional formulae, over some set of propositional variables which are not given in the question.

$\color{red}{\text{Think about this question:}}$ How many rows are there in the truth table of expression $F_1 \wedge F_2 \rightarrow F_3 $?

If your answer is $8$ then you have not understood the difference between a propositional formula and propositional variable. So, watch the above video.

Number of rows in the truth table of expression $F_1 \wedge F_2 \rightarrow F_3 $ will depend on the propositional variables of these propositional formulas $F_i.$ If $F_i$ is propositional formula over 10 propositional variables then number of rows in the truth table of $F_1 \wedge F_2 \rightarrow F_3 $ will be $2^{10}.$

If each $F_i$ is propositional formula over propositional variables $p,q$ then number of rows in the truth table of $F_1 \wedge F_2 \rightarrow F_3 $ will be $4$ only, not 8.

For example, $F_1 = \neg p, F_2 = p \wedge q, F_3 = p \rightarrow q$ will satisfy all the conditions given in the question. But here, truth table of $F_1 \wedge F_2 \rightarrow F_3 $ will have only 4 rows, not 8, as the number of rows is determined by propositional variables, not by propositional formulas.

The $\color{red}{\text{Detailed Video Solution}}$ of this GATE question, MUST watch to get conceptual clarity:

https://youtu.be/85YwyEd_iaI

$\color{Purple}{\text{Some Variations:}}$

Variation 1: https://youtu.be/Gc40DqkSK3w

Variation 2: https://youtu.be/0TvPUMrtQ_8

Variation 3: https://youtu.be/Bw5At8oLeRY

So, answer will be Option B But the method of some students is Not correct.


NOTE that the mistake of Not understanding the difference between propositional variable and propositional formula can sometimes give you wrong answer and hence, negative marks.

For example, Consider the statements:

Let $\text{A, B}$ be two propositional formulas.

Which of the following assertions is/are true?

  1. If $\text{A} \wedge \text{B}$ is contradiction, then $\text{A}$ is contradiction or $\text{B}$ is contradiction.
  2. If $\text{A} \rightarrow \text{B}$ is tautology, then $\text{A}$ is contradiction or $\text{B}$ is tautology.
  3. If $\text{A} \leftrightarrow \text{B}$ is tautology, then either both $\text{A, B}$ are tautology or both $\text{A, B}$ are contradictions.
  4. If $\text{A} \wedge \text{B}$ is tautology, then both $\text{A, B}$ are tautology.

You can think about this question.

Answer is Only statement 4 is True. Statement 1,2,3 are Not true.

Solution here: https://gateoverflow.in/526/gate-cse-1991-question-03-xii?show=396158#c396158 

edited by
37 votes
37 votes

answer is option (B).

False $\rightarrow$ anything $=$ True, always

edited by
21 votes
21 votes
" F1∧F2→F3 and F1∧F2→∼F3 are both tautologies " it is possible in 2 cases
case 1) True→True
case 2) False→False/True
here F3 is in both F3 and ∼F3 form so only case 2) will apply
so F1∧F2 is False means F1=False and F2=False

(a). "Both F1 and F2 are tautologies" is INCORRECT

(b). "The conjunction F1∧F2 is not satisfiable" is INCORRECT becoz for being satisfiable atleast one possibility of F1 and F2 should be True

(c). "Neither is tautologous" is INCORRECT as both are Tautologies

(d). "Neither is satisfiable " is INCOORECT as both are Tautologies so also satisfiable

Hence correct ans is B
edited by
15 votes
15 votes

Given that $F_1 \land F_2 \rightarrow F_3$ and $F_1 \land F_2 \rightarrow \sim F_3$ are tautologies.

$\implies$ irrespecitve of the truth value of $F_1 ,F_2 ,F_3$ given 2 conditional statements are always $true$

solution

 

Answer:

Related questions

36 votes
36 votes
4 answers
4
Kathleen asked Sep 12, 2014
12,399 views
The total size of address space in a virtual memory system is limited by:the length of MARthe available secondary storagethe available main memoryall of the abovenone of ...