How many valuations of these literals satisfy this expression? considering all the possible valuations of literals A, B, C, D, E, F, G and H (256 valuations in total), how would you go about finding how many of these valuations satisfy this expression:
$$ (A\rightarrow B) \wedge (B\rightarrow C) \wedge (D\rightarrow E) \wedge (F\rightarrow G) \wedge (G\rightarrow H)$$
I know I could draw the truth table with all the possible valuations, but what's a more efficient method? The solution that I calculated through software simulation should be 48.
 A: Note that you can divide the expression in three parts:
$$
\underbrace{(A\rightarrow B) \wedge (B\rightarrow C)}_{P} \wedge \underbrace{(D\rightarrow E)}_{Q} \wedge \underbrace{(F\rightarrow G) \wedge (G\rightarrow H)}_{R}
$$
The value of $P$ depends only on $A,B,C$, the value of $Q$ depends only on $D,E$, and the value of $R$ depends only on $F,G,H$. So if $N_P$ is the number of choices of $A,B,C$ for which $P$ is true, $N_Q$ is the number of choices of $D,E$ for which $Q$ is true, and $N_R$ is the number of choices of $F,G,H$ for which $R$ is true, the total number is 
$$
N_P N_Q N_R.
$$
A: Observe that the three groups $\{A,B,C\}$, $\{D,E\}$, and $\{F,G,H\}$ are essentially independent; we can analyze them separately.
In a group like $\{A, B, C\}$, not all truth values are possible, if $A$ is true then so are $B$ and $C$; if $B$ is true then so is $C$.  If we consider $A$ to be ‘earlier’ then $B$, and $B$ to be ‘earlier’ than $C$, then it suffices to know the earliest true value in the set of three; this completely determines the other values.  For example, if $B$ is the earliest true value than $A$ is false (since it is earlier than $B$) and $C$ is true (since $B\to C$).  So there there only four values this group can have: any of $A$, $B$, or $C$ can be the earliest true value, or else none is true; this is four possibilities.
$\{F,G,H\}$ similarly has four possible values.
$\{D,E\}$ similarly has three values: none is true; $E$ is the earliest true value, or $D$ is the earliest true value.
$4\cdot 4\cdot 3 = 48$.
A: Take subsets and then combinations.
From A,B,C we can make a subset, that has I think 4 solutions.
For F,G,H, the same.
And for D,E only 3 solution.
But all combinations can occur, so 4x4x3
A: Welcome to Edinburgh 
This part concerns the 256 possible truth valuations of the following eight propositional letters A, B, C, D, E, F, G, H. For each of the following ex- pressions, say how many of the 256 valuations satisfy the expression, and briefly explain your reasoning. For example, the expression D is satisfied by half of the valuations, that is 128 of the 256, since for each valuation that makes D true there is a matching valuation that makes D false.
