Let $$\left( {\left\{ {p,\,q} \right\},\, * } \right)$$ be a semi group where $$p * p = q$$. Show that: (a) $$p * q = q * p,$$, and (b) $$q * q = q$$

(a) Show that the formula $$\left[ {\left( { \sim p \vee Q} \right) \Rightarrow \left( {q \Rightarrow p} \right)} \right]$$ is not a tautology.

(b) Let $$A$$ be a tautology and $$B$$ be any other formula. Prove that $$\left( {A \vee B} \right)$$ is a tautology.

The number of binary relations on a set with $$n$$ elements is:

The number of binary strings of $$n$$ zeros and $$k$$ ones such that no two ones are adjacent is: