Mathematical Logic

Question

Consider the following well formed formula:

 

The maximum number of rows in truth table of above formula which evaluate to true are ________.

$\left ( p\vee \sim q\vee\vee \sim r\vee s \right )\rightarrow t\vee \sim u$

__________________________________________________________________________

I got 5 and ans given 49

Comments

here only 4 case 

case 1 : when   t=1 then left hand side anything so 2'4=16

case 2 when u=0 then left hand side anything so again 2'4=16

case 3 when t=1 and u=0  then left hand side anything so 2;4=16

case 4: when t=0 and u=1 then left hand side only  one combination for true

total = 16+16+16+1=49 

Answer 1

The given expression will evaluate to :

p.~q.r.~s+t+~u(after we apply the various simplification rules : a->b=~a+b and demorgan's rule)

So the given expression ontains 6 variables. Each variable can take either 1 or 0 i.e. only 2 values. So total possible combinations are 2^6=64. Now lets see for what combinations we will get the value 1.

Case 1:

For t=1 value =1. It can be seen that for 32 values t=1. (t=0 for 32 values and t=1 for 32 values)

Similarly for u=0 result =1. It is also for 32 values.

So either t=1 or u=0 result is 1.

No of combinations: No.of combinations (t=1)+No.of Combinations (u=0)-No. of combinations(t=1&u=0)=32+32-16=48

Case 2: when p.~q.r.~s=1 Only one case will be valid (after we remove the case 1 possiblities).

So Total no. of cases=48+1=49

Comments

t=1&u=0

it will be

t=1 or u=0 

right? 

---

ya it will be t=1 or u=0 for both the value will be 1. So I have taken first the case of t then u and then subtracted the common part as in the case of set union

---

and what is +1??

I got upto 48

but why 49

---

It is because of case 2 there are 3 terms that are there.The result will be one when any one is one. So it is the case when p.~q.r.~s is 1

Answer 2

Before answer i must say that if we have union of any number(k) of variable(say x=avbvcvd), it is FALSE(x=false) only when all values are False(1 way)

and if we perform union of say(k) variable

=> number of ways values are T = 2^k-1 (as we can have total 2^k ways for variable to be t/f)

and F = 1 always--------------------@1

we have to prove that its tautology

(total propositional ways - contradiction)

here we have 6 variables in total so #Ways we put values = 2^6 =64  

and A->B, a contradiction only when:  A=T and B= F

#here A (LHS) IS T only for = 24-1= 15 ways/- .......................@1

#B( RHS) is F = 1 way only/- ..................................................@1

TAUTOLOGY = TOTAL PROPOSITIONAL WAYS -CONTRADICTION

                          = 64-15 = 49 answer.

Comments

yes its when all varaibles are separated by "v " than we can say that...

---

why 

2^k-1??

---

SUPPOSE we have 2 variable (x=avb) its false only when both of them are false ( 1 way) and true when either of them is true (TT,TF,FT) =3ways . as a variable can have 2 values either t or false.
and we can deduce from this that truth values will be for 2^k-1 times for either values of variable as true