Wie kann ich die Zeilen von Tabellen vergrößern?

Dein Beispiel ist ein Paradebeispiel für den Sinn und Zweck des booktabs booktabs mit seinen zusätzlichen Befehlen für besser platzierte horizontale Linien:

\documentclass{article}
\usepackage{booktabs}
\usepackage[utf8]{inputenc}
\begin{document}
\begin{tabular}{ccc}\toprule
  \textbf{Bezeichnung} & \textbf{Schreibweise} & \textbf{Sprechweise} \\
  \midrule
  Implikation & $p \Rightarrow q$ & aus $p$ folgt $q$\\
  Äquivalenz & $p \Leftrightarrow q$ & $p$ genau dann, wenn $q$\\
  \bottomrule
\end{tabular}
\end{document}

Hier das Ergebnis:

Sollte auch das in seltenen Fällen nicht genügen, so kann man den den Abstand wahlweise mit dem optionalen Argument von \\ oder mit der ebenfalls von booktabs bereitgestellten Anweisung \addlinespace erhöhen:

\documentclass{article}
\usepackage{booktabs}
\usepackage[utf8]{inputenc}
\begin{document}
\begin{tabular}{ccc}\toprule
  \textbf{Bezeichnung} & \textbf{Schreibweise} & \textbf{Sprechweise} \\
  \midrule
  Implikation & $p \Rightarrow q$ & aus $p$ folgt $q$\\[.5ex]
  Äquivalenz & $p \Leftrightarrow q$ & $p$ genau dann, wenn $q$\\
  \bottomrule
\end{tabular}
\end{document}

mit dem Ergebnis:

Will man generell alle Zeilen sowohl in der Höhe als auch in der Tiefe etwas dehnen, so kann man sich \arraystretch bedienen:

\documentclass{article}
\usepackage{booktabs}
\usepackage[utf8]{inputenc}
\begin{document}
\renewcommand*{\arraystretch}{1.2}
\begin{tabular}{ccc}\toprule
  \textbf{Bezeichnung} & \textbf{Schreibweise} & \textbf{Sprechweise} \\
  \midrule
  Implikation & $p \Rightarrow q$ & aus $p$ folgt $q$\\
  Äquivalenz & $p \Leftrightarrow q$ & $p$ genau dann, wenn $q$\\
  \bottomrule
\end{tabular}
\end{document}

Der hier verwendete Wert 1.2 ist ein Erfahrungswert, der häufig zu guten Ergebnissen führt.