Smallest Congruence Relation generated by a set $\newcommand{\cl}{\operatorname{cl}}$
Let $R \subset S \times S$ be a binary relation, the smallest
i) reflexive relation containing it is
$$
\cl_\mathrm{ref} = R \cup \{ (x,x) : x \in S \}
$$
ii) symmetric relation
$$
\cl_\mathrm{sym} = R \cup \{ (y,x) : (x,y) \in R \}
$$
ii) transitive relation
$$
\cl_\mathrm{trans}(R) = R \cup \{ (x_1, x_n) : (x_1, x_2), \ldots, (x_{n-1}, x_n) \in R \} = \bigcup_{i = 1}^\infty R^i.
$$
And the smallest equivalence relation containing it is
$$
\cl_\mathrm{ref}(R) \cup \cl_\mathrm{sym}(R) \cup \cl_\mathrm{trans}(R)
$$
But how looks the smallest congruence relation on a set $R$ with respect to some $n$-ary operation $f$? Is there a similar "constructive" way of defining it?
EDIT: Formula for transitive closure is wrong, see comments. Correct version
$$
\cl_\mathrm{trans}(\cl_\mathrm{sym}(\cl_\mathrm{ref}(R))).
$$
 A: Let $\mathfrak{S}=(S,F)$ be an algebra where $S$ is the universe and $F$ is the collection of fundamental operations on $S$. For an arbitrary $R \subseteq S \times S$, define $R\circ R$ to be $\{(x,z): (x,y),(y,z)\in R\}$.
Define $R_0=R\cup \{(x,x):x\in S\} \cup \{(y,x):(x,y)\in R\} = \mathrm{cl}_{sym}(\mathrm{cl}_{ref}(R))$.
Then define $R_{n+1} = (R_n \circ R_n) \cup \{\big(f(x_1,\ldots,x_n),f(y_1,\ldots,y_n)\big):f\in F \text{ and } (x_1,y_1),\ldots, (x_n,y_n) \in R_n\}$.
Then $\displaystyle\bigcup_{i=0}^\infty R_i$ is the smallest congruence relation containing $R$.
A: Congruence relations on $\mathfrak{A} = (A, F)$ can be also viewed as the equivalence relations on $A$ which are the subalgebras of $\mathfrak{A} \times \mathfrak{A}$. Consider
$\mathfrak{B} = (A \times A, F, t, (\cdot)^{-1}, \triangle_{A})$, where 


*

*$\triangle_{A} = \{(a, a)\ |\ a \in A\}$ is the set of nullary operations.

*$(a, b)^{-1} = (b, a)$ is the unary operation.

*$t((a, b), (c, d)) = \begin{cases} (a, d), &\mbox{if } b = c,\\ 
     (a, b) & \mbox{if } b \neq c. \end{cases}$


Given any subset $R \subseteq A \times A$, the smallest congruence containing $R$ is the same as the subalgebra of $\mathfrak{B}$ generated by $R$, which can be constructed inductevly for any algebra as follows. 
Let $\mathfrak{A} = (A, F)$ be an algebra. For any $X \subseteq A$ denote by $Sg(X)$ the subalgebra generated by $X$. Let $Y_0 = X$ and $Y_{n+1} = Y_n \cup \{f(x_1, \dots, x_n)\ |\ f \in F, x_1, \dots, x_n \in Y_n\, \text{, where } n \text{ is the arity of $f$}\}.$
Hence $Sg(X) = \bigcup_{n = 0}^{\infty} Y_n$.
This construction is very similar to that from Eran's answer but in terms of subalgebras.
