\documentclass[12pt]{article} %Page set up \setlength{\topmargin}{-0.75in} \setlength{\textwidth}{7in} \setlength{\oddsidemargin}{-.25in} \setlength{\textheight}{9in} \newtheorem{thm}{Theorem} \newtheorem{ex}[thm]{Example} %Packages \usepackage{amssymb,amsmath,pstricks,framed} \usepackage{array} \usepackage{color} \usepackage{url} % Start document \setcounter{page}{1} \begin{document} \begin{center} {\Large \bf Logic} \\ (The language of Mathematics) \\ \end{center} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Defining propositions %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Propositions} \begin{framed} {\bf Definition} \\ A proposition, or statement, is a declarative sentence that is either true or false. \end{framed} \noindent \textbf{\textit{Notes:}} \begin{itemize} \item We refer to T (true) or F (false) as the truth value of the proposition \item Note that we may not know if a proposition is true of false. We do know, however, that it is either true, or false, but not both. \item When a sentence can be both true and false, we say that it is a paradox. A famous example is the liar's paradox. I refer the reader to the excellent article in the Stanford encyclopedia of philosophy on this paradox( see \url{https://plato.stanford.edu/entries/liar-paradox/}) and especially their first paragraph: \\ \textit{`The first sentence in this essay is a lie. There is something odd about saying so, as has been known since ancient times. To see why, remember that all lies are untrue. Is the first sentence true? If it is, then it is a lie, and so it is not true. Conversely, suppose that it is not true. We (viz., the authors) have said it, and normally things are said with the intention of being believed. Saying something that way when it is untrue is a lie. But then, given what the sentence says, it is true after all!"} \end{itemize} \noindent \textbf{\textit{Examples:}} \begin{center} \begin{tabular}{m{5.5cm} | m{5.5cm}| m{5cm} | } \textbf{Sentence} & \textbf{Is it a proposition?} & \textbf{Truth value} \\ \hline $1+2=4$ & Yes & F \\ \hline $2\times 3 = 6$ & Yes & T \\ \hline Today is Friday & Yes & It depends! It is a proposition that is true on Friday, and false the other days of the week \\ \hline It will rain on July 4th 2022 & Yes & We will know in 6 months \\ \hline $x+1=2$ & No (we do not know what $x$ is) & \\ \hline I am lying now & No (liar's paradox) & \\ \hline \end{tabular} \end{center} \vspace{0.1in} \noindent \textbf{\textit{Notation:}} \\ \begin{center}$p$: ``Today is Monday" \end{center} means that $p$ is the proposition ``Today is Monday". %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Compound propositions % Definition; truth tables % NOT, AND, OR, XOR, ->, and <-> %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Compound propositions} \begin{framed} {\bf Definition} \\ A \underline{compound proposition} is a proposition that involves the assembly of possibly multiple propositions, where the assembly is performed using logic operators. \end{framed} \noindent \textbf{\textit{Notes:}} \begin{itemize} \item There are two types of logic operators: \begin{itemize} \item Those that operate on a single proposition (\underline{unary}) \item Those that operate on two propositions (\underline{binary}) \end{itemize} \item The truth value of a compound proposition depends on the truth values of the propositions that define it. To analyze this dependence, we usually use a \underline{truth table} that lists exhaustively all options. A compound proposition that depends on $N$ proposition will be represented with a truth table with $2^N$ possibilities. \end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % NOT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Negation (NOT) \textit{(unary)}} \begin{framed} {\bf Definition} \\ Let $p$ be a proposition. The sentence ``It is not the case that $p$" is another proposition, called the negation of $p$, denoted $\lnot p$, sometimes $\sim p$. \end{framed} \noindent The negation of $p$ is also read ``not $p$". \vspace{0.1in} \noindent \textbf{\textit{Truth table:}} \\ \begin{center} %\begin{table}[!h] \begin{tabular}{| c | c |} \hline $p$ & $\lnot p$\\ \hline T & \textcolor{red}{F}\\ F & \textcolor{red}{T}\\ \hline \end{tabular} %\end{table} \end{center} \noindent \textbf{\textit{Examples:}} \begin{center} \begin{tabular}{m{5.3cm} | m{2.2cm} | | m{6cm}| m{2.2cm} | } \textbf{Proposition $p$} & \textbf{Truth value} & \textbf{Negation $\lnot p$} & \textbf{Truth value} \\ \hline $2+2=4$ & T & $2+2 \ne 4$ & F\\ \hline $1=0$ & F & $1 \ne 0$ & T \\ \hline All politicians are crooks & & There is at least one politician that is not a crook & \\ \hline All students in this class will get an A in ECS17 & & There is at least one student in this class that will not get an A &\\ \hline \end{tabular} \end{center} \break %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % AND %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Conjunction (AND) \textit{(binary)}} \begin{framed} {\bf Definition} \\ The conjunction of two propositions $p$ and $q$ is the compound proposition that we write $p \land q$ and read ``$p$ and $q$", which is only true if both $p$ and $q$ are true. \end{framed} \vspace{0.1in} \noindent \textbf{\textit{Truth table:}} \\ \begin{center} \begin{tabular}{| c | c | c |} \hline $p$ & $q$ & $p\land q$\\ \hline T & T & \textcolor{red}{T}\\ T & F & \textcolor{red}{F}\\ F & T & \textcolor{red}{F}\\ F & F & \textcolor{red}{F}\\ \hline \end{tabular} \end{center} \noindent \textbf{\textit{Examples:}} \\ \begin{center} $p$: ``John likes pizza" \\ $q$: ``Bill likes milk" \\ \end{center} \begin{center} \begin{tabular}{m{3cm} | m{10cm} | } \textbf{Proposition} & \textbf{Value} \\ \hline $p\land q$ & John likes pizza and Bill likes milk \\ \hline $\lnot p\land q$ & John does not like pizza and Bill likes milk \\ \hline $p\land \lnot q$ & John likes pizza and Bill does not like milk \\ \hline $\lnot p\land \lnot q$ & John does not like pizza and Bill does not like milk \\ \hline \end{tabular} \end{center} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % OR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Disjunction (OR) \textit{(binary)}} \begin{framed} {\bf Definition} \\ The disjunction of two propositions $p$ and $q$ is the compound proposition that we write $p \lor q$ and read ``$p$ or $q$", which is true if $p$ is true, $q$ is true, or both $p$ and $q$ are true. \end{framed} \vspace{0.1in} \noindent \textbf{\textit{Truth table:}} \\ \begin{center} \begin{tabular}{| c | c | c |} \hline $p$ & $q$ & $p\lor q$\\ \hline T & T & \textcolor{red}{T}\\ T & F & \textcolor{red}{T}\\ F & T & \textcolor{red}{T}\\ F & F & \textcolor{red}{F}\\ \hline \end{tabular} \end{center} \noindent \textbf{\textit{Examples:}} \\ \begin{center} $p$: ``The butler did it" \\ $q$: ``The cook did it" \\ $p\lor q$: ``Either the butler or the cook did it" \end{center} \noindent \textbf{\textit{Notes:}} \begin{center} $p \land \lnot p$ is always false, while $p \lor \lnot q$ is always true. \end{center} \begin{center} \begin{tabular}{| c | c | c || c | c |c |} \hline $p$ & $\lnot p$ & $p \land \lnot p$ & $p$ & $\lnot p$ & $p \lor \lnot p$\\ \hline T & F & \textcolor{red}{F}& T & F & \textcolor{red}{T}\\ F & T & \textcolor{red}{F} & F & T & \textcolor{red}{T}\\ \hline \end{tabular} \end{center} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % XOR %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Exclusive or (XOR) \textit{(binary)}} \begin{framed} {\bf Definition} \\ The exclusive or of two propositions $p$ and $q$ is the compound proposition that we write $p \oplus q$, which is true if and only if $p$ is true, or $q$ is true, but not when both $p$ and $q$ are true. \end{framed} \vspace{0.1in} \noindent \textbf{\textit{Truth table:}} \\ \begin{center} \begin{tabular}{| c | c | c |} \hline $p$ & $q$ & $p\oplus q$\\ \hline T & T & \textcolor{red}{F}\\ T & F & \textcolor{red}{T}\\ F & T & \textcolor{red}{T}\\ F & F & \textcolor{red}{F}\\ \hline \end{tabular} \end{center} \noindent \textbf{\textit{Examples:}} \\ \begin{center} $p$: ``The butler did it" \\ $q$: ``The cook did it" \\ $p\oplus q$: ``Either the butler or the cook did it, but they did not do it together!" \end{center} \noindent \textbf{\textit{Notes:}} \begin{center} $p \oplus p$ is always false, while $p \oplus \lnot q$ is always true. \end{center} \begin{center} \begin{tabular}{| c | c | c || c | c |c |} \hline $p$ & $p$ & $p \oplus p$ & $p$ & $\lnot p$ & $p \oplus \lnot p$\\ \hline T & T & \textcolor{red}{F}& T & F & \textcolor{red}{T}\\ F & F & \textcolor{red}{F} & F & T & \textcolor{red}{T}\\ \hline \end{tabular} \end{center} \break %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Implication %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{(Material) implication \textit{(binary)}} \begin{framed} {\bf Definition} \\ The compound proposition $p \rightarrow q$ that reads ``$p$ implies $q$" is true unless $p$ is true and $q$ is false. \end{framed} \vspace{0.1in} \noindent \textbf{\textit{Truth table:}} \\ \begin{center} \begin{tabular}{| c | c | c |} \hline $p$ & $q$ & $p\rightarrow q$\\ \hline T & T & \textcolor{red}{T}\\ T & F & \textcolor{red}{F}\\ F & T & \textcolor{red}{T}\\ F & F & \textcolor{red}{T}\\ \hline \end{tabular} \end{center} Note: when $p$ is false, $p \rightarrow q$ is true, no matter what the truth value of $q$ is. \vspace{0.1in} \noindent \textbf{\textit{Example:}} \vspace{0.1in} Consider the statement ``If you earn an A in this class, then I will buy you a car". This is a compound proposition made of the two propositions \begin{center} $p$: ``You earn an A in this class" \\ $q$: ``I'll buy you a car" \end{center} that reads ``$p\rightarrow q$. This statement can be seen as a ``contract" between you and me. If you do satisfy your part of the contract, namely you earn an A, and I buy you a car, then the contract is satisfied; we call it true. However, if you do satisfy your part of the contract, but I do not buy you a car, then the contract is broken; we call it false. Interestingly, if you do not satisfy your part of the contract, then it does not matter what I do, the contract does not apply, or at least is not broken; it is then true. \begin{framed} {\bf Definitions} \\ \begin{itemize} \item [i)] The compound proposition $\lnot q \rightarrow \lnot p$ is called the \underline{contrapositive} of the proposition $p \rightarrow q$. \item [ii)] The compound proposition $q \rightarrow p$ is called the \underline{converse} of the proposition $p \rightarrow q$. \end{itemize} \end{framed} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % biconditional %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Biconditional \textit{(binary)}} \begin{framed} {\bf Definition} \\ The biconditional compound proposition $p \leftrightarrow q$ is defined as the compound proposition $(p\rightarrow q) \land (q\rightarrow p)$, for any proposition $p$ and $q$. \end{framed} \vspace{0.1in} \noindent \textbf{\textit{Truth table:}} \\ \begin{center} \begin{tabular}{| c | c | c |} \hline $p$ & $q$ & $p\leftrightarrow q$\\ \hline T & T & \textcolor{red}{T}\\ T & F & \textcolor{red}{F}\\ F & T & \textcolor{red}{F}\\ F & F & \textcolor{red}{T}\\ \hline \end{tabular} \end{center} \vspace{0.1in} \noindent \textbf{\textit{Phrasing:}}\\ \vspace{0.1in} \noindent The biconditional between two propositions $p$ and $q$ can be written as: \begin{itemize} \item ``$p$ if and only if $q$", often written as ``$p$ iff $q$" \item ``$p$ is necessary and sufficient for $q$" \item ``$p$ is equivalent to $q$" \end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Comparing propositions %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \break \section{Comparing Propositions} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % logical equivalence %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Logical equivalence - Tautology - Contradiction} \begin{framed} {\bf Definitions} \\ \begin{itemize} \item [i)] Two propositions $p$ and $q$ are logically equivalent if they always have the same truth values. We write $p \Leftrightarrow q$. \item [ii)] A compound proposition $p$ is a tautology if and only if it is always true. We write $ p \Leftrightarrow T$, where $T$ is used to indicate a proposition that is always true. \item [iii)] A compound proposition $q$ is a contradiction if and only if it is always false.We write $ p \Leftrightarrow F$, where $F$ is used to indicate a proposition that is always false. \end{itemize} \end{framed} \noindent \textbf{\textit{Notes:}} \begin{itemize} \item Do note the difference between $p \leftrightarrow q$ and $p \Leftrightarrow q$: in the former, $\leftrightarrow$ refers to the logical operator ``biconditional", while in the latter, $\Leftrightarrow$ refers to the comparison of $p$ and $q$, signaling that they always have the same truth value. \item From the definition of the biconditional, we note that to show that two propositions $p$ and $q$ are logically equivalent, it is enough to show that the proposition $p\leftrightarrow q$ is a tautology. In practice, however, we check directly the truth values of both propositions to see if they are equal. \item One way to prove that two propositions are logically equivalent is to build the truth table associated with those two propositions, and check the corresponding columns. Please note, however, that there are other possibilities. We will see some of them later. \end{itemize} \vspace{0.1in} \noindent \textbf{\textit{Examples of logical equivalences:}} \vspace{0.1in} \noindent Let $p$ and $q$ be two propositions. Then, \begin{itemize} \item [a)] $\lnot (\lnot p) \Leftrightarrow p$. \item [b)] $p \lor p \Leftrightarrow p$. \item [c)] $p \land p \Leftrightarrow p$. \item [d)] $p \oplus q \Leftrightarrow (p\lor q) \land (\lnot (p \land q))$. \end{itemize} Let us show that $d)$ is true using a truth table. I leave the three others ($a)$, $b)$, and $c)$) as exercises. \begin{center} \begin{tabular}{| c | c | c | c | c | c | c| } \hline $p$ & $q$ & $p\lor q$ & $p\land q$ & $\lnot (p\land q)$ & $(p\lor q)\land \lnot (p\land q)$ & $p \oplus q$ \\ \hline T & T &T & T &F & \textcolor{red}{F} & \textcolor{blue}{F}\\ T & F & T & F & T & \textcolor{red}{T} & \textcolor{blue}{T}\\ F & T & T & F & T & \textcolor{red}{T} & \textcolor{blue}{T}\\ F & F & F & F & T & \textcolor{red}{F} & \textcolor{blue}{F}\\ \hline \end{tabular} \end{center} The two propositions $(p\lor q)\land \lnot (p\land q)$ and $p \oplus q$ (columns 6 and 7 in the truth table) always have the same truth values; they are therefore equivalent. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % de Morgan's law %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{De Morgan's laws in logic} \begin{framed} Let $p$ and $q$ be two propositions. Then, \begin{itemize} \item [a)] $\lnot (p \land q) \Leftrightarrow \lnot p \lor \lnot q$. \item [b)] $\lnot (p \lor q) \Leftrightarrow \lnot p \land \lnot q$. \end{itemize} \end{framed} Let us prove both laws using truth tables: \begin{itemize} \item [a)] Let $p$ and $q$ be two propositions. \begin{center} \begin{tabular}{| c | c | c | c | c | c | c |} \hline $p$ & $q$ & $p\land q$ & $\lnot (p\land q)$ & $\lnot p$ & $\lnot q$ & $\lnot p\lor \lnot q$\\ \hline T & T & T & \textcolor{blue}{F} &F &F & \textcolor{red}{F}\\ T & F & F & \textcolor{blue}{T} &F &T & \textcolor{red}{T}\\ F & T & F & \textcolor{blue}{T} &T & F & \textcolor{red}{T}\\ F & F &F & \textcolor{blue}{T} & T & T & \textcolor{red}{T}\\ \hline \end{tabular} \end{center} The two propositions $\lnot (p\land q)$ and $\lnot p\lor \lnot q$ (columns 4 and 7 in the truth table) always have the same truth values; they are therefore equivalent. \item [b)] Let $p$ and $q$ be two propositions. \begin{center} \begin{tabular}{| c | c | c | c | c | c | c |} \hline $p$ & $q$ & $p\lor q$ & $\lnot (p\lor q)$ & $\lnot p$ & $\lnot q$ &$\lnot p\land \lnot q$\\ \hline T & T & T & \textcolor{blue}{F} &F &F & \textcolor{red}{F}\\ T & F & T & \textcolor{blue}{F} &F &T & \textcolor{red}{F}\\ F & T & T & \textcolor{blue}{F} &T & F & \textcolor{red}{F}\\ F & F &F & \textcolor{blue}{T} & T & T & \textcolor{red}{T}\\ \hline \end{tabular} \end{center} The two propositions $\lnot (p\lor q)$ and $\lnot p\land \lnot q$ (columns 4 and 7 in the truth table) always have the same truth values; they are therefore equivalent. \end{itemize} \vspace{0.1in} \noindent \textbf{\textit{Example of application:}} \vspace{0.1in} \noindent Let $p$ and $q$ be two propositions. Show that, \begin{center} $(p\lor q) \lor (\lnot p \land \lnot q)$. is a tautology. \end{center} \begin{itemize} \item[a)] \textbf{\textit{Method 1:}} we use a truth table. \begin{center} \begin{tabular}{| c | c | c | c | c | c | c |} \hline $p$ & $q$ & $p\lor q$ & $\lnot p$ & $\lnot q$ & $\lnot p\land \lnot q$ & $(p\lor q)\lor (\lnot p\land \lnot q)$\\ \hline T & T & T & F & F & F & \textcolor{red}{T}\\ T & F &T &F &T & F & \textcolor{red}{T}\\ F & T & T & T & F &F & \textcolor{red}{T}\\ F & F & F & T & T & T & \textcolor{red}{T}\\ \hline \end{tabular} \end{center} As $(p\lor q)\lor (\lnot p\land \lnot q)$, it is a tautology. \item[b)] \textbf{\textit{Method 2:}} using De Morgan's law. \\ \begin{itemize} \item Note first that $p \lor p$ is a tautology. Indeed, \begin{center} \begin{tabular}{| c | c | c |} \hline $p$ & $\lnot p$ & $p\lor \lnot p$\\ \hline T & \textcolor{blue}{F} & \textcolor{red}{T}\\ F & \textcolor{blue}{T} & \textcolor{red}{T}\\ \hline \end{tabular} \end{center} \item Let $A=(p\lor q)\lor (\lnot p\land \lnot q)$. According to de Morgan's law, \begin{equation*} \lnot p \land \lnot q \Leftrightarrow \lnot (p \lor q) \end{equation*} Therefore, \begin{equation*} A \Leftrightarrow (p\lor q)\lor \lnot (p \lor q) \end{equation*} Defining $B = p\lor q$, we get, \begin{eqnarray*} A &\Leftrightarrow & (p\lor q)\lor \lnot (p \lor q) \\ A &\Leftrightarrow & B \lor \lnot B \\ A &\Leftrightarrow & T \end{eqnarray*} using the first property we established. \end{itemize} \end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Properties of conditional %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Important properties of conditionals} \begin{framed} Let $p$ and $q$ be two propositions. Then, \begin{itemize} \item [a)] $p\rightarrow q \Leftrightarrow (\lnot p) \lor q$. \item [b)] $p\rightarrow q \Leftrightarrow \lnot q \rightarrow \lnot p$, namely a conditional proposition and its contrapositive are logically equivalent. \end{itemize} \end{framed} Let us prove both properties using truth tables: \begin{itemize} \item [a)] Let $p$ and $q$ be two propositions. \begin{center} \begin{tabular}{| c | c | c | c | c | c |} \hline $p$ & $q$ & $p \rightarrow q$ & $\lnot p$ & $q$ & $\lnot p \lor q$ \\ \hline T & T & \textcolor{blue}{T} & F & T & \textcolor{red}{T}\\ T & F & \textcolor{blue}{F} & F & F & \textcolor{red}{F}\\ F & T & \textcolor{blue}{T} & T & T & \textcolor{red}{T}\\ F & F & \textcolor{blue}{T} & T & F & \textcolor{red}{T}\\ \hline \end{tabular} \end{center} The two propositions $p \rightarrow q$ and $\lnot p \lor q$ (columns 3 and 6 in the truth table) always have the same truth values; they are therefore equivalent. \item [a)] Let $p$ and $q$ be two propositions. \begin{center} \begin{tabular}{| c | c | c | c | c | c | } \hline $p$ & $q$ & $p \rightarrow q$ & $\lnot q$ & $\lnot p$ & $\lnot q \rightarrow \lnot p$ \\ \hline T & T & \textcolor{blue}{T} & F & F & \textcolor{red}{T}\\ T & F & \textcolor{blue}{F} & T & F & \textcolor{red}{F}\\ F & T & \textcolor{blue}{T} & F & T & \textcolor{red}{T}\\ F & F & \textcolor{blue}{T} & T & T & \textcolor{red}{T}\\ \hline \end{tabular} \end{center} The two propositions $p \rightarrow q$ and $\lnot q \rightarrow \lnot p$ (columns 3 and 6 in the truth table) always have the same truth values; they are therefore equivalent. \end{itemize} \break %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Important equivalences %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{List of important logical equivalences} \vspace{0.2in} Let $p$, $q$, and $r$ be two propositions. $T$ is a tautology and $F$ is a contradiction. \vspace{0.2in} \begin{center} \begin{tabular}{l l} \hline \textbf{Logical equivalence} & \textbf{Name} \\ \hline & \\ $\lnot ( \lnot p) \Leftrightarrow p$ & Double negation \\ & \\ $p \lor p \Leftrightarrow p$ & Idempotent 1 \\ $p \land p \Leftrightarrow p$ & Idempotent 2 \\ & \\ $p \lor q \Leftrightarrow q \lor p$ & Commutativity 1 \\ $p \land q \Leftrightarrow q \land p$ & Commutativity 2 \\ & \\ $p \lor ( q \lor r) \Leftrightarrow (p \lor q) \lor r$ & Associativity 1 \\ $p \land ( q \land r) \Leftrightarrow (p \land q) \land r$ & Associativity 2 \\ & \\ $p \lor ( q \land r) \Leftrightarrow (p \lor q) \land (p \lor r)$ & Distributivity 1 \\ $p \land ( q \lor r) \Leftrightarrow (p \land q) \lor (p \land r)$ & Distributivity 2 \\ & \\ $\lnot (p \land q) \Leftrightarrow \lnot p \lor \lnot q$ & De Morgan's law 1 \\ $\lnot (p \lor q) \Leftrightarrow \lnot p \land \lnot q$ & De Morgan's law 2 \\ & \\ $p \lor F \Leftrightarrow p$ & Absorption law 1 \\ $p \lor T \Leftrightarrow T$ & Absorption law 2 \\ $p \land F \Leftrightarrow F$ & Absorption law 3 \\ $p \land T \Leftrightarrow p$ & Absorption law 4 \\ & \\ $\lnot T \Leftrightarrow F$ & Complement law 1 \\ $\lnot F \Leftrightarrow T$ & Complement law 2 \\ $p \lor \lnot p \Leftrightarrow T$ & Complement law 3 \\ $p \land \lnot p \Leftrightarrow F$ & Complement law 4 \\ & \\ $p\rightarrow q \Leftrightarrow (\lnot p) \lor q$ & Implication law 1\\ $p\rightarrow q \Leftrightarrow \lnot q \rightarrow \lnot p$ & Implication law 2 \\ & \\ $(p \leftrightarrow q) \Leftrightarrow (p \rightarrow q) \land (q \rightarrow p)$ & Equivalence law \\ & \\ \hline \end{tabular} \end{center} \break %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{ Predicates and quantifiers} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Definitions} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% We have seen that the expression ``$x+3=1$" is not a proposition as we cannot assess of its truth value. We can denote this expression as $P(x)$, where $x$ is the variable defined in a ``universe" $\mathbb{D}$ and $P$ is the \textbf{\emph{predicate}}. A predicate can become a proposition through quantification. \begin{framed} There are two main types of quantification: \begin{itemize} \item Universal quantification: $P(x)$ is true for all $x$ in the universe $\mathbb{D}$ of discourse \underline{Notation}: $\forall x \in \mathbb{D}, P(x)$ \textit{Example}: $\forall n \in \mathbb{N}, n^2 \ge 0$. \item Universal quantification: There exists a value $x$ in the universe $\mathbb{D}$ if discourse such at $P(x)$ is true. \underline{Notation}: $\exists x \in \mathbb{D}, P(x)$ \textit{Example}: $\exists n \in \mathbb{N}, n$ is prime. \end{itemize} \end{framed} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{How do we validate a quantified predicate?} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{center} \begin{tabular}{m{2.8cm} | m{6.8cm} | m{6.8cm}} \textbf{Statement} & \textbf{When is is true?} & \textbf{When is it false?} \\ \hline $\forall x \in \mathbb{D}, P(x)$ & We need to show that $P(x)$ is true for all $x \in \mathbb{D}$ & There exists (at least) one $x \in \mathbb{D}$ for which $P(x)$ is false \\ \hline $\exists x \in \mathbb{D}, P(x)$ & There is (at least) one $x \in \mathbb{D}$ for which $P(x)$ is true & We need to show that $P(x)$ is false for all $x \in \mathbb{D}$ \\ \hline \end{tabular} \end{center} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Negating quantifiers} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{center} \begin{tabular}{m{4cm} | m{4cm} | m{6cm}} \textbf{Statement} & \textbf{Negation} & \textbf{Equivalent statement} \\ \hline $\forall x \in \mathbb{D}, P(x)$ & $\lnot ( \forall x \in \mathbb{D}, P(x) ) $ & $\exists x \in \mathbb{D}, \lnot P(x)$\\ \hline $\exists x \in \mathbb{D}, P(x)$ & $\lnot ( \exists x \in \mathbb{D}, P(x) ) $ & $\forall x \in \mathbb{D}, \lnot P(x)$\\ \hline \end{tabular} \end{center} \break %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{ Some Applications} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Boolean searches} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Boolean operators form the basis of database logic. They connect your search words together to either narrow or broaden your set of results. Given two search terms, the three basic boolean operators are: \begin{itemize} \item AND: match records that contains both terms \item OR: match records that contains either term \item NOT.: match records that do not contain a term \end{itemize} \noindent Why use Boolean operators? \begin{itemize} \item To focus a search, particularly when your topic contains multiple search terms. \item To connect various pieces of information to find exactly what you're looking for. \end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Logic puzzles: Smullyan's island} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% These puzzles are set on a fictional island, Smullyan's island, where all inhabitants are either \textbf{knights}, who always tell the truth, or  \textbf{knaves}, who always lie. \vspace{0.1in} The puzzles involve a visitor to the island who meets a small group of inhabitants. The aim is for the visitor to deduce the inhabitants' type only from their statements. We solve those puzzles using a table: \begin{itemize} \item[i)] Assign all possible types for the inhabitants: rows of the table \item[ii)] For each assignment (row of the table), evaluate the truth values of the statements of the inhabitants. \item[iii)] Finally, check for each row of the table, check if the truth values assigned in ii) are compatible with the corresponding types of the inhabitant \end{itemize} The solution is then the row that is found compatible in step iii). Note that some problems my be ill-posed, in which case multiple solutions, or no solutions are possible. \vspace{0.1in} \noindent \textbf{\textit{Examples}} \begin{itemize} \item [a)] Let John and Bill be two inhabitants of the island. John says, "the two of use are both knights," but Bill says, "John is a knave.? Can you find out what types John and Bill are? We define: \begin{center} $P_{J}$: ``The two of us are both knights" \\ $P_{B}$: ``John is a knave" \\ \end{center} the statements provided by John and Bill, respectively. Then, \begin{center} \begin{tabular}{m{2cm} | m{2cm} | | m{1cm}| m{1cm} | | m{8cm}} \hline If John is a & If Bill is a & $P_J$ & $P_B$ & Validity \\ \hline Knight & Knight & T & F & \textcolor{red}{No: Bill would be a knight that lies} \\ Knight & Knave & F & F & \textcolor{red}{No: John would be a knight that lies} \\ Knave & Knight & F & T & \textcolor{blue}{Yes, John is a Knave that lies and Bill is a Knight that tells the truth} \\ Knave & Knave & F & T & \textcolor{red}{No: Bill would be a knave that tells the truth} \\ \hline \end{tabular} \end{center} Therefore, John is a knave, and Bill is a Knight. \item [b)] Let John and Bill be two inhabitants of the island. John says, "We are both knaves," but Bill says nothing. Can you find out what types John and Bill are? We define: \begin{center} $P_{J}$: ``The two of us are knaves" \\ \end{center} the statement provided by John. Then, \begin{center} \begin{tabular}{m{2cm} | m{2cm} | | m{1cm} | | m{8.5cm}} \hline If John is a & If Bill is a & $P_J$ & Validity \\ \hline Knight & Knight & F & \textcolor{red}{No:John would be a knight that lies} \\ Knight & Knave & F & \textcolor{red}{No: John would be a knight that lies} \\ Knave & Knight & F & \textcolor{blue}{Yes, John is a Knave that lies} \\ Knave & Knave & T & \textcolor{red}{No: John would be a knave that tells the truth} \\ \hline \end{tabular} \end{center} Therefore, John is a knave, and Bill is a Knight. \end{itemize} \end{document}