Scattered notes for Discrete Structures at Hunter College.

discrete-structures-notes.tex

\PassOptionsToPackage{unicode=true}{hyperref} % options for packages loaded elsewhere
\PassOptionsToPackage{hyphens}{url}
\documentclass[oneside]{book}
\usepackage[margin=2.3cm]{geometry}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
% \usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provides euro and other symbols
\else % if luatex or xelatex
  \usepackage{unicode-math}
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
%\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\usepackage{hyperref}
\hypersetup{pdftitle={Discrete Structures Guided Walk-through},
            pdfauthor={Ralph D. Vente},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
% set default figure placement to htbp
\makeatletter
\def\fps@figure{htbp}
\makeatother

\usepackage[md]{titlesec}
\titleformat{\section}{\filcenter\Large}{}{0em}{}[\hrule]
\titleformat{\subsection}{\filcenter}{}{0em}{}[\hrule]
\titleformat{\subsubsection}[runin]{}{}{}{\sc Item }[:]
%\titleformat{\section}[display]{\normalfont\bfseries}{}{0pt}{\Huge} % gets rid
%of numbering

%\titleformat{\subsection}[runin]{}{}{}{}[]
%\titleformat{\subsection}[runin]{}{}{}{}[\hrulefill]

%\titlespacing*{\section} {0pt}{1.5ex plus 1ex minus .2ex}{1.5ex plus 0.3ex}

\titlespacing*{\section}{0pt}{1ex}{0ex}
\titlespacing*{\subsection}{0pt}{3pt}{0ex}
\titlespacing*{\subsubsection}{0pt}{0.5ex plus 1ex minus .2ex}{1ex}

%\titlespacing*{\section} {1pt}{4.5ex plus 1ex minus .2ex}{4.3ex plus .2ex}
% % \titlespacing*{<command>}{<left>}{<before-sep>}{<after-sep>}
\usepackage{multicol}
\usepackage[fleqn]{mathtools}

%\setcounter{secnumdepth}{6}

\setcounter{tocdepth}{6}

\title{Discrete Structures Guided Walk-through}
\author{Ralph Vente}
\date{\today}

\begin{document}

\maketitle
\tableofcontents

\chapter{Common Track Material} % after chapter is when multicols start

\begin{multicols}{2}
\section{Common Track Textbook Notes}
\subsection{Sophisticated Sums}
\subsubsection{1} 

Compute the sum of the first n integers. 

\begin{center}
	\setlength\tabcolsep{.5ex} 
  \begin{tabular}{ r r r r r r r r r r}
    &    &1   +&  2 +&   3& + &\ldots &+&100 &  \\ 
    & +( &100 +& 99 +&  98& + &\ldots &+&1   &) \\ 
    & =  &101 +&101 +& 101& + &\ldots &+&101 &  \\
  \end{tabular}
\end{center}

There are 100 numbers in the resulting line. so we would get
$100(101)$ but we added the sum to itself, so this is twice the sum we
want. We must now divide by 2.

$100(101)/2$

\subsubsection{2}

Generalize the trend from {\sc Item 1.}

\begin{center}
	\setlength\tabcolsep{.5ex} 
  \begin{tabular}{ r r r r r r r r r r}
    &    &$1$   +&  $2$ +&   $3$& + &\ldots &+&$n$ &  \\ 
    & $+( $&$n$ +& $n-1 $+&  $n-2$ & + &\ldots &+&$1 $  &) \\ 
    & =  &$n+1$ +&$n+1$+& $n+1$& + &\ldots &+&$n+1$ &  \\
  \end{tabular}
\end{center}

Like before, we added two of the same sum to itself, so we have to divide by two
to get the value of just one of them. The sum of the first n integers that
increment by 1 is ${n(n+1)}/2$.

$n$ is value of the number where we stop adding. We started at 1.

\subsubsection*{5}

Compute $5+8+11+\ldots+275$.

This too can be added to itself backwards, but it's also possible to break the
sum up into $2+(3 \times 1) + 2+(3 \times 2) + 2+(3 \times 3) \dots 2 + (3 \times 91)$. There it becomes
$(2+2+2+\dots+2)+(3 \times 1)+(3 \times 2)+(3 \times 3) + \dots + (3 \times 91)$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  
\end{multicols}
\chapter{{\sc Track A} Material}
\begin{multicols}{2}
\section{{\sc Track A} Textbook Notes}

\subsection{Fib Numbers \& Rabbits}
\subsubsection{61}

How many ways are there to climb a staircase with $n$ stairs if you can take
them either 1 or 2 at a time.
\footnote{Reference items 36 \& 49. Know Sanskrit
  poetry from the homework problems.}
\footnote{The closed form formula we saw
  in item 41 works here as well.}

\begin{center}
  \begin{tabular}{ l l }
    {Base Cases: } & {Recursive Definition: }\\ 
    $N_1 = 1 , N_2 = 2$ &  $N_n =  N_{n-1} + N_{n-2}$  
  \end{tabular}
\end{center}

This means that the value of a particular element is the sum of the previous
element and the element before it.

In general, the number of ways to climb a staircase with
$n$ stairs is $N_n =  N_{n-1} + N_{n-2}$ .

Suppose that (1) it takes a month for rabbits to mature, (2) each pair of
rabbits produces a new pair of immature rabbits, (3) rabbits don't die for the
length of the observation.

The number born is equal to the number of mature rabbits last month, this number
in turn is also equal to the total amount of rabbits 2 months ago.

Fibonacci numbers are given as $1, 1, 2, 3, 5,8, \dots$, since Fib's study
started with immature rabbits so for consistency, the first item is called $F_0$
and subsequent items continue from it.

\begin{center}
\begin{tabular}{ c |c |c |c |c |c  }
  $F_0$ & $F_1$ & $F_2$ & $F_3$& $F_4$&  $F_5$\\ \hline 
  1 & 1 & 2 & 3 & 5 & 8 \\
\end{tabular}
\end{center}

\subsubsection{62}

Prove that $\displaystyle \sum_{i=0}^{n}{F_i} = F_{n+2} -1 $.

In other words, Prove that the sum of the first n terms of the Fibonacci
sequence is equal to the value of the Fibonacci number after the next one (the
Fib number 2 places rightward). Note: $\top$ means ``is true'' in propositional
logic. IH is short for ``inductive hypothesis''. BC is short for ``base case.''

\begin{center}
Base Case

      n = 0\\
  $n = 0$  $\therefore$  $F_n = F_0 =1$    \\
\end{center}

\begin{center}
  \setlength\tabcolsep{.5ex} 
  Inductive Hypothesis on Base Case

  \begin{tabular}{ r c r l }
    Prove for BC &&$\sum_{i=0}^{n}{F_i} $&=  $F_{n+2} -1 $.  \\
    % $n=0$ & $\therefore$ & $\sum_{i=0}^{0}{F_i}$ & = $F_{0+2} -1 $ \\
    substitute 0 for n& $\therefore$ & $\sum_{i=0}^{0}{F_i}$ & = $F_{0+2} -1 $  \\
    evaluate limit& $\therefore$ & $F_0$ & = $F_{0+2} -1 $   \\
    simplify  & $\therefore$ & $F_0$ & = $F_{2} -1 $  \\
    $F_2 = 2$& $\therefore$ & $F_0$ & = $2 -1 $  \\
    & $\therefore$ & $F_0$ & = $ 1 $  \\
    $F_0 = 1$& $\therefore$ & & IH $\top$ BC\\
  \end{tabular}
\end{center}


\begin{center}
\setlength\tabcolsep{.5ex}
  Inductive Step  

  \begin{tabular}{ r c r l }
    && & IH $\top  $ for $0 \leq n $ \\
    Prove &&$\sum_{i=0}^{n+1}{F_i} $&=  $F_{(n+1)+2} -1$. \\
    extract last sum term &$\therefore$&$\sum_{i=0}^{n+1}{F_i} $&=  $\sum_{i=0}^{n}{F_i} + F_{n+1} $ \\
    assume IH $\top  $&$\therefore$&$\sum_{i=0}^{n+1}{F_i} $&=  $F_{n+2}-1 + F_{n+1}$ \\
    rearrange &$\therefore$&$\sum_{i=0}^{n+1}{F_i}$ &$=  F_{n+1}+F_{n+2}-1  $ \\
    $F_n+F_{n+1} = F_{n+2}$ &$\therefore$&$\sum_{i=0}^{n+1}{F_i}$ & $=  F_{n+3}-1  $ \\
  \end{tabular}
\end{center}

\subsubsection{64} Get a formula for $N_n$ in terms of $F_n$ assuming that
$N_n=N_{n-1}+N_{n-2} \text{ and } N_0=1 \text{ and }N_1=b$.

What happens to the Fibonacci sequence if we changed the base cases?

\begin{center}
\setlength\tabcolsep{.5ex} 
  \begin{tabular}{ c |c |c |c |c |c  }
  $F_0$ & $F_1$ & $F_2$ & $F_3$& $F_4$&  $F_5$  \\ \hline 
  $a$ & $b$ & $a+b$ & $a+2b $& $2a+3b$ & $5a+8b$  \\
  \end{tabular}
\end{center}

It appears that $N_n=F_{n-2}a+F_{n-1}b$. Prove it by induction on n.

\begin{center}
  Base case \\
  $n=2$\\
\end{center}

This is the first place where all $n$'s in $N_n=F_{n-2}a+F_{n-1}b$ are 
defined. If $n$ were any lower, $n=0$ for example, you would have $F_{n-2}$ is
$F_{-2}$ and that's not defined.

\begin{center}
\setlength\tabcolsep{.5ex} 
  Inductive Hypothesis on Base Case \\ \hfil \\
  \begin{tabular}{ r c l }
    Prove IH $\top$ BC \\
    $N_0=a$, $N_1=b$   \\
    $n=2$               & $\therefore$ & $N_2=F_{2-2}a+F_{2-1}b$ \\
    simplify            & $\therefore$ & $N_2=F_{0}a+F_{1}b$ \\
    $F_0=$, $F_1=1$     &  $\therefore$ & $N_2=1a+1b$ \\
    $N_0=a$, $N_1=b$    &  $\therefore$ & $N_2=N_0+N_1$ \\
                        &  $\therefore$ & $N_2=N_2$ \\
                        &  $\therefore$ & IH $\top$ BC\\
  \end{tabular}
\end{center}


%TODO: finish this proof

\subsection{Floor and Ceiling Functions}

\subsubsection{65} How many bits does it take to write the number n?

If that number is $2^m$, the answer is easy. It would be written as 1 followed by
$m$ zeroes, which makes $m+1$ bits in all.

\subsection{Remainders}
\subsubsection{68} Find the greatest common divisor of 66,445 and 73,295.

Result: 6

This process uses Euclid's Algorithm.

I've written it in Python here:

\begin{verbatim}
def GCD(small, large):
    while True:
        if (large % small == 0):
            return small
        else:
            prev_large = large
            large = small
            small = prev_large % small
\end{verbatim}

This may be hard to read in terms of code, so here it is in practice. Set up in
3 columns, starting with large, then small, and the last one should be the
remainder when you divide large by small. In other words, the last column should
be equal to (large \% small).

\begin{center}
\setlength\tabcolsep{.5ex} 
   Euclid's Algorithm in Practice \\ \hfil \\
  \begin{tabular}{ r r c l }
    $60$ &$\% $ & $42$ & $=18$ \\
    $42$ &$\% $ & $18$ & $=6$ \\
    $18$ &$\% $ & $6$  & $=0$ \\
  \end{tabular}\\ \hfil \\
    The greatest common divisor is 6
\end{center}

\subsubsection{68.1} In proving the Euclidian Algorithm correct, prove that $a
\mid b \wedge a | c \implies a | (b+c)$

Greatest common divisor and greatest common factor mean the same thing. The GCD
of a and b is written $(a,b)$. $a \mid b$, $a$ divides $b$ is the equivalent to
saying $a\%b=0$ or $(a,b) = a$ where $a$ is the smaller integer of the two. It's
also equivalent to saying $ka = b$ where k is an integer.

%TODO: Finish this proof
% \begin{center}
% \setlength\tabcolsep{.5ex} 
%   Inductive Hypothesis on Base Case \\ \hfil \\
%   \begin{tabular}{ r c l }
%     Prove IH $\top$ BC \\
%     $N_0=a$, $N_1=b$   \\
%     $N_0=a$, $N_1=b$    &  $\therefore$ & $N_2=N_0+N_1$ \\
%                         &  $\therefore$ & $N_2=N_2$ \\
%   \end{tabular}
% \end{center}


\subsubsection{69} Given integers $x$ and $y$, find integers $m$ and $n$ such
that $mx+ny = (x,y)$. In other words, find factors for x and y that 

Generalizing, suppose $a_0$ and $a_1$ are the two starting terms, analogous to
69 and 42 in the example. The remainder is $a_2$. When $a_2 = 0$, $a_1$ is the
greatest common divisor. 


\subsection{Groups}

%TODO: add on to this section, so far it is just copy pasted from the end. Expand on it
\subsubsection{70} Prove that there are an infinite number of primes.

The proof relies on the fact that:

$p! + 1 (\text{mod } p) = 1$

\subsubsection{70.1} Modus tollens and modus ponens

\begin{center}
{ \sc \small
  modus ponens
} \\
If $P \implies Q \wedge \neg P $ then $\neg Q$
\end{center}

\begin{center}
{ \sc \small
  modus tolens
} \\
If $P \implies Q \wedge \neg Q $ then $\neg P$ \\ \hfil \\ 
\end{center} 

\begin{center}
  $P \text{ implies } Q$ truth table \\ \hfill \\
	\setlength\tabcolsep{1ex} 
  \begin{tabular}{ r r c }
    $P$ & $Q$ & $P \implies Q$\\
    \hline
     F  &  F  &  T \\
     F  &  T  &  T \\
     T  &  F  &  F \\
     T  &  T  &  T \\
  \end{tabular}
\end{center}

\subsubsection{71}

A group:
\begin{itemize}
  \item contains 1
  \item is closed under multiplication
  \item contains a multiplicative inverse for every element
  \item multiplication is associative
\end{itemize}

Construction of a set $G_n$ with primes relative to and less than n form a group.

$G_{15} = \{1,2,4,7,8,11,13,14\}$

Is closed under multiplication. Construction of a group of relative primes mean
that $(x,n) = 1$. In other words, all elements of the group share no factors
(other than 1) with n or any other members of the group.

where $a \subset G_n$

$(x,n) = 1$

$ax+bn = 1$

$ax = 1-bn \equiv ax \equiv 1 (\text{mod } n)$

Thus proving that every member of the group has a multiplicative inverse in the
group.


\subsubsection{72} Prove that the order of a subgroup must divide the group.

The order of a group is the size of that group, written $|G|$. The
multiplicative inverse of element $g$ of set $G$ is called g-inverse: $g^{-1}$.

In $G_{15}$, let's make a subset $S$ with some of its elements:

$ S \subseteq G$

$G_{15} = \{1,2,4,7,8,11,13,14\}$

$S = \{1,4\} $

\subsubsection{73} The order of the subgroup created by successive powers of an
element in a finite group divides the order of the group.

The order of an element is the number of powers you raise that element to before
you get 1 back. In other words, the order of an element is the number of
elements in a subgroup of its powers. All of the elements that fit into $G_n$ under $\text{mod } n$
form a subgroup.

Take an element of $G_{15} = \{1,2,4,7,8,11,13,14\}$ For example, choose 4.

${4^0,4^1,4^2,4^3\dots,}  $

${1,4,4^2,4^3,\dots} $ note: $16 (\text{mod } 15) = 1$

${1,4,1,4,\dots} $

$S = \{1,4\} $

The order of $S$ is 2 because it has 2 elements.

The inverse of an element is one greater than its order. The order of 4 is 2.
$4^3 = 1$ The inverse of any element in a group $a^n$ is going to be $a^{k-n}$
where $k$ is the order of that group. In this case. The inverse of the element
$4^1 = 4$ is $4^{k-n}$. $k$, the order of that element is 2. $n$ is the power of
the element we're taking the inverse of, 1. $4^{2-1} = 4^1 \equiv 4(\text{mod }
15)$, so here, 4 is its own inverse, but this works in general for all subgroups
formed this way.

\subsubsection{74} The order of group $G_n$ formed using relative primes less
than $n$ is equivalent to the totient of n, or $\phi (n)$

$\phi(60) = 16$ because there are 60 relative primes between 0 and 60.

We can get this in general using inclusion and exclusion to derive the formula

$ \phi (n) = \displaystyle \left(1 - \frac{1}{f_1}\right) \left(1 -
  \frac{1}{f_2}\right)\left(1 - \frac{1}{f_3}\right) \dots\left(1 - \frac{1}{f_n}\right)$ where all $f_i$
factors of $n$ are listed

\subsection{Graphs}
\subsubsection{80}

Prove that any $n$ vertex graph with more than $\binom{n-1}{2}$ edges is
connected.

$\binom{n}{2}$ is the total amount of edges in a complete graph. A complete
graph has every vertex connected with every other vertex. This makes sense
because $\binom{n}{2}$ is equivalent to $n(n-1)/2$ which is the same as the sum
of the numbers up to $n$. If you have 2 vertices, you have one edge between
them. If you have three, you add 2 edges. If you have 4, you add 3 edges. When
you get to $n$ vertices, you have gotten $n-1$ vertices. The process for the sum
of the first $n$ consecutive integers has us multiply the stopping position by
one greater than itself and then divide by 2. Thus, $(n-1)n/2$, or
$\binom{n}{2}$ is the amount of vertices it takes to fully connect a graph.
Anything less than that, and it can't be fully complete.

