Assume $G$ be an undirected graph. Let $P(x,y)$ mean that there is a path from vertex $x$ to vertex $y$ .
How to translate the given English statements into Predicate logic ?
- $G$ has atleast $3$ connected components.
- $G$ has exactly $3$ connected components.
- $G$ has atmost $3$ connected components.
My Try:
- $G$ has atleast $3$ connected components.
This can be written as $∃x∃y∃z(P'(x,y)∧P'(y,z)∧P'(x,z))$
- $G$ has atmost $3$ connected components.
The first one was like saying "There are atleast $3$ $P$'s" and to get "There are atmost $3$ $P$'s" is to by denying the fact that "There are atleast $4$ $P$'s"
I can write this as $¬∃x∃y∃z∃t(P'(x,y)∧P'(y,z)∧P'(z,t)∧P'(t,x))$
- $G$ has exactly $3$ connected components is the intersection of $1$st one and $2$nd one.
These are my thoughts for this question. Let me know if I am wrong somewhere ?
I'll do the first one for you:
If $G=(V,E)$ has at least $3$ connected components, then there exists vertices $u,v,w$ such that there is no path between $u$ and $ v$, $u$ and $w$, and $v$ and $ w$, i.e., $$ \exists u,v,w \in V\; |\; \bar{P}(u,v),\bar{P}(u,w),\bar{P}(v,w) $$ where $\bar{P}$ is the negative of $P$.