(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:

(a) Mr. X claims the following:
If a relation R is both symmetric and transitive, then R is reflexive. For this, Mr. X offers the following proof.

"From xRy, using symmetry we get yRx. Now because R is transitive, xRy and yRx togethrer imply xRx. Therefore, R is reflextive."

Briefly point out the flaw in Mr. X' proof.

(b) Give an example of a relation R which is symmetric and transitive but not reflexive.