GATE Artificial Intelligence formula sheet

Uniform tree with branching factor $b$, goal at depth $d$, the last iteration generating every node to depth $d$, root counted in every iteration. Nodes at depth $i$ are generated $d+1-i$ times.

From the sum above with $k=d-i$: $N_{\text{IDS}}=b^d{\sum }_{k=0}^d(k+1)b^{-k}<b^d(1-1/b{)}^{-2}$. For $b=2$ the factor is 4; for $b=10$ it is about 1.23.

The usual first step (after rewriting $\leftrightarrow$) when converting to CNF or DNF.

True exactly when p and q have the same truth value.

Each conditional is defined only when the event it conditions on has positive probability ($P(B)>0$ for $P(A\mid B)$).

Sum over every value of each variable being removed.