But what about connected? The maximum number of edges that can be connected
without being a complete graph is $\binom{n-1}{2}$ because this is the graph
with all of the vertices connected and only one not connected. If you add a
single vertex, it only has one place to go: to the single vertex that wasn't
connected before, not making the whole thing connected. 

\subsubsection{81}

What is the minimum number of edges in a connected graph with $n$ vertices?

Solution: $\displaystyle n -1$ edges.

In Item 34, we defined a cycle as a path from a vertex back to that same vertex.
There are two ways to get to $v_1$ from $v_2$. You can go from the edge that
directly connects them, or go around the long way, since a cycle means there's a
circle of connected vertices.

This proves that a connected graph with the minimum number of vertices cannot
have a cycle. The edge connecting the two points must be redundant. Every point
is still connected even if the edge between $v_1$ and $v_2$ didn't exist.

Consider a graph with no cycles and consider the longest path in it that has no
vertex repeated. This path would be $v_1,v_2,v_3,\dots$ There can't be an edge
from $v_1$ to any other vertex $v_i$ because that would no be the longest path.
$v_1$ must only be connected to a single other vertex. The degree of a vertex is
the number of connections to that vertex. A fully connected graph with no cycles
has vertices of degree 1.

It's obvious now that a connected graph with no cycles, the connected graph with
the minimum number of vertices, must have $n-1$ connections, only 1 between all of
the vertices.

