GATE CSE 1991 | Question: 03,xii

Question

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:

• A. Both $F_1$ and $F_2$ are tautologies
• B. The conjunction $F_1 \land F_2$ is not satisfiable
• C. Neither is tautologous
• D. Neither is satisfiable
• E. None of the above

Comments

When taken individually F1 and F2 are tautologies, but when taken together it is a contingency.

---

Answer by Deepak Sir . Very very important to understand the intricacies if this question.

---

Find correct logic, correct answer for this question here:

https://gateoverflow.in/526/Gate-cse-1991-question-03-xii?show=374238#a374238

Answer 1

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 

Comments

@Pranavpurkar

 

1. False because  both can be contradiction at the same time.

I guess this is covered in “If A∧B is contradiction, then A is contradiction or B is contradiction”.

A or B includes “both” can be contradiction.

---

Let $A,B$ be two propositional formulas.

If $A \wedge B$ is Contradiction then $A,B$ both can be contingencies as well.

For example, $A = P \oplus Q$, $B = P \odot Q$, then $A \wedge B$ is Contradiction.

https://www.youtube.com/watch?v=0TvPUMrtQ_8 

---

.

Answer 2

answer is option (B).

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

Comments

How ?

---

sir i know there is many way to solve a question i used to sole such type of question by making table. but when i used to solve this i am getting f1^f2 are satisfiale .can you correct me.??

---

What is difference between option B and option D

Answer 3

" 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

Comments

Here, F1 and F2 can take any three values respectively…

T F

F T

F F

because all resulting the F1 ∧ F2 being false. So, we don’t care about the right side of implication.

---

“F1∧F2 is False means F1=False and F2=False” Here instead of F1 and F2 both are false, use OR. Either F1 can be false or F2 can be false.

---

Written incorrect for all options and then ….B is the answer ???how?

Answer 4

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$

 

Comments

Thanks a lot @subbus

---

nice approach😀

---

really love these type of concept😘ty