GO Classes CS 2025 | Weekly Quiz 1 | Propositional Logic | Question: 12

Answer 1

TLDR;)

Just adding the answer incase someone doesn’t understand how to approach it.

Notice that, P is a compound proposition in 4 variables, and finally P is defined as “a → b”. So naturally it might confuse us that it must just depend on a and b only; so we might argue that the answer should be 3, since only 3 rows are TRUE for a 2 -variable implication statement. This thought process is Wrong, because it is possible that a proposition is dependent on four variables yet some variables may not appear in the final formula for the compound proposition(you can relate this to FDs and candidate keys in DBMS or Minimized SOPs in Digital Logic).

Now back to the question, with $n$ variables we have $2^n$ rows. So, with 4 variables we have 16 rows, pretty easy right! Let’s now analyse a bit on the truth value of P. For $a=True, b =True$, how many rows do we have? 4 rows(contemplate a bit for now, the answer is provided below). So, for each truth value combination of $a \& b$, we have four rows. The following are the 4 cases with $P: a \implies b $, considering the truth values of $a$ and $b$.

• For $a=True$ and $b=True$, $P=True$ ---- So, $P=True$ for 4 rows
• For $a=True$ and $b=False$, $P=False$ ---- So, $P=False$ for 4 rows ---- (Mind this)
• For $a=False$ and $b=True$, $P=True$ ---- So, $P=True$ for 4 rows
• For $a=False$ and $b=True$, $P=True$ ---- So, $P=True$ for 4 rows

We are done with all the 16 rows in the compound proposition, with the above four cases. 

We see that, out of all the 16 rows, only 4 rows are False and the rest 12 rows are all True. So, $P$ is $True$ for 12 rows. Hence, as per the definition of model given in the question, we have 12 models in the Truth table of the compound proposition $P$.

** Why 4 rows for each case of $a$ and $b$?

Because, for each case of $a$ and $b$, we have the following cases of $c$ and $d$.

• $c=True$, $d=True$
• $c=True$, $d=False$
• $c=False$, $d=True$
• $c=False$, $d=False$. So, we have 4 rows for each case of $a$ and $b$.

CAUTION: Why I didn’t take $c$ and $d$’s cases for the truth value of the compound proposition $P$? Because, P’s truth value can be found out without using the truth values of $c$ and $d$, as $P$ is defined $a\implies b$. 

Comments

Thnks a lot for such a detailed explanation.Cleared all my doubts.👍

Answer 2

P is model iff a implies b is true. Let’s think in what cases is that possible. 3 cases viz, both a and b true, both false or a false and b true. Ok, we have c and d which are free to take any truth values. So, there will be 2^2 = 4 combinations. Each of the 3 cases (of a,b) have 4 combinations (of c,d). Thus total models = 3 * 4 = 12.

Answer 3

Here we have the given expression as $a→ b$ and there is no constraint on $c$ and $d$ 
Let call the given expression as P:$a→ b$
We need P to be true which happens in three cases 

• $a$ is T and $b$ is F
• $a$ is F and $b$ is T
• $a$ is F and $b$ is F
   

So we got three possibilities here but for the rest $c$ and $d$ we have 2 posibilities for each one of them
By multiplication theorem of combinatorics we will get → 3 * 2 *2 = 12 possibilities 

Correct answer will be 12.

Answer 4

No. of combinations of (a,b) for a → b to be true is 3. (Set A = {(T,T), (F,T), (F,F)} => |A| = 3)

And no. of all possible combinations of (c,d) is 4. (Set B = {(T,T), (T,F), (F,T), (F,F)} => |B| = 4)

So, total no. of combinations of (a,b,c,d) for a → b to be true is 3x4=12. (no. of elements in AxB = |AxB| = |A| x |B| = 12)