In the words of Cullen Schaffer, Computer Science Professor at Hunter College,

\emph{ A simple induction argument now shows that the minimum number of edges in
  a connected graph with $n$ vertices is $n-1$. A graph with one vertex is
  connected and has no edges, confirming the claim for $n=1$. If the claim is
  true for connected graphs with $n$ vertices, what about one with $n+1$? We’ve
  seen that it has a vertex $v$ of degree 1. Removing $v$ and the edge
  connecting it to the rest of the graph leaves a connected graph of $n$
  vertices with a minimum number of edges which, by hypothesis, must be
  $n-1$.{\bfseries We have to take one of them to reach the inductive
    hypothesis.} Adding $v$ and its incident edge back in yields a total of $n$
  edges, proving the claim true for the next higher number of vertices. }

\subsubsection{82}

Prove that a connected graph of n vertices with more than $n-1$ edges must have
a cycle.

\subsubsection{88}

Given a set of n labeled vertices, in how many ways can we add edges to make a
tree.

Let $N_n$ represent the number of trees where n is the number of vertices. if
$n=2$ the only way to make a tree is to draw an edge between two vertices is
with a single edge between them. As a reminder, a tree is an acyclic connected
graph. This by extension means that a tree has $n-1$ edges where n is the number
of vertices. $N_2=1$. $N_3=3$. That's because we have three possible vertices to
choose as the root. The root of the tree by necessity has to have more than a
degree of 1. Let $A_n$ be the subset of trees where vertex $n$ is of degree 1.

