%!TEX root = proofs+concepts.tex

\chapter{Propositional Logic}
\label{ch.SL}

%\begin{quote}
%\it Mathematicians are like Frenchmen; when you say something to them, they translate it into their own language, and it immediately becomes something completely different.
%\par\raggedleft \small\rm\sf
%Johann Wolfgang von Goethe (1749--1832), German writer
%\\
%\emph{Maximen und Reflexionen \#1279}
%\end{quote}

\begin{quote}
\it The grand aim of all science is to cover the greatest number of
   empirical facts by logical deduction from the smallest number of
   hypotheses or axioms.
\par\raggedleft \small\rm\sf
Albert Einstein (1879--1955), Nobel prize-winning physicist
\\ 
in \emph{Life} magazine
\end{quote}

\medskip\noindent
For our purposes, Logic is the science of deciding whether or not a deduction is valid; that is, deciding whether or not a particular conclusion is a consequence of particular assumptions.  (The assumptions can also be called  ``\define[hypothesis]{hypotheses}'' or ``\define[axiom]{axioms}\rlap.'')





\section{Assertions, deductions, and validity}
\label{intro.assertions}

We will begin our discussion of Logic by introducing three basic ingredients: assertions, deductions, and validity.

Here is one possible deduction:

\label{argRaining}
\begin{earg}
\item[(1)] It is raining heavily.
\item[(2)] If you do not take an umbrella, you will get soaked.
\conclusion You should take an umbrella.
\end{earg}

\noindent 
(The validity of this particular deduction will be analyzed in \cref{argRainingInvalid} below.)

%In this first chapter, we will disucss some basic logical notions that will be used throughout the rest of the book. All of the deductions in this chapter are written in plain English, but we will soon be translating deductions from English into mathematical notation. 
%(It is important to have a clear understanding of what deductions are and of what it means for a deduction to be valid.) 



In Logic, we are only interested in sentences that can be a hypothesis or conclusion of a deduction. 
These are called ``assertions'': 

\begin{defn}
An \define{assertion} is a sentence that is either true or false.
\end{defn}

\begin{otherterm}
Some textbooks use the term \emph{proposition} or \emph{statement} or \emph{sentence}, instead of \emph{assertion}.
\end{otherterm}

%Also, there are things that would count as ``sentences'' in a linguistics or grammar course that we will not count as sentences in Logic.

\begin{eg} \ 
\begin{itemize}
\item\textbf{Questions} The sentence ``Are you sleepy yet?'' is \emph{not} an assertion. Although you might be sleepy or you might be alert, the question itself is neither true nor false. For this reason, questions do not count as assertions in Logic. 

%In contrast, suppose you answer the question: ``I am not sleepy\rlap.'' This statement is either true or false, and so it is an assertion in the logical sense. 
%
%Generally, \emph{questions} do not count as assertions, but \emph{answers} do. 
%For example, ``What is this course about?'' is not an assertion, but ``No one knows what this course is about'' is an assertion.

\item\textbf{Imperatives} Commands are often phrased as imperatives like ``Wake up!\rlap,'' ``Sit up straight\rlap,'' and so on. %(In a grammar class, these would be called imperative sentences.) 
Although it might be good for you to sit up straight or it might not, the command itself is neither true nor false. 
%Note, however, that commands are not always phrased as imperatives. ``If you sit up straight, then you will get a cookie'' is either true or false, and so it counts as an assertion in the logical sense.

\item\textbf{Exclamations} ``Ouch!'' is sometimes called an exclamatory sentence, but it is neither true nor false. so it is another example of a sentence that is not an assertion.
%We will treat ``Ouch, I hurt my toe!'' as meaning the same thing as ``I hurt my toe\rlap.'' The ``ouch'' does not add anything that could be true or false.

\end{itemize}
\end{eg}

\begin{rem}
Roughly speaking, an assertion is a statement of fact, such as ``The earth is bigger than the moon'' or ``Edmonton is the capital of Alberta\rlap.'' However, it is important to remember that an assertion may be false, in which case it is a mistake (or perhaps a deliberate lie), such as ``There are less than 1,000 automobiles in all of Canada\rlap.'' In many cases, the truth or falsity of an assertion depends on the situation. For example, the assertion ``It is raining'' is true in certain places at certain times, but it is false at others.

In this \lcnamecref{ch.SL} and the next, which are introductory, we will deal mostly with assertions about the real world, where facts are not always clear-cut. (For example, if Alice and Bob are almost the same height, it may be impossible to determine whether it is true that ``Alice is taller than Bob\rlap.'') We are taking a mathematical (or scientific) view toward Logic, not a philosophical one, so we will ignore the imperfections of these real-world assertions, which provide motivation and illustration, because our goal is to learn to use Logic to understand mathematical objects (not real-world objects), where there are no grey areas.
%You should not confuse the idea of an assertion that can be true or false with the difference between fact and opinion. Assertions will often express things that would count as facts (such as ``Justin Trudeau is the Prime Minister of Canada'' or ``Edmonton is the capital of Alberta''), but they can also express things that you might think of as matters of opinion (such as ``maple syrup tastes good on pancakes'').
\end{rem}

Throughout this text, you will find exercises that review and explore the material that has just been covered. There is no substitute for actually working through some problems, because this course, like most advanced mathematics, is more about a way of thinking than it is about memorizing facts.
\begin{exers}
\label{pr.whichassertions}
Which of the following are ``assertions'' in the logical sense?
\begin{tasks}(2)
\task\fixtask \label{pr.whichassertions.EnglandChina}%
 England is smaller than China.
\task\fixtask \label{pr.whichassertions.Greenland}%
 Greenland is south of Jerusalem.
\task\fixtask \label{pr.whichassertions.NewJersey}%
 Is New Jersey east of Wisconsin?
\task\fixtask \label{pr.whichassertions.Helium2}%
 The atomic number of helium is 2.
\task\fixtask \label{pr.whichassertions.HeliumPi}%
 The atomic number of helium is $\pi$.
%\task\fixtask \label{pr.whichassertions.HateNoodles}%
% I hate overcooked noodles.
%%\task\fixtask \label{pr.whichassertions.Blech}%
%% Blech! Overcooked noodles!
%\task\fixtask \label{pr.whichassertions.disgusting}%
% Overcooked noodles are disgusting.
\task\fixtask \label{pr.whichassertions.taketime}%
 Take your time.
\task\fixtask \label{pr.whichassertions.last}%
 This is the last question.
\task\fixtask \label{pr.whichassertions.Rihanna}%
Rihanna was born in Barbados.
\end{tasks}
\end{exers}

\begin{defn}
A \define{deduction} is a series of hypotheses that is followed by a conclusion. (The conclusion and each of the hypotheses must be an assertion.)
\end{defn}

 If the hypotheses are true and the deduction is a good one, then you have a reason to accept the conclusion.
%Notice that this definition is quite general. 

\begin{eg}
Here are two deductions.
%\smallskip
\begin{enumerate}
\item
\begin{earg}
\item[] All men are mortal.
\item[] Socrates is a man.
\conclusion Socrates is mortal.
\end{earg}

\item
\begin{earg}
\item[] The Mona Lisa was painted by Leonardo da Vinci.
\item[] Neil Armstrong was the first man on the moon.
\conclusion The Prime Minister went swimming yesterday.
\end{earg}

\end{enumerate}
The first of these deductions is very famous (and was discussed by the ancient Greek philosopher Aristotle), but the second one is lame. It may seem odd to even call it a deduction, because the two hypotheses have nothing at all to do with the conclusion, but, given our definition, it does count as a deduction. However, it is is a very poor one, so it cannot be relied on as evidence that the conclusion is true.
\end{eg}

We are interested in the deductions that \emph{do} provide solid evidence for their conclusions:

\begin{defn}
A deduction is \define[valid deduction]{valid} if its conclusion is true whenever all of its hypotheses are true. 
In other words, %it is impossible for all of its hypotheses to be true and the  conclusion to be false.
%The crucial thing about a valid deduction is that 
%it is impossible for the hypotheses to be true \emph{at the same time} that the conclusion is false. 
it is impossible to have a situation in which all of the hypotheses are true, but the conclusion is false. 
\end{defn}

  A major task of Logic is to distinguish valid deductions from invalid ones.

\begin{eg} \ 
\\ %Consider this deduction.
\vbox{%
\medskip
\begin{earg}
\item[] Oranges are either fruits or musical instruments.
\item[] Oranges are not fruits.
\conclusion Oranges are musical instruments.
\end{earg}%
}
\noindent
The conclusion is ridiculous. Nevertheless, the deduction is valid, because its conclusion follows without fail from its hypotheses; that is, \emph{if} both hypotheses were true, \emph{then} the conclusion would necessarily be true. For example, you might be able to imagine that, in some remote river valley, there is a variety of orange that is not a fruit, because it is hollow inside, like a gourd. Well, if the other hypothesis is also true in that valley, then the residents must use the oranges to play music.
\end{eg}

This shows that a logically valid deduction does not need to have true hypotheses or a true conclusion. 
Conversely, having true hypotheses and a true conclusion is not enough to make a deduction valid:

\begin{eg} \ 
\begin{earg}
\item[] London is in England.
\item[] Beijing is in China.
\conclusion Paris is in France.
\end{earg}
\noindent The hypotheses and conclusion of this deduction are, as a matter of fact, all true. This is a terrible deduction, however, because the hypotheses have nothing to do with the conclusion. For example, if Paris declared independence from the rest of France, then the conclusion would be false, even though the hypotheses would both still be true. Thus, it is \emph{logically possible} to have a situation in which the hypotheses of this deduction are true and the conclusion is false. Therefore, the deduction is \emph{not} valid.
\end{eg}


\begin{eg} \label{argRainingInvalid}
Recall the deduction that you should take an umbrella (on p.~\pageref{argRaining}, above), 
%If hypothesis (1) is false---if it is sunny outside---then the deduction gives you no reason to carry an umbrella. Furthermore, even if it is raining outside, you might not get wet. (For example, you might wear a rain poncho or keep to covered walkways.) So there are situations in which hypothesis (2) is false, since you could go out without an umbrella and still avoid getting soaked.
and suppose for a moment that both of its hypotheses are true. (Thus, you will get wet if you do not take an umbrella.) Now is it necessarily true that you should take an umbrella? No---perhaps you enjoy walking in the rain, and you would like to get soaked. In that case, even though the hypotheses were true, the conclusion would be false. Thus, the deduction is not valid.
\end{eg}

%For any deduction, there are two ways that it could be weak:
%	\begin{enumerate}
%	\item One or more of the hypotheses might be false. A deduction gives you a reason to believe its conclusion only if you believe its hypotheses. 
%	\item The deduction might not be valid, so the hypotheses fail to entail the conclusion. 
%%Even if the hypotheses were true, the form of the deduction might be weak.
%	\end{enumerate}
%The example we just considered is weak in both ways.
%
%When a deduction is weak in the second way, there is something wrong with the \emph{logical form} of the deduction: hypotheses of the kind given do not necessarily lead to a conclusion of the kind given. We will be interested primarily in the logical form of deductions.

\begin{eg} \ 
\begin{earg}
\item[] You are reading this book.
\item[] This is an undergraduate textbook.
\conclusion You are an undergraduate student.
\end{earg}
\noindent
This is not a terrible deduction, because most people who read this book are undergraduate students. Yet, it is possible for someone besides an undergraduate to read this book. For example, if a friend of yours  picked up the book and thumbed through it, they would not immediately become an undergraduate. So the hypotheses of this deduction, even though they are true, do not guarantee the truth of the conclusion. Thus, even though some people might say that the deduction has some value, it is certainly not valid.
\end{eg}

\begin{rem}
It is important to remember that validity of a deduction is not about the truth or falsity of the deduction's assertions in the real world. Instead, it is about the form of the deduction, in that the truth of the hypotheses is incompatible with the falsity of the conclusion in every possible world (real or imaginary).
Furthermore, a deduction gives you a reason to believe its conclusion only in situations where its hypotheses are true.
 \end{rem}
 
\begin{exers}
\label{pr.EnglishCombinationsa}
Which of the following is possible? If it is possible, give an example. If it is not possible, explain why.
\begin{problist}
\item \label{pr. EnglishCombinationsa-validhyps}
 A valid deduction that has one false hypothesis and one true hypothesis.
\item \label{pr. EnglishCombinationsa-validfalseconc}
 A valid deduction that has a false conclusion.
 \item \label{pr. EnglishCombinationsa-validonefalsetrue}
 A valid deduction that has at least one false hypothesis, and a true conclusion.
 \item \label{pr. EnglishCombinationsa-validalltruefalse}
 A valid deduction that has all true hypotheses, and a false conclusion.
 \item \label{pr. EnglishCombinationsa-invalidonefalsetrue}
 An invalid deduction that has at least one false hypothesis, and a true conclusion.
 \end{problist}
\end{exers}
%\begin{earg}
%\item All men are carrots.
%\item Socrates is a man.
%\item{\therefore} Therefore, Socrates is a carrot.
%\end{earg}


%\begin{earg}
%\item Abe Lincoln was either born in Illinois or he was once president.
%\item Abe Lincoln was never president.
%\conclusion Abe Lincoln was born in Illinois.
%\end{earg}

%\begin{earg}
%\item Abe Lincoln was either from France or from Luxemborg.
%\item Abe Lincoln was not from Luxemborg.
%\conclusion Abe Lincoln was from France.
%\end{earg}


%\begin{earg}
%\item If the world were to end today, then I would not need to get up tomorrow morning.
%\item I will need to get up tomorrow morning.
%\conclusion The world will not end today.
%\end{earg}


%\subsection{Inductive deductions}

%There can be good deductions which nevertheless fail to be deductively valid. Consider this one:

%\begin{earg}
%\item[] In January 1997, it rained in San Diego.
%\item[] In January 1998, it rained in San Diego.
%\item[] In January 1999, it rained in San Diego.
%\conclusion It rains every January in San Diego.
%\end{earg}

%This is an \define{inductive} deduction, because it generalizes from many cases to a conclusion about all cases.

%Certainly, the deduction could be made stronger by adding additional hypotheses: In January 2000, it rained in San Diego. In January 2001$\ldots$ and so on. Regardless of how many hypotheses we add, however, the deduction will still not be deductively valid. It is possible, although unlikely, that it will fail to rain next January in San Diego. Moreover, we know that the weather can be fickle. No amount of evidence should convince us that it rains there \emph{every} January. Who is to say that some year will not be a freakish year in which there is no rain in January in San Diego; even a single counter-example is enough to make the conclusion of the deduction false.

%Inductive deductions, even good inductive deductions, are not deductively valid. We will not be interested in inductive deductions in this book.






\section{Logic puzzles} \label{LogicPuzzlesSect}

Clear thinking (or logic) is important not only in mathematics, but in everyday life, and can also be fun;
many logic puzzles (or brain teasers) can be found on the internet or in bookstores.
%(For example, Sudoku puzzles give your logical skills a good workout.)
Here are just a few. Solving problems like these provides good practice for some of the logic skills that will be needed later in this book.

\begin{exer}[\!\normalfont(found online at \textsf{http://philosophy.hku.hk/think/logic/puzzles.php})] % \! to avoid overfull !!!
\label{RobberyPuzzle}
 There was a robbery in which a lot of goods were stolen. The robber(s) left in a truck. It is known that: 
\begin{enumerate}
\item \label{RobberyPuzzle-OnlyABC}
No one other than A, B and C was involved in the robbery. 
\item\label{RobberyPuzzle-CNotAlone}
 C never commits a crime without including A as an accomplice. 
\item \label{RobberyPuzzle-BNotDrive}
B does not know how to drive. 
\end{enumerate}
So, can you tell whether A is innocent?
%\item Suppose there is such a little town : (1) No two inhabitants have exactly the same number of hairs. (2) No inhabitant has exactly 409 hairs. (3) There are more inhabitants than there are hairs on the head of any inhabitant. So, what is the largest possible number of inhabitants in that little town?
\end{exer}



\begin{exers} \label{KnightKnave}
On the island of Knights and Knaves\rlap,\footnote{\url{http://en.wikipedia.org/wiki/Knights_and_knaves}}
every resident is either a Knight or a Knave (and they all know the status of everyone else).
It is important to know that:
\begin{itemize}
\item Knights \emph{always} tell the truth.
\item Knaves \emph{always} lie.
\end{itemize}
More precisely, every assertion spoken by a Knight is true, and every assertion spoken by a Knave is false.

You will meet some residents of the island, and your job is to figure out whether each of them is a Knight or a Knave.

\begin{enumerate}

\item \label{KnightKnave-Alice}
 You meet Alice and Bob on the island. Alice says ``Bob and I are Knights\rlap.'' Bob says, ``That's a lie! She's a Knave!'' What are they?

\item \label{KnightKnave-Charlie}
 You meet Charlie, Diane, and Ed on the island.  
Charlie says, ``Be careful, not all three of us are Knights\rlap.''
Diane says, ``But not all of us are Knaves, either\rlap.''
Ed says, ``Don't listen to them, I'm the only Knight\rlap.''
What are they?

\item \label{KnightKnave-Frances}
 You meet Frances and George on the island. Frances mumbles something, but you can't understand it. George says, ``She said she's a Knave. And she sure is --- don't trust her!'' What are they?

\end{enumerate}
\end{exers}


\begin{exer} \label{MiniSudoku}
Complete each of these mini-Sudoku puzzles, by putting a number from 1 to 4 in each box, so that no number appears twice in any row or column, or in any of the four $2 \times 2$ boxes with dark outlines. (Each of the puzzles has a unique solution.)
\smallskip
\begin{multicols}{3}
\begin{enumerate} \renewcommand{\theenumi}{\alph{enumi}}

\item \label{MiniSudoku-4123}
{\Large $\begin{array}{@{\vrule width 1.5pt \hskip\arraycolsep}c|c@{\hskip\arraycolsep\vrule width 1.5pt \hskip\arraycolsep}c|c@{\hskip\arraycolsep\vrule width 1.5pt}}
\noalign{\hrule height 1.5pt}
4&\phantom{0}&&\phantom{0}\\
\noalign{\hrule}
&&1&\\
\noalign{\hrule height 1.5pt}
&&2&\\
\noalign{\hrule}
3&&&\\
\noalign{\hrule height 1.5pt}
\end{array}$}
%solution:
%{\Large $\begin{array}{@{\vrule width 1.5pt \hskip\arraycolsep}c|c@{\hskip\arraycolsep\vrule width 1.5pt \hskip\arraycolsep}c|c@{\hskip\arraycolsep\vrule width 1.5pt}}
%\noalign{\hrule height 1.5pt}
%4&1&3&2\\
%\noalign{\hrule}
%2&3&1&4\\
%\noalign{\hrule height 1.5pt}
%1&4&2&3\\
%\noalign{\hrule}
%3&2&4&1\\
%\noalign{\hrule height 1.5pt}
%\end{array}$}

\item \label{MiniSudoku-32234}
{\Large $\begin{array}{@{\vrule width 1.5pt \hskip\arraycolsep}c|c@{\hskip\arraycolsep\vrule width 1.5pt \hskip\arraycolsep}c|c@{\hskip\arraycolsep\vrule width 1.5pt}}
\noalign{\hrule height 1.5pt}
&&3&\\
\noalign{\hrule}
&&&2\\
\noalign{\hrule height 1.5pt}
2&&&3\\
\noalign{\hrule}
4&\phantom{0}&&\\
\noalign{\hrule height 1.5pt}
\end{array}$}
%solution:
%{\Large $\begin{array}{@{\vrule width 1.5pt \hskip\arraycolsep}c|c@{\hskip\arraycolsep\vrule width 1.5pt \hskip\arraycolsep}c|c@{\hskip\arraycolsep\vrule width 1.5pt}}
%\noalign{\hrule height 1.5pt}
%1&2&3&4\\
%\noalign{\hrule}
%3&4&1&2\\
%\noalign{\hrule height 1.5pt}
%2&1&4&3\\
%\noalign{\hrule}
%4&3&2&1\\
%\noalign{\hrule height 1.5pt}
%\end{array}$}

\item \label{MiniSudoku-4121}
{\Large $\begin{array}{@{\vrule width 1.5pt \hskip\arraycolsep}c|c@{\hskip\arraycolsep\vrule width 1.5pt \hskip\arraycolsep}c|c@{\hskip\arraycolsep\vrule width 1.5pt}}
\noalign{\hrule height 1.5pt}
\phantom{0}&&&\\
\noalign{\hrule}
&&4&1\\
\noalign{\hrule height 1.5pt}
&&&2\\
\noalign{\hrule}
&1&&\\
\noalign{\hrule height 1.5pt}
\end{array}$}
% solution:
%{\Large $\begin{array}{@{\vrule width 1.5pt \hskip\arraycolsep}c|c@{\hskip\arraycolsep\vrule width 1.5pt \hskip\arraycolsep}c|c@{\hskip\arraycolsep\vrule width 1.5pt}}
%\noalign{\hrule height 1.5pt}
%1&4&2&3\\
%\noalign{\hrule}
%3&2&4&1\\
%\noalign{\hrule height 1.5pt}
%4&3&1&2\\
%\noalign{\hrule}
%2&1&3&4\\
%\noalign{\hrule height 1.5pt}
%\end{array}$}

\end{enumerate}
\end{multicols}
\end{exer}

\begin{exer} \label{MasterMind}
In a game similar to \emph{Mastermind}, one player chooses a secret $4$-digit number, using only the digits 1--6, inclusive. (Repeated digits \emph{are} allowed.) The other player makes a series of guesses. After each guess, the first player tells the other how many of the digits are in the guess are perfectly correct, and how many of the other digits are correct, but in the wrong place. In each of the following games, there is now enough information to determine the secret number. Figure out the secret number.
% (and explain how you know it is the only possibility).
\smallskip
\begin{multicols}{2}
\begin{enumerate} \renewcommand{\theenumi}{\alph{enumi}}

\medskip

\item  \label{MasterMind-4512}
$ \begin{array}{|c|c|c|}
\noalign{\hrule}
\text{guess} & \text{\# correct} & \text{\# in wrong spot} \\
\noalign{\hrule}
1234 & 0 & 3 \\
2354 & 0 & 3 \\
3642 & 1 & 1 \\
5143 & 0 & 3 \\
4512&1 &2 \\
&4 &0 \\
%3521 & 4 & 0 \\
\noalign{\hrule}
\end{array} $

\item  \label{MasterMind-5411}
$ \begin{array}{|c|c|c|}
\noalign{\hrule}
\text{guess} & \text{\# correct} & \text{\# in wrong spot} \\
\noalign{\hrule}
1234 & 0 & 2 \\
4516 & 1 & 2 \\
4621 & 1 & 1 \\
6543 & 0 & 2 \\
5411 & 0 & 3 \\
&4 &0 \\
%4155 & 4 & 0 \\
\noalign{\hrule}
\end{array} $

\end{enumerate}
\end{multicols}
\end{exer}

%Here is a version of a famous difficult problem that is said to have been made up by Albert Einstein when he was a boy, but, according to Wikipedia, there is no evidence for this.
%
%\begin{exer}[\normalfont(``Zebra Puzzle'' or ``Einstein's Riddle'')]
%There are 5~houses, all in a row, and each of a different colour. One person lives in each house, and each person has a different nationality, a different type of pet, a different model of car, and a different drink than the others. Also:
%\begin{itemize}
%\item The Englishman lives in the red house.
%\item The Spy owns the dog.
%\item Coffee is drunk in the green house.
%\item The Ukrainian drinks tea.
%\item The green house is immediately to the right of the ivory house.
%\item The Oldsmobile driver owns snails.
%\item A Cadillac is driven by the owner of the yellow house.
%\item Milk is drunk in the middle house.
%\item The Norwegian lives in the first house.
%\item The person who drives a Honda lives in a house next to the person with the fox.
%\item The person who drives a Cadillac lives next-door to the house where the horse is kept.
%\item The person with a Ford drinks orange juice.
%\item The Japanese drives a Toyota.
%\item The Norwegian lives next to the blue house.
%\end{itemize}
%Who owns the zebra? (Assume that one of the people \emph{does} have a zebra!)
%\end{exer}







%\section{Formal languages \optional}

%Here is a famous valid deduction:
%\begin{earg}
%\item[] All men are mortal.
%\item[] Socrates is a man.
%\conclusion Socrates is mortal.
%\end{earg}
%This is an iron-clad deduction. The only way you could challenge the conclusion is by denying one of the hypotheses---the logical form is impeccable. What about this next deduction?

%\begin{earg}
%\item[] All men are carrots.
%\item[] Socrates is a man.
%\conclusion Socrates is a carrot.
%\end{earg}

%This deduction might be less interesting than the first, because the second hypothesis is obviously false. There is no clear sense in which all men are carrots. Yet the deduction is valid. To see this, notice that both deductions have this form:

%\begin{earg}
%\item[] $S$ is $M$.
%\item[] All $M$s are $C$s.
%\conclusion $S$ is $C$.
%\end{earg}

%In both deductions $S$ stands for Socrates and $M$ stands for man. In the first deduction, $C$ stands for mortal; in the second, $C$ stands for carrot. Both deductions have this form, and every deduction of this form is valid. So both deductions are valid.

%%\subsection{Aristotelean logic}

%What we did here was replace words like ``man'' or ``carrot'' with symbols like ``M'' or ``C'' so as to make the logical form explicit. This is the central idea behind formal logic. We want to remove irrelevant or distracting features of the deduction to make the logical form more obvious.

%Starting with a deduction in a \emph{natural language} like English, we translate the deduction into a \emph{formal language}. Parts of the English sentences are replaced with letters and symbols. The goal is to reveal the formal structure of the deduction, as we did with these two.

%There are formal languages that work like the symbolization we gave for these two deductions. A logic like this was developed by Aristotle, a philosopher who lived in Greece during the 4th century BC. Aristotle was a student of Plato and the tutor of Alexander the Great. Aristotle's logic, with some revisions, was the dominant logic in the western world for more than two millennia.

%In Aristotelean logic, categories are replaced with capital letters. Every assertion of a deduction is then represented as having one of four forms, which medieval logicians labeled in this way: (A) All $A$s are $B$s. (E) No $A$s are $B$s. (I) Some $A$ is $B$. (O) Some $A$ is not $B$.

%It is then possible to describe valid \emph{syllogisms}, two-hypothesis deductions like the two we considered above. Medieval logicians gave mnemonic names to all of the valid deduction forms. The form of our two deductions, for instance, was called \emph{Barbara}. The vowels in the name, all As, represent the fact that the two hypotheses and the conclusion are all (A) form assertions.

%There are many limitations to Aristotelean logic. One is that it makes no distinction between kinds and individuals. So the first hypothesis might just as well be written ``All $S$s are $M$s'': All Socrateses are men. Despite its historical importance, Aristotelean logic has been superseded. The remainder of this book will discuss two formal languages:
%\begin{itemize}
%\item In \emph{\SL}, the smallest units are assertions themselves. Simple assertions are represented as letters and connected with {logical connectives} like ``and'' and ``not'' to make more complex assertions.
%\item In \emph{\QL}, the basic units are objects, properties of objects, and relations between objects.
%\end{itemize}

%

%%\subsection{Why there are different formal languages}
%When we translate a deduction into a formal language, we hope to make its logical structure clearer. We want to include enough of the structure of the English language deduction so that we can judge whether the deduction is valid or invalid. If we included every feature of the English language, all of the subtlety and nuance, then there would be no advantage in translating to a formal language. We might as well think about the deduction in English.

%At the same time, we would like a formal language that allows us to represent many kinds of English language deductions. This is one reason to prefer {\QL} to Aristotelean logic; {\QL} can represent every valid deduction of Aristotelean logic and more.

%%So when deciding on a formal language, there is inevitably a tension between wanting to capture as much structure as possible and wanting a simple formal language---simpler formal languages leave out more. This means that there is no perfect formal language. Some will do a better job than others in translating particular English-language deductions.

%In this book, we make the assumption that \emph{true} and \emph{false} are the only possible truth-values. Logical languages that make this assumption are called \emph{bivalent}, which means \emph{two-valued}. Aristotelean logic, {\SL}, and {\QL} are all bivalent, but there are limits to the power of bivalent logic. For instance, some philosophers have claimed that the future is not yet determined. If they are right, then assertions about \emph{what will be the case} are not yet true or false.
%Some formal languages accommodate this by allowing for assertions that are neither true nor false, but something in between.
%Other formal languages, so-called paraconsistent logics, allow for assertions that are both true \emph{and} false.

%The languages presented in this book are not the only possible formal languages. However, 
%First-Order Logic is the system used by mathematicians and scientists throughout the world.
%%most nonstandard logics extend on the basic formal structure of the bivalent logics discussed in this book. So this is a good place to start.




\section{Using letters to symbolize assertions}
In the remainder of this \lcnamecref{ch.SL}, we will discuss a logical language called {\SL}. 
It provides a convenient way to describe the logical relationship between two (or more) assertions, by using capital letters to represent assertions. 
Considered only as a symbol of {\SL}, the letter $A$ could mean any assertion. So, when translating from English into {\SL}, it is important to provide a \define{symbolization key}
%(or \emph{dictionary})
that specifies what assertion is represented by each letter.
%The key provides an English language assertion for each assertion letter used in the symbolization.

For example, consider this deduction:
\begin{earg}
\item[] There is an apple on the desk.
\item[] If there is an apple on the desk, then Jenny made it to class.
\conclusion Jenny made it to class.
\end{earg}
\noindent
This is obviously a valid deduction in English. 

%In symbolizing it, we want to preserve the structure of the deduction that makes it valid.
What happens if we replace each assertion with a letter? Our symbolization key would look like this:
\begin{ekey}
\item[A]There is an apple on the desk.
\item[B]If there is an apple on the desk, then Jenny made it to class.
\item[C]Jenny made it to class.
\end{ekey}
We would then symbolize the deduction in this way:
\begin{earg}
\item[] $A$
\item[] $B$
\conclusion $C$
\end{earg}
\noindent
Unfortunately, there is no necessary connection between two assertions $A$ and~$B$, which could be any assertions, and a third assertion~$C$, which could be any assertion, so this is not a valid deduction.
Thus, the validity of the original deduction has been lost in this translation; we need to do something else in order to preserve the logical structure of the original deduction and obtain a valid translation.

The important thing about the original deduction is that the second hypothesis is not merely \emph{any} assertion, logically divorced from the other assertions in the deduction. Instead, the second hypothesis contains the first hypothesis and the conclusion \emph{as parts}. Our symbolization key for the deduction only needs to include meanings for $A$ and $C$, and we can build the second hypothesis from those pieces. So we could symbolize the deduction this way:
\begin{earg}
\item[] $A$
\item[] If $A$, then $C$.
\conclusion $C$
\end{earg}
\noindent
This preserves the structure of the deduction that makes it valid, but it still makes use of the English expression ``If$\ldots$ then$\ldots$\rlap.'' Eventually, we will replace all of the English expressions with mathematical notation, but this is a good start.

The assertions that are symbolized with a single letter are called \emph{atomic assertions}, because they are the basic building blocks out of which more complex assertions are built. Whatever logical structure an assertion might have is lost when it is translated as an atomic assertion. From the point of view of {\SL}, the assertion is just a letter. It can be used to build more complex assertions, but it cannot be taken apart.

%Atomic assertions go together to make complex assertions in much the same way that physical atoms go together to make molecules. Physical atoms were originally called ``atoms''' because chemists thought that they were irreducible. Chemists were wrong, and physical atoms can be split.

%It is important to remember that a symbolization key only gives the meaning of atomic assertions for purposes of translating a specific deduction.

%\begin{rem}
%There are only twenty-six letters in the English alphabet, but there is no logical limit to the number of atomic assertions. We can use the same English letter to symbolize different atomic assertions by adding a subscript (that is, a small number written after the letter). 
%For example, we could have a symbolization key that looks like this:
%\begin{ekey}
%\item[A_1] The apple is under the armoire.
%\item[A_2] Deductions always contain atomic assertions.
%\item[A_3] Adam Ant is taking an airplane from Anchorage to Albany.
%\item[] \hfil $\vdots$ \hfil
%\item[A_{294}] Alliteration angers all astronauts.
%\end{ekey}
%Keep in mind that $A_1$,$A_2$,$A_3$,\dots\ are all considered to be different letters---when there are subscripts in the symbolization key, it is important to keep track of them.
%\end{rem}

\begin{notation}
The symbol ``$\therefore$'' means ``therefore\rlap,'' and we will often use
	$$ A, B, C, \ldots, \  \therefore Z $$
as an abbreviation for the deduction
	\begin{earg}
	\item[] $A$
	\item[] $B$
	\item[] $C$
	\item[] \  $\vdots$
	\conclusion $Z$.
	\end{earg}
\end{notation}



\section{\texorpdfstring{Connectives ($\enot$, $\eand$, $\eor$, $\implies$, $\eiff$)}{Connectives (not, and, or, implies, iff)}}\label{ConnectivesSect}
Logical connectives are used to build complex assertions from simpler pieces. There are five logical connectives in {\SL}. This table summarizes them, and they are explained below.

%\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
symbol&nickname&what it means\\
\hline
$\enot$ &not&``It is not the case that  $\blank$''\\
$\eand$ &and&``Both $\blank$\ and $\blank$''\\
$\eor$ &or&``Either $\blank$\ or $\blank$''\\
$\eif$ &implies&``If $\blank$\ then $\blank$''\\
$\eiff$ &iff&``$\blank$ if and only if $\blank$''\\
\hline
\end{tabular}
\end{center}
%\end{table}

\begin{rem}
As we learn to write proofs, it will be important to be able to produce a deduction in Propositional Logic from a sequence of assertions in English. It will also be important to be able to retrieve the English meaning from a sequence of assertions in Propositional Logic, given a symbolization key.  The above table should prove useful in both of these tasks.
\end{rem}



\subsection{\texorpdfstring{\index{not ($\enot$)}Not $(\enot)$}{Not}}%
\nindex{$\enot$}
As an example, consider how we might symbolize these assertions:
\begin{assertlist}
\item[\ex{not1}] Mary is in Barcelona.
\item[\ex{not2}] Mary is not in Barcelona.
\item[\ex{not3}] Mary is somewhere other than Barcelona.
\end{assertlist}

In order to symbolize \assert{not1}, we will need one letter. We can provide a symbolization key:

\begin{ekey}
\item[B]Mary is in Barcelona.
\end{ekey}

Note that here we are giving $B$ a different interpretation than we did in the previous section. The symbolization key only specifies what $B$ means \emph{in a specific context}. It is vital that we continue to use this meaning of $B$ so long as we are talking about Mary and Barcelona. Later, when we are symbolizing different assertions, we can write a new symbolization key and use $B$ to mean something else.

Now, \assert{not1} is simply $B$. 

Since \assert{not2} is obviously related to \assert{not1}, we do not want to introduce a different letter to represent it. To put it partly in English, the assertion means ``It is not true that~$B$\rlap.'' For short, logicians say ``Not~$B$\rlap.'' This is called the \define[negation, logical]{logical negation} of~$B$. In order to convert it entirely to symbols, we will use ``$\enot$'' to denote logical negation. Then we can symbolize ``Not~$B$'' as $\enot B$.

\assert{not3} is about whether or not Mary is in Barcelona, but it does not contain the word ``not\rlap.'' Nevertheless, they both mean ``It is not the case that Mary is in Barcelona\rlap.'' As such, we can translate both \assert{not2} and \assert{not3} as $\enot B$.
\factoidbox{
An assertion can be symbolized as $\enot\script{A}$ if
\\ it can be paraphrased in English as ``It is not the case that \script{A}\rlap.''
}
Consider these further examples:
\begin{assertlist}
\item[\ex{not4}] The widget can be replaced if it breaks.
\item[\ex{not5}] The widget is irreplaceable.
\item[\ex{not5b}] The widget is not irreplaceable.
\end{assertlist}


If we let $R$ mean ``The widget is replaceable\rlap,'' then \assert{not4} can be translated as~$R$.

What about \assert{not5}? Saying the widget is irreplaceable means that it is not the case that the widget is replaceable. So even though \assert{not5} is not negative in English, we symbolize it using negation as $\enot{R}$.

\assert{not5b} can be paraphrased as ``It is not the case that the widget is irreplaceable\rlap.'' 
Now, as we have already discussed, ``The widget is irreplaceable'' can be symbolized as ``$\enot R$\rlap.'' Therefore, \assert{not5b} can be formulated as ``it is not the case that $\enot R$\rlap.'' Hence, it is the negation of $\enot R$, so it can be symbolized as $\enot \enot R$. This is a \emph{double negation}.
%Using negation twice, we translate this as $\enot\enot R$. The two negations in a row each work as negations, so the assertion means ``It is not the case that$\ldots$ it is not the case that$\ldots$ $R$\rlap.'' 
(However, if you think about the assertion in English, it is another way of saying the same thing as \assert{not4}. 
In general, we will see that if $A$ is any assertion, then $A$ and $\enot\enot A$ are ``logically equivalent\rlap.'')

More examples:
\begin{assertlist}
\item[\ex{not6}] Elliott is short. %happy.
\item[\ex{not7}] Elliott is tall. %unhappy.
\end{assertlist}


If we let $S$ mean ``Elliot is short\rlap,'' then we can symbolize \assert{not6} as~$S$.

However, it would be a mistake to symbolize \assert{not7} as $\enot{S}$. If Elliott is tall, then he is not short---but \assert{not7} does not mean the same thing as ``It is not the case that Elliott is short\rlap.'' It could be that he is not tall but that he is not short either: perhaps he is somewhere between the two (average height). In order to symbolize \assert{not7}, we would need a new assertion letter.

For any assertion \script{A}: 
\begin{multicols}{2}
\begin{itemize}
\item If \script{A} is true, then $\enot\script{A}$ is false. 
\item If $\enot\script{A}$ is true, then \script{A} is false. 
\end{itemize}
\end{multicols}
Using ``\true'' for true and ``\false'' for false, we can summarize this in a \emph{truth table} for negation:
$$\begin{array}{c||c}
\script{A} & \enot\script{A}\\
\hline
\true & \false\\
\false & \true 
\end{array}
$$%We will discuss truth tables at greater length in the next chapter.

\begin{exers} \label{pr.monkeysuitsnot}
Using the given symbolization key, translate each English-language assertion into {\SL}.
\begin{ekey}
\item[M] Those creatures are men in suits. 
\item[C] Those creatures are chimpanzees. 
\item[G] Those creatures are gorillas.
\end{ekey}
\begin{problist}
\item \label{pr.monkeysuitsnot-notmeninsuits}
Those creatures are not men in suits.
\item \label{pr.monkeysuitsnot-notnotgorillas}
It is not the case that those creatures are not gorillas.
\item  \label{pr.monkeysuitsnot-notchimps}
Of course those creatures are not chimpanzees!
\end{problist}
\end{exers}

\vbox{
\begin{exers} \label{pr.monkeysuitsnotEng}
Using the same symbolization key, translate each symbolic assertion into English.
%\vskip-0.5\baselineskip
\begin{multicols}{5}
\begin{problist}
\item \label{pr.monkeysuitsnotEng-G}
$G$
\item \label{pr.monkeysuitsnotEng-notM}
$\enot M$
\item \label{pr.monkeysuitsnotEng-notnotC}
$\enot \enot C$
\end{problist}
\end{multicols}
\end{exers}
}


\subsection{\texorpdfstring{\index{and ($\eand$)}And $(\eand)$}{And}}%
\nindex{$\eand$}
Consider these assertions:
\begin{assertlist}
\item[\ex{and1}]Adam is athletic.
\item[\ex{and2}]Barbara is athletic.
\item[\ex{and3}]Adam is athletic, and Barbara is also athletic.
\end{assertlist}

We will need separate assertion letters for \asserts{and1}{and2}, so we define this symbolization key:
\begin{ekey}
\item[A] Adam is athletic.
\item[B] Barbara is athletic.
\end{ekey}

\assert{and1} can be symbolized as $A$.

\assert{and2} can be symbolized as $B$.

\assert{and3} can be paraphrased as ``$A$ and $B$\rlap.\,'' In order to fully symbolize this assertion, we need another symbol. We will use ``$\eand$\rlap.'' We translate ``$A$ and $B$\,'' as $A\eand B$. We will call this connective ``and'' (but many logicians call it \define[conjunction ($\eand$)]{conjunction}). 

Notice that we make no attempt to symbolize ``also'' in \assert{and3}. Words like ``both'' and ``also'' function to draw our attention to the fact that two things are being conjoined. They are not doing any further logical work, so we do not need to represent them in {\SL}.

Some more examples:
\begin{assertlist}
\item[\ex{and4}]Barbara is athletic and energetic.
\item[\ex{and5}]Barbara and Adam are both athletic.
\item[\ex{and6}]Although Barbara is energetic, she is not athletic.
\item[\ex{and7}]Barbara is athletic, but Adam is more athletic than she is.
\end{assertlist}

\assert{and4} is obviously a conjunction. The assertion says two things about Barbara, so in English it is permissible to refer to Barbara only once. It might be tempting to try this when translating the deduction: Since $B$ means ``Barbara is athletic\rlap,'' one might paraphrase the assertions as ``$B$ and energetic\rlap.'' This would be a mistake. Once we translate part of an assertion as $B$, any further structure is lost. $B$ is an atomic assertion; it is nothing more than true or false. Conversely, ``energetic'' is not an assertion; on its own it is neither true nor false. We should instead paraphrase the assertion as ``$B$ and Barbara is energetic\rlap.'' Now we need to add an assertion letter to the symbolization key. Let $E$ mean ``Barbara is energetic\rlap.'' Now the assertion can be translated as $B\eand E$.
\factoidbox{
An assertion can be symbolized as $\script{A}\eand\script{B}$ if 
\\it can be paraphrased in English as ``Both \script{A}, and \script{B}\rlap.'' 
%Each of the conjuncts must be an assertion.
}

\assert{and5} says one thing about two different subjects. It says of both Barbara and Adam that they are athletic, and in English we use the word ``athletic'' only once. In translating to {\SL}, it is important to realize that the assertion can be paraphrased as, ``Barbara is athletic, and Adam is athletic\rlap.'' Thus, this translates as $B\eand A$.

\assert{and6} is a bit more complicated. The word ``although'' sets up a contrast between the first part of the assertion and the second part. Nevertheless, the assertion says both that Barbara is energetic and that she is not athletic. In order to make the second part into an atomic assertion, we need to replace ``she'' with ``Barbara\rlap.''

So we can paraphrase \assert{and6} as, ``\emph{Both} Barbara is energetic, \emph{and} Barbara is not athletic\rlap.'' The second part contains a negation, so we paraphrase further: ``\emph{Both} Barbara is energetic \emph{and} \emph{it is not the case that} Barbara is athletic\rlap.'' This translates as $E\eand\enot B$.

\assert{and7} contains a similar contrastive structure. It is irrelevant for the purpose of translating to {\SL}, so we can paraphrase the assertion as ``\emph{Both} Barbara is athletic, \emph{and} Adam is more athletic than Barbara\rlap.'' (Notice that we once again replace the pronoun ``she'' with her name.) How should we translate the second part? We already have the assertion letter $A$ which is about Adam's being athletic and $B$ which is about Barbara's being athletic, but neither is about one of them being more athletic than the other. We need a new assertion letter. Let $M$ mean ``Adam is more athletic than Barbara\rlap.'' Now the assertion translates as $B\eand M$.
\factoidbox{Assertions that can be paraphrased ``\script{A}, but \script{B}'' or ``Although \script{A}, \script{B}'' 
\\ are best symbolized using ``and'': $\script{A}\eand\script{B}$.}

It is important to keep in mind that the assertion letters $A$, $B$, and $M$ are atomic assertions. Considered as symbols of {\SL}, they have no meaning beyond being true or false. We have used them to symbolize different English language assertions that are all about people being athletic, but this similarity is completely lost when we translate to {\SL}. No formal language can capture all the structure of the English language, but as long as this structure is not important to the deduction there is nothing lost by leaving it out.

For any assertions \script{A} and \script{B}, 
\factoidbox{$\script{A}\eand\script{B}$ is true if and only if both \script{A} and \script{B} are true.}
 We can summarize this in the {truth table} for ``and'':
$$\begin{array}{c|c||c}
\script{A} & \script{B} & \script{A}\eand\script{B}\\
\hline
\true & \true & \true\\
\true & \false & \false\\
\false & \true & \false\\
\false & \false & \false
\end{array}$$
%The connective ``and'' is \emph{commutative} because we can swap the two terms without changing the truth-value of the assertion: regardless of what \script{A} and \script{B} are, \script{A}\eand\script{B} is logically equivalent to \script{B}\eand\script{A}. 

\begin{exers} \label{pr.avacareerand}
Using the given symbolization key, translate each English-language assertion into {\SL}.
\begin{ekey}
\item[E_1] Ava is an electrician.
\item[E_2] Harrison is an electrician.
\item[F_1] Ava is a firefighter.
\item[F_2] Harrison is a firefighter.
\item[S_1] Ava is satisfied with her career.
\item[S_2] Harrison is satisfied with his career.
\end{ekey}
\begin{enumerate}
\item \label{pr.avacareerand-E1andE2}
Ava and Harrison are both electricians.
\item \label{pr.avacareerand-E2andNotS2}
Harrison is an unsatisfied electrician.
\item \label{pr.avacareerand-notE1andNotE2}
Neither Ava nor Harrison is an electrician.
\item \label{pr.avacareerand-E1andE2But}
Both Ava and Harrison are electricians, but neither of them find it satisfying.
\item \label{pr.avacareerand-Not(E2andF2)}
It cannot be that Harrison is both an electrician and a firefighter.
\item \label{pr.avacareerand-NotE1andNotF1}
Ava is neither an electrician, nor a firefighter.
\end{enumerate}
\end{exers}

\begin{exers} \label{pr.RomeoLike}
Using the given symbolization key, translate each symbolic assertion into English.
\begin{ekey}
\item[J] Romeo likes Juliet.
\item[M] Mercutio likes Juliet.
\item[T] Romeo likes Tybalt.
\end{ekey}
\begin{multicols}{3}
\begin{problist}
\item \label{pr.RomeoLike-MandJ}
$M \eand J$
\item  \label{pr.RomeoLike-JandNotT}
$J \eand \enot T$
\item  \label{pr.RomeoLike-notMandJ}
$\enot M \eand J$
\end{problist}
\end{multicols}
\end{exers}


\subsection{\texorpdfstring{\index{or ($\eor$)}Or $(\eor)$}{Or}}%
\nindex{$\eor$}
Consider these assertions:
\begin{assertlist}
\item[\ex{or1}]Either Denison will play golf with me, or he will watch movies.
\item[\ex{or2}]Either Denison or Ellery will play golf with me. 
\end{assertlist}

For these assertions we can use this symbolization key:

\vbox{%
\begin{ekey}
\item[D] Denison will play golf with me.
\item[E] Ellery will play golf with me.
\item[M] Denison will watch movies.
\end{ekey}%
}

\assert{or1} is ``Either $D$ or $M$\rlap.'' To fully symbolize this, we introduce a new symbol. The assertion becomes $D \eor M$. We will call this connective ``or'' (but many logicians call it \define[disjunction ($\eor$)]{disjunction}).

\assert{or2} is only slightly more complicated. There are two subjects, but the English assertion only gives the verb once. In translating, we can paraphrase it as. ``Either Denison will play golf with me, or Ellery will play golf with me\rlap.'' Now it obviously translates as $D \eor E$.
\smallskip
\factoidbox{
An assertion can be symbolized as $\script{A}\eor\script{B}$ if
\\ it can be paraphrased in English as ``Either \script{A}, or \script{B}\rlap.'' 
%Each of the disjuncts must be an assertion.
}

Sometimes in English, the word ``or'' excludes the possibility that both disjuncts are true. This is called an \define[or ($\eor$)!exclusive]{exclusive or}.  An \emph{exclusive or} is clearly intended when it says, on a restaurant menu, ``Entrees come with either soup or salad\rlap.'' You may have soup; you may have salad; but, if you want \emph{both} soup \emph{and} salad, then you have to pay extra.

At other times, the word ``or'' allows for the possibility that both disjuncts might be true. This is probably the case with \assert{or2}, above. I might play with Denison, with Ellery, or with both Denison and Ellery. \assert{or2} merely says that I will play with \emph{at least} one of them. This is called an \define[or ($\eor$)!inclusive]{inclusive or}.

The symbol ``$\eor$'' represents an \emph{inclusive or}.
So $D \eor E$ is true if $D$ is true, if $E$ is true, or if both $D$ and $E$ are true. It is false only if both $D$ and $E$ are false. We can summarize this with the {truth table} for ``or'':
$$\begin{array}{c|c||c}
\script{A} & \script{B} & \script{A}\eor\script{B} \\
\hline
\true & \true & \true\\
\true & \false & \true\\
\false & \true & \true\\
\false & \false & \false
\end{array}$$

Like ``and\rlap,'' the connective ``or'' is commutative: $\script{A}\eor\script{B}$ is logically equivalent to $\script{B}\eor\script{A}$ \fullcsee{BasicEquivs}{commutativity}.
\factoidbox{
In mathematical writing, ``or'' \emph{always} means \textbf{inclusive} or.
}



These assertions are somewhat more complicated:

\begin{assertlist}
\item[\ex{or3}] Either you will not have soup, or you will not have salad.
\item[\ex{or4}] You will have neither soup nor salad.
\item[\ex{or.xor}] You get either soup or salad, but not both.
\end{assertlist}

We let $S_1$ mean that you get soup and $S_2$ mean that you get salad.

\assert{or3} can be paraphrased in this way: ``Either \emph{it is not the case that} you get soup, or \emph{it is not the case that} you get salad\rlap.'' Translating this requires both ``or'' and ``not\rlap.'' It becomes $\enot S_1 \eor \enot S_2$.

\assert{or4} also requires negation. It can be paraphrased as, ``\emph{It is not the case that} either you get soup or you get salad\rlap.'' We use parentheses to indicate that ``not'' negates the entire assertion $S_1 \eor S_2$, not just $S_1$ or~$S_2$: ``It is not the case that $(S_1 \eor S_2)$\rlap.'' This becomes simply $\enot (S_1 \eor S_2)$.

Notice that the parentheses are doing important work here. The assertion $\enot S_1 \eor S_2$ would mean ``Either you will not have soup, or you will have salad\rlap.''

\assert{or.xor} is an \emph{exclusive or}. We can break the assertion into two parts. The first part says that you get one or the other. We translate this as $(S_1 \eor S_2)$. The second part says that you do not get both. We can paraphrase this as, ``It is not the case that both you get soup and you get salad\rlap.'' Using both ``not'' and ``and\rlap,'' we translate this as $\enot(S_1 \eand S_2)$. Now we just need to put the two parts together. As we saw above, ``but'' can usually be translated as ``and\rlap.'' \assert{or.xor} can thus be translated as $(S_1 \eor S_2) \eand \enot(S_1 \eand S_2)$.

Although ``$\eor$'' is an \emph{inclusive or}, the preceding paragraph illustrates that we can symbolize an \emph{exclusive or} in {\SL}. We just need more than one connective to do it.

\begin{exers} \label{pr.monkeysuitsor}
Using the given symbolization key, translate each English-language assertion into {\SL}.
\begin{ekey}
\item[M] Those creatures are men in suits. 
\item[C] Those creatures are chimpanzees. 
\item[G] Those creatures are gorillas.
\end{ekey}
\begin{problist}
\item \label{pr.monkeysuitsor-suit}
Those creatures are men in suits, or they are not.
\item \label{pr.monkeysuitsor-gor}
Those creatures are either gorillas or chimpanzees.
\item \label{pr.monkeysuitsor-chimp}
Either those creatures are chimpanzees, or they are not gorillas.
\end{problist}
\end{exers}

\begin{exers} \label{pr.spiesor}
Give a symbolization key and symbolize the following assertions in {\SL}.
\begin{problist}
\item \label{pr.spiesor-AorB}
Either Alice or Bob is a spy, but not both.
\item \label{pr.spiesor-B}
Either Bob is a spy, or it is the case both that the code has been broken and the German embassy is in an uproar.
\item \label{pr.spiesor-C}
Either the code has been broken or it has not, but the German embassy is in an uproar regardless.
\item \label{pr.spiesor-A}
Alice may or may not be a spy, but the code has been broken in any case.
\end{problist}
\end{exers}

\begin{exers} \label{RomeoLikesOr}
Using the given symbolization key, translate each assertion into English.
\begin{ekey}
\item[J] Romeo likes Juliet.
\item[M] Mercutio likes Juliet.
\item[T] Romeo likes Tybalt.
\end{ekey}
\begin{multicols}{3}
\begin{problist}
\item \label{RomeoLikesOr-MorT}
$M \eor T$
\item \label{RomeoLikesOr-Tor}
$T \eor (\enot J \eand M)$
\item \label{RomeoLikesOr-MorJ}
$\enot (M \eor J) \eand \enot T$
\end{problist}
\end{multicols}
\end{exers}


\subsection{\texorpdfstring{\index{implies ($\eif$)}Implies $(\eif)$}{Implies}}%
\nindex{$\eif$}
\label{subsection.eif}
For the following assertions, let $R$ mean ``You will cut the red wire'' and $B$ mean ``The bomb will explode\rlap.''

\begin{assertlist}
\item[\ex{if1}] If you cut the red wire, then the bomb will explode.
\item[\ex{if1'}] The bomb will explode if you cut the red wire.
\item[\ex{if2}] The bomb will explode only if you cut the red wire.
\end{assertlist}

\assert{if1} can be translated partially as ``If $R$, then $B$\rlap.'' We can rephrase this as ``$R$ implies~$B$\rlap.'' We will use the symbol ``$\eif$'' to represent ``implies'': the assertion becomes $R\eif B$. We call this connective ``implies'' or ``if-then'' (but many logicians call it a \define[conditional ($\eif$)]{conditional}). The assertion on the left-hand side ($R$ in this example) is called the \define{hypothesis}, and the assertion on the right-hand side ($B$) is called the \define{conclusion}.

\assert{if1'} tells us that if you cut the red wire, then the bomb will explode. Thus, it is logically equivalent to \assert{if1}, so it can be symbolized as $R \eif B$.

\assert{if2} is also a conditional assertion that tells us something must be true if some other thing is true. Since the word ``if'' appears in the second half of the assertion, it might be tempting to symbolize this in the same way as \asserts{if1}{if1'}. That would be a mistake.

The implication $R\eif B$ says that \emph{if} $R$ were true, \emph{then} $B$ would also be true. It does not say that your cutting the red wire is the \emph{only} way that the bomb could explode. Someone else might cut the wire, or the bomb might be on a timer. The assertion $R\eif B$ does not say anything about 
what to expect if $R$ is false. \assert{if2} is different. It says that the only conditions under which the bomb will explode involve your having cut the red wire; i.e., if the bomb explodes, then you must have cut the wire. As such, \assert{if2} should be symbolized as $B \eif R$.

\begin{rem} \label{OnlyIfSymbolization}
The paraphrased assertion ``\script{A} only if \script{B}'' 
is logically equivalent to ``If \script{A}, then~\script{B}\rlap.''
\end{rem}

%It is important to remember that the connective ``\eif'' says only that, if the hypothesis is true, then the conclusion is true. It says nothing about the \emph{causal} connection between the two events. Translating \assert{if2} as $B \eif R$ does not mean that the bomb exploding would somehow have cause your cutting the wire. Both \assert{if1} and \assertif2} suggest that, if you cut the red wire, your cutting the red wire would be the cause of the bomb exploding. They differ on the \emph{logical} connection. If \assert{if2} were true, then an explosion would tell us---those of us safely away from the bomb---that you had cut the red wire. Without an explosion, \assert{if2} tells us nothing.

\nix{Could discuss necessary and sufficient conditions here.}

``If \script{A}, then \script{B}'' means that if \script{A} is true, then so is \script{B}. So we know that if the hypothesis \script{A} is true, but the conclusion \script{B} is false, then the implication ``If \script{A}, then \script{B}'' is false. (For example, if you cut the red wire, but the bomb does not explode, then \assert{if1} is obviously false.) We now consider the other possible situations, and determine whether the assertion ``If \script{A}, then \script{B}'' is true or not.
\begin{itemize}
\item Suppose, for instance, that you do \emph{not} cut the red wire. Then \assert{if1} is not a lie, whether the bomb explodes or not, because the assertion does not promise anything in this case. Thus, we consider \assert{if1} to be true in this case. In general, if $\script{A}$ is false, then the implication ``$\script{A} \eif \script{B}$'' is true. (It does not matter whether $\script{B}$ is true or not.)
\item The only remaining case to consider is when you cut the red wire and the bomb does explode. In this case, \assert{if1} has told the truth. In general, if $\script{A}$ and~$\script{B}$ are true, then the implication ``$\script{A} \eif \script{B}$'' is true.
\end{itemize}
\factoidbox{$\script{A}\eif\script{B}$ is true unless \script{A} is true and \script{B} is false.
\\ In that case, the implication is false.}
 We can summarize this with a truth table for ``implies\rlap.''
$$\begin{array}{c|c||c}
\script{A} & \script{B} & \script{A}\eif\script{B} \\
\hline
\true & \true & \true\\
\true & \false & \false\\
\false & \true & \true\\
\false & \false & \true
\end{array}$$

\begin{rem}
Logic students are sometimes confused by the fact that $\script{A}\eif \script{B}$ is true whenever $\script{A}$ is false, but it is actually quite natural.
For example, suppose a teacher promises, ``If you do all of the homework, then you will pass the course\rlap.'' A student who fails to do all of the homework cannot accuse the teacher of a falsehood, whether he passes the course or not.

Also, people often use this principle when speaking sarcastically.  An example is the assertion, ``If Rudy is the best player on the team, then pigs can fly\rlap.'' We all know that pigs cannot fly, but, logically, the assertion is true as long as Rudy is \emph{not} the best player on the team.
\end{rem}

\begin{warn}
The connective ``implies'' is \emph{not} commutative: you cannot swap the hypothesis and the conclusion without changing the meaning of the assertion, because it is easy to find a situation in which $\script{A}\eif\script{B}$ is true, but  $\script{B}\eif\script{A}$ is false. (Namely, suppose \script{A} is false and \script{B} is true.)
\end{warn}

Let us go back to the example with which we started our discussion of~``$\eif$\rlap,'' in which $R$ is the assertion ``You will cut the red wire\rlap,'' and $B$ means ``The bomb will explode\rlap.''  There are many different ways of saying $R \eif B$ in English.  Here are some of the ways; all of these mean the same thing!
\begin{itemize}
\item If you cut the red wire, then the bomb will explode.
\item You cutting the red wire implies that the bomb will explode.
\item In any circumstances in which you cut the red wire, the bomb will explode.
\item Whenever you cut the red wire, the bomb will explode.
\item The bomb will explode whenever you cut the red wire.
\item The bomb exploding is a necessary consequence of you cutting the red wire.
\item You cutting the red wire is sufficient to ensure that the bomb will explode.
\item You cutting the red wire guarantees that the bomb will explode.
%\item You cutting the red wire is a stronger condition than the bomb exploding.
%\item The bomb exploding is a weaker condition than you cutting the red wire.
\item You cut the red wire only if the bomb will explode.
\item If the bomb does not explode, you must not have cut the red wire.
\item Either you will not cut the red wire, or the bomb will explode.
\end{itemize}

%\begin{assertlist}
%\item[\ex{if3}] Everytime a bell rings, an angel earns its wings.
%\item[\ex{if4}] Bombs always explode when you cut the red wire.
%\end{assertlist}

%Not all assertions of the form ``If$\ldots$ then$\ldots$'' are conditionals. Consider this assertion:

%\begin{assertlist}
%\item[\ex{if5}] If anyone wants to see me, then I will be on the porch.
%\end{assertlist}

%If I say this, it means that I will be on the porch, regardless of whether anyone wants to see me or not---but if someone did want to see me, then they should look for me there. If we let $P$ mean ``I will be on the porch\rlap,'' then \assert{if5} can be translated simply as $P$.

\begin{exers} \label{pr.AceMurderif}
Using the given symbolization key, translate each English-language assertion into {\SL}.
\noprelistbreak
\begin{ekey}
\item[A] Mister Ace was murdered.
\item[B] The butler committed the murder.
\item[C] The cook committed the murder.
\item[D] The Duchess is lying.
\item[E] Mister Edge was murdered.
\item[F] The murder weapon was a frying pan.
\end{ekey}
\begin{problist}
\item \label{pr.AceMurderif-AC}
If Mister Ace was murdered, then the cook did it.
\item \label{pr.AceMurderif-EnC}
If Mister Edge was murdered, then the cook did not do it.
%\item The cook did it only if the Duchess is lying.
\item \label{pr.AceMurderif-FC}
If the murder weapon was a frying pan, then the culprit must have been the cook.
\item \label{pr.AceMurderif-nFCB}
If the murder weapon was not a frying pan, then the culprit was either the cook or the butler.
\item \label{pr.AceMurderif-DE}
Either the Duchess is lying, or it was Mister Edge who was murdered.
\item \label{pr.AceMurderif-AF}
If Mister Ace was murdered, he was done in with a frying pan.
\item \label{pr.AceMurderif-CEnF}
The cook murdered Mister Edge, but she did not use the frying pan.
\end{problist}
\end{exers}

\begin{exers} \label{pr.GregorBaseballif}
Give a symbolization key and symbolize the following assertions in {\SL}.
\begin{problist}
\item \label{pr.GregorBaseballif-GL}
If Gregor plays first base, then the team will lose.
\item \label{pr.GregorBaseballif-GEnM}
If either Gregor or Evan plays first base, then there will not be a miracle.
\item \label{pr.GregorBaseballif-GEM}
If neither Gregor nor Evan plays first base, then there will be a miracle.
\item \label{pr.GregorBaseballif-LM}
The team will lose if there is no miracle.
\item \label{pr.GregorBaseballif-MnC}
If there is a miracle, then Gregor's mom will not bake cookies.
\end{problist}
\end{exers}


\begin{exers} \label{pr.SymbArg}
For each deduction, write a symbolization key and translate the deduction as well as possible into {\SL}.
\begin{problist}
\item If Dorothy plays the piano in the morning, then Roger wakes up cranky. Dorothy plays piano in the morning if she is not distracted. So if Roger does not wake up cranky, then Dorothy must be distracted.
\item It will either rain or snow on Tuesday. If it rains, Neville will be sad. If it snows, Neville will be cold. Therefore, Neville will either be sad or cold on Tuesday.
\item If Zoog remembered to do his chores, then things are clean but not neat. If he forgot, then things are neat but not clean. Therefore, things are either neat or clean---but not both.
\end{problist}
\end{exers}

\vbox{% don't want a page break inside the exercise !!!
\begin{exers} \label{RomeoLikesIf}
Using the given symbolization key, translate each assertion into English.
\begin{ekey}
\item[J] Romeo likes Juliet.
\item[M] Mercutio likes Juliet.
\item[T] Romeo likes Tybalt.
\end{ekey} 
\begin{multicols}{3}
\begin{problist}
\item \label{RomeoLikesIf-MJ}
$M \eif J$
\item \label{RomeoLikesIf-JMnT}
$J \eor (M \eif \enot T)$
\item \label{RomeoLikesIf-TJMJ}
$(T \eif J) \eand (M \eif J)$
\end{problist}
\end{multicols}
\end{exers}%
}


\subsection{\texorpdfstring{\index{iff ($\eiff$)}Iff $(\eiff)$}{Iff}}%
\nindex{$\eiff$}
Consider these assertions:
\noprelistbreak
\begin{assertlist}
\item[\ex{iff2}] The figure on the board is a triangle if it has exactly three sides.
\item[\ex{iff1}] The figure on the board is a triangle only if it has exactly three sides.
\item[\ex{iff3}] The figure on the board is a triangle if and only if it has exactly three sides.
\end{assertlist}

Let $T$ mean ``The figure is a triangle'' and $S$ mean ``The figure has exactly three sides\rlap.''

\assert{iff2} can be rephrased as, ``If the figure has exactly three sides, then it is a triangle\rlap.'' So it can be translated as $S\eif T$.

\assert{iff1} is importantly different. \Cref{OnlyIfSymbolization} tells us that it can be translated as $T\eif S$.

\assert{iff3} says two things: that ``$T$ is true if $S$ is true'' \emph{and} that ``$T$ is true only if $S$ is true\rlap.'' The first half is \assert{iff2}, and the second half is \assert{iff1}; thus, it can be translated as 
$$ (S\eif T) \eand (T \eif S) .$$
However, this ``if and only if'' comes up so often that it has its own name. We call this connective ``\define[iff ($\eiff$)]{iff}\rlap,'' which is short for ``if and only if'' (but many logicians call it a \define[biconditional ($\eiff$)]{biconditional}).

Because we could always write $(\script{A}\eif\script{B})\eand(\script{B}\eif\script{A})$ instead of $\script{A}\eiff\script{B}$, we do not strictly speaking \emph{need} to introduce a new symbol for ``iff\rlap.'' Nevertheless, it is useful so often that it is commonly accepted as one of the basic logical connectives.
\factoidbox{$\script{A}\eiff\script{B}$ is true if and only if \script{A} and \script{B} have the same truth value \\(either both are true or both are false).}
This is the truth table for ``iff'':
$$\begin{array}{c|c||c}
\script{A} & \script{B} & \script{A}\eiff\script{B}\\
\hline
\true & \true & \true\\
\true & \false & \false\\
\false & \true & \false\\
\false & \false & \true
\end{array}$$
\begin{exers} \label{pr.avacareeriff}
Using the given symbolization key, translate each English-language assertion into {\SL}.
\begin{ekey}
\item[E_1] Ava is an electrician.
\item[E_2] Harrison is an electrician.
\item[F_1] Ava is a firefighter.
\item[F_2] Harrison is a firefighter.
\item[S_1] Ava is satisfied with her career.
\item[S_2] Harrison is satisfied with his career.
\end{ekey}
\begin{problist}
\item \label{pr.avacareeriff-AnH}
If Ava is not an electrician, then neither is Harrison, but if she is, then he is too.
\item \label{pr.avacareeriff-AiffnH}
Ava is satisfied with her career if and only if Harrison is not satisfied with his.
\item \label{pr.avacareeriff-HAiffnE}
Harrison and Ava are both firefighters if and only if neither of them is an electrician.
\end{problist}
\end{exers}

\vbox{% don't want a page break in the exercise !!!
\begin{exers}\label{RomeoLikesIff}
Using the given symbolization key, translate each assertion into English.
\begin{ekey}
\item[J] Romeo likes Juliet.
\item[M] Mercutio likes Juliet.
\item[T] Romeo likes Tybalt.
\item[Y] Romeo likes Yorick.
\end{ekey}
\begin{multicols}{3}
\begin{problist}
\item \label{RomeoLikesIff-TiffY}
$T \eiff Y$
\item \label{RomeoLikesIff-MiffJY}
$M \eiff (J \eor Y)$
\item \label{RomeoLikesIff-JiffMTY}
$(J \eiff M) \eand (T \eif Y)$
\end{problist}
\end{multicols}
\end{exers}%
}




\section{Determining whether an assertion is true} \label{DeterminingTrue}

%The truth-value of assertions that contain only one connective is given by the truth table for that connective. 
To put them all in one place, the truth tables for the connectives of {\SL} are repeated here:
% in \cref{table.CharacteristicTTs}.
\medskip
%\begin{figure}[ht]
%\begin{center}
\factoidbox{$\begin{array}{c||c}
\script{A} & \enot\script{A}\\
\hline
\true & \false\\
\false & \true 
\end{array}
\qquad
\begin{array}{c|c||c|c|c|c}
\script{A} & \script{B} & \script{A}\eand\script{B} & \script{A}\eor\script{B} & \script{A}\eif\script{B} & \script{A}\eiff\script{B}\\
\hline
\true & \true & \true & \true & \true & \true\\
\true & \false & \false & \true & \false & \false\\
\false & \true & \false & \true & \true & \false\\
\false & \false & \false & \false & \true & \true
\end{array}$}
\begin{center}
%\end{center}
%\caption
\textsf{Truth tables for the connectives of {\SL}.}
\end{center}
%\label{table.CharacteristicTTs}
%\end{figure}
\medskip
Every advanced math student needs to be able to quickly reproduce \emph{all} of these truth tables, without looking them up.

Using these tables, you should be able to decide whether any given assertion is true or false, for any particular values of its assertion letters.
(In this \lcnamecref{DeterminingTrue}, we often refer to assertion letters as ``\define[variable]{variables}\rlap.'')
%We use \true\ to represent the value \define{true}, and \false\ ~to represent the value \define{false}.

\begin{eg}
Assume
	$A$ is true,
	$B$ is false,
	and
	$C$ is false.
Is %the assertion 
$(A \eor B) \eif (B \eand \enot C)$ true?
\end{eg}

\begin{solution}
We have
	\begin{align*}
	(A \eor B) \eif (B \eand \enot C)
	&\quad= \quad(\true \eor \false) \eif (\false \eand \enot \false)
	\\&\quad= \quad\true \eif (\false \eand \true)
	\\&\quad= \quad\true \eif \false
	\\&\quad= \quad\false
	. \end{align*}
The assertion is not true.
\end{solution}

\emph{What does this mean in English?}
Suppose, for example, that  we have the symbolization key
	\begin{ekey}
	\item[A] Bill baked an apple pie,
	\item[B] Bill baked a banana pie,
	\item[C] Bill baked a cherry pie.
	\end{ekey}
Also suppose Ellen tells us (maybe because she knows what ingredients Bill has):
	\begin{quote}
	 If Bill baked either an apple pie or a banana pie, \\
	then he baked a banana pie, but did not bake a cherry pie.
	\end{quote}
Now, it turns out that
	$$ \text{Bill baked an apple pie, but did not bake a banana pie, and did not bake a cherry pie.} $$
Then the above calculation shows that \emph{Ellen was wrong}; her assertion is \emph{false}.

\begin{eg}
Assume $A$ is true, $B$ is false, and $C$ is true.
Is \ $(A \eor C) \eif \enot (A \eif B) $ \ true?

\begin{solution}
We have
	\begin{align*}
	(A \eor C) \eif \enot (A \eif B)
	&\speq (\true \eor \true)  \eif \enot (\true \eif \false)
	\\& \speq \true \eif  \enot \false
	\\& \speq \true \eif  \true
	\\& \speq \true
	. \end{align*}
The assertion is true.
\end{solution}
\end{eg}

\begin{exers} \label{TFEx}
Determine whether each assertion is true for the given values of the variables.
\noprelistbreak 
\begin{tasks}(2) 
\task\fixtask \label{TFEx-ABC}%%
 $(A \eor C) \eif \enot (A \eif B) $
	\begin{enumerate}
	\item \label{TFEx-ABC-TFF}
 $A$ is true, $B$ is false, and $C$ is false.
	\item \label{TFEx-ABC-FTF}
 $A$ is false, $B$ is true, and $C$ is false.
	\end{enumerate}

\task\fixtask \label{TFEx-PQR}%%
 $ \bigl(P \eor \enot (Q \eif R) \bigr) \eif \bigl( (P \eor Q) \eand R \bigr)$
	\begin{enumerate}
	\item \label{TFEx-PQR-TTT}
 $P$, $Q$, and~$R$ are all true.
	\item \label{TFEx-PQR-TFT}
 $P$ is true, $Q$ is false, and $R$ is true.
	\item \label{TFEx-PQR-FTF}
 $P$ is false, $Q$ is true, and $R$ is false.
	\item \label{TFEx-PQR-FFF}
 $P$, $Q$, and~$R$ are all false.
	\end{enumerate}

\task\fixtask \label{TFEx-UVW}%%
 $\bigl( (U \eand \enot V) \eor (V \eand \enot W) \eor (W \eand \enot U) \bigr)$
 	\newline\hbox{\hskip 4em} $\eif \enot (U \eand V \eand W)$ % manually break the formula !!!
	\begin{enumerate}
	\item \label{TFEx-UVW-TTT}
 $U$, $V$, and~$W$ are all true.
	\item \label{TFEx-UVW-TTF}
 $U$ is true, $V$ is true, and $W$ is false.
	\item \label{TFEx-UVW-FTF}
 $U$ is false, $V$ is true, and $W$ is false.
	\item \label{TFEx-UVW-FFF}
 $U$, $V$, and~$W$ are all false.
	\end{enumerate}

\task\fixtask \label{TFEx-XY}%%
 $(X \eor \enot Y) \eand (X \eif Y)$
	\begin{enumerate}
	\item \label{TFEx-XY-TT}
 $X$ and $Y$ are both true.
	\item \label{TFEx-XY-TF}
 $X$ is true and $Y$ is false.
	\item \label{TFEx-XY-FT}
 $X$ is false and $Y$ is true.
	\item \label{TFEx-XY-FF}
 $X$ and $Y$ are both false.
	\end{enumerate}
\end{tasks}
\end{exers}

%\section{Other symbolization \optional}
%We have now introduced all of the connectives of {\SL}. We can use them together to translate many kinds of assertions. Consider these examples of assertions that use the English-language connective ``unless'':

%\begin{assertlist}
%\item[\ex{unless1}] Unless you wear a jacket, you will catch cold. 
%\item[\ex{unless2}] You will catch cold unless you wear a jacket. 
%\end{assertlist}

%Let $J$ mean ``You will wear a jacket'' and let $C$ mean ``You will catch a cold\rlap.''

%We can paraphrase \assert{unless1} as ``Unless $J$, $C$\rlap.'' This means that if you do not wear a jacket, then you will catch cold; with this in mind, we might translate it as $\enot J \eif C$. It also means that if you do not catch a cold, then you must have worn a jacket; with this in mind, we might translate it as $\enot C \eif J$.

%Which of these is the correct translation of \assert{unless1}? Both translations are correct, because the two translations are logically equivalent in {\SL}.

%\assert{unless2}, in English, is logically equivalent to \assert{unless1}. It can be translated as either $\enot J \eif C$ or $\enot C \eif J$.

%When symbolizing assertions like \assert{unless1} and \assert{unless2}, it is easy to get turned around. Since ``implies'' is not commutative, it would be wrong to translate either assertion as $J \eif \enot C$. Fortunately, there are other logically equivalent expressions. Both assertions mean that you will wear a jacket or---if you do not wear a jacket---then you will catch a cold. So we can translate them as $J \eor C$. (You might worry that the ``or'' here should be an exclusive or. However, the assertions do not exclude the possibility that you might \emph{both} wear a jacket \emph{and} catch a cold; jackets do not protect you from all the possible ways that you might catch a cold.)

%
%\factoidbox{
%If an assertion can be paraphrased as ``Unless \script{A}, \script{B}\rlap,'' then it can be symbolized as $\script{A}\eor\script{B}$.
%}

%Symbolization of standard assertion types is summarized on p.~\pageref{app.symbolization}.





%\section{Assertions of {\SL} \optional}
%The assertion ``Apples are red, or berries are blue'' is an assertion of English, and the assertion ``$(A\eor B)$'' is an assertion of {\SL}. Although we can identify assertions of English when we encounter them, we do not have a formal definition of ``assertion of English\rlap.'' In {\SL}, it is possible to formally define what counts as an assertion. This is one respect in which a formal language like {\SL} is more precise than a natural language like English.

%It is important to distinguish between the logical language {\SL}, which we are developing, and the the language that we use to talk about {\SL}. When we talk about a language, the language that we are talking about is called the \define{object language}. The language that we use to talk about the object language is called the \define{metalanguage}.
%\label{def.metalanguage}

%The object language in this chapter is {\SL}. The metalanguage is English---not conversational English, but English supplemented with some logical and mathematical vocabulary. The assertion ``$(A\eor B)$'' is an assertion in the object language, because it uses only symbols of {\SL}. The word ``assertion'' is not itself part of {\SL}, however, so the assertion ``This expression is an assertion of {\SL}'' is not an assertion of {\SL}. It is an assertion in the metalanguage, an assertion that we use to talk \emph{about} {\SL}.

%In this section, we will give a formal definition for ``assertion of {\SL}\rlap.'' The definition itself will be given in mathematical English, the metalanguage.

%\subsection{Expressions}
%\nix{The concept of an expression does not actually do any work, since a wff can be defined without reference to it. Yet it is sometimes handy to be able to use the word.}

%There are three kinds of symbols in {\SL}:

%\begin{center}
%\begin{tabular}{|c|c|}
%\hline
%assertion letters & $A,B,C,\ldots,Z$\\
%with subscripts, as needed & $A_1, B_1,Z_1,A_2,A_{25},J_{375},\ldots$\\
%\hline
%connectives & \enot,\eand,\eor,\eif,\eiff\\
%\hline
%parentheses&( , )\\
%\hline
%\end{tabular}
%\end{center}

%We define an \define{expression of {\SL}} as any string of symbols of {\SL}. Take any of the symbols of {\SL} and write them down, in any order, and you have an expression.

%
%\subsection{Well-formed formulae}

%Since any sequence of symbols is an expression, many expressions of {\SL} will be gobbledegook. A meaningful expression is called a \emph{well-formed formula}. It is common to use the acronym \emph{wff}; the plural is wffs.

%Obviously, individual assertion letters like $A$ and $G_{13}$ will be wffs. We can form further wffs out of these by using the various connectives. Using negation, we can get $\enot A$ and $\enot G_{13}$. Using conjunction, we can get $A \eand G_{13}$, $G_{13} \eand A$, $A \eand A$, and $G_{13} \eand G_{13}$. We could also apply negation repeatedly to get wffs like $\enot \enot A$ or apply negation along with conjunction to get wffs like $\enot(A \eand G_{13})$ and $\enot(G_{13} \eand \enot G_{13})$. The possible combinations are endless, even starting with just these two assertion letters, and there are infinitely many assertion letters. So there is no point in trying to list all the wffs.

%Instead, we will describe the process by which wffs can be constructed. Consider negation: Given any wff \script{A} of {\SL}, $\enot\script{A}$ is a wff of {\SL}. It is important here that \script{A} is not the assertion letter $A$. Rather, it is a variable that stands in for any wff at all. Notice that this variable \script{A} is not a symbol of {\SL}, so $\enot\script{A}$ is not an expression of {\SL}. Instead, it is an expression of the metalanguage that allows us to talk about infinitely many expressions of {\SL}: all of the expressions that start with the negation symbol. Because \script{A} is part of the metalanguage, it is called a \emph{metavariable}.

%We can say similar things for each of the other connectives. For instance, if \script{A} and \script{B} are wffs of {\SL}, then $(\script{A}\eand\script{B})$ is a wff of {\SL}. Providing clauses like this for all of the connectives, we arrive at the following formal definition for a {well-formed formula of {\SL}}:

%\begin{enumerate}
%\item Every atomic assertion is a wff.
%\item If \script{A} is a wff, then $\enot\script{A}$ is a wff of {\SL}.
%\item If \script{A} and \script{B} are wffs, then $(\script{A}\eand\script{B})$, is a wff.
%\item If \script{A} and \script{B} are wffs, then $(\script{A}\eor\script{B})$ is a wff.
%\item If \script{A} and \script{B} are wffs, then $(\script{A}\eif\script{B})$ is a wff.
%\item If \script{A} and \script{B} are wffs, then $(\script{A}\eiff\script{B})$ is a wff.
%\item All and only wffs of {\SL} can be generated by applications of these rules.
%\end{enumerate}

%
%Notice that we cannot immediately apply this definition to see whether an arbitrary expression is a wff. Suppose we want to know whether or not $\enot \enot \enot D$ is a wff of {\SL}. Looking at the second clause of the definition, we know that $\enot \enot \enot D$ is a wff \emph{if} $\enot \enot D$ is a wff. So now we need to ask whether or not $\enot \enot D$ is a wff. Again looking at the second clause of the definition, $\enot \enot D$ is a wff \emph{if} $\enot D$ is. Again, $\enot D$ is a wff \emph{if} $D$ is a wff. Now $D$ is an assertion letter, an atomic assertion of {\SL}, so we know that $D$ is a wff by the first clause of the definition. So for a compound formula like $\enot \enot \enot D$, we must apply the definition repeatedly. Eventually we arrive at the atomic assertions from which the wff is built up.

%Definitions like this are called \emph{recursive}. Recursive definitions begin with some specifiable base elements and define ways to indefinitely compound the base elements. To determine whether or not something meets the definition, you may have to refer back to the definition many times.

%The connective that you look to first in decomposing an assertion is called the \define{main logical operator} of that assertion. For example. The main logical operator of $\enot (E \eor (F \eif G))$ is negation, \enot. The main logical operator of $(\enot E \eor (F \eif G))$ is disjunction, \eor.

%
%\subsection{Assertions}
%Recall that an assertion is a meaningful expression that can be true or false. Since the meaningful expressions of {\SL} are the wffs and since every wff of {\SL} is either true or false, the definition for an assertion of {\SL} is the same as the definition for a wff. Not every formal language will have this nice feature. In the language {\QL}, which is developed later in the book, there are wffs which are not assertions. 

%The recursive structure of assertions in {\SL} will be important when we consider the circumstances under which a particular assertion would be true or false. The assertion $\enot \enot \enot D$ is true if and only if the assertion $\enot \enot D$ is false, and so on through the structure of the assertion until we arrive at the atomic components: $\enot \enot \enot D$ is true if and only if the atomic assertion $D$ is false. We will return to this point in the next chapter.

%
%%\null{This should come as no surprise. In English, there are meaningful expressions that are not assertions. Take, for example, ``the tallest peak in the Himalayas\rlap.''}

%
%\subsection{Notational conventions}
%\label{{\SL}conventions}
%A wff like $(Q \eand R)$ must be surrounded by parentheses, because we might apply the definition again to use this as part of a more complicated assertion. If we negate $(Q \eand R)$, we get $\enot(Q \eand R)$. If we just had $Q \eand R$ without the parentheses and put a negation in front of it, we would have $\enot Q \eand R$. It is most natural to read this as meaning the same thing as $(\enot Q \eand R)$, something very different than $\enot(Q\eand R)$. The assertion $\enot(Q \eand R)$ means that it is not the case that both $Q$ and $R$ are true; $Q$ might be false or $R$ might be false, but the assertion does not tell us which. The assertion $(\enot Q \eand R)$ means specifically that $Q$ is false and that $R$ is true. As such, parentheses are crucial to the meaning of the assertion.

%So, strictly speaking, $Q \eand R$ without parentheses is \emph{not} an assertion of {\SL}. When using {\SL}, however, we will often be able to relax the precise definition so as to make things easier for ourselves. We will do this in several ways.

%First,  we understand that $Q \eand R$ means the same thing as $(Q \eand R)$. As a matter of convention, we can leave off parentheses that occur \emph{around the entire assertion}.

%Second, it can sometimes be confusing to look at long assertions with many, nested pairs of parentheses. We adopt the convention of using square brackets ``['' and ``]'' in place of parenthesis. There is no logical difference between $(P\eor Q)$ and $[P\eor Q]$, for example. The unwieldy assertion
%$$(((H \eif I) \eor (I \eif H)) \eand (J \eor K))$$
%could be written in this way:
%$$\bigl[(H \eif I) \eor (I \eif H)\bigr] \eand (J \eor K)$$

%
%Third, we will sometimes want to translate the conjunction of three or more assertions. For the assertion ``Alice, Bob, and Candice all went to the party\rlap,'' suppose we let $A$ mean ``Alice went\rlap,'' $B$ mean ``Bob went\rlap,'' and $C$ mean ``Candice went\rlap.'' The definition only allows us to form a conjunction out of two assertions, so we can translate it as $(A \eand B) \eand C$ or as $A \eand (B \eand C)$. There is no reason to distinguish between these, since the two translations are logically equivalent. There is no logical difference between the first, in which $(A \eand B)$ is conjoined with $C$, and the second, in which $A$ is conjoined with $(B \eand C)$.  So we might as well just write $A \eand B \eand C$. As a matter of convention, we can leave out parentheses when we conjoin three or more assertions.

%Fourth, a similar situation arises with multiple disjunctions. ``Either Alice, Bob, or Candice went to the party'' can be translated as $(A \eor B) \eor C$ or as $A \eor (B \eor C)$. Since these two translations are logically equivalent, we may write $A \eor B \eor C$.

%These latter two conventions only apply to multiple conjunctions or multiple  disjunctions. If a series of connectives includes both disjunctions and conjunctions, then the parentheses are essential; as with $(A \eand B) \eor C$ and $A \eand (B \eor C)$. The parentheses are also required if there is a series of conditionals or biconditionals; as with $(A \eif B) \eif C$ and $A \eiff (B \eiff C)$.

%We have adopted these four rules as \emph{notational conventions}, not as changes to the definition of an assertion. Strictly speaking, $A \eor B \eor C$ is still not an assertion. Instead, it is a kind of shorthand. We write it for the sake of convenience, but we really mean the assertion $(A \eor (B \eor C))$.

%If we had given a different definition for a wff, then these could count as wffs. We might have written rule 3 in this way: ``If \script{A}, \script{B}, $\ldots$ \script{Z} are wffs, then $(\script{A}\eand\script{B}\eand\ldots\eand\script{Z})$, is a wff\rlap.'' This would make it easier to translate some English assertions, but would have the cost of making our formal language more complicated. We would have to keep the complex definition in mind when we develop truth tables and a proof system. We want a logical language that is \emph{expressively simple} and allows us to translate easily from English, but we also want a \emph{formally simple} language. Adopting notational conventions is a compromise between these two desires.










%\solutions
%\problempart
%\label{pr.wiff{\SL}}
%For each of the following: (a) Is it a wff of {\SL}? (b) Is it an assertion of {\SL}, allowing for notational conventions?
%\begin{enumerate}
%\item $(A)$
%\item $J_{374} \eor \enot J_{374}$
%\item $\enot \enot \enot \enot F$
%\item $\enot \eand S$
%\item $(G \eand \enot G)$
%\item $\script{A} \eif \script{A}$
%\item $(A \eif (A \eand \enot F)) \eor (D \eiff E)$
%\item $[(Z \eiff S) \eif W] \eand [J \eor X]$
%\item $(F \eiff \enot D \eif J) \eor (C \eand D)$
%\end{enumerate}



%\problempart
% In \cref{ch.SL}, we symbolized \emph{exclusive or} using \eor, \eand, and~\enot. 
%\begin{enumerate}
%%\item Are there any wffs of {\SL} that contain no assertion letters? Why or why not?
%\item Symbolize $\eif$ using only $\eor$ and~$\enot$.
%\item Symbolize $\eor$ using only $\eif$ and~$\enot$.
%\item Symbolize $\eand$ using only $\eor$ and~$\enot$.
%\item Symbolize $\eand$ using only $\eif$ and $\enot$.
%\item Symbolize \emph{exclusive or} using only $\eif$ and~$\enot$.
%\end{enumerate}



\section{Tautologies and contradictions} \label{TautologySect}

Most assertions are true in some situations, and false in others. But some assertions are true in all situations, and others are false in all situations.

\begin{defn} \ 
\begin{itemize}
\item A \define{tautology} is an assertion of {\SL} that is true in all situations; that is, it is true for all possible values of its variables.
\item A \define{contradiction} is an assertion of {\SL} that is false in all situations; that is, it is false for all possible values of its variables.
\end{itemize}
\end{defn}


%\begin{eg}
%Consider the assertion $R \eif R$. 
%	\begin{itemize}
%	\item If $R$ is true, then 
%		$$ R \eif R 
%		\quad = \quad \true \eif \true
%		\quad = \quad \true
%		. $$
%	\item If $R$ is false, then 
%		$$ R \eif R 
%		\quad = \quad \false \eif \false
%		\quad = \quad \true
%		. $$
%	\end{itemize}
%Thus, the assertion is true in all possible situations (that is, whether $R$ is true or not), so it is a tautology.
%\end{eg}

\begin{eg}
The assertion $A \eor B$ is true when $A$~is true (or $B$ is true), but it is false when $A$ and~$B$ are both false. Thus, the assertion is sometimes true and sometimes false; it is neither a contradiction nor a tautology.
\end{eg}

\begin{eg}
Show that the assertion $\bigl( P \eand (\enot Q \eor \enot R) \bigr) \eif (P \eif \enot Q)$ is neither a tautology nor a contradiction.
\end{eg}

\begin{scratchwork}
We need to find values of the variables that make the assertion true, and other values that make the assertion false.

It is easy to make the assertion true, because an implication is true whenever its conclusion is true, so we just need to make $P \eif \enot Q$ true. And we can make this true by making $\enot Q$ true. So we let $Q$ be false. Then we can let $P$ and~$R$ be whatever we want: it's probably simplest to let them both be false (the same as~$Q$).

To make the assertion false, we need to make its hypothesis true and its conclusion false.
	\begin{itemize}
	\item Let's start with the conclusion $P \eif \enot Q$. To make this false, we need to make $P$ true and $\enot Q$ false. Thus, we let $P = \true$ and $Q = \true$.
	\item Now, we consider the hypothesis $P \eand (\enot Q \eor \enot R)$. Fortunately, we already decided to make~$P$ true, but we also need to make $\enot Q \eor \enot R$ true. Since we already decided to make $Q$ true, we need to make $\enot R$ true, so we let $R = \false$. 
	\end{itemize}
\end{scratchwork}

\begin{solution}
If $P$, $Q$, and~$R$ are all false, then
	\begin{align*}
	\bigl( P \eand (\enot Q \eor \enot R) \bigr) \eif (P \eif \enot Q)
	& \quad = \quad \bigl( \false \eand (\enot \false \eor \enot \false) \bigr) \eif (\false \eif \enot \false)
	\\& \quad = \quad \bigl( \false \eand (\true \eor \true) \bigr) \eif (\false \eif \true)
	\\& \quad = \quad \bigl( \false \eand \true \bigr) \eif (\true)
	\\& \quad = \quad \false  \eif \true
	\\& \quad = \quad \true
	, \end{align*}
whereas if $P$ and~$Q$ are true, but $R$ is false, then
	\begin{align*}
	\bigl( P \eand (\enot Q \eor \enot R) \bigr) \eif (P \eif \enot Q)
	& \quad = \quad \bigl( \true \eand (\enot \true \eor \enot \false) \bigr) \eif (\true \eif \enot \true)
	\\& \quad = \quad \bigl( \true \eand (\false \eor \true) \bigr) \eif (\true \eif \false)
	\\& \quad = \quad \bigl( \true \eand \true \bigr) \eif (\false)
	\\& \quad = \quad \true  \eif \false
	\\& \quad = \quad \false
	. \end{align*}
Thus, the assertion is sometimes true and sometimes false, so it is neither a tautology nor a contradiction.
\end{solution}

\begin{exers} \label{NotTaut}
Show that each of the following assertions is neither a tautology nor a contradiction.
	\begin{tasks}(3)
	\task\fixtask \label{NotTaut-A->}%
 $A \eif (A \eand B)$
	\task\fixtask \label{NotTaut-AorB}%
 $(A \eor B) \eif A$
	\task\fixtask \label{NotTaut-A<>B}%
 $(A \eiff B) \eor (A \eand \enot B)$ 
	\task\fixtask \label{NotTaut-Z->Z}%
 $(X \eif Z) \eif (Y \eif Z)$
	\task\fixtask \label{NotTaut-(Q->R}%
 $\bigl( P \eand \enot(Q \eand R) \bigr) \eor (Q {\eif} R)$ % {\eif} to avoid overfull !!!
%	\task\fixtask \label{NotTaut-(P->notQ)}%
% $\bigl( P \eand (\enot Q \eor \enot R) \bigr) \eif (P \eif \enot Q)$
%	\task\fixtask \label{NotTaut-P->Q}%
% $\bigl( (P \eif Q) \eand (Q \eif R) \bigr) \eif (R \eif P)$
%	\task\fixtask \label{NotTaut-X<>Y}%
% $(X \eiff Y) \eor (X \eiff Z) \eor (Y \eand Z)$
%	\task\fixtask \label{NotTaut-notX}%
%$( \enot X \eor \enot Y \eor \enot Z) \eif \bigl( (\enot X \eor \enot Y) \eand (\enot Y \eor \enot Z) \bigr)$
	\end{tasks}
\end{exers}

%By evaluating an assertion of {\SL}  for all possible values of its variables, you can decide whether it is a tautology, a contradiction, or neither.
%
%\begin{eg}
%Is the assertion $(H \eand I) \eif H$ a tautology?
%\end{eg}
%
%\begin{solution}
%The variables $H$ and~$I$ may each be either true or false, and we will evaluate the assertion for all possible combinations. To make it clear that none of the possibilities have been missed, we proceed systematically: for each value of~$H$, we consider the two possible values for~$I$.
%%To do this systematically, we assign a value to~$H$, and consider each of the possible values for~$I$, then pass to the next value for~$H$:
%	\begin{enumerate}
%	\item[Case 1:] Assume $H$ is true.
%		\begin{enumerate}
%		\item[Subcase 1.1:] Assume $I$ is true.
%		We have
%			$$ (H \eand I) \eif H
%			\speq (\true \eand \true) \eif \true
%			\speq \true \eif \true
%			\speq \true 
%			.$$
%		\item[Subcase 1.2:] Assume $I$ is false.
%		We have
%			$$ (H \eand I) \eif H
%			\speq (\true \eand \false) \eif \true
%			\speq \false \eif \true
%			\speq \true 
%			.$$
%		\end{enumerate}
%	\item[Case 2:] Assume $H$ is false.
%		\begin{enumerate}
%		\item[Subcase 2.1:] Assume $I$ is true.
%		We have
%			$$ (H \eand I) \eif H
%			\speq (\true \eand \false) \eif \true
%			\speq \false \eif \true
%			\speq \true 
%			.$$
%		\item[Subcase 2.2:] Assume $I$ is false.
%		We have
%			$$ (H \eand I) \eif H
%			\speq (\false \eand \false) \eif \false
%			\speq \false \eif \false
%			\speq \true 
%			.$$
%		\end{enumerate}
%	\end{enumerate}
%The assertion is true in all cases, so it is a tautology.
%\end{solution}

\begin{eg}[(Law of Excluded Middle)] \label{LawExclMidEx}
It is easy to see that the assertion $A \eor \enot A$ is true when $A$ is true, and also when $A$~is false. Thus, the assertion is true for both possible values of the variable $A$, so it is a tautology:
	\factoidbox{$A \eor \enot A$  is a tautology.}
\end{eg}

\begin{rem}
The above tautology is called the ``Law of Excluded Middle'' because it says every assertion is either true or false: there is no middle ground where an assertion is partly true and partly false.
\end{rem}

\begin{eg}
It is easy to see that the assertion $A \eand \enot A$ is false when $A$ is true, and also when $A$~is false. Thus, the assertion is false for both possible values of the variable $A$, so it is a contradiction:
	\factoidbox{$A \eand \enot A$  is a contradiction.}
\end{eg}

\begin{rem}
The assertions $A \eor \enot A$ and $A \eand \enot A$ are the most important (and most common) examples of tautologies and contradictions. However, they will usually arise with some other expression plugged into the variable~$A$. For example, by letting $A$ be the assertion $(P \eor Q) \eif R$, we obtain the tautology 
	$$ \bigl( (P \eor Q) \eif R \bigr) \eor \enot \bigl( (P \eor Q) \eif R \bigr) , $$
which is a more complicated example of the Law of Excluded Middle, and we also obtain the  contradiction
		$$ \bigl( (P \eor Q) \eif R \bigr) \eand \enot \bigl( (P \eor Q) \eif R \bigr) . $$
\end{rem}


\begin{eg}
We can also give examples in English, rather than in symbols;
consider these assertions:
\begin{enumerate} 
\item[\ex{Acontingent}] It is raining.
\item[\ex{Atautology}] Either it is raining, or it is not.
\item[\ex{Acontradiction}] It is both raining and not raining.
\end{enumerate}
In order to know whether \assert{Acontingent} is true, you would need to check the weather. Logically speaking, it could be either true or false, so it is neither a tautology nor a contradiction.
%Assertions like this are said to be \emph{contingent}.

\assert{Atautology} is different. You do not need to look outside to know that it is true, regardless of what the weather is like. So it is a tautology.

You do not need to check the weather to know about \assert{Acontradiction}, either. It must be false, simply as a matter of logic. It might be raining here and not raining across town, or it might be raining now but stop raining even as you read this, but it is impossible for it to be both raining and not raining in any given situation (at any particular time and place). Thus, the third assertion is false in every possible situation; it is a contradiction.
\end{eg}
%
%\begin{exers}
%\begin{problist}
%\item What can you say about the negation of a tautology?
%\item What can you say about the negation of a contradiction?
%\item What can you say about the negation of an assertion that is neither a tautology nor a contradiction?
%\end{problist}
%\end{exers}

%Here are quick ways to remember these tables:
%\begin{itemize}
%\item $\script{A}\eand\script{B}$ is false unless $\script{A}$ and $\script{B}$ are both true;
%\item $\script{A}\eor\script{B}$ is true unless $\script{A}$ and $\script{B}$ are both false;
%\item $\script{A}\eif\script{B}$ is true unless $\script{A}$ is true and $\script{B}$ is false;
%\item $\script{A}\eiff\script{B}$ is true if $\script{A}$ and $\script{B}$ are the same.
%\end{itemize}


%\section{Truth-functional connectives}

%Any non-atomic assertion of {\SL} is composed of atomic assertions with sentential connectives. The truth-value of the compound assertion depends only on the truth-value of the atomic assertions that comprise it. In order to know the truth-value of $(D\eiff E)$, for instance, you only need to know the truth-value of $D$ and the truth-value of $E$. Connectives that work in this way are called \define{truth-functional}.

%In this chapter, we will make use of the fact that all of the logical operators in {\SL} are truth-functional---it makes it possible to construct truth tables to determine the logical features of assertions. You should realize, however, that this is not possible for all languages. In English, it is possible to form a new assertion from any simpler assertion \script{X} by saying ``It is possible that \script{X}\rlap.'' The truth-value of this new assertion does not depend directly on the truth-value of \script{X}. Even if \script{X} is false, perhaps in some sense \script{X} \emph{could} have been true---then the new assertion would be true. Some formal languages, called \emph{modal logics}, have an operator for {possibility}. In a modal logic, we could translate ``It is possible that \script{X}'' as {\large $\diamond$}\script{X}. However, the ability to translate assertions like these come at a cost: The {\large $\diamond$} operator is not truth-functional, and so modal logics are not amenable to truth tables.

%\section{How to construct a truth table}

%%It is important to be able to construct a truth table for any assertion of Propositional Logic.

%%The truth table for conjunction, for example, gives the truth conditions for any assertion of the form $(\script{A}\eand\script{B})$. Even if the conjuncts \script{A} and \script{B} are long, complicated assertions, the conjunction is true if and only if both \script{A} and \script{B} are true. 

%As an example, suppose we need a truth table for the assertion 
%$$(H\eand I)\eif H .$$
%We begin by considering all the possible combinations of true and false for $H$ and $I$: both may be true, or one may be true and the other false, or both may be false. There are $4$ possible combinations, so the truth table has $4$ rows:
%\begin{center}
%\begin{tabular}{c|c||c*{4}T}
%$H$&$I$&$(H$&\eand&$I)$&\eif&$H$\\
%\hline
% T & T & \\
% T & F & \\
% F & T & \\
% F & F & 
%\end{tabular}
%\end{center}
%That was the easy part. The hard part is to fill in the final column that provides the truth value of the assertion we are interested in.

%Note that the assertion is of the form $\script{A} \eif \script{B}$, with $\script{A}$ being the assertion $H \eand I$, and $\script{B}$ being the assertion~$H$. 
%Thus, as progress toward the final answer, we should find the truth value of the expression $H \eand I$. Let's insert a column into the truth table for this.
%\begin{center}
%\begin{tabular}{c|c||c*{2}T|c*{4}T}
%$H$&$I$&$H$&\eand&$I$&$(H$&\eand&$I)$&\eif&$H$\\
%\hline
% T & T &&&&& \\
% T & F &&&&& \\
% F & T &&&&& \\
% F & F &&&&&
%\end{tabular}
%\end{center}
%Now, in the column for $H \eand I$, it may be helpful to lightly (or in a different color) pencil in the value of the variables $H$ and~$I$, directly under the name of the variable in the column's title:
%\begin{center}
%\begin{tabular}{c|c||c*{2}T|c*{4}T}
%$H$&$I$&$H$&\eand&$I$&$(H$&\eand&$I)$&\eif&$H$\\
%\hline
% T & T &\faint{T}&&\faint{T}&& \\
% T & F &\faint{T}&&\faint{F}&& \\
% F & T &\faint{F}&&\faint{T}&& \\
% F & F &\faint{F}&&\faint{F}&&
%\end{tabular}
%\end{center}
%It is now easy to determine the truth value of the expression $H \eand I$ in each row; it is true in the row where both $H$ and~$I$ are~$\TTbf{T}$, and it is false in all of the other rows. We write these truth values in a tidy column.
%%, directly under the connective $\eand$ in the column's title.
%\begin{center}
%\begin{tabular}{c|c||c*{2}T|c*{4}T}
%$H$&$I$&$H$&\eand&$I$&$(H$&\eand&$I)$&\eif&$H$\\
%\hline
% T & T &\faint{T}& \TTbf{T}&\faint{T}&& \\
% T & F &\faint{T}& \TTbf{F}&\faint{F}&& \\
% F & T &\faint{F}& \TTbf{F}&\faint{T}&& \\
% F & F &\faint{F}& \TTbf{F}&\faint{F}&&
%\end{tabular}
%\end{center}
%Now, in the column for $(H \eand I) \eif H$, it may be helpful to lightly pencil in the value of the expression $H \eand I$ and of the variable~$H$. 
%%(These values need to be put in neat columns, directly under the connective $\eand$ and the variable~$H$ in the column's title, respectively.) 
%\begin{center}
%\begin{tabular}{c|c||c*{2}T|c*{4}T}
%$H$&$I$&$H$&\eand&$I$&$(H$&\eand&$I)$&\eif&$H$\\
%\hline
% T & T &\faint{T}& \TTbf{T}&\faint{T}&& \faint{T}&&&\faint{T} \\
% T & F &\faint{T}& \TTbf{F}&\faint{F}&& \faint{F}&&&\faint{T} \\
% F & T &\faint{F}& \TTbf{F}&\faint{T}&& \faint{F}&&&\faint{F} \\
% F & F &\faint{F}& \TTbf{F}&\faint{F}&& \faint{F}&&&\faint{F}
%\end{tabular}
%\end{center}
%It is now easy to determine the truth value of the entire assertion: there are no rows in which $H \eand I$ is true, but $H$ is false, so the assertion $(H \eand I) \eif H$ is true in every row; we write the truth value $T$ in each row. 
%%(These values are put in a neat column, directly under the connective $\eif$.)
%\begin{center}
%\begin{tabular}{c|c||c*{2}T|c*{4}T}
%$H$&$I$&$H$&\eand&$I$&$(H$&\eand&$I)$&\eif&$H$\\
%\hline
% T & T &\faint{T}& \TTbf{T}&\faint{T}&& \faint{T}&& \TTbf{T}&\faint{T} \\
% T & F &\faint{T}& \TTbf{F}&\faint{F}&& \faint{F}&& \TTbf{T}&\faint{T} \\
% F & T &\faint{F}& \TTbf{F}&\faint{T}&& \faint{F}&& \TTbf{T}&\faint{F} \\
% F & F &\faint{F}& \TTbf{F}&\faint{F}&& \faint{F}&& \TTbf{T}&\faint{F}
%\end{tabular}
%\end{center}
%This completes the construction of the truth table. If you are told to \emph{show your work} when making a truth table, then be sure to include columns for any intermediate results, as in the above table (but including the pencilled-in values is optional).

%
%\begin{rem}
%It is good to finish by making a copy of the final result without scratchwork or extra columns:
%\begin{center}
%\begin{tabular}{c|c||c*{4}T}
%$H$&$I$&$(H$&\eand&$I)$&\eif&$H$\\
%\hline
% T & T && && \TTbf{T}&\\
% T & F && && \TTbf{T}&\\
% F & T && && \TTbf{T}&\\
% F & F && && \TTbf{T}&
%\end{tabular}
%\end{center}
%\end{rem}

%
%\section{More examples}

%A \define{truth table} has a row for all the possible combinations of T and F for all of the variables, so the size of the table depends on the number of different variables in the assertion being studied. 

%An assertion that contains only one variable requires only two rows, as in the truth table for negation. This is true even if the same variable is repeated many times, as in the assertion
%$(C \eif \enot C) \eand (\enot C \eif C)$.
%The truth table requires only two lines because there are only two possibilities: either $C$ is true or it is false. (A single variable can never be marked both T and F on the same row.) The truth table (including all of the scratchwork) for this assertion looks like this:
%\begin{center}
%\begin{tabular}{c||cT|c*{3}T|c*{3}T|%
% c*{8}T}
%$C$&$\enot$&$C$&$C$&$\eif$&$\enot$&$C$&$\enot$&$C$&$\eif$&$C$&$(C$&$\eif$&$\enot$&%
%$C)$&$\eand$&$(\enot$&$C$&$\eif$&$C)$\\
%\hline
% T&F&\faint{T}&\faint{T}  & F & \faint{F}  && \faint{F} &&T&  \faint{T} &&\faint{F}&&& \TTbf{F}&&&\faint{T}  \\
% F&T&\faint{F}&\faint{F}  & T & \faint{T}  && \faint{T} &&F&  \faint{F} &&\faint{T}&&& \TTbf{F}&&&\faint{F}  
%\end{tabular}
%\end{center}
%Without the scratchwork, the truth table is:
%\begin{center}
%\begin{tabular}{c||c}
%$C$&$(C \eif \enot C) \eand (\enot C \eif C)$ \\
%\hline
%T&F\\
%F&F
%\end{tabular}
%\end{center}

%An assertion that contains two variables requires four lines in its truth table, as in the truth tables for the connectives $\eand$, $\eor$, $\eif$ and~$\eiff$, and in the table for $(H \eand I)\eif I$.

%An assertion that contains three variables requires eight lines. For example:
%\begin{center}
%\begin{tabular}{c|c|c||c*{2}T|c*{2}T}
%$M$&$N$&$P$&$N$&\eor&$P$&$M$&\eand&$(N \eor P)$\\
%\hline
%T & T & T &\faint{T}&T&\faint{T}&\faint{T}&\TTbf{T}&\faint{T}\\
%T & T & F &\faint{T}&T&\faint{F}&\faint{T}&\TTbf{T}&\faint{T}\\
%T & F & T &\faint{F}&T&\faint{T}&\faint{T}&\TTbf{T}&\faint{T}\\
%T & F & F &\faint{F}&F&\faint{F}&\faint{T}&\TTbf{F}&\faint{F}\\
%F & T & T &\faint{T}&T&\faint{T}&\faint{F}&\TTbf{F}&\faint{T}\\
%F & T & F &\faint{T}&T&\faint{F}&\faint{F}&\TTbf{F}&\faint{T}\\
%F & F & T &\faint{F}&T&\faint{T}&\faint{F}&\TTbf{F}&\faint{T}\\
%F & F & F &\faint{F}&F&\faint{F}&\faint{F}&\TTbf{F}&\faint{F}\\
%\end{tabular}
%\end{center}
%%From this table, we know that the assertion $M\eand(N\eor P)$ might be true or false, depending on the truth-values of $M$, $N$, and $P$.

%A complete truth table for an assertion that contains four different variables requires 16 lines. Five variables, 32 lines. Six variables, 64 lines. And so on. To be perfectly general: 
%\factoidbox{A truth table with $n$ different variables
%must have $2^n$ rows.}
%In order to fill in the columns of a complete truth table, begin with the right-most variable and alternate Ts and~Fs. In the next column to the left, write two~Ts, write two~Fs, and repeat. For the third variable, write four~Ts followed by four~Fs. This yields an eight-line truth table like the one above. For a 16 line truth table, the next column of variables should have eight~Ts followed by eight~Fs. For a 32-line table, the next column would have 16~Ts followed by 16~Fs. And so on.  
%It is important to be organized, so the reader can see easily that none of the possibilities have been left out of your table, or have been repeated by mistake---\emph{do not list the possibilities in some random order!}


%\begin{rem} \ 
%\begin{enumerate}
%\item Recall that an assertion is a \define{tautology} if it must be true as a matter of logic. This means that its truth-value is ``true\rlap,'' no matter what truth-values are assigned to its variables. 
%\begin{itemize}
%\item To show that an assertion \emph{is} a tautology, we could calculate its truth-value for every possible assignment to its variables. (If the result comes out ``true'' for every one of the possibilities, then the assertion is a tautology.) Unfortunately, this will be a lot of work if there are many variables.
%%With a truth table, we consider all of the ways that the world might be. Thus, if the assertion is true on every line of a truth table, then it is true as a matter of logic, regardless of what the world is like.
%\item  It takes a lot less work to show that an assertion is \emph{not} a tautology. This is because
%it suffices to find a single choice of truth-values for its variables that makes the assertion false.
%For example, if $M$ and~$N$ are true, and $P$~is false, then $\enot M \eor (N \eif P)$ is false. Therefore, the assertion $\enot M \eor (N \eif P)$ is not a tautology.
%\end{itemize}
%
%\item Similarly, an assertion of {\SL} is a \define{contradiction} if its truth-value is ``false\rlap,'' no matter what truth-values are assigned to its variables. So there is more work involved in showing that an assertion is a contradiction than there is in showing that it is not.
%%\begin{itemize}
%%\item  To show that an assertion is \emph{not} a contradiction,
%%find an assignment of truth-values for its variables that makes the assertion true.
%%It is enough to find just one example.
%For example, if $M$, $N$~and~$P$ are all true, then $\enot M \eor (N \eif P)$ is true, so the assertion $\enot M \eor (N \eif P)$ is not a contradiction.
%%\item A truth table is a good way to check whether an assertion of {\SL} is a contradiction: if the truth-value of an assertion is \TTbf{F} in every row of its truth table, then the assertion is a contradiction.
%%\end{itemize}
%
%\item An assertion of {\SL} is neither a tautology nor a contradiction if there is an assignment for which its truth value is false, and some other assignment for which its truth value is true. For example, the assertion $\enot M \eor (N \eif P)$ is neither a tautology nor a contradiction, because (as we have seen above):
%\begin{itemize}
%\item its truth value is false if $M$~is true, and $N$~and~$P$ are false, 
%but
%\item its truth value is true if $M$, $N$~and~$P$ are all true.
%\end{itemize}
%\end{enumerate}
%\end{rem}

%\begin{exers}
%\label{pr.TT.TTorC}
%Determine whether each of the following assertions is a tautology, a contradiction, or neither. 
%(Justify your answer.)
%\begin{problist}
%\item \label{pr.TT.TTorC-A<>A}
%$A \eif A$ %taut
%\item \label{pr.TT.TTorC-C->notC}
% $C \eif\enot C$ %contingent
%\item \label{pr.TT.TTorC-(A<>B)<>not}
% $(A \eiff B) \eiff \enot(A\eiff \enot B)$ %tautology
%\item \label{pr.TT.TTorC-(A->B)or(B->A)}
% $(A \eif B) \eor (B \eif A)$ % taut
%\item \label{pr.TT.TTorC-(AandB)->(BorA)}
% $(A \eand B) \eif (B \eor A)$  %taut
%\item \label{pr.TT.TTorC-not(AorB)<>(notAandnotB)}
% $\enot(A \eor B) \eiff (\enot A \eand \enot B)$ %taut
%\item \label{pr.TT.TTorC-BLAHandC}
% $\bigl[(A\eand B) \eand\enot(A\eand B)\bigr] \eand C$ %contradiction
%\item \label{pr.TT.TTorC-(AandBandC->B}
% $[(A \eand B) \eand C] \eif B$ %taut
%\item \label{pr.TT.TTorC-(CorA)orB}
% $\enot\bigl[(C\eor A) \eor B\bigr]$ %contingent
%\item \label{pr.TT.TTorC-(C->enotC)and(notC->C)}
%$(C\eif \enot C) \eand (\enot C \eif C)$ % (contradiction)
%\end{problist}
%\end{exers}



%\begin{exers}
%\label{pr.TT.TTorC(given)}
%Use the given truth table to determine whether each assertion is a tautology, a contradiction, or a contingent assertion (and provide a brief justification).
%\begin{problist}
%\item $\enot B \eand B$ %contra
%\hfil
%\begin{tabular}{c||c*{2}T}
%$B$&$\enot B$ &$\eand$ & $B$ \\
%\hline
% T & &F& \\
% F & &F&
%\end{tabular}
%\medskip
%\item $\enot D \eor D$ %taut
%\hfil
%\begin{tabular}{c||c*{2}T}
%$D$&$\enot D$ & $ \eor$ & $ D$ \\
%\hline
% T & &T \\
% F & &T
%\end{tabular}
%\medskip
%\item $(A\eand B) \eor (B\eand A)$ %contingent
%\hfil
%\begin{tabular}{c|c||c}
%$A$& $B$ & $(A\eand B) \eor (B\eand A)$ \\
%\hline
% T & T & T\\
% T & F & F\\
% F & T & F\\
% F & F & F
%\end{tabular}
%\medskip
%\item $\enot[A \eif (B \eif A)]$ %contra
%\hfil
%\begin{tabular}{c|c||cT}
%$A$& $B$ & $\enot$ & $[A \eif (B \eif A)]$ \\
%\hline
% T & T & F\\
% T & F & F\\
% F & T & F\\
% F & F & F
%\end{tabular}
%\medskip
%\item $A \eiff [A \eif (B \eand \enot B)]$ %contra
%\hfil
%\begin{tabular}{c|c||c*{2}T}
%$A$& $B$ & $A$ & $\eiff$ & $ [A \eif (B \eand \enot B)]$ \\
%\hline
% T & T & &F\\
% T & F & &F\\
% F & T & &F\\
% F & F & &F
%\end{tabular}
%\medskip
%\item $\enot(A\eand B) \eiff A$ %contingent
%\hfil
%\begin{tabular}{c|c||c*{2}T}
%$A$& $B$ & $\enot(A\eand B)$ & $ \eiff$ & $ A$ \\
%\hline
% T & T & &F\\
% T & F & &T\\
% F & T & &F\\
% F & F & &F
%\end{tabular}
%\medskip
%\item $A\eif(B\eor C)$ %contingent
%\hfil
%\begin{tabular}{c|c|c||c*{2}T}
%$A$& $B$ & $C$ & $A$ & $\eif$ & $(B\eor C)$ \\
%\hline
% T & T & T && T\\
% T & T & F && T\\
% T & F & T && T\\
% T & F & F && F\\
% F & T & T && T\\
% F & T & F && T\\
% F & F & T && T\\
% F & F & F && T
%\end{tabular}
%\medskip
%\item $(A \eand\enot A) \eif (B \eor C)$ %tautology
%\hfil
%\begin{tabular}{c|c|c||c*{2}T}
%$A$& $B$ & $C$ & $(A \eand\enot A) $ & $\eif$ & $ (B \eor C)$ \\
%\hline
% T & T & T && T\\
% T & T & F &&T\\
% T & F & T &&T\\
% T & F & F && T\\
% F & T & T &&T\\
% F & T & F && T\\
% F & F & T && T\\
% F & F & F && T
%\end{tabular}
%\medskip

%%  
%\vbox{
%\item $(B\eand D) \eiff [A \eiff(A \eor C)]$%contingent
%\begin{center}
%\begin{tabular}{c|c|c|c||c*{2}T}
%$A$& $B$ & $C$ & $D$ & $(B\eand D)$ & $ \eiff$ & $ [A \eiff(A \eor C)]$ \\
%\hline
% T & T & T & T && T\\
% T & T & T & F && F\\
% T & T & F & T && T\\
% T & T & F & F && F\\
% T & F & T & T && F\\
% T & F & T & F && F\\
% T & F & F & T && F\\
% T & F & F & F && F\\
% F & T & T & T && F\\
% F & T & T & F && T\\
% F & T & F & T && T\\
% F & T & F & F && F\\
% F & F & T & T && T\\
% F & F & T & F && T\\
% F & F & F & T && F\\
% F & F & F & F && F
%\end{tabular}
%\end{center}
%}
%\end{problist}
%\end{exers}





\begin{exers}
\label{pr.EnglishCombinationsb}
Which of the following are possible? For those that are possible, give an example. For those that are not, explain why.
\begin{problist}
\item \label{pr.EnglishCombinationsb-validcontra}
 A valid deduction whose conclusion is a contradiction.
\item \label{pr.EnglishCombinationsb-validtaut}
 A valid deduction whose conclusion is a tautology.
%\item \label{pr. EnglishCombinationsb-validcontingent}
% A valid deduction whose conclusion is contingent.
\item \label{pr.EnglishCombinationsb-validhyptaut}
 A valid deduction that has a tautology as one of its hypotheses.
\item \label{pr.EnglishCombinationsb-validhypcontra}
  A valid deduction that has a contradiction as one of its hypotheses.
\item \label{pr.EnglishCombinationsb-invalidcontra}
 An invalid deduction whose conclusion is a contradiction.
\item \label{pr.EnglishCombinationsb-invalidtaut}
 An invalid deduction whose conclusion is a tautology.
%\item \label{pr. EnglishCombinationsb-invalidcont}
% An invalid deduction whose conclusion is a contingent.
\item \label{pr.EnglishCombinationsb-invalidhyptaut}
 An invalid deduction that has a tautology as one of its hypotheses.
\item \label{pr.EnglishCombinationsb-invalidhypcontra}
  An invalid deduction that has a contradiction as one of its hypotheses.
%\item \label{pr. EnglishCombinationsb-tautcontingent}
% A tautology that is contingent.
 \end{problist}
\end{exers}



\section{Logical equivalence}

In your previous mathematics classes (such as algebra and trigonometry), you encountered many examples where two different-looking formulas turned out to be equal. Analogously, in Logic, there can be two different assertions that happen to have the same truth value in all possible situations. (This means that, for every possible assignment of true or false to the variables, either both of the assertions are true, or both are false.) Such assertions are said to be  \define[equivalent, logically]{logically equivalent}.

\begin{notation}
We will write $\script{A} \equiv \script{B}$ to denote that $\script{A}$ is logically equivalent to~$\script{B}$.
\end{notation}

It can take a lot of work to verify that two assertions are logically equivalent. On the other hand, to show that two assertions are \emph{not} logically equivalent, you only need to find one example of an assignment to the variables, such that one of the assertions is true and the other is false. 
 
 \begin{eg}
 If $A$ is true and $B$~is false, then $A \eor B$ is true, but $A \eif B$ is false. Therefore, the assertions $A \eor B$ and $A \eif B$ are \emph{not} logically equivalent. 
 \end{eg}

\begin{exer} \label{NotEquiv}
Show that each of the following pairs of sentences are \emph{not} logically equivalent.
\begin{enumerate}
\item \label{NotEquiv-ABC}
 $A \eor B \eor \enot C$, $(A \eor B) \eand (C \eif A)$
\item \label{NotEquiv-PQ}
 $(P \eif Q) \eor (Q \eif P)$, $P \eor Q$
\item \label{NotEquiv-XYZ}
 $(X \eand Y) \eif Z$, $X \eor (Y \eif Z)$
\end{enumerate}
\end{exer}

\begin{eg} \label{Not(AorB)Eg}
Show that  $\enot(A \eor B) \equiv \enot A \eand \enot B$.
\end{eg}

\begin{solution}
The variables $A$ and~$B$ may each be either true or false, and we will evaluate both assertions for all possible combinations. To make it clear that none of the possibilities have been missed, we proceed systematically: for each value of~$A$, we consider the two possible values for~$B$.
%%To do this systematically, we assign a value to~$H$, and consider each of the possible values for~$I$, then pass to the next value for~$H$:We consider all the possible values of the variables.
	\begin{enumerate}
	\item[Case 1:] Assume $A$ is true.
		\begin{enumerate}
		\item[Subcase 1.1:] Assume $B$ is true.
		We have
			$$\enot(A \eor B) \speq \enot(T \eor T) \speq \enot T \speq F $$
		and
			$$ \enot A \eand \enot B
			 \speq \enot T \eand \enot T
			 \speq F \eand F
			 \speq F .$$
		Both assertions are false.
		\item[Subcase 1.2:] Assume $B$ is false.
		We have
			$$\enot(A \eor B) \speq \enot(T \eor F) \speq \enot T \speq F $$
		and
			$$ \enot A \eand \enot B
			 \speq \enot T \eand \enot F
			 \speq T \eand F
			 \speq F .$$
		Both assertions are false.
		\end{enumerate}
	\item[Case 2:] Assume $A$ is false.
		\begin{enumerate}
		\item[Subcase 2.1:] Assume $B$ is true.
		We have
			$$\enot(A \eor B) \speq \enot(F \eor T) \speq \enot T \speq F $$
		and
			$$ \enot A \eand \enot B
			 \speq \enot F \eand \enot T
			 \speq T \eand F
			 \speq F .$$
		Both assertions are false.
		\item[Subcase 2.2:] Assume $B$ is false.
		We have
			$$\enot(A \eor B) \speq \enot(F \eor F) \speq \enot F \speq T $$
		and
			$$ \enot A \eand \enot B
			 \speq \enot F \eand \enot F
			 \speq T \eand T
			 \speq T .$$
		Both assertions are true.
		\end{enumerate}
	\end{enumerate}
In all cases, either both assertions are true, or both are false. Therefore, they are logically equivalent.
\end{solution}

We can also solve the problem without doing so much work:

\begin{proof}[Easier solution] % would be better to use solution environment
Note that the assertion $\enot(A \eor B)$ is true if and only if $A \eor B$ is false, which means that neither $A$ nor~$B$ is true. Therefore,
	$$ \text{$\enot(A \eor B)$ is true if and only if $A$ and~$B$ are both false.} $$
Also, $\enot A \eand \enot B$ is true if and only if $\enot A$ and $\enot B$ are both true, which means that:
	$$  \text{$\enot A \eand \enot B$ is true if and only if $A$ and~$B$ are both false.} $$

So the two assertions $\enot(A \eor B)$ and $\enot A \eand \enot B$ are true in exactly the same situation (namely, when $A$ and~$B$ are both false); and they are both false in all other situations. Therefore, they are logically equivalent.
\end{proof}

%\subsection{Consistency}
%A set of assertions in English is consistent if it is logically possible for them all to be true at once.
%A set of assertions of~{\SL} are \define{logically consistent} if there is at least one line of a truth table on which all of the assertions are true. It is \define{inconsistent} otherwise.


%\begin{exers}
%\label{pr.TT.equiv}
%Determine whether each pair of assertions is logically equivalent (and justify your answer).
%\begin{problist}
%\item \label{pr.TT.equiv-A}
%$A\eif A$, $A \eiff A$ % yes
%%\hfil
%%\begin{tabular}{c||c|c}
%%$A$& $A\eif A$ & $A \eiff A$ \\
%%\hline
%% T & T & T\\
%% F & T & T
%%\end{tabular}
%%\medskip
%\item \label{pr.TT.equiv-AornotB}
%$(A \eor \enot B)$, $(A\eif B)$ %No
%%\hfil
%%\begin{tabular}{c|c||c|c}
%%$A$& $B$ & $A \eor \enot B$ & $A\eif B$ \\
%%\hline
%% T & T & T & T\\
%% T & F & T & F\\
%% F & T & F & T\\
%% F & F & T & T
%%\end{tabular}
%%\medskip
%\item \label{pr.TT.equiv-AandnotA}
%$A \eand \enot A$, $\enot B \eiff B$ %Yes
%%\hfil
%%\begin{tabular}{c|c||c|c}
%%$A$& $B$ & $A \eand \enot A$ & $\enot B \eiff B$ \\
%%\hline
%% T & T & F & F\\
%% T & F & F & F\\
%% F & T & F & F\\
%% F & F & F & F
%%\end{tabular}
%%\medskip
%\item \label{pr.TT.equiv-not(AandB)}
%$\enot(A \eand B)$, $(\enot A \eor \enot B)$ %Yes
%%\hfil
%%\begin{tabular}{c|c||c|c}
%%$A$& $B$ & $\enot(A \eand B)$ & $\enot A \eor \enot B$ \\
%%\hline
%% T & T & F & F\\
%% T & F & T & T\\
%% F & T & T & T\\
%% F & F & T & T
%%\end{tabular}
%%\medskip
%\end{problist}
%\end{exers}
%
%\begin{exers}
%\label{pr.TT.concepts}
%Answer each of the questions below and justify your answer.
%\begin{problist}
%\item Suppose that \script{A} and \script{B} are logically equivalent. What can you say about $\script{A}\eiff\script{B}$?
%%\script{A} and \script{B} have the same truth value on every line of a complete truth table, so $\script{A}\eiff\script{B}$ is true on every line. It is a tautology.
%\item Suppose that \script{A} and \script{B} are \emph{not} logically equivalent. What can you say about $\script{A}\eiff\script{B}$?
%\item Suppose that \script{A} and \script{B} are logically equivalent. What can you say about $(\script{A}\eor\script{B})$?
%%Not much. $(\script{A}\eor\script{B})$ is a tautology if \script{A} and \script{B} are tautologies; it is a contradiction if they are contradictions; it is contingent if they are contingent.
%\item Suppose that \script{A} and \script{B} are \emph{not} logically equivalent. What can you say about $(\script{A}\eor\script{B})$?
%%\script{A} and \script{B} have different truth values on at least one line of a complete truth table, and $(\script{A}\eor\script{B})$ will be true on that line. On other lines, it might be true or false. So $(\script{A}\eor\script{B})$ is either a tautology or it is contingent; it is \emph{not} a contradiction.
%
%\end{problist}
%\end{exers}

\begin{exers} \label{BasicEquivs}
Verify each of the following important logical equivalences. For most of these, you should not need to evaluate the assertions for all possible values of the variables.

\begin{problist} 

\item \label{BasicEquivs-negation}
 rules of negation:
	\begin{align*}
	\enot \enot A   \qquad  &\equiv  \qquad   A
	\\
	\enot(A \eand B)  \qquad &\equiv  \qquad  \enot A \eor \enot B
	\\
	\enot(A \eor B)  \qquad &\equiv  \qquad  \enot A \eand \enot B
	\\
	\enot ( A \eif B)   \qquad  &\equiv  \qquad   A \eand \enot B
	\\
	\enot ( A \eiff B)   \qquad  &\equiv  \qquad   A \eiff \enot B
	\end{align*}

\item \label{BasicEquivs-commutativity}
 commutativity of $\eand$, $\eor$, and $\eiff$:
	\begin{align*} 
	A \eand B \qquad &\equiv  \qquad  B \eand A
	\\ 	A \eor B \qquad &\equiv  \qquad B \eor A
	\\ 	A \eiff B \qquad &\equiv  \qquad B \eiff A
	\end{align*}

\item  \label{BasicEquivs-associativity}
associativity of $\eand$ and $\eor$:
	\begin{align*} 
	(A \eand B) \eand C \qquad &\equiv  \qquad A \eand (B \eand C) 
	\\	(A \eor B) \eor C \qquad &\equiv  \qquad A \eor (B \eor C)
	\end{align*}

\end{problist}
\end{exers}

\begin{rem}
The rules of negation for $\eand$ and~$\eor$ are often called \emph{De\,Morgan's Laws}, in honour of the British mathematician Augustus De\,Morgan (1806--1871, \url{http://en.wikipedia.org/wiki/Augustus_De_Morgan}).
\end{rem}

The rules of negation can be used to simplify the negation of any assertion.

\begin{eg}
Simplify \ $\enot \bigl( (A \eor B) \eif (A \eand \enot C) \bigr)$.
\end{eg}

\begin{solution}
We have
	\begin{align*}
	\enot \bigl( (A \eor B) \eif (A \eand \enot C) \bigr)
	&\equiv (A \eor B) \eand \enot (A \eand \enot C)
	\\& \equiv (A \eor B) \eand (\enot A \eor \enot \enot C)
	\\& \equiv (A \eor B) \eand (\enot A \eor C)
	. \qedhere \end{align*}
\end{solution}

\begin{rem}
If $\script{A} \equiv \script{B}$, then $\script{A}, \ \therefore \script{B}$ is a valid deduction. For example, the above example shows that 
	$$\enot \bigl( (A \eor B) \eif (A \eand \enot C) \bigr), \ \therefore (A \eor B) \eand (\enot A \eor C)$$
is a valid deduction.
\end{rem}

\begin{exer} \label{DeMorganEx}
Use the rules of negation to simplify each of the following assertions (until negation is not applied to anything but variables).
\begin{tasks}[after-item-skip = 5pt plus 0.5pt minus 0.5pt, before-skip = 5pt plus 0.5pt minus 0.5pt](2) % !!!
\task\fixtask \label{DeMorganEx-(AorB)->(CandD)}%
 $\enot \bigl( (A \eor B) \eif (C \eand D) \bigr)$ 
\task\fixtask \label{DeMorganEx-(A->B)or(CandD)}%
 $\enot \bigl( (A \eif B) \eor (C \eand D) \bigr)$ 
\task\fixtask \label{DeMorganEx-A->(B->(C->D))}%
 $\enot \Bigl( A \eif \bigl( B \eif( C \eif D) \bigr) \Bigr)$
\task\fixtask \label{DeMorganEx-((A->B)->C)->D}%
 $\enot \Bigl( \bigl( (A \eif B) \eif C \bigr) \eif D \Bigr)$
\task\fixtask \label{DeMorganEx-(PornotQ)andR}%
 $\enot \bigl(  (P \eor \enot Q) \eand R \bigr)$
\task\fixtask \label{DeMorganEx-PandQandRandS}%
 $ \enot (P \eand Q \eand R \eand S)$
\task\fixtask \label{DeMorganEx-(P->(QandenotR))or(PandnotQ)}%
 $ \enot \Bigl( \bigl( P \eif ( Q \eand \enot R) \bigr) \eor (P \eand \enot Q) \Bigr)$
\end{tasks}
\end{exer}

\begin{exer} \label{DeMorganEnglish}
Use the rules of negation to simplify the \emph{negation} of each of these assertions. Express your answers in English.
\begin{problist}
\item  \label{DeMorganEnglish-raining}
If it is raining, then the bus will not be on time.
\item  \label{DeMorganEnglish-sick}
I am sick, and I am tired.
\item  \label{DeMorganEnglish-Pope}
Either the Pope is here, or the Queen and the Registrar are both here.
\item  \label{DeMorganEnglish-Tom}
If Tom forgot his backpack, then Sam will eat either a pickle or a potato, and either Bob will not have lunch, or Alice will drive to the store.
\end{problist}
\end{exer}



%\begin{exers}
%\label{pr.altConnectives}
%It was mentioned in \cref{ch.SL} that ``$\eiff$'' is not necessary, because 
%$A\eiff B$ is just an abbreviation for $(A\eif B) \eand (B\eif A)$.
%%We could leave out the biconditional (\eiff) out of the language. If we did that, we could still write ``$A\eiff B$'' so as to make assertions easier to read, but that would be shorthand for $(A\eif B) \eand (B\eif A)$. The resulting language would be formally equivalent to {\SL}, since $A\eiff B$ and $(A\eif B) \eand (B\eif A)$ are logically equivalent in {\SL}. If we valued formal simplicity over expressive richness, we could replace more of the connectives with notational conventions and still have a language equivalent to {\SL}. 
%Some of the other connectives are also unnecessary.
%
%\begin{problist}
%\item %There are a number of equivalent languages with only two connectives. 
%It would be enough to have only ``not'' and~``implies\rlap.'' Show this by writing assertions that are logically equivalent to each of the following, using only parentheses, assertion letters, ``\enot\rlap,'' and~``\eif\rlap.''
%\begin{multicols}{3}
%\begin{enumerate}
%\item\leftsolutions\ $A\eor B$
%%$\enot A \eif B$
%\item\leftsolutions\ $A\eand B$
%%$\enot(A \eif \enot B)$
%\item\leftsolutions\ $A\eiff B$
%%$\enot [(A\eif B) \eif \enot(B\eif A)]$
%\end{enumerate}
%\end{multicols}
%%...
%% Break out of the {earg} environment to give new instructions. 
%
%\item %We could have a language that is equivalent to {\SL} with only negation and disjunction as connectives. 
%As an alternative, show that it would be enough to have only ``not'' and~``or'': using only parentheses, assertion letters, ``\enot\rlap,'' and~``\eor\rlap,'' write assertions that are logically equivalent to each of the following.
%% Resume the {earg} environment and restore the counter.
%%...
%\begin{multicols}{3}
%\begin{enumerate}
%\item $A \eand B$
%%$\enot(\enot A \eor \enot B)$
%\item $A \eif B$
%%$\enot A \eor B$
%\item $A \eiff B$
%%$\enot(\enot A \eor \enot B) \eor \enot(A \eor B)$
%\end{enumerate}
%\end{multicols}
%%...
%\item \newcommand{\nand}{\ensuremath{\mathbin{\mathord{|}\mkern-8.5mu\mathord{\wedge}}}}
%The logical connective ``\define{nand}'' (also called the ``\emph{Sheffer stroke}'') has the following truth table:
%\begin{center}
%\begin{tabular}{c|c||c}
%\script{A} & \script{B} & \script{A}$\nand$\script{B}\\
%\hline
%\true & \true & \false\\
%\true & \false & \true\\
%\false & \true & \true\\
%\false & \false & \true
%\end{tabular}
%\end{center}
%%...
%\begin{enumerate}
%\item Write an assertion using the connectives of {\SL} that is logically equivalent to $A\nand B$.
%\item %Every assertion written using a connective of {\SL} can be rewritten as a logically equivalent assertion using one or more Sheffer strokes. 
%Show that it would suffice to have only ``nand\rlap,'' and no other connectives: using only~``$\nand$'' (and parentheses and assertion letters), write assertions that are equivalent to each of the following. 
%%...
%\begin{multicols}{3}
%\begin{enumerate}
%\item $\enot A$
%\item $A\eand B$
%\item $A\eor B$
%\item $A\eif B$
%\item $A\eiff B$
%\end{enumerate}
%\end{multicols}
%\end{enumerate}
%\end{problist}
%\end{exers}






\section{Converse and contrapositive} \label{ConverseSect}

The \define{converse} of an implication $\script{A} \eif \script{B}$ is the implication $\script{B} \eif \script{A}$. For example, the converse of ``if Bob pays the cashier a dollar, then the server gives Bob an ice cream cone'' is ``if the server gives Bob an ice cream, then Bob pays the cashier a dollar\rlap.'' It should be clear that these are not saying the same thing. (For example, perhaps Bob has a coupon for a free cone.) This illustrates the fact that the converse of an assertion is usually not logically equivalent to the original assertion. In other words (as was mentioned in \cref{subsection.eif}), the connective $\eif$ is \emph{not} commutative: 
%$A \eif B$ is \emph{not} logically equivalent to $B \eif A$. 

\begin{exer} \label{ContrapositiveNotEquiv}
Show that $A\eif B$ is \emph{not} logically equivalent to its converse $B \eif A$.
%, by finding values of the variables $A$ and~$B$ for which the two assertions have different truth values.
\end{exer}

%\begin{center}
%\begin{tabular}{c|c||c*{2}T|c*{2}T|cT|
%cT|c*{2}T|c*{2}T}
%$A$&$B$&$A$&$\eif$&$B$&$B$&$\eif$&$A$&\enot&$A$&\enot&$B$&$\enot A$&$\eif$&$\enot B$&$\enot B$&$\eif$&$\enot A$\\
%\hline
% T & T & \faint{T} & \TTbf{T} & \faint{T} & \faint{T} & \TTbf{T} & \faint{T}
%       &{F} & \faint{T} & {F} & \faint{T}
%       & \faint{F}\hphantom{A}& \TTbf{T} & \faint{F}\hphantom{B} 
%       & \faint{F}\hphantom{B}& \TTbf{T} & \faint{F}\hphantom{A}  \\
% T & F & \faint{T} & \TTbf{F} & \faint{F} & \faint{F} & \TTbf{T} & \faint{T}
%       &{F} & \faint{T} & {T} & \faint{F}
%       & \faint{F}\hphantom{A}& \TTbf{T} & \faint{T}\hphantom{B} 
%       & \faint{T}\hphantom{B}& \TTbf{F} & \faint{F}\hphantom{A}  \\
% F & T & \faint{F} & \TTbf{T} & \faint{T} & \faint{T} & \TTbf{F} & \faint{F}
%       &{T} & \faint{F} & {F} & \faint{T}
%       & \faint{T}\hphantom{A}& \TTbf{F} & \faint{F}\hphantom{B} 
%       & \faint{F}\hphantom{B}& \TTbf{T} & \faint{T}\hphantom{A}  \\
% F & F & \faint{F} & \TTbf{T} & \faint{F} & \faint{F} & \TTbf{T} & \faint{F}
%       &{T} & \faint{F} & {T} & \faint{F}
%       & \faint{T}\hphantom{A}& \TTbf{T} & \faint{T}\hphantom{B} 
%       & \faint{T}\hphantom{B}& \TTbf{T} & \faint{T}\hphantom{A}  \\
%\end{tabular}
%\end{center}

The \define[inverse!of an implication]{inverse} of an implication $\script{A} \eif \script{B}$ is the implication $\enot\script{A} \eif \enot\script{B}$. For example, the inverse of ``if Bob pays the cashier a dollar, then the server gives Bob an ice cream cone'' is ``if Bob does not pay the cashier a dollar, then the server does not give Bob an ice cream cone\rlap.'' It should be clear that these are not saying the same thing (because one assertion is about what happens if Bob pays a dollar, and the other is about the completely different situation in which Bob does not pay a dollar). This illustrates the fact that the inverse of an assertion is usually not logically equivalent to the original assertion: 
%$A \eif B$ is \emph{not} logically equivalent to $\enot A \eif \enot B$. 

\begin{exer} \label{InverseNotEquiv}
Show that $A\eif B$ is \emph{not}  logically equivalent to its inverse $\enot A \eif \enot B$.
%, by finding values of the variables $A$ and~$B$ for which the two assertions have different truth values.
\end{exer}

The \define{contrapositive} of an implication is the converse of its inverse (or the inverse of its converse, which amounts to the same thing). That is, 
	\factoidbox{the contrapositive of $\script{A} \eif \script{B}$ is the implication $\enot\script{B} \eif \enot\script{A}$.}
 For example, the contrapositive of ``if Bob pays the cashier a dollar, then the server gives Bob an ice cream cone'' is ``if the server does not give Bob an ice cream cone, then Bob does not pay the cashier a dollar\rlap.'' A bit of thought should convince you that these \emph{are} saying the same thing. This illustrates the following important fact:
\factoidbox{Any implication is logically equivalent to its contrapositive.}


\begin{exer} \label{ContrapositiveEquiv}
Show that $A\eif B$ is logically equivalent to its contrapositive $\enot B \eif \enot A$.
%, by verifying that the two assertions have the same truth value, for all possible values of the variables $A$ and~$B$.
\end{exer}

\begin{rem}
The inverse will not be important to us, although the converse and the contrapositive are fundamental.  However, it may be worth mentioning that the inverse is the contrapositive of the converse, and therefore
the inverse and the converse are logically equivalent to each other.
\end{rem}

\begin{warn}
Implications (that is, those of the form $\script{A} \eif \script{B}$) are the only assertions that have a converse or a contrapositive. For example, the converse of ``I hate cheese'' does not exist, because this assertion is not an if-then statement.
\end{warn}

%If you want additional practice, you can construct truth tables for any of the assertions and deductions in the exercises for the previous chapter.




%\solutions
%\problempart
%\label{pr.TT.consistent}
%Determine whether each set of assertions is consistent or inconsistent. Justify your answer with a complete or partial truth table where appropriate.
%\begin{earg}
%\item $A\eif A$, $\enot A \eif \enot A$, $A\eand A$, $A\eor A$ %consistent
%\item $A \eand B$, $C\eif \enot B$, $C$ %inconsistent
%\item $A\eor B$, $A\eif C$, $B\eif C$ %consistent
%\item $A\eif B$, $B\eif C$, $A$, $\enot C$ %inconsistent
%\item $B\eand(C\eor A)$, $A\eif B$, $\enot(B\eor C)$  %inconsistent
%\item $A \eor B$, $B\eor C$, $C\eif \enot A$ %consistent
%\item $A\eiff(B\eor C)$, $C\eif \enot A$, $A\eif \enot B$ %consistent
%\item $A$, $B$, $C$, $\enot D$, $\enot E$, $F$ %consistent
%\end{earg}


\begin{exers} \label{pr.ConverseContra}%
% want to be able to reference (a) and (b) (this assumes enumiv counter is not being used !!!)
\setcounter{enumiv}{0}\renewcommand{\theenumiv}{\alph{enumiv}}%
\makeatletter\renewcommand{\p@enumiv}{}\makeatother
State \refstepcounter{enumiv}\label{pr.ConverseContra-converse}\pref{pr.ConverseContra-converse}~the converse 
and \refstepcounter{enumiv}\label{pr.ConverseContra-contra}\pref{pr.ConverseContra-contra}~the contrapositive of each implication.
\noneed
\begin{problist}
\item \label{pr.ConverseContra-CL}
If the students come to class, then the teacher lectures.
\item \label{pr.ConverseContra-RU}
If it rains, then I carry my umbrella.
\item \label{pr.ConverseContra-SW}
If I have to go to school this morning, then today is a weekday.
\item \label{pr.ConverseContra-5A}
If you give me \$5, I can take you to the airport.
\item \label{pr.ConverseContra-HP}
If the Mighty Ducks are the best hockey team, then pigs can fly.
\item \label{pr.ConverseContra-A}
Alberta is a province. %% this isn''t an implication
\item \label{pr.ConverseContra-MH}
If you want to do well in your math class, then you need to do all of the homework. % problems
\end{problist}
\end{exers}



\section{Some valid deductions} \label{ValiditySect}

Recall that a deduction %in English 
is \define[valid deduction]{valid} if its conclusion is true in all situations where all of its hypotheses are true. This means, for each and every possible assignment of true/false to the variables, if all of the hypotheses true, then the conclusion is also true.

\begin{eg} \label{EasyValid}
Explain how you know that the following deduction is valid.
$$ A \eor B, \quad \enot A, \quad \therefore \ B .$$
%\begin{earg}
%\item \label{EasyValid-AorB}  $A \eor B$
%\item \label{EasyValid-notA} $\enot A$
%\conclusion $B$
%\end{earg}
\end{eg}

\begin{solution}
Assume we are in a situation in which both hypotheses of the deduction are true. Then, from 
the first hypothesis, %\cref{EasyValid-AorB}, 
we know that either $A$ is true or $B$~is true. However, from 
the second hypothesis, %\cref{EasyValid-notA}, 
we know that $A$ is \emph{not} true. Therefore, it must be~$B$ that is true. Hence, the conclusion of the deduction is true.
\end{solution}

%\begin{eg} \label{LJValidEg}
%Show that the following deduction is valid:
%\begin{earg}
%\item \label{ValidEg-if}  $\enot L \eif (J \eor L)$
%\item \label{ValidEg-NotL} $\enot L$
%\conclusion $J$
%\end{earg}
%\end{eg}
%
%\begin{solution}
%We proceed in two steps.
%
%\setcounter{step}{0}
%
%\begingroup \renewcommand{\thestep}{\Roman{step}}
%
%\begin{step} \label{LJValidEg-HypTrue}
%We look at all possible combinations of values of the variables, to find out which ones make the hypotheses true.
%\end{step}
%To do this, we consider each of the two possible values ($\true$ or~$\false$) of the variable~$J$ as separate case. In each case, we consider the two possible values of the variable~$L$ as subcases.
%
%\setcounter{case}{0}
%
%	\begin{case} 
%	Assume $J$ is true.
%	\end{case}
%	
%	\begin{subcase}
%	 Assume $L$ is true.
%	 \end{subcase}
%		We have
%			$$ \enot L \speq \enot T \speq F ,$$
%		so Hypothesis \pref{ValidEg-NotL} is false.
%	\begin{subcase} \label{LJValidEg-HypTrue-TF}
%	Assume $L$ is false.
%	\end{subcase}
%		We have
%			$$ \enot L \eif (J \eor L)
%			\speq \enot F \eif (T \eor F) 
%			\speq T \eif T
%			\speq T $$
%		and
%			$$ \enot L \speq \enot F \speq T ,$$
%		so both hypotheses are true in this case.
%	\begin{case}
%	 Assume $J$ is false.
%	 \end{case}
%	 \begin{subcase}
%	 Assume $L$ is true.
%	 \end{subcase}
%		We have
%			$$ \enot L \speq \enot T \speq F ,$$
%		so Hypothesis  \pref{ValidEg-NotL} is false.
%	\begin{subcase}
%	Assume $L$ is false.
%	\end{subcase}
%		We have
%			$$ \enot L \eif (J \eor L)
%			\speq \enot F \eif (F \eor F) 
%			\speq T \eif F
%			\speq F $$
%		so Hypothesis \pref{ValidEg-if} is false.
%
%\begin{step}
%We find the truth value of the conclusion for each assignment of variables that makes all of the hypotheses true.
%\end{step}
%From the work in \cref{LJValidEg-HypTrue}, we see that the only situation where both hypotheses are true is in \cref{LJValidEg-HypTrue-TF}, where
%	$$ \text{$J$ is true and $L$ is false.} $$
%In this situation, the conclusion~$J$ is obviously true.
%
%\endgroup % \renewcommand\thestep
%
%\medskip
%
%Since the conclusion of the deduction is true in the only situation where both hypotheses are true, the deduction is valid.
%\end{solution}

%\begin{rem}
%Checking all of the possible values of the variables is called \define{case-by-case analysis}; it can be a lengthy and tedious process. In the future, we will usually try to show that a deduction is valid without having to do so much work. The logician's tools for doing this are the main topic of \cref{ch.threecolumn} and, in particular, \cref{LJValidProof} provides a short proof that the above deduction is valid, without having to check all of the cases.
%\end{rem}

%\section{Partial truth tables}
%In order to show that an assertion is a tautology, we need to show that it is T on every row. So we need a complete truth table. To show that an assertion is \emph{not} a tautology, however, we only need one line: a line on which the assertion is F. Therefore, in order to show that something is not a tautology, it is enough to provide a one-line \emph{partial truth table}---regardless of how many assertion letters the assertion might have in it.

%Consider, for example, the assertion $(U \eand T) \eif (S \eand W)$. We want to show that it is \emph{not} a tautology by providing a partial truth table. We fill in F for the entire assertion. The main connective of the assertion is a conditional. In order for the conditional to be false, the antecedent must be true (T) and the consequent must be false (F). So we fill these in on the table:
%\begin{center}
%\begin{tabular}{c|c|c|c||c*{2}T|c*{2}T|c*{2}T}
%$S$&$T$&$U$&$W$&$U$&\eand&$T$&$S$&\eand&$W$&$(U \eand T)$&$\eif$&$(S\eand W)$\\
%\hline
% & & & & & T & & & F & & \faint{T} & \TTbf{F} & \faint{F} 
%\end{tabular}
%\end{center}
%In order $U\eand T$ to be true, both $U$ and $T$ must be true.
%\begin{center}
%\begin{tabular}{c|c|c|c||c*{2}T|c*{2}T|c*{2}T}
%$S$&$T$&$U$&$W$&$U$&\eand&$T$&$S$&\eand&$W$&$(U \eand T)$&$\eif$&$(S\eand W)$\\
%\hline
% & T & T & & \faint{T} & T & \faint{T} & & F & & \faint{T} & \TTbf{F} & \faint{F} 
%\end{tabular}
%\end{center}
%Now we just need to make $(S\eand W)$ false. To do this, we need to make at least one of $S$ and $W$ false. We can make both $S$ and $W$ false if we want. All that matters is that the whole assertion turns out false on this line. Making an arbitrary decision, we finish the table in this way:
%\begin{center}
%\begin{tabular}{c|c|c|c||c*{2}T|c*{2}T|c*{2}T}
%$S$&$T$&$U$&$W$&$U$&\eand&$T$&$S$&\eand&$W$&$(U \eand T)$&$\eif$&$(S\eand W)$\\
%\hline
%F & T & T & F & \faint{T} & T & \faint{T} & \faint{F} & F & \faint{F} & \faint{T} & \TTbf{F} & \faint{F} 
%\end{tabular}
%\end{center}

%Showing that something is a contradiction requires a complete truth table. Showing that something is \emph{not} a contradiction requires only a one-line partial truth table, where the assertion is true on that one line.

%An assertion is contingent if it is neither a tautology nor a contradiction. So showing that an assertion is contingent requires a \emph{two-line} partial truth table: The assertion must be true on one line and false on the other. For example, we can show that the assertion above is contingent with this partial truth table:
%\begin{center}
%\begin{tabular}{c|c|c|c||c*{2}T|c*{2}T|c*{2}T}
%$S$&$T$&$U$&$W$&$U$&\eand&$T$&$S$&\eand&$W$&$(U \eand T)$&$\eif$&$(S\eand W)$\\
%\hline
%F & T & T & F & \faint{T} & T & \faint{T} & \faint{F} & F & \faint{F} & \faint{T} & \TTbf{F} & \faint{F} \\
%F & T & F & F & \faint{F} & F & \faint{T} & \faint{F} & F & \faint{F} & \faint{F} & \TTbf{T} & \faint{F} 
%\end{tabular}
%\end{center}
%Note that there are many combinations of truth values that would have made the assertion true, so there are many ways we could have written the second line.

%Showing that an assertion is \emph{not} contingent requires providing a complete truth table, because it requires showing that the assertion is a tautology or that it is a contradiction.  If you do not know whether a particular assertion is contingent, then you do no know whether you will need a complete or partial truth table. You can always start working on a complete truth table. If you complete rows that show the assertion is contingent, then you can stop. If not, then complete the truth table. Even though two carefully selected rows will show that a contingent assertion is contingent, there is nothing wrong with filling in more rows.

%Showing that two assertion are logically equivalent requires providing a complete truth table. Showing that two assertions are \emph{not} logically equivalent requires only a one-line partial truth table: Make a row in which one assertion is true and the other is false.

%Showing that a set of assertions is consistent requires providing one row of a truth table on which all of the assertions are true. The rest of the table is irrelevant, so a one-line partial truth table will do. Showing that a set of assertions is inconsistent, on the other hand, requires a complete truth table: You must show that on every row of the table at least one of the assertions is false.

%Showing that a deduction is valid requires a complete truth table. Showing that a deduction is \emph{invalid} only requires providing a one-line truth table: If you can produce a line on which the hypotheses are all true and the conclusion is false, then the deduction is invalid.

%\begin{table}
%\begin{center}
%\begin{tabular}{c|c|c|}
%\cline{2-3}
% & YES & NO\\
%\cline{2-3}
%tautology? & complete & one-line partial\\
%contradiction? &  complete  & one-line partial\\
%contingent? & two-line partial & complete\\
%equivalent? & complete & one-line partial\\
%consistent? & one-line partial & complete\\
%valid? & complete & one-line partial\\
%\cline{2-3}
%\end{tabular}
%\end{center}
%\caption{Do you need a complete truth table or a partial truth table? It depends on what you are trying to show.}
%\label{table.CompleteVsPartial}
%\end{table}

%\cref{table.CompleteVsPartial} summarizes when a complete truth table is required and when a partial truth table will do. 




%\section{The material conditional}
%\label{MaterialConditional}

%The material conditional has some odd properties. For one thing, it does not require that the antecedent and consequent are related in any way.

%contradiction in the antecedent

%tautology in the consequent


%\fix{Summary of test conditions}

%\begin{exers}
%\label{pr.TT.valid(given)}
%Use the given truth table to determine whether each deduction is valid or invalid (and give a brief justification).
%\begin{problist}
%\item $A\eif A$, \therefore\ $A$ %invalid
%\hfil
%\begin{tabular}{c||c}
%$A$&$A\eif A$ \\
%\hline
% T & T \\
% F & T
%\end{tabular}
%\medskip
%\item $A\eor\bigl[A\eif(A\eiff A)\bigr]$, \therefore\ A %invalid
%\hfil
%\begin{tabular}{c||c*{2}T}
%$A$&$A$&$\eor$&$\bigl[A\eif(A\eiff A)\bigr]$ \\
%\hline
% T & &T \\
% F & &T
%\end{tabular}
%\medskip
%\item $A\eif(A\eand\enot A)$, \therefore\ $\enot A$ %valid
%\hfil
%\begin{tabular}{c||c|c}
%$A$&$A\eif(A\eand\enot A)$ & $\enot A$\\
%\hline
% T & F & F \\
% F & T & T
%\end{tabular}
%\medskip
%\item $A\eiff\enot(B\eiff A)$, \therefore\ $A$ %invalid
%\hfil
%\begin{tabular}{c|c||c*{2}T}
%$A$& $B$ & $A$&$\eiff$&$\enot(B\eiff A)$ \\
%\hline
% T & T && F\\
% T & F && T\\
% F & T && F\\
% F & F && T
%\end{tabular}
%\medskip
%\item $A\eor(B\eif A)$, \therefore\ $\enot A \eif \enot B$ %valid
%\hfil
%\begin{tabular}{c|c||c*{2}T|c}
%$A$& $B$ & $A$&$\eor$&$(B\eif A)$ & $\enot A \eif \enot B$ \\
%\hline
% T & T && T && T\\
% T & F && T && T\\
% F & T && F && F\\
% F & F && T && T
%\end{tabular}
%\medskip
%\item $A\eif B$, $B$, \therefore\ $A$ %invalid
%\hfil
%\begin{tabular}{c|c||c}
%$A$& $B$ & $A\eif B$ \\
%\hline
% T & T & T\\
% T & F & F\\
% F & T & T\\
% F & F & T
%\end{tabular}
%\medskip
%\item $A\eor B$, $B\eor C$, $\enot A$, \therefore\ $B \eand C$ %invalid
%\begin{center}
%\begin{tabular}{c|c|c||c|c|c|c}
%$A$& $B$ & $C$ & $A\eor B$ & $B\eor C$ & $\enot A$ & $B \eand C$ \\
%\hline
% T & T & T & T & T & F\hphantom{A} & T\\
% T & T & F & T & T & F\hphantom{A} & F\\
% T & F & T & T & T & F\hphantom{A} & F\\
% T & F & F & T & F & F\hphantom{A} & F\\
% F & T & T & T & T & T\hphantom{A} & T\\
% F & T & F & T & T & T\hphantom{A} & F\\
% F & F & T & F & T & T\hphantom{A} & F\\
% F & F & F & F & F & T\hphantom{A} & F
%\end{tabular}
%\end{center}

%\item $A\eor B$, $B\eor C$, $\enot B$, \therefore\ $A \eand C$ %valid
%\begin{center}
%\begin{tabular}{c|c|c||c|c|c|c}
%$A$& $B$ & $C$ & $A\eor B$ & $B\eor C$ & $\enot B$ & $A \eand C$ \\
%\hline
% T & T & T & T & T & F\hphantom{B} & T\\
% T & T & F & T & T & F\hphantom{A} & F\\
% T & F & T & T & T & T\hphantom{A} & T\\
% T & F & F & T & F & T\hphantom{A} & F\\
% F & T & T & T & T & F\hphantom{A} & F\\
% F & T & F & T & T & F\hphantom{A} & F\\
% F & F & T & F & T & T\hphantom{A} & F\\
% F & F & F & F & F & T\hphantom{A} & F
%\end{tabular}
%\end{center}

% 

%\item $(B\eand A)\eif C$, $(C\eand A)\eif B$, \therefore\ $(C\eand B)\eif A$ %invalid
%\begin{center}
%\begin{tabular}{c|c|c||c*{2}T|c*{2}T|c*{2}T}
%$A$& $B$ & $C$ & $(B\eand A)$&$\eif$&$ C$ & $(C\eand A)$&$\eif$&$ B$ & $(C\eand B)$&$\eif$&$ A$ \\
%\hline
% T & T & T && T &&& T &&& T\\
% T & T & F && F &&& T &&& T\\
% T & F & T && T &&& F &&& T\\
% T & F & F && T &&& T &&& T\\
% F & T & T && T &&& T &&& F\\
% F & T & F && T &&& T &&& T\\
% F & F & T && T &&& T &&& T\\
% F & F & F && T &&& T &&& T
%\end{tabular}
%\end{center}
%\item $A\eiff B$, $B\eiff C$, \therefore\ $A\eiff C$ %valid
%\begin{center}
%\begin{tabular}{c|c|c||c|c|c}
%$A$& $B$ & $C$ & $A\eiff B$ & $B\eiff C$ & $A\eiff C$ \\
%\hline
% T & T & T & T & T & T\\
% T & T & F & T & F & F\\
% T & F & T & F & F & T\\
% T & F & F & F & T & F\\
% F & T & T & F & T & F\\
% F & T & F & F & F & T\\
% F & F & T & T & F & F\\
% F & F & F & T & T & T
%\end{tabular}
%\end{center}
%\end{problist}
%\end{exers}





\begin{exers} \label{pr.TT.conceptsargs}
Answer each of the questions below and justify your answer.
\begin{problist}
\item \label{pr.TT.conceptsargs-nTnC}
Assume $(\script{A}\eand\script{B})\eif\script{C}$ is neither a tautology nor a contradiction. What can you say about the deduction ``\script{A}, \script{B}, \therefore\script{C}''?
%The assertion is false on some line of a complete truth table. On that line, \script{A} and \script{B} are true and \script{C} is false. So the deduction is invalid.
%\item Suppose that $\{\script{A},\script{B}, \script{C}\}$ is inconsistent. What can you say about $(\script{A}\eand\script{B}\eand\script{C})$?
%Since there is no line of a complete truth table on which all three assertions are true, the conjunction is false on every line. So it is a contradiction.
\item \label{pr.TT.conceptsargs-C}
Assume \script{A} is a contradiction. What can you say about the deduction ``\script{A}, \script{B}, \therefore\script{C}''?
%Since \script{A} is false on every line of a complete truth table, there is no line on which \script{A} and \script{B} are true and \script{C} is false. So the deduction is valid.
\item \label{pr.TT.conceptsargs-T}
Assume \script{C} is a tautology. What can you say about the deduction ``\script{A}, \script{B}, \therefore\script{C}''?
%Since \script{C} is true on every line of a complete truth table, there is no line on which \script{A} and \script{B} are true and \script{C} is false. So the deduction is valid.
\end{problist}
\end{exers}


\begin{terminology}
 Any valid deduction can be called a \define{theorem}.
 \end{terminology}

\vbox{% !!!
\begin{exer}[(Rules of {\SL})] \label{BasicThmEx}
It is not difficult to see that each of the following is a valid deduction. For each of them, either give a short explanation of how you know that it is valid, or verify the deduction by evaluating the conclusion for all possible values of the variables that make the hypotheses true.

\begin{enumerate} \itemsep=\medskipamount

\SLrule{BasicThmEx-repeat}{repeat}{repeat}%
	{$A$, \ \therefore $A$}

\SLrule{BasicThmEx-AndIntro}{$\eand$-introduction}{and ($\eand$)!-introduction@-introduction}%
	{$A$, $B$, \  \therefore $A \eand B$}

\SLrule{BasicThmEx-AndElim}{$\eand$-elimination}{and ($\eand$)!-elimination@-elimination}%
{ $A \eand B$, \ \therefore $A$ \hskip0.25in $A \eand B$, \ \therefore $B$}

\SLrule{BasicThmEx-OrIntro}{$\eor$-introduction}{or ($\eor$)!-introduction@-introduction}%
{$A$, \ \therefore $A \eor B$ \hskip0.25in $B$, \ \therefore $A \eor B$}

\SLrule{BasicThmEx-OrElim}{$\eor$-elimination}{or ($\eor$)!-elimination@-elimination}%
{$A \eor B$, $\enot A$, \ \therefore $B$ \hskip0.25in $A \eor B$, $\enot B$, \ \therefore $A$}

\SLrule{BasicThmEx-IfElim}{$\eif$-elimination}{implies ($\eif$)!-elimination@-elimination}%
{$A \eif B$, $A$, \ \therefore $B$}

\SLrule{BasicThmEx-IffIntro}{$\eiff$-introduction}{iff ($\eiff$)!-introduction@-introduction}%
{$A \eif B$, $B \eif A$, \ \therefore $A \eiff B$}

\SLrule{BasicThmEx-IffElim}{$\eiff$-elimination}{iff ($\eiff$)!-elimination@-elimination}%
{$A \eiff B$, \ \therefore $A \eif B$ \hskip0.25in $A \eiff B$, \ \therefore $B \eif A$}

\SLrule{BasicThmEx-cases}{proof by cases}{proof!by cases}%
{$A \eor B$, $A \eif C$, $B \eif C$, \ \therefore $C$}
\end{enumerate}
\end{exer}
}

All of the theorems in \cref{BasicThmEx} will be used on a regular basis in the following chapters (and in your later mathematics courses).

 
\begin{otherterm}
Most logicians call the $\eif$-elimination rule by its Latin name, which is \define{modus ponens}.
(According to \href{https://en.wikipedia.org/wiki/Modus_ponens}{\emph{Wikipedia}}, this is short for \emph{modus ponendo ponens}, which means ``the way that affirms by affirming\rlap.'')
 \end{otherterm}

\begin{rem}
A theorem remains valid if we change the names of the variables. For example, 
	$P \eor Q$, $\enot P$, \therefore $Q$
is the same as $\eor$-elimination, but we have replaced $A$ with~$P$ and $B$~with~$Q$. (In the language of high-school algebra, we have plugged in~$P$ for~$A$, and plugged in~$Q$ for~$B$.) Indeed, it should be clear that any theorem remains valid even if we substitute more complicated expressions into the variables.
\end{rem}

\begin{eg}
The theorem
	$$ (X \eor Y) \eif (Y \eor Z), \  X \eor Y, \ \therefore Y \eor Z $$
is obtained from ``$\eif$-elimination\rlap,'' by letting $A = (X \eor Y)$ and $B = (Y \eor Z)$.
\end{eg}

\begin{exer} \label{SubstitutePL}
Each of the following is a valid theorem that is obtained from one of the basic theorems of \cref{BasicThmEx}, by substituting some expressions into the variables. Identify the theorem it is obtained from, and the expressions that were substituted into each variable.
\begin{enumerate}
%\item $(A \eor B) \eand (Y \eif Z), \  \therefore (Y \eif Z) \eand (A \eor B) $
\item \label{SubstitutePL-AE}
$(A \eor B) \eand (Y \eif Z), \  \therefore Y \eif Z$
\item \label{SubstitutePL-R}
$(A \eor B) \eand (Y \eif Z), \  \therefore (A \eor B) \eand (Y \eif Z)$
\item \label{SubstitutePL-OI}
$A \eor B, \  \therefore (A \eor B) \eor (Y \eif Z)$
\item \label{SubstitutePL-AI}
$(A \eor B), (Y \eif Z), \  \therefore (A \eor B) \eand (Y \eif Z) $
\end{enumerate}
\end{exer}

\begin{exer} \label{SubstituteEnglish}
Each of the following is the English-language version of a valid theorem that is obtained from one of the basic theorems of \cref{BasicThmEx}, by substituting some expressions into the variables. Identify the theorem it is obtained from.
\begin{enumerate}
\item  \label{SubstituteEnglish-Cases}
Susie will stop at either the grocery store or the drug store. If she stops at the grocery store, she will buy milk. If she stops at the drug store, she will buy milk. Therefore, I am sure that Susie will buy milk.
\item  \label{SubstituteEnglish-AndIntro}
My opponent in this election is a liar! My opponent in this election is a cheat! Therefore, I say to you that my opponent is a liar and a cheat!
\item  \label{SubstituteEnglish-Repeat}
John went to the store.  Therefore, as I already told you, John went to the store.
\item  \label{SubstituteEnglish-IfElim}
If I had \$50, I would be able to buy a new coat. Hey, look! I found a \$50 bill on the sidewalk! So I will be able to buy a new coat.  
\end{enumerate}
\end{exer}



\begin{summary}
\item Assertions stated in English can be translated into {\SL} (and vice-versa)
\item In mathematics, ``or'' is inclusive.
\item Notation:
\begin{itemize}
\item $\enot$ (not; means ``It is not the case that\blank'')
\item $\eand$  (and; means ``Both $\blank$\ and $\blank$'')
\item $\eor$ (or; means ``Either $\blank$\ or $\blank$'')
\item $\eif$  (implies; means ``If $\blank$\ then $\blank$'')
\item $\eiff$  (iff; means ``$\blank$ if and only if $\blank$'')
\end{itemize}
\item Important definitions:
\begin{itemize}
\item assertion
\item deduction
\item valid, invalid
%\item truth table
\item tautology
\item contradiction
%\item contingent assertion
\item logically equivalent
\item converse
\item contrapositive
\end{itemize}
\item Determining whether an assertion is true (for particular values of its variables)
\item An implication might \emph{not} be equivalent to its converse.
\item Every implication is logically equivalent to its contrapositive.
\item Basic laws of {\SL}:
\begin{itemize} 
\item Law of Excluded Middle
\item rules of negation
\item commutativity of $\eand$, $\eor$, and $\eiff$
\item associativity of $\eand$ and $\eor$
\end{itemize}
\item ``Theorem'' is another word for ``valid deduction''
\item Basic theorems of {\SL}:
\begin{itemize} 
\item repeat
\item introduction and elimination rules for $\eand$, $\eor$, and $\eiff$
\item elimination rule for $\eif$
\item proof by cases
\end{itemize}

\end{summary}

