
# 3.1: Prelude to Symbolic Logic and Proofs

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\def\d{\displaystyle}$$
$$\newcommand{\f}[1]{\mathfrak #1}$$
$$\newcommand{\s}[1]{\mathscr #1}$$
$$\def\N{\mathbb N}$$
$$\def\B{\mathbf{B}}$$
$$\def\circleA{(-.5,0) circle (1)}$$
$$\def\Z{\mathbb Z}$$
$$\def\circleAlabel{(-1.5,.6) node[above]{A}}$$
$$\def\Q{\mathbb Q}$$
$$\def\circleB{(.5,0) circle (1)}$$
$$\def\R{\mathbb R}$$
$$\def\circleBlabel{(1.5,.6) node[above]{B}}$$
$$\def\C{\mathbb C}$$
$$\def\circleC{(0,-1) circle (1)}$$
$$\def\F{\mathbb F}$$
$$\def\circleClabel{(.5,-2) node[right]{C}}$$
$$\def\A{\mathbb A}$$
$$\def\twosetbox{(-2,-1.5) rectangle (2,1.5)}$$
$$\def\X{\mathbb X}$$
$$\def\threesetbox{(-2,-2.5) rectangle (2,1.5)}$$
$$\def\E{\mathbb E}$$
$$\def\O{\mathbb O}$$
$$\def\U{\mathcal U}$$
$$\def\pow{\mathcal P}$$
$$\def\inv{^{-1}}$$
$$\def\nrml{\triangleleft}$$
$$\def\st{:}$$
$$\def\~{\widetilde}$$
$$\def\rem{\mathcal R}$$
$$\def\sigalg{\sigma-algebra }$$
$$\def\Gal{\mbox{Gal}}$$
$$\def\iff{\leftrightarrow}$$
$$\def\Iff{\Leftrightarrow}$$
$$\def\land{\wedge}$$
$$\def\And{\bigwedge}$$
$$\def\entry{\entry}$$
$$\def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}$$
$$\def\Vee{\bigvee}$$
$$\def\VVee{\d\Vee\mkern-18mu\Vee}$$
$$\def\imp{\rightarrow}$$
$$\def\Imp{\Rightarrow}$$
$$\def\Fi{\Leftarrow}$$
$$\def\var{\mbox{var}}$$
$$\def\Th{\mbox{Th}}$$
$$\def\entry{\entry}$$
$$\def\sat{\mbox{Sat}}$$
$$\def\con{\mbox{Con}}$$
$$\def\iffmodels{\bmodels\models}$$
$$\def\dbland{\bigwedge \!\!\bigwedge}$$
$$\def\dom{\mbox{dom}}$$
$$\def\rng{\mbox{range}}$$
$$\def\isom{\cong}$$
$$\DeclareMathOperator{\wgt}{wgt}$$
$$\newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}}$$
$$\newcommand{\va}[1]{\vtx{above}{#1}}$$
$$\newcommand{\vb}[1]{\vtx{below}{#1}}$$
$$\newcommand{\vr}[1]{\vtx{right}{#1}}$$
$$\newcommand{\vl}[1]{\vtx{left}{#1}}$$
$$\renewcommand{\v}{\vtx{above}{}}$$
$$\def\circleA{(-.5,0) circle (1)}$$
$$\def\circleAlabel{(-1.5,.6) node[above]{A}}$$
$$\def\circleB{(.5,0) circle (1)}$$
$$\def\circleBlabel{(1.5,.6) node[above]{B}}$$
$$\def\circleC{(0,-1) circle (1)}$$
$$\def\circleClabel{(.5,-2) node[right]{C}}$$
$$\def\twosetbox{(-2,-1.4) rectangle (2,1.4)}$$
$$\def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}$$
$$\def\ansfilename{practice-answers}$$
$$\def\shadowprops ParseError: EOF expected (click for details) Callstack: at (Template:MathJaxLevin), /content/body/div/p[1]/span, line 1, column 11 at template() at (Bookshelves/Combinatorics_and_Discrete_Mathematics/Book:_Discrete_Mathematics_(Levin)/3:_Symbolic_Logic_and_Proofs/3.0:_Prelude_to_Symbolic_Logic_and_Proofs), /content/body/p/span, line 1, column 22 at wiki.page() at (Courses/Saint_Mary's_College,_Notre_Dame,_IN/SMC:_MATH_339_-_Discrete_Mathematics_(Rohatgi)/Text/3:_Symbolic_Logic_and_Proofs/3.1:_Prelude_to_Symbolic_Logic_and_Proofs), /content/body/div/pre, line 2, column 10 $$
$$\renewcommand{\bar}{\overline}$$
$$\newcommand{\card}[1]{\left| #1 \right|}$$
$$\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}$$
$$\newcommand{\lt}{&lt;}$$
$$\newcommand{\gt}{&gt;}$$
$$\newcommand{\amp}{&amp;}$$

$$\newcommand{\hexbox}[3]{ \def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2} \def\y{-\r*#1-sin{30}*\r*#1} \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle; \draw (\x,\y) node{#3}; }$$

$$\renewcommand{\bar}{\overline}$$
$$\newcommand{\card}[1]{\left| #1 \right|}$$
$$\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}$$
$$\newcommand{\lt}{<}$$
$$\newcommand{\gt}{>;}$$
$$\newcommand{\amp}{&}$$

Logic is the study of consequence. Given a few mathematical statements or facts, we would like to be able to draw some conclusions. For example, if I told you that a particular real-valued function was continuous on the interval $$[0,1]\text{,}$$ and $$f(0) = -1$$ and $$f(1) = 5\text{,}$$ can we conclude that there is some point between $$[0,1]$$ where the graph of the function crosses the $$x$$-axis? Yes, we can, thanks to the Intermediate Value Theorem from Calculus. Can we conclude that there is exactly one point? No. Whenever we find an “answer” in math, we really have a (perhaps hidden) argument. Mathematics is really about proving general statements (like the Intermediate Value Theorem), and this too is done via an argument, usually called a proof. We start with some given conditions, the premises of our argument, and from these we find a consequence of interest, our conclusion.

The problem is, as you no doubt know from arguing with friends, not all arguments are good arguments. A “bad” argument is one in which the conclusion does not follow from the premises, i.e., the conclusion is not a consequence of the premises. Logic is the study of what makes an argument good or bad. In other words, logic aims to determine in which cases a conclusion is, or is not, a consequence of a set of premises.

By the way, “argument” is actually a technical term in math (and philosophy, another discipline which studies logic):

Definition: Arguments

An argument is a set of statements, one of which is called the conclusion and the rest of which are called premises. An argument is said to be valid if the conclusion must be true whenever the premises are all true. An argument is invalid if it is not valid; it is possible for all the premises to be true and the conclusion to be false.

For example, consider the following two arguments:

 If Edith eats her vegetables, then she can have a cookie. Edith eats her vegetables. $$\therefore$$ Edith gets a cookie.
 Florence must eat her vegetables in order to get a cookie. Florence eats her vegetables. $$\therefore$$ Florence gets a cookie.

(The symbol “$$\therefore$$” means “therefore”)

Are these arguments valid? Hopefully you agree that the first one is but the second one is not. Logic tells us why by analyzing the structure of the statements in the argument. Notice the two arguments above look almost identical. Edith and Florence both eat their vegetables. In both cases there is a connection between the eating of vegetables and cookies. But we claim that it is valid to conclude that Edith gets a cookie, but not that Florence does. The difference must be in the connection between eating vegetables and getting cookies. We need to be skilled at reading and comprehending these sentences. Do the two sentences mean the same thing? Unfortunately, in everyday language we are often sloppy, and you might be tempted to say they are equivalent. But notice that just because Florence must eat her vegetables, we have not said that doing so would be enough (she might also need to clean her room, for example). In everyday (non-mathematical) practice, you might be tempted to say this “other direction” is implied. In mathematics, we never get that luxury.

Before proceeding, it might be a good idea to quickly review Section 0.2 where we first encountered statements and the various forms they can take. The goal now is to see what mathematical tools we can develop to better analyze these, and then to see how this helps read and write proofs