$|A_1|=(n-1)N_{n-1}$

$\binom{n}{2}$ are the two vertices of degree 1 that we're choosing from the set
of all vertices.

$N_n = $ 

\end{multicols}


\chapter{Formulae} % after chapter is when multicols start

\begin{multicols*}{2}
\section{Common Track Formulae}
\subsection{Summations}

\subsubsection{2} Sum of the first n integers. \\
  $\displaystyle \sum_{i=1}^ni = \frac{n(n+1)}{2}$

\subsubsection{3} Eight people arrive at a meeting and everyone shakes hands.
Compute the number of handshakes.\\
  $\displaystyle \sum_{i=1}^ni = \frac{n(n+1)}{2}$

\subsubsection{4} Comparisons in bubblesort of 1000 items \\
  $\displaystyle \sum_{i=1}^ni = \frac{n(n+1)}{2}$

\subsubsection{5} $5+8+11+\dots+275$
\begin{itemize}
  \item Find common difference, $d$.
  \item Find offset between initial term and $d$. Call this $k$
  \item Subtract k from the last term. Divide this by $d$. Call this $n$
  \item Evaluate the following summation:
\end{itemize}
\begin{center}
  $\displaystyle \sum_{i=1}^n(k + di) = $ \\
  $\displaystyle \sum_{i=1}^n(k)+\sum_{i=1}^n(di) = $ \\
  $\displaystyle \sum_{i=1}^n(k)+d\sum_{i=1}^n(i) = $ \\
  $\displaystyle k(n) + d \left(\frac{n(n+1)}{2}\right)$
