\documentclass[12pt]{article} \usepackage{amsmath} \usepackage{url} \usepackage[top=1.5 in, left=1.5 in, bottom=1.5 in, right=1.5 in]{geometry} \usepackage{graphicx} \setlength{\parindent}{0in} \setlength{\parskip}{+.2in} \pagestyle{empty} \def\not{\neg} \def\implies{\Rightarrow} \def\and{\wedge} \def\vel{\vee} \def\aut{\times} \def\iff{\Leftrightarrow} \def\tilde{\sim} \def\foo{1.5} \def\bar#1{\overline{#1}} \setlength{\marginparwidth}{1.2in} \newcommand{\margin}[1]{\marginpar{\raggedright \tiny #1}} \begin{document} {\large \bf Math 348 Truth Tables} \margin{Corrected 24aug07, 24jan11 revised to correlate with D'Angelo-West notation.} {\bf Content:} In these lectures you will learn the notation, concepts, and logical calculus of propositions, or {\bf Propositional Calculus}. {\bf Definition} A {\it proposition} is a sentence which can be either true or false. If you cannot imagine discovering or assigning the truth value to the sentence, it is not a proposition. {\bf Definition} A {\it sentence} consists of a {\it subject} and a {\it predicate}. What a subject and predicate is we shall leave to your experience of 13-18 years of schooling. {\bf Examples} Here are two examples of sentences that are not proposition. \begin{itemize} \item{The king of France is bald.} \item{The study of square circles is difficult.} \item{Math class is tough.} \end{itemize} {\bf Comments:} The first non-proposition is a classical example proposed by the most famous logician in recent times, Bernard Russell. What makes this a non-proposition is the impossibility of determining whether it is true or false, since France has had no king for several centuries. The second example fails for the same reason. The third example was a recording in an issue of Barbie Dolls\footnote{\url{http://www.youtube.com/watch?v=NO0cvqT1tAE}} was programmed to say some years ago. Mattel had to remove this sexist sentiment by popular demand. Did Barbie utter a proposition? We will next develop the rudiments of {\it propositional logic}, which is a set of rules concerning propositions. The rules of logic seem to be ingrained in our minds, humans think logically by nature. However, once a certain complexity sets in, for example in legal matters, or in mathematics, common sense logic is no longer reliable. We need rules. The establishement of rules in logic is an example of {\it formalization}. We formalize rules when we want an efficient and reliable way of teaching these rules to hitherto innocent students (or ignorant computers !). Whenever we formalize a science, we need a language to do it with. The language we use to formalize something, is called a {\it meta-language}. Thus the rules of the propositional calculus themselves are the subject of {\it meta-logic}. In this course we our meta-logic will be {\it informal}, i.e. we will depend on common English and common sense to talk about the rules of logic. {\bf Conjunction:} The conjunction of two propositions $A$ and $B$, is written $A\and B$ and is spoken A and B". To see that a conjunction is again a proposition, all we have to do is to decide the truth-values of the conjuction as a function of the truth-values of the the constituents. We assign the symbol $0$ for {\it false} and the symbol $1$ for {\it true}. Then, a {\it truth table} for conjunctions looks like a multiplication table. \footnote{In fact, it is the multiplication table for the finite field of order 2 we shall study later in the course.} \begin{tabular}{|r|r|r|}\hline $A\and B$& 0 & 1 \\ \hline 0 & 0 & 0 \\ \hline 1 & 0 & 1 \\ \hline \end{tabular} The symmetry of this table shows that the conjunction $B\and A$ has the same table. Therefore, we consider these two propositions to be logically {\it equivalent} and write $A\and B \tilde B\and A$ There are two further common notations used for logical equivalence. $A\and B \equiv B \and A \mbox{ and } A\and B \iff B\and A$. {\bf Negations:} The negation of a proposition $A$, written $\not A$ (and sometimes as $\bar{A}$) , is also a proposition since its truth table is \begin{tabular}{|r|r|r|}\hline $A$& 0 & 1 \\ \hline $\not A$& 1 & 0 \\ \hline \end{tabular} Often it is more efficient to write truth tables in this way \begin{tabular}{|r|r|r|r|r|}\hline $AB$ & 00 &01&10 &11 \\ \hline $A\and B$&0 &0 &0 & 1 \\ \hline \end{tabular} {\bf Disjunction:} The disjunction of two propositions $A$ and $B$, is written $A\vel B$ and is spoken A or B". To see that this is again a proposition, all we have to do is to decide the truth-values of the disjunction as a function of the truth-values of the the constituents. \begin{tabular}{|r|r|r|}\hline $A\vel B$& 0 & 1 \\ \hline 0 & 0 & 1 \\ \hline 1 & 1 & 1 \\ \hline \end{tabular} Unlike with and", we cannot depend on our common language here to distinguish or" from and/or" . Latin does have two different words for or". The inclusive and/or" is vel" in Latin, and hence the symbol $\vel$. The exclusive or, also called xor" and sometimes denoted by $\aut$, has the Latin word aut" for it. So now our truth table looks like this. \begin{tabular}{|r|r|r|r|r|}\hline $AB$ & 00 &01&10 &11 \\ \hline $A\and B$&0 &0 &0 & 1 \\ \hline $A\vel B$&0 &1 &1 & 1 \\ \hline $A\aut B$&0 &1 &1 & 0 \\ \hline $\not{A} \vel \not{B}$& & & & \\ \hline $A\ \ \ \ B$&1 &1 &0 & 1 \\ \hline \end{tabular} {\bf Exercise:} Can you justify the 3rd line? Fill in the blanks in th 4th line and formulate a logical rule that your answer proves. What connective has the truth values on the 5th line? How many different logical connectives are there? Hint: How far can this table be extended? {\bf Implication:} The most common, and most commonly misunderstood logical form in mathematics is {\it material implication}. You have met it in such statements as If $A$ then $B$", written $A\implies B$. Its truth table has already been listed above. And because it gives novices so much trouble, it is wise to use its equivalent form $( A \implies B) \tilde ( \bar{A} \vel B)$ To verify a rule of propositional logic we may use previously proved rules or if necessary, compute the truth tables and see that they match. {\bf Exercises } \begin{itemize} \item[1.] Prove that $A \and (B \vel C)) \tilde (A \and B)\vel (A \and C)$. \item[2.] What is $A \vel (B \and C))$ equivalent to? \item[3.] Simplify $\not( A \implies B)$. \item[4.] Are you surprised that the answer to 3. is not $B \implies A$ ? \item[5.] Write  $A$ if and only if $B$" in symbols and find its truth table. \end{itemize} \end{document}