Doch, `m` wirkt in der letzten Zeile und eigentlich ist genau das das Problem, da die zusätzlichen `4ex` erst unten angefügt werden und dann die Zentrierung stattfindet. Für Deinen Zweck ist daher `\arraystretch` alleine wie in [meiner Antwort auf die andere Frage][1] gezeigt, weit besser geeignet als `m`-Spalten, bzw. sind ganz normale l-Spalten besser geeignet als `m`-Spalten.
`m`-Spalten. Wenn Du auf `m`-Spalten bestehst, solltest Du am Ende eine dummy-Spalte anfügen:
\documentclass{article}
\usepackage{array}
\renewcommand*{\arraystretch}{1.3}
\usepackage[utf8]{inputenc}
\begin{document}
\begin{tabular}{m{2.5cm}m{2.5cm}m{4cm}m{0pt}@{}}
\hline
\textbf{Bezeichnung} & \textbf{Schreibweise} & \textbf{Sprechweise} \\
\hline
Implikation & $p \Rightarrow q$ & aus $p$ folgt $q$ & \\[4ex]
Äquivalenz & $p \Leftrightarrow q$ & $p$ genau dann, wenn $q$ & \\[4ex]
\hline
\end{tabular}
\end{document}
oder statt `\\[4ex]` auf `\addlinespace` ausweichen:
\documentclass{article}
\usepackage{array,booktabs}
\renewcommand*{\arraystretch}{1.3}
\usepackage[utf8]{inputenc}
\begin{document}
\begin{tabular}{m{2.5cm}m{2.5cm}m{4cm}m{0pt}}
\hline
\textbf{Bezeichnung} & \textbf{Schreibweise} & \textbf{Sprechweise} \\
\hline
\addlinespace[4ex]
Implikation & $p \Rightarrow q$ & aus $p$ folgt $q$ & \\
\addlinespace[4ex]
Äquivalenz & $p \Leftrightarrow q$ & $p$ genau dann, wenn $q$ & \\
\addlinespace[4ex]
\hline
\end{tabular}
\end{document}
[1]: http://texwelt.de/wissen/fragen/719/wie-kann-ich-die-zeilen-von-tabellen-vergroern/720