\end{center}

\subsubsection{6} Note that when re-indexing a summation, the initial and final
terms must be the same. The number of terms must also be the same, but this
follows from the two previous statements. Apply appropriate transformations. \\
  $\displaystyle \sum_{i=-5}^{50}(1+4i) = \sum_{j=1}^{56}(1+4(j-6))$

%TODO: finish this section
%\subsection{Chooses and Counting}
%\subsubsection{Title}

\subsection{Divisibility Formulae}

\subsubsection{68} Find the greatest common divisor of two large numbers.

\begin{center}
{ \sc \small
  The greatest common divisor of $a$ and $b$ is:
}

$gcd(a,b) = (a,b)$ \\

{ \sc \small
  $a$ divides $b$ without any remainder is:
} %TODO: find a more meaningful replacement to leftrightarrow if it exists

$a \mid b \Longleftrightarrow ka = b$

{ \sc \small
If $a$ divides two integers, $a$ divides their sum.
}

$a\mid b \wedge a | c \implies a | (b+c)$ 

{ \sc \small
If $a$ divides two integers, $a$ divides their product.
}

$a\mid b \wedge a | c \implies a | (b \times c)$ 
\end{center}

\subsubsection{70} Prove that there are an infinite number of primes.

The proof relies on the fact that:

$p! + 1 (\text{mod } p) = 1$

\subsubsection{70.1} Modus tollens and modus ponens

\begin{center}
{ \sc \small
  modus ponens
} \\
If $P \implies Q$ and $P \top$ then $Q\top$
\end{center}

\begin{center}
{ \sc \small
  modus tolens
} \\
If $P \implies Q$ then $\neg Q \implies \neg P$
% If $P \implies Q \wedge \neg Q $ then $\neg P$ \\ \hfill \\ 
\end{center}

\begin{center}
  $P \text{ implies } Q$ truth table \\ \hfill \\
	\setlength\tabcolsep{1ex} 
  \begin{tabular}{ r r c }
    $P$ & $Q$ & $P \implies Q$\\
    \hline
     F  &  F  &  T \\
     F  &  T  &  T \\
     T  &  F  &  F \\
     T  &  T  &  T \\
  \end{tabular}
\end{center}


\end{multicols*}

\end{document}