in Mathematical Logic retagged by
580 views
5 votes
5 votes
Let $P$ be a compound proposition over $4$ propositional variables: $a,b,c,d$.
We know that for a compound proposition over $n$ propositional variables, we have $2^n$ rows in the truth table.
Every row of truth table of $P$ is called an Interpretation of $P.$
A row in truth table of $P$ is called “model” iff $P$ is true for that row.
Let $P$ be $"a \rightarrow b"$.
How many models are there for $P$ ?
in Mathematical Logic retagged by
580 views

3 Answers

8 votes
8 votes
Best answer

TLDR;)

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

Notice that, 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=True$ ---- 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=False$ ---- 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$?

Becasuse, 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$. 

selected by

1 comment

Thnks a lot for such a detailed explanation.Cleared all my doubts.👍
1
1
8 votes
8 votes
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.
reshown by
0 votes
0 votes
As per question P is a compund proposition of 4 variables. So the number of rows that are possible for these number of variables is 16. Now if any row is called model iff P is true for that row and we know that  P is a->b. A->B is false when A is true and B is false and so for the rest of the variables we don't care what their truth values are. If we draw the truth table of the variable and the model p then it will be false only when A is true and B is false. So, if you draw with this truth values  then there would be only 4 cases out of 16 that are possible where A is true and B is false. So this is called model for remaining 12 cases. Hence, 12 is the answer.
Answer:

Related questions