FMLogic.tex

\chapter{Logic}\label{Chapter:Logic}


\section{Statements}\label{Section:Statements}

Something thats often misunderstood about Math is that people think that Math is the study of numbers.  This is false, and not even historically justifiable.  Certainly numeracy has taken on a great role within mathematics, but that is not fundamentally what the discipline is.  Really, even when Math deals with numbers, the fundamental thing that is studied are not numbers but \textbf{statements}.  What is a statement?  It is a sentence that is true or false, but not both.  For example:

\begin{enumerate}
\item MSU-Billings is a State School.
\item $10+5=12$.
\item $x<4$.
\end{enumerate}

The first sentence is a true sentence, the second sentence is a false sentence.  The third is true or false depending on the value of $x$, but at no point can it take on the value of both true and false.\\

So we're going to be doing something in this chapter that seems fairly strange. We are going to be working with variables that are placeholders for statements rather than numbers.  The possible values for these statements then, are ``True" and ``False".  We will be performing operations on these statements as in standard algebra, but since every variable has only 2 possible values, the rules of our algebra are going to be different.


\section{Operations on Statements}\label{Section:OperationsStatements}

\subsection{Not}

The first sort of operation we can perform is  \textbf{negation}.  Given any statement, the negation is a statement that is false whenever the original statement is true, and true when the original is false.\\

For example if $p=\text{``It will rain today"}$,  then it's negation $\sim p=\text{``it will not rain today"}$, similarly if $q=``x>10"$, then it's negation $\sim q =``x\leq 10"$.  These are statements that are true whenever the original statement is false and false when they are true.\\

A convenient way to record when a statement is true or false is by something called a ``truth table".  By listing all the truth values of $p$, we can see when $\sim p$ is true:

$$\begin{array}{c|c}
p&\sim p\\
\hline
T & F\\
F&T
\end{array}$$


\subsection{And}

Given statements $p$, $q$, the statement $p\wedge q$ pronounced $p$ and $q$ is when $p$ and $q$ are both true, otherwise it is false.\\

For example, if $p=$``I will eat breakfast today" and $q=$``I will eat lunch today", then the statement $p\wedge q$ is the statement ``I will breakfast today and I will eat lunch today" which is only true if you eat both meals, if you skip one or both, then it is false.

$$\begin{array}{c|c|c}
p&q&p\wedge q\\
\hline
T & T&T\\
T&F&F\\
F&T&F\\
F&F&F
\end{array}$$

So if you skipped breakfast but had lunch, you could take a look at the third line and see that the compound statement ``I will breakfast today and I will eat lunch today" is false.



\subsection{Or}

Given statements $p$, $q$, the statement $p\vee q$ pronounced $p$ or $q$ is when either $p$ or $q$ is true, otherwise it is false.\\

So as in the above example, $p\vee q$ would be ``I will eat breakfast today or I will eat lunch today" and you're covered as long as you either have breakfast or lunch.  If you skip both, then you're lying, but as long as you had either you're telling the truth.

$$\begin{array}{c|c|c}
p&q&p\vee q\\
\hline
T & T&T\\
T&F&T\\
F&T&T\\
F&F&F
\end{array}$$

So if you had breakfast and skipped lunch, you can look at the second row and see that the statement ``I will eat breakfast today or I will eat lunch today" is still true.


\section{Compound Statements}\label{Section:CompoundStatements}

Suppose a friend of your has a test coming up tomorrow .  You ask them about their study plans and they say ``Well, I'll either study today, or I'll skip class tomorrow and study tomorrow."  Now your friend says this, but all sorts of things could happen between now and the test, so under what circumstances is your friend telling the truth and when are they lying?\\

Looking at their statement, there seems to be three fundamental underlying events:

\begin{itemize}
\item Studying today, lets call this $p$.
\item Going to class tomorrow, let's call this $q$.
\item Studying tomorrow, let's call this $r$.
\end{itemize}

Then the sentence ``I'll either study today, or I'll skip class tomorrow and study tomorrow." can be broken down as: $$p\vee (\sim q \wedge r)$$ that is ``Either $p$ OR not $q$ AND $r$".  \\

So when is this statement true?  We first note that $p,q,r$ could all be true or false, your friend could potentially do or not do any of these things.  All the combinations are as follows:

 $$\begin{array}{c|c|c}
p&q&r\\
\hline
T & T&T\\
T&T&F\\
T&F&T\\
T&F&F\\
F & T&T\\
F&T&F\\
F&F&T\\
F&F&F
\end{array}$$

Since $\sim q$ is in our expression, it may be helpful to list out what it's values are.  Remember, that $\sim q$ is the opposite of $q$.  As you get more experienced one may be tempted to skip stuff like $\sim q$ but for now let's proceed with caution:

 $$\begin{array}{c|c|c|c}
p&q&r&\sim q\\
\hline
T & T&T&F\\
T&T&F&F\\
T&F&T&T\\
T&F&F&T\\
F & T&T&F\\
F&T&F&F\\
F&F&T&T\\
F&F&F&T
\end{array}$$

Next, we have the statement $\sim q \wedge r$, which is true whenever both $\sim q$ and $r$ are true\ldots

 $$\begin{array}{c|c|c|c|c}
p&q&r&\sim q & \sim q \wedge r\\
\hline
T & T&T&F & \\
T&T&F&F& \\
T&F&\textcolor{red}{T}&\textcolor{red}{T}&\textcolor{red}{T}\\
T&F&F&T\\
F & T&T&F\\
F&T&F&F\\
F&F&\textcolor{red}{T}&\textcolor{red}{T}&\textcolor{red}{T}\\
F&F&F&T
\end{array}$$

\ldots and false otherwise:

 $$\begin{array}{c|c|c|c|c}
p&q&r&\sim q & \sim q \wedge r\\
\hline
T & T&T&F&F\\
T&T&F&F&F \\
T&F&T&T&T\\
T&F&F&T&F\\
F & T&T&F&F\\
F&T&F&F&F\\
F&F&T&T&T\\
F&F&F&T&F
\end{array}$$

Finally, we have the statement $p\vee (\sim q \wedge r)$ which is true whenever either $p$ or $\sim q \wedge r$ is true \ldots


 $$\begin{array}{c|c|c|c|c|c}
p&q&r&\sim q & \sim q \wedge r& p\vee(\sim q \wedge r)\\
\hline
\textcolor{red}{T} & T&T&F&F&\textcolor{red}{T}\\
\textcolor{red}{T}&T&F&F&F&\textcolor{red}{T} \\
\textcolor{red}{T}&F&T&T&\textcolor{red}{T}&\textcolor{red}{T}\\
\textcolor{red}{T}&F&F&T&F&\textcolor{red}{T}\\
F & T&T&F&F\\
F&T&F&F&F\\
F&F&T&T&\textcolor{red}{T}&\textcolor{red}{T}\\
F&F&F&T&F
\end{array}$$

\ldots and false otherwise:


 $$\begin{array}{c|c|c|c|c|c}
p&q&r&\sim q & \sim q \wedge r& p\vee (\sim q \wedge r)\\
\hline
T & T&T&F&F&T\\
T&T&F&F&F&T \\
T&F&T&T&T&T\\
T&F&F&T&F&T\\
F & T&T&F&F&F\\
F&T&F&F&F&F\\
F&F&T&T&T&T\\
F&F&F&T&F&F
\end{array}$$

If your friend studies today, goes to class tomorrow and studies tomorrow, did they lie?  In this case $p$ is true, $q$ is true and $r$ is true, so looking at the first row:

 $$\begin{array}{c|c|c|c|c|c}
p&q&r&\sim q & \sim q \wedge r& p\vee (\sim q \wedge r)\\
\hline
\textcolor{blue}{T} & \textcolor{blue}T&\textcolor{blue}T&F&F&\textcolor{blue}T\\
T&T&F&F&F&T \\
T&F&T&T&T&T\\
T&F&F&T&F&T\\
F & T&T&F&F&F\\
F&T&F&F&F&F\\
F&F&T&T&T&T\\
F&F&F&T&F&F
\end{array}$$

Your friend was telling the truth!  Let's say instead, they didn't study today, went to class tomorrow and studied tomorrow.  Then $p$ is false, $q$ is true, $r$ is true and we have:

 $$\begin{array}{c|c|c|c|c|c}
p&q&r&\sim q & \sim q \wedge r& p\vee (\sim q \wedge r)\\
\hline
T & T&T&F&F&T\\
T&T&F&F&F&T \\
T&F&T&T&T&T\\
T&F&F&T&F&T\\
\textcolor{blue}F & \textcolor{blue}T&\textcolor{blue}T&F&F&\textcolor{blue}F\\
F&T&F&F&F&F\\
F&F&T&T&T&T\\
F&F&F&T&F&F
\end{array}$$

Then, they would be lying.  They said either they would go to class today (they didn't) or, they would skip class AND study tomorrow.  They studied tomorrow but didn't skip class, so what they said ultimately wasn't true.






\subsection{Sage}

We can automatically generate the truth tables with SageCells.  Using the symbols:

\begin{itemize}
\item    $\&$ -and
\item    $|$-or
\item    $\sim$-not
\item    $\wedge$-xor
 \item   $->$-if-then
\item    $<->$-if and only if
\end{itemize}


We haven't covered all these operations yet.  But if we wanted to say ``$p$ or (not $q$ and $r$)"  That could be recorded as $p|(\sim q\&r)$.  So we could generate the truth table here:  \url{https://sagecell.sagemath.org/?z=eJxLU7BVKCjKL0hOzEnWS8svyi3NSdRQKqjRqCtUK9JU0uTlStMrKSotyShJTMpJ1dAEAIzpD_A=&lang=sage}  It generates the table in a different order than what we have but the same rows still correspond to the same values.



\section{Equivalent Statements}\label{Section:EquivalentStatements}


Naturally, in mathematics, we care about equivalence of things.  For example, one might say that given any $x$, $2(x+3)=2x+6$.  Another example of equivalent statements would be ``I own a red dog" and ``I own a dog and it is red."  Suffice to say, the same information can be transmitted in a lot of distinct ways, and we should have some mechanism for detecting that.\\

Let's take a closer look at $2(x+3)=2x+6$.  What does this really mean?  In essence, it says that no matter what $x$ is, the left hand side and right hand side will yield the same value.  If I plug in $x=0$ then $2(0+3)=2(0)+6=6$, if I plug in $x=4$ then $2(4+3)=2(4)+6=14$, if I plug in $x=-1$ then $2(-1+3)=2(-1)+6=4$ and so forth.  The statements $2(x+3)$ and $2x+6$ have the same value under the same circumstances.  So this is how we define equivalence of logical statements. \textbf{Two logical statements are equivalent if they have the same values under the same circumstances.}\\

For algebraic expressions like the ones above, $x$ can take on infinitely many values, so we can't just sit there and plug in infinitely many values into both sides, so it becomes imperative that we establish some sort of general rules and laws, like distribution, to avoid having to do this, while still being able to meaningfully accomplish things.  The nice thing about logical statements is that for any variable, we only have 2 possible values, $T$ or $F$.  The statement itself can only take on the values $T$ or $F$, so it's much easier to see if two logical statements are equivalent, compared to algebraic ones.\\

\begin{example}
Is ``$\sim(p \vee q)=\sim p \vee \sim q$?"\\

Before we jump into the formal stuff, it helps to concretize this with actual statements.  Let's say $p$ is ``I'll eat breakfast" and $q$ is ``I'll eat lunch".  Then $p \vee q$ is ``I'll eat breakfast or I'll eat lunch".  Is NOT doing this the same as $\sim p \vee \sim q$ which is ``I'll not eat breakfast or I'll not eat lunch?"\\

The first statement is basically ``I'm not eating breakfast or lunch", the second is ``I'll not eat breakfast or I'll not eat lunch", they sound similar spoken aloud but there is a subtle difference.\\

Let's say you skip breakfast and eat lunch.  Since you ate lunch, $p\vee q$ is true, so $\sim(p\vee q)$ must be false, you didn't not eat breakfast or eat lunch.  What about $\sim p \vee \sim q$?  Well you skipped breakfast so $\sim p$ is true and therefore $\sim p \vee \sim q$ is true, so it would seem like they are not the same.\\

Formally, we can look at these truth tables:

$$\begin{array}{c|c|c|c}
p&q&p\vee q& \sim (p\vee q)\\
\hline
T & T&T&F\\
T&F&T&F\\
F&T&T&F\\
F&F&F&T
\end{array}$$

$$\begin{array}{c|c|c|c|c}
p&q&\sim p& \sim q & \sim p \vee \sim q\\
\hline
T & T&F&F&F\\
T&F&F&T&T\\
F&T&T&F&T\\
F&F&T&T&T
\end{array}$$

So $\sim(p\vee q)$ i.e.\ ``I'm not eating breakfast or lunch" is only true if you skip both meals.  If you eat either then you lied.  On the other hand, $\sim p \vee \sim q$ i.e.\  ``I'll skip breakfast or I'll skip lunch" is true so long as you skip either meal.  It's only false if you go ahead and eat both.\\

So what does $\sim(p \vee q)$ equal?
\end{example}

\begin{example}
Does $\sim(p \vee q)=\sim p \wedge \sim q$?\\

Start with the concrete before the formal.  In our extended example, $\sim(p\vee q)$ means ``I'm not eating breakfast or lunch", whereas $\sim p \wedge \sim q$ means ``I'm not eating breakfast and I'm not eating lunch."  It does kinda seem like they're the same\ldots\\

So formally:

$$\begin{array}{c|c|c|c}
p&q&p\vee q& \sim (p\vee q)\\
\hline
T & T&T&F\\
T&F&T&F\\
F&T&T&F\\
F&F&F&T
\end{array}$$

$$\begin{array}{c|c|c|c|c}
p&q&\sim p& \sim q & \sim p \wedge \sim q\\
\hline
T & T&F&F&F\\
T&F&F&T&F\\
F&T&T&F&F\\
F&F&T&T&T
\end{array}$$

now THIS makes more sense.  In order to say ``I'm not having breakfast OR lunch"  you really are saying ``I'm skipping breakfast AND I'm skipping lunch".  So these statements are in fact identical, they have the same values under the same circumstances.\\

This is half of a pair of equivalences called \textbf{DeMorgan's Laws}:

\begin{itemize}
\item $\sim(p \vee q)=\sim p \wedge \sim q$
\item $\sim(p \wedge q)=\sim p \vee \sim q$
\end{itemize}

It's not a bad idea to check this second equivalence, build the truth tables and see if they are the same.

\end{example}



\begin{example}
Is $\sim((p \vee q)\wedge \sim r)=(\sim p \wedge \sim q )\vee r$?\\

So yeah sure, we could go ahead and build truth tables for all this, but at this point Im sure laying out 8 rows of T and F and all these combinations is a real hassle.  On the other hand, we have in fact these very nice laws described above.  One of the reasons we develop algebraic rules is convenience, so let's go ahead:

\begin{eqnarray*}
\sim((p \vee q)\wedge \sim r)&=&\sim(p \vee q)\vee \sim\sim r\ \ \text{By DeMorgan's Law}\\
&=&\sim(p \vee q)\vee r \ \ \text{since $\sim\sim r=r$}\\
&=&(\sim p \wedge \sim q )\vee r \ \ \text{by DeMorgans law again.}
\end{eqnarray*}

So yes, they are equal, fairly nice.
\end{example}



\section{Conditional Statements}\label{Section:ConditionalStatements}

These things go by a few names, conditional statements, if-then statements.  They are statements of the form ``If $p$, then $q$."  When the condition $p$ is satisfied, it implies the statement $q$.  This is written in formal logic as $p\to q.$\\


Let's suppose that you have a child and you say to them ``If you are clean your room, I'll buy you ice-cream!"  What would make you a liar and what would make you a truth teller.\\

If your kid cleans their room, and you buy them ice-cream, then hooray, you kept your promise!  If your kid cleans their room and and you don't buy them ice-cream, then you didn't keep your promise and are a liar.\\

Now this part is sometimes tricky for students, but bear with me.  If your kid doesn't clean their room, you can do whatever you want.  You only said that you would do something if they cleaned their room, you made no promises as to what you would do if they didn't.  So now whether or not you buy them ice-cream, you've technically kept your promise.  This may make you a pushover parent, depending, but it wouldn't make you a liar.\\

So, if we let $p$=``kid cleans room" and $q$=``you buy them ice-cream"  Then the above sentence may be written as $p\to q$ which has the following truth table:

$$
\begin{array}{c|c|c}
p&q&p\to q\\
\hline
T&T&T\\
T&F&F\\
F&T&T\\
F&F&T
\end{array}
$$


As we can see ``If $p$ then $q$" is always true unless $p$ happens and then $q$ does not happen as promised.

\subsection{An equivalent statement}

Notice that $p\to q$ is only false under one circumstance.  So is the statement $p\vee q$.  Is it possible then to rewrite $p\to q$ as an ``or" statement somehow?\\

I claim that $p \to q = \sim p \vee q$.  To see this, consider:


 
$$
\begin{array}{c|c|c|c|c}
p&q&p\to q&\sim p & \sim p \vee q\\
\hline
T&T&T&F&T\\
T&F&F&F&F\\
F&T&T&T&T\\
F&F&T&T&T
\end{array}
$$

And we see that these things have the same truth values and are equivalent statements.  But, more importantly, consider what $\sim p \vee q$ would mean in our example.  ``Either you don't clean your room or you can have ice-cream."  One might rephrase this as ``You can either not clean your room or you can have ice-cream."  Isn't this basically saying ``If you clean your room you can have ice-cream?"  So that definitely sounds like an equivalent statement to me.

\subsection{Negation}

What about the negation of $p\to q$?  Well, one can try all sorts of combinations of $p, q$, but what we do know is how to negate and/or statements, and how to rewrite $p\to q$ so:

\begin{eqnarray*}
\sim(p\to q)&=&\sim(\sim p \vee q)\\
&=&\sim\sim p\wedge \sim q\\
&=&p\wedge \sim q.
\end{eqnarray*}

How does that play out in practice, again using our parenting example, $p\wedge \sim q$ is ``You cleaned your room and I'm not buying you ice-cream."  Damn.  That's basically exactly the opposite of what you said before, which is what a negation is supposed to be.  

\subsection{A Longer Example}

Using these facts, we can take relatively complicated statements, break them down, and negate them with relative ease.  Consider this sentence:\\

``If it is sunny and I am in a good mood, then I will take a walk."\\

So let's let:

\begin{itemize}
\item $p$=``It's Sunny"
\item $q$=``I'm in a good mood."
\item $r$=``I take a walk".
\end{itemize}

We can summarize this whole thing as $(p\wedge q)\to r$.  It's not the easiest thing to see when this statement may be true.  So, we can break this thing down as follows:

\begin{eqnarray*}
(p\wedge q)\to r&=&\sim (p\wedge q)\vee r\\
&=&(\sim p \vee \sim q) \vee r
\end{eqnarray*}

So this is an equivalent statement, and it's not much easier to see that it is true as long as it isn't sunny, you're in a bad mood, or if you take a walk. We would read this as ``Either it's not sunny, or I'm not in a good mood, or I'm taking a walk." \\ 

 If we negate this thing:



\begin{eqnarray*}
\sim ((p\wedge q)\to r)&=&\sim ((\sim p \vee \sim q) \vee r)\\
&=&\sim (\sim p \vee \sim q) \wedge \sim r\\
&=& (\sim \sim p  \wedge \sim \sim q) \wedge \sim r\\
&=&(p\wedge q)\wedge \sim r
\end{eqnarray*}

We would read this as ``It IS sunny and I'm in a good mood and for some reason I'm not going to walk." which is the opposite of what was promised before.


\subsection{Misconceptions}

There are some common misinterpretations of the conditional statement that should be addressed.  In particular, there are colloquial statements which people believe that are equivalent to the conditional which are not.\\

Given the statement $p\to q$, is it equivalent to say $q\to p$?  (We say that $q\to p$ is the \textbf{converse} of $p\to q$.)  We can check with truth tables, but before that, let's ask ourselves this:  Suppose that $p=$``I drink bleach" and $q=$``I get sick."  I think we can all buy that $p\to q$ i.e.\ if I drink bleach then I will get sick.  Now the converse, $q\to p$ is the statement ``If I get sick, then I drank bleach".  Is this the same statement?\\

Doesn't seem so, you could have gotten sick from any sort of things, it didn't have to be bleach.  Another example is if $p=$``I'm a square" and $q=$``I'm a rectangle."  All squares are rectangles, not all rectangles are squares.  So if $p\to q$, we can think of that as all the circumstances where $p$ is true lives inside the collection of circumstances where $q$ is true, and that the reverse is not the same thing.  And of course:

$$\begin{array}{c|c|c|c}
p & q & p\to q & q\to p\\
\hline
T & T & T & T\\
T & F & F & T\\
F & T & T & F \\
F & F & T & T
\end{array}$$


So these columns are not the same and so the statements are not equal.\\

What about $\sim p \to \sim q$? (This is the  \textbf{inverse} of $p\to q$)  Well this would be ``If I'm not drinking bleach then I won't get sick" or ``If I'm not a square then I'm not a rectangle."  This doesn't seem like it's true either.  You can not drink bleach, but then drink paint thinner instead and you'd be sick, and of course there are plenty of rectangles that aren't squares.  That and:

$$\begin{array}{c|c|c|c|c|c}
p & q & p\to q &\sim p & \sim q& \sim p\to \sim q\\
\hline
T & T & T & F & F & T\\
T & F & F & F & T &T\\
F & T & T & T & F & F \\
F & F & T & T & T & T
\end{array}$$


What about $\sim q \to \sim p$ (the \textbf{ contrapositive"} of $p\to q$)?  In our example, that would be, ``If I didn't get sick then I didn't drink bleach" or ``If I'm not a rectangle then I'm not a square".  These DO seem true.  If you didn't get sick you couldn't have drank bleach, if you're not a rectangle, there's no way you could be a square.  Rather than use truth tables, consider:

\begin{eqnarray*}
\sim q \to \sim p&=&(\sim \sim q \vee \sim p)\\
&=&q \vee \sim p\\
&=&\sim p \vee q\\
&=&p\to q.
\end{eqnarray*}

So these things ARE the same.


\subsection{Biconditional}

Maybe you want to describe 2 statements where $p\to q$ and $q\to p$, i.e. whenever 1 is true then the other is true.  Well this is literally $(p\to q)\wedge (q\to p)$.



$$\begin{array}{c|c|c|c|c}
p & q & p\to q & q\to p& (p\to q)\wedge (q\to p)\\
\hline
T & T & T & T&T\\
T & F & F & T&F\\
F & T & T & F &F\\
F & F & T & T&T
\end{array}$$



We symbolize this with $p\leftrightarrow q:$



$$\begin{array}{c|c|c}
p & q & p\leftrightarrow q \\
\hline
T & T & T \\
T & F & F\\
F & T & F \\
F & F & T 
\end{array}$$



\section{Circuits}\label{Section:Circuits}

Consider $$\begin{circuitikz}

\draw (0,0) to[ospst=$p$] (2,0);

\end{circuitikz}$$

This is the diagram of the ``circuit" $p$ Imagine $T$ as been the bridge open and $F$ as the bridge closed.  Can you cross over, well, yes as long as the bridge is open, i.e. as long as $p$ is true.\\

Now how about this:


Consider $$\begin{circuitikz}

\draw (0,0) to[ospst=$p$] (2,0);

\draw (2,0) to[ospst=$q$] (4,0);

\end{circuitikz}$$

Can you get to the other side?  Well, as long as both bridges are open, i.e.  $p\wedge q$.\\


How about this? $$\begin{circuitikz}

\draw (0,0) to (2,0);
\draw (2,0) to (2,1);
\draw (2,0) to (2,-1);

\draw (2,1) to[ospst=$p$] (4,1);

\draw (2,-1) to[ospst=$q$] (4,-1);

\draw(4,1) to (4,0);
\draw(4,-1) to (4,0);

\draw(4,0) to (6,0);


\end{circuitikz}$$


Can you get from one side to the other?  Yes, as long as either bridge is open we can, so this is $p\vee q$.\\

Using these circuit diagrams, we can model any logical statement.  For example $p\wedge ((q\wedge r) \vee (\sim q \wedge \sim r))$ would be:


$$\begin{circuitikz}

\draw (0,0) to[ospst=$p$] (2,0);
\draw (2,0) to (2,1);
\draw (2,0) to (2,-1);

\draw (2,1) to[ospst=$q$] (3,1);
\draw (3,1) to[ospst=$r$] (4,1);

\draw (2,-1) to[ospst=$\sim q$] (3,-1);
\draw (3,-1) to[ospst=$\sim r$] (4,-1);

\draw(4,1) to (4,0);
\draw(4,-1) to (4,0);

\draw(4,0) to (5,0);


\end{circuitikz}$$

And


$$\begin{circuitikz}

\draw (0,0) to[ospst=$p$] (2,0);
\draw (2,0) to (2,1);
\draw (2,0) to (2,-1);

\draw (2,1) to[ospst=$q$] (3,1);
\draw (3,1) to[ospst=$r$] (4,1);

\draw (2,-1) to (3,-1);
\draw (3,-1) to (3,-.5);
\draw (3,-1) to (3,-1.5);

\draw (3,-.5) to[ospst=$\sim s$] (4,-.5);
\draw (3,-1.5) to[ospst=$\sim t$] (4,-1.5);





\draw(4,1) to (4,0);
\draw(4,-1.5) to (4,0);

\draw(4,0) to (5,0);


\end{circuitikz}$$


would be $p \wedge ((q\wedge r)\vee (\sim s\vee \sim t))$.\\

Here, it again helps to be able to break everything down into ands/ors.  We don't have something for implications, but of we wanted to do the circuit for $\sim((p\vee q)\to r)$, we could note:

\begin{eqnarray*}
\sim((p\vee q)\to r)&=&\sim(\sim(p\vee q)\vee r)\\
&=&(p\vee q)\wedge \sim r.
\end{eqnarray*}

So it's circuit would be:

$$\begin{circuitikz}

\draw (0,0) to (2,0);
\draw (2,0) to (2,1);
\draw (2,0) to (2,-1);

\draw (2,1) to[ospst=$p$] (4,1);

\draw (2,-1) to[ospst=$q$] (4,-1);

\draw(4,1) to (4,0);
\draw(4,-1) to (4,0);

\draw(4,0) to[ospst=$\sim r$] (6,0);


\end{circuitikz}$$



\section{Quantifiers}\label{Quantifiers}

There are a lot of things in the world.  A lot of people, a lot of animals, a lot of numbers, a lot of toppings available for pizza, a lot of things I could add to this list.  Presumably, sometimes we'd want to make statements about all these things, and sometimes we want to make statements about some of these things.\\

Suppose $x$ is an MSUB student and $I(x)$ is the statement ``$x$ likes ice cream."  We want to perhaps say something more subtle than this. So we introduce the quantifiers $\forall$ and $\exists$.\\

The $\forall$ is pronounced ``for all" or ``for every", indicates that the following statement is true for all values of $x$.  So $\forall I(x)$ would denote ``For every MSUB student $x$, $x$ likes Ice Cream.".  In order for a $\forall$ statement to be true, it has to be true for EVERY possible value of $x$.\\

The $\exists$ pronounced ``there exists" or ``there is" indicates the following statement is true for some values of $x$.  It could be true for 1 of them, or a bunch of them, or for all of them.  The only thing we know for sure is that there is AT LEAST 1 value of $x$ for which it is true.  So $\exists I(x)$ would mean ``There is an MSUB student who likes Ice Cream." or ``At least one MSUB student likes Ice Cream."\\

Let's let $M(x)$ be ``$x$ is a Math Major", $C(x)$ be ``$x$ takes Calculus".  Then consider the following equivalences:

$$
\begin{tabular}{c|c}
\textbf{ Logic} & \textbf{ English}\\
\hline
$\forall (M(x)\to C(x))$& For every MSUB student, if you're a Math Major then you take Calculus.\\
$\exists (\sim M(x)\wedge \sim C(x))$ & There is an MSUB student who isn't a Math Major and doesn't take Calculus.\\
$\forall \sim C(x)$ & Every MSUB student does not take calculus.
\end{tabular}
$$

Putting aside whether or not the above statements are actually true, here we just see how we can translate statements from english to logical symbols with quantifiers and back.\\

Also, whenever you see a statement $\forall p(x)$, no matter what $p(x)$ is, it is fair to deduce $\exists p(x)$ automatically.  If somethings true for EVERY $x$, then it also has to be true for at least 1 $x$.  The converse is obviously NOT true.  If something is true for a single $x$, it doesn't mean it will be true for more.


\subsection{Negating Quantifiers}

Let's consider $\forall I(x)$ or ``Every MSUB student likes Ice Cream."   If this were NOT true, what would that mean?  It would mean that there is some poor soul out on our campus who does not like Ice Cream.  In other words: $\exists \sim I(x)$.\\

What would the negation of $\exists I(x)$ be?  The statement is saying ``There is a student who likes Ice Cream."  What is the opposite of this?  It would mean that every single student doesn't like Ice Cream, i.e.\ $\forall \sim I(x)$.  So our negation rules are:

\begin{eqnarray*}
\sim(\forall p(x))&=&\exists \sim p(x)\\
\sim(\exists p(x))&=&\forall \sim p(x).
\end{eqnarray*}

So let's practice on the statements we made earlier:

\begin{itemize}
\item The negation of ``For every MSUB student, if you're a Math Major then you take Calculus." is:

\begin{eqnarray*}
\sim(\forall (M(x)\to C(x)))&=&\exists\sim (M(x)\to C(x))\\
&=&\exists\sim (\sim M(x)\vee C(x))\\
&=&\exists(M(x)\wedge \sim C(x))\\
\end{eqnarray*}
``At MSUB, there is a student who is a Math Major and doesn't take Calculus."

\item The negation of ``There is an MSUB student who isn't a Math Major and doesn't take Calculus." is:

\begin{eqnarray*}
\sim(\exists (\sim M(x)\wedge \sim C(x)))&=&\forall \sim(\sim M(x)\wedge \sim C(x))\\
&=&\forall M(x)\vee C(x)
\end{eqnarray*}

``Every student at MSUB either is a Math Major or takes Calculus."

\item The negation of ``Every MSUB student does not take calculus." is:

\begin{eqnarray*}
\sim(\forall \sim C(x))&=&\exists \sim\sim C(x)\\
&=&\exists C(x)
\end{eqnarray*}
``There is an MSUB student taking Calculus."






\end{itemize}
Again, I'm not claiming any of these things are true IRL.  But given the original statements, these should read and feel like real opposites.



\section{Argument Types}\label{Section:Arguments}

Here are some valid types of arguments.

\subsection{Modus Ponens}

$$\begin{array}{l}
p\to q \\
p\\
\hline
q
\end{array}$$

In other words, if you know $p\to q$ and $p$, then $q$ must be true.  So say ``If your pet is a pitbull, then it is a dog."  ``Your pet is a pitbull."  It would then be fair to conclude ``Therefore your pet is a dog."




\subsection{Modus Tollens}

$$\begin{array}{l}
p\to q \\
\sim q\\
\hline
\sim p
\end{array}$$

In other words, if you know $p\to q$ and $\sim q$, then $\sim p$ must be true.  So say ``If your pet is a pitbull, then it is a dog."  ``Your pet is not a dog."  It would then be fair to conclude ``Therefore your pet is not a pitbull."


\subsection{Disjunctive Syllogism}



$$\begin{array}{l}
p\vee q \\
\sim q\\
\hline
p
\end{array}$$
$$\begin{array}{l}
p\vee q \\
\sim p\\
\hline
q
\end{array}$$


If you know $p \vee q$ and one isn't true, then the other must be true.  ``I have to take either math or science next semester, I'm not going to take math, so therefore, I must take science."

\subsection{Reasoning by Transitivity}

$$\begin{array}{l}
p\to q \\
q\to r\\
\hline
p\to r
\end{array}$$

``If it rains then I will get wet.  If I get wet, I will get sick."  $\to $ ``Therefore, if it rains, I will get sick."


\section{Fallacies}\label{Fallacies}

The following are common \textbf{ Fallacies}.  They seem like they could be true but they are not.

\subsection{Fallacy of the Converse}

$$\begin{array}{l}
p\to q \\
q\\
\hline
p
\end{array}$$



\subsection{Fallacy of the Inverse}

$$\begin{array}{l}
p\to q \\
\sim p\\
\hline
\sim q
\end{array}$$

The reason these are fallacies are covered in the previous write-up.


\section{Valid and invalid arguments}\label{Section:ValidArguments}

So are the following valid?

\begin{example}
If I read the handouts and I watch the videos  then I will pass.  I didn't pass. I read the handouts, therefore I didn't watch the videos.\\

So let:

\begin{itemize}
\item $h=$``read handouts."
\item $v=$``watch videos."
\item $p=$``pass class."
\end{itemize}

So what we know is $(h\wedge v)\to p, h, \sim p.$  So:

$$\begin{array}{lcl}
(h\wedge v)\to p&\ \ \ &\\
\sim p\\
\hline
\sim(h\wedge v)=\sim h \vee\sim v & &\text{Modus Tollens}\\
 \\
\sim h \vee \sim v \\
h=\sim \sim h\\
\hline
\sim v  & &\text{Disjunctive Syllogism}
\end{array}$$

Therefore $\sim v$, I did not watch the videos.  This was a valid argument.


\end{example}


\begin{example}
If I drink coffee, I will be happy.  If I drink coffee, I will be wired.  If I am happy, then I am wired.\\

So let:

\begin{itemize}
\item $c=$``drink coffee."
\item $h=$``be happy."
\item $w=$``be wired."
\end{itemize}

What we have is $c\to h, c\to w$.  But there's nothing here to connect $h$ to $w$.  If we knew this person drank coffee, we could make that conclusion, but since we don't know that, if we knew that they were happy, it could be for some reason other than drinking coffee.  So we have no idea whether or not they'd be wired as well.  So we cannot conclude $h \to w$ and this is NOT a valid argument.


\end{example}