Using \underbrace with table columns

There is also \upbracefill (and \downbracefill) which uses \leaders to build an extending brace. For example, \hbox to 5cm{\upbracefill} would "fill" that five centimeter length with the brace.

\documentclass{article}
\begin{document}
\[
  \begin{array}{|c|c|c|c}
     p
   & q
   & p\lor{}q
   & p\land{}q \\
  \hline
  0 & 0 & 0 & 0 \\
  0 & 1 & 1 & 0 \\
  1 & 0 & 1 & 0 \\
  1 & 1 & 1 & 1 \\
  \hline
  \noalign{\vspace{-3pt}}
  \multicolumn{2}{c}{}&
    \multicolumn{2}{@{}c@{}}{${\upbracefill}$} \\
  \multicolumn{2}{c}{}&
    \multicolumn{2}{c}{\scriptstyle\ell} \\
  \end{array}
\]
\end{document}

You need to play around with the spaces used inside of array:

\documentclass{article}
\begin{document}
\[
  \begin{array}{|c|c|c|c}
      p
    & q
    & p\lor{}q
    & p\land{}q \\
    \hline
    0 & 0 & 0 & 0 \\
    0 & 1 & 1 & 0 \\
    1 & 0 & 1 & 0 \\
    1 & 1 & 1 & 1 \\
    \hline
    \multicolumn{1}{c}{} & \multicolumn{1}{c}{} & \multicolumn{2}{@{}l@{}}{%
      \raisebox{.5\normalbaselineskip}{%
      \rlap{$\underbrace{\hphantom{\mbox{$p\lor{}q$\hspace*{\dimexpr4\arraycolsep+\arrayrulewidth}$p\land{}q$}}}_{\ell}$}}%
    }
  \end{array}
\]
\end{document}

The last two columns have the combined width of

• $p\lor{}q$ (third column heading)
• $p\land{}q$ (fourth column heading)
• 4\arraycolsep (two on either side of the two headings, totalling 4)
• \arrayrulewidth (between the two headings)

The addition of \multicolumns is to remove the vertical rules inserted with your column specification |c|c|c|c|. Finally, \raisebox{.5\normalbaselineskip} raises the entire \underbrace up half a line.

You can also use the usual overkill solution with tikz.

Note:

• This does require two runs. First one to determine the locations, and the second to do the drawing.

References:

• This is a tweaked version of Overbrace in amsmath align environment. A \VerticalOffset have been added to shift the brace to compensate for the \hline.
• The brace is adapted from adding a large brace next to a body of text

Code:

\documentclass{article}

\usepackage{amsmath}
\usepackage{tikz}
\usetikzlibrary{calc}
\usetikzlibrary{decorations.pathreplacing}

\newcommand{\tikzmark}[1]{\tikz[overlay,remember picture] \node (#1) {};}

\newcommand*{\BraceAmplitude}{0.5em}%  Can be tweaked if
\newcommand*{\VerticalOffset}{1.2ex}%  necessary.
\newcommand*{\HorizontalOffset}{0.8em}%  necessary.
\newcommand*{\InsertUnderBrace}[4][]{%
    \begin{tikzpicture}[overlay,remember picture]
\draw [decoration={brace,amplitude=\BraceAmplitude},decorate, thick,draw=blue,text=black,#1]
        ($(#3)+(\HorizontalOffset,-\VerticalOffset)$) -- 
        ($(#2)+(-\HorizontalOffset,-\VerticalOffset)$)
        node [below=\VerticalOffset, midway] {#4};
    \end{tikzpicture}%
}%


\begin{document}
\[
\begin{array}{|c|c|c|c}
   p
 & q
 & p\lor{}q
 & p\land{}q \\
\hline
0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 \\
1 & 1 & \tikzmark{StartBrace}1 & 1\tikzmark{EndBrace} \\
\hline
\end{array}
\]
\InsertUnderBrace[draw=red,text=blue]{StartBrace}{EndBrace}{Explanation}
\end{document}