\documentclass{article}
\usepackage{amsfonts}
\usepackage{graphicx}
\begin{document}
\noindent
CS 173, Lecture A\\
Introduction to Logic, Sets, Graphs, and Functions \\
Tandy Warnow\\
\section{Today's material}
\begin{itemize}
\item Introduction to proofs by contradiction
\item Introduction to sets (notation, operations, terminology)
\item Introduction to logic (propositions, predicates, quantifiers, operations)
\item Introduction to graphs (terminology)
\item Introduction to function notation and recursively defined sets and functions
\item Satisfiability and Conjunctive Normal Form
\item Truth Tables
\end{itemize}
\section{Proofs}
\begin{itemize}
\item
You want to prove that some statement A is true.
\item
You can try to prove it directly, or you can prove it indirectly? we will show examples of each type of proof.
\end{itemize}
\paragraph{Example of Direct Proof}
Theorem: Every odd integer is the difference of two perfect squares. (In other words, $\forall$ odd integers $x$, $\exists y,z$ integers such that $x = y^2 - z^2$.)
\vspace{.1in}
Note: $\forall x$ is the same as ``for all x" and
$\exists x$ is the same as ``there exists an x".
\paragraph{Example of Direct Proof}
Theorem: Every odd integer is the difference of two perfect squares. (Put more formally $\forall$ odd integers $x$, $\exists y,z$ integers such that $x = y^2 - z^2$.)
\vspace{.1in}
Proof: Since $x$ is odd, there is an integer $L$ such that $x=2L+1$. \\
Note that $(L+1)^2 = L^2 +2L +1$\\
Hence $(L+1)^2-L^2 = x$ \\
Q.E.D.
\paragraph{Proof by contradiction}
Theorem: $\sqrt 7$ is irrational.
\vspace{.1in}
Proof by contradiction.
\vspace{.1in}
If $\sqrt 7$ is rational, then \textit{by definition} $\exists $ integers $a,b$
such that $\frac{a}{b} = \sqrt 7$. \\
Without loss of generality, we will assume $a$ and $b$ are
relatively prime
(where relatively prime means that they have no common factors greater than 1).
\vspace{.1in}
Therefore $a^2 = 7b^2$ (Arithmetic)
\vspace{.1in}
Hence 7 divides $a^2$ (Because $a^2 = 7b^2$, and $7$ divides $7b^2$)
\vspace{.1in}
Because 7 is prime, this implies that 7 divides $a$
\vspace{.1in}
But then $7^2$ divides $a^2$ (obvious)
\vspace{.1in}
and so $7^2$ divides $7b^2$ (because $a^2 = 7b^2$)
\vspace{.1in}
And so 7 divides $b^2$ (obvious)
\vspace{.1in}
Because 7 is prime, this implies that 7 divides $b$
\vspace{.1in}
Hence 7 is a common divisor of both $a$ and $b$, which contradicts
our earlier assumption.
\vspace{.1in}
Note that 7 being prime was important in the proof.
\vspace{.1in}
We said that if 7 divides $a^2$ then 7 divides $a$, and we used that
$7$ is prime.
\vspace{.1in}
This was necessary since it doesn't hold that if 4 divides $a^2$ then 4 divides $a$
(e.g., let $a=6$).
\vspace{.1in}
Here's a longer justification for why 7 must divide $a$ if 7 divides $a^2$.
\vspace{.1in}
Remember that every integer greater than 1 has a unique prime factorization.
\vspace{.1in}
So let the prime factorization of $a$ be:
$$a = \prod_{i=1}^k p_i^{l_i}$$
where $p_i$ is a prime and $l_i$ is a positive integer.
\vspace{.1in}
Hence the unique prime factorization of $a^2$ must be
$$a^2 = \prod_{i=1}^k p_i^{2l_i}$$
\vspace{.1in}
If 7 divides $a^2$ then $7=p_i$ for some $i, 1 \leq i \leq k$.
(the definition of saying that 7 divides $a^2$)
\vspace{.1in}
Hence 7 is one of the prime factors for $a$, and so 7 divides a.
\paragraph{Class exercise}
Prove that $\sqrt 5$ is irrational.
\section{Introduction to Sets}
A set S is just a collection of objects. \\
Some sets are finite (e.g., $\{1,2,3,5\}$)
and some are infinite (e.g., the set $\mathbb{Z}$ of integers). \\
We can specify a set explicitly, as in $\{1,2,3,5\}$, or implicitly using ``set-builder notation?":
\begin{itemize}
\item $\{x \in \mathbb{Z}| 0 < x < 6, x \neq 4\}$
\end{itemize}
Note that $\{x \in \mathbb{Z}| 0 < x < 6, x \neq 4\} = \{1,2,3,5\}$. \\
\vspace{.1in}
The emptyset is denoted by $\emptyset$ or by $\{\}$, and is the set that has no elements.
\paragraph{Terminology}
We write $x \in A$ to indicate that $x$ is an element of set $A$. \\
For example, $5 \in \mathbb{Z}$.\\
\vspace{.1in}
We write $x \not \in A$ to indicate that $x$ is not an element of $A$. \\
For example, $\sqrt 7 \not \in \mathbb{Z}$.\\
\vspace{.1in}
We say that a set $A$ is a subset of $B$ if every element of $A$ is an element of $B$.
This is denoted $A \subseteq B$. For example, $\mathbb{Z} \subseteq \mathbb{R}$, where $\mathbb{Z}$ denotes the set of integers and $\mathbb{R}$ denotes the set of real numbers.
\vspace{.1in}
The intersection and unions of sets $A$ and $B$ are represented using $A \cap B$ and $A \cup B$, respectively.
\vspace{.1in}
The set difference between sets $A$ and $B$ is denoted $A \setminus B$, and is the set $\{x \in A| x \not \in B\}$.
\vspace{.1in}
The number of elements in a set $A$ (also called its cardinality) is denoted by $|A|$.
\paragraph{Set builder notation}
Let $\mathbb{Z}$ denote the integers and $\mathbb{R}$ denote the real numbers.
What are these sets?
\begin{itemize}
\item $A = \{f: \mathbb{Z} \rightarrow \{1,2,3\} \}$
\item $B = \{x \subseteq \{0,1,2,3\}| 1 \in x\}$
\item $C = \{x \subseteq \mathbb{Z}| |x| \leq 2\}$
\item $D = \{f: \mathbb{R} \rightarrow \mathbb{R}| \forall x (f(x) = f(0)) \}$
\item $E = \{x \in \mathbb{Z}| x > 0\}$
\item $F = \{x \in \mathbb{Z}| x-1 \in \mathbb{Z}\}$
\item $G = \{x \in \mathbb{Z}| x^2 < x\}$
\end{itemize}
\paragraph{Another proof by contradiction}
Theorem: Let $A \subseteq \mathbb{Z}$ be finite and satisfy
\begin{itemize}
\item If $x \in A$ then $x+1 \in A$
\end{itemize}
Then $A = \emptyset$.
\paragraph{Proving $A = \emptyset$}
Recall that we assume $A$ is a finite set of integers and satisfies $x \in A \rightarrow x+1 \in A$.
We first show that $A$ cannot be non-empty, and then we show that $A = \emptyset$ satisfies the constraint.
\begin{itemize}
\item
If $A$ is finite but non-empty, then it has $n$ elements, and so $A = \{x_1, x_2, \ldots, x_n\}$.
Let $y$ be the maximum element of $A$.
Since $y \in A$, it follows that $y+1 \in A$. \\
But $y+1 $ is bigger than every element of $A$, which is a contradiction.
Hence, $A$ cannot be non-empty.
\item
On the other hand, does $A = \emptyset$ satisfy the required property:
\begin{itemize}
\item If $x \in A$ then $x+1 \in A$
\end{itemize}
Yes, because an ``IF-THEN" statement is true whenever the first half is false. And $x \in \emptyset$ is always false.
\end{itemize}
\clearpage
\section{Introduction to Graphs}
Graphs are objects with vertices and edges.
We write this as $G=(V,E)$, so $V$ is the set of vertices
and $E$ is the set of edges.
Every edge is an un-ordered pair of vertices.
\begin{figure}[b!]
\includegraphics[width=0.5\linewidth]{graph-example.png}
\caption{Graph with 6 vertices, public domain figure taken from
https://en.wikipedia.org/wiki/Graph\_(discrete\_mathematics),
}
\end{figure}
A graph is simple if it has no self-loops or parallel edges. \\
The degree of a node $v$, denoted $deg(v)$, is the number of edges incident with it. \\
deg(1) = 2\\
deg(2) = 3\\
deg(3) = 2\\
deg(4) = 3\\
deg(5) = 3\\
deg(6) = 1\\
The number of nodes of odd degree is 4.\\
Theorem:
Every finite simple graph has an even number of vertices of
odd degree.
\vspace{.1in}
Proof: Every edge connects two vertices.
Hence, $SUM$ (the sum of
the degrees in a graph) is always even (Handshaking Theorem).
Let $ODD$ denote the set of vertices of odd degree and $EVEN$
denote the set of vertices of even degree.
$$SUM = \sum_{v \in ODD} deg(v) + \sum_{v \in EVEN} deg(v)$$
Since $SUM$ is even and $ \sum_{v \in EVEN} deg(v)$ is even,
$ \sum_{v \in ODD} deg(v)$ must also be even.
But then $|ODD|$ is even!
Q.E.D.
\section{Introduction to Logic}
Topics:
\begin{itemize}
\item
Logical variables (items that can be true or false)
\item
Propositions (statements that are true or false)
\item Predicates (statements that are true or false, but depend on the variables)
\item
Quantifiers (for all, there exists)
\item AND, OR, XOR
\item
If-then
\item
if-and-only-if
\item
Negation
\item Simplifying logical expressions
\item Conjunctive Normal Form
\item Tautologies
\item Satisfiability
\end{itemize}
\paragraph{Quantifiers: For all ($\forall$) and There Exists ($\exists$)}
A proposition is either True or False.
Which of these statements are True?
\begin{itemize}
\item $\forall x \in \emptyset, x>0$
\item $\exists x \in \emptyset, x>0$
\item $\exists x \in \emptyset$
\item All flying elephants eat pizza
\item There exists a flying elephant that eats pizza
\item There exists a flying elephant
\item No flying elephant eats pizza
\item For all flying elephants $x$, $x$ does not eat pizza
\end{itemize}
\paragraph{Order of quantifiers matters!}
We write ``s.t." for ``such that". Now, think about these two statements:
\begin{itemize}
\item $\forall x \in \mathbb{Z}~ \exists y \in \mathbb{Z} ~s.t.~x>y$
\item $\exists y \in \mathbb{Z} ~s.t.~\forall x \in \mathbb{Z}, ~x>y$
\end{itemize}
Is either of these statements true?
\paragraph{Predicates}
Some logical statements depend on variables. Consider:
\begin{itemize}
\item Let $P(x)$ denote the statement ``$x \in \mathbb{Z}$". Is $P(3)$ true? Is $P(\sqrt 7)$ true?
\item Let $Q(x,y)$ denote the statement ``$|x| > |y|$". Is $Q(\{3,5\},\mathbb{Z})$ true? Is $Q(\mathbb{Z},\emptyset)$ true?
\item Let $R(x)$ denote the statement ``$0 \in x$". Give an example of $x$ for which $R(x)$ is false.
\end{itemize}
\paragraph{Reading Mathematics}
Let $G=(V,E)$ denote a graph. \\
What do the following statements mean?
\begin{enumerate}
\item
$\forall v \in V, \exists y \in V s.t.~(v,y) \in E$
\item
$\exists y \in V ~s.t.~\forall v \in V\setminus\{y\}, ~ (v,y) \in E$
\item
$\forall \{a,b\} \subseteq V, (a,b) \in E$
\end{enumerate}
\vspace{.1in}
Give an example of a graph that satisfies each statement.\\
\vspace{.1in}
Find an example of graph that satisfies exactly one
of these statements. \\
\paragraph{AND, OR, and XOR}
Suppose $A$ and $B$ are propositions (and hence are either true or false). \\
$A ~AND~B$ (i.e., $A \land B$) is True if and only if {\em both} $A$ and $B$ are true. \\
$A ~OR ~B$ (i.e., $A \lor B$) is True if and only if {\em at least one of} $A$ and $B$ is true. \\
$A ~XOR ~B$ (i.e., $A \oplus B$) is True if and only if {\em exactly one of} $A$ and $B$ is true. \\
\vspace{.1in}
Examples:
\begin{itemize}
\item
All flying elephants eat pizza OR State Island is a borough in New York City
\item
All flying elephants eat pizza AND State Island is a borough in New York City
\item
All flying elephants eat pizza XOR State Island is a borough in New York City
\end{itemize}
\paragraph{If-then}
IF A THEN B (sometimes denoted $A \rightarrow B$, and worded as ``A implies B") is the same as:
\begin{itemize}
\item
whenever A is True, B must be True
\item
It isn't possible for B to be False if A is True
\end{itemize}
So, how would you show that ``IF A THEN B" is False?
\paragraph{If-then statements}
Key point: IF A THEN B is only False if A is True and B is False!
\vspace{.1in}
In other words, $$ A \rightarrow B \equiv \lnot (A \wedge \lnot B) \equiv \lnot A \vee B$$
where $\lnot X$ is the same as ``not X".
\paragraph{When is an IF-THEN statement true?}
\vspace{.1in}
Which of the following statements are true?
\begin{enumerate}
\item IF ($ 0 \in \emptyset$) THEN (Obama is still president)
\item IF ($0 \not \in \emptyset$) THEN (Obama is still president)
\item IF(all flying elephants eat pizza) THEN (Obama is still president)
\item IF(no flying elephants eat pizza) THEN (Obama is still president)
\item IF (some flying elephant eats pizza) THEN (Obama is still president)
\end{enumerate}
\paragraph{NOT X ($\lnot X$)}
$\lnot X$ is True if and only if X is False.
\vspace{.1in}
Can we simplify these?
\begin{itemize}
\item $\lnot$ (A OR B)
\item $\lnot$ (A AND B)
\item $\lnot$ (IF A THEN B)
\item $\lnot$ (A XOR B)
\end{itemize}
\paragraph{Logic exercises}
\begin{itemize}
\item
Simplifying logical expressions, and seeing when two
logical expressions are equivalent
\item
Determining if a logical expression can be {\em satisfied}
\item
Expressing English statements in logic
\end{itemize}
\paragraph{Simplifying logical expression}
Objectives:
\begin{itemize}
\item Remove all unnecessary parentheses
\item Remove all $\rightarrow$ or $\leftrightarrow$
\end{itemize}
Hence, you need to be able to simplify expressions like
$$\neg (a \rightarrow b) \vee (\neg b)$$
\paragraph{Simplifications (warm-up)}
When $A$ and $B$ are logical expressions, and you say $A \equiv B$,
you mean that they have the same truth values.
(You can also write this as $A \leftrightarrow B$.)
For example:
\begin{itemize}
\item $\neg \neg x \equiv x$ (obvious)
\item $x \vee (x \wedge y) \equiv x$
\begin{itemize}
\item[]
Similarly, you can write $x \vee (x \wedge y) \leftrightarrow x$.
In other words,
$x \vee (x \wedge y)$ is true if and only if $x$ is true.
\end{itemize}
\item $x \vee \neg x \equiv T$
\begin{itemize}
\item [] In other words,
$x \vee \neg x$ is always true, no matter what $x$ is.
\end{itemize}
\item $x \wedge \neg x \equiv F$
\begin{itemize}
\item []
In other words, $x \wedge \neg x$ is never true, no matter what $x$ is.
\end{itemize}
\end{itemize}
\paragraph{De Morgan's Laws}
\begin{itemize}
\item
Negation of $A \wedge B$:
$\neg A \vee \neg B$
This is also written as
$$\neg(A \wedge B) \equiv \neg A \vee \neg B$$
or as
$$\neg(A \wedge B) \leftrightarrow \neg A \vee \neg B$$
\item
Negation of $A \vee B$:
$\neg A \wedge \neg B$
This is also written as
$$ \neg(A \vee B) \equiv \neg A \wedge \neg B$$
or as
$$ \neg(A \vee B) \leftrightarrow \neg A \wedge \neg B$$
\end{itemize}
\paragraph{Negation, warm up with quantifiers}
\begin{itemize}
\item
Negation of $\forall x \in S, P(x)$:
\begin{itemize}
\item[]
$\exists x \in S$ s.t.~$\neg P(x)$
\end{itemize}
\item[]
Negation of $\exists x \in S$ s.t.~$P(x)$
\begin{itemize}
\item
$\forall x \in S, \neg P(x)$
\end{itemize}
\end{itemize}
Consider the expression
$$A \rightarrow B$$
To negate this, we have:
$$\neg(A \rightarrow B)$$
$$\equiv \neg(\neg A \vee B)$$
$$\equiv \neg \neg A \wedge \neg B$$
$$\equiv A \wedge \neg B$$
Our next example is a bit harder.
Negate: $(x \rightarrow y) \wedge \neg x$
First Solution:
$$\neg [(x \rightarrow y) \wedge \neg x]$$
$$\equiv \neg (x \rightarrow y) \vee \neg \neg x$$
$$\equiv \neg (\neg x \vee y) \vee x$$
$$\equiv (\neg \neg x \wedge \neg y) \vee x$$
$$\equiv (x \wedge \neg y) \vee x$$
$$\equiv x$$
Second Solution: We begin by simplifying the expression
above before negating it.
Note that
$$ x \rightarrow y \equiv \neg x \vee y$$
Hence
$$ (x \rightarrow y) \wedge \neg x$$
$$\equiv (\neg x \vee y) \wedge \neg x$$
$$\equiv (\neg x \wedge \neg x) \vee (y \wedge \neg x)$$
$$ \equiv \neg x \vee (y \wedge \neg x)$$
$$\equiv \neg x$$
Therefore,
$$ \neg [(x \rightarrow y) \wedge \neg x] \equiv \neg \neg x \equiv x$$
\paragraph{Simplifying a logical expression}
Simplify this:
\begin{itemize}
\item $\lnot$ (A OR B)
\end{itemize}
Solution: \\
$A~OR~B$ is true when at least one of $A$ or $B$ is true.
Hence it is false if and only if both $A$ and $B$ are false.
In other words:
$$\lnot (A~OR~ B) \equiv \lnot A~AND~\lnot B$$
Simplify this:
\begin{itemize}
\item $\lnot$ (A AND B)
\end{itemize}
Solution:
$A~AND~B$ is true when both $A$ or $B$ are true.
Hence it is false if and only if at least one of $A$ or $B$ is false.
In other words:
$$\lnot (A~AND~ B) \equiv \lnot A~OR~\lnot B$$
Note the effect of $\lnot$: AND changes to OR and vice-versa, and $X$ changes to $\lnot X$.
\paragraph{Classroom exercise}
Simplify one or both:
\begin{itemize}
\item
$\lnot (A ~OR \lnot B)$
\item
$\lnot A \rightarrow A$
\end{itemize}
\paragraph{Satisfiability}
Some logical expressions can never be true, some are
always true, and some depend on the values of their
variables.
{\bf T} and {\bf F} refer
to the logical constants True
and False, respectively.
Examples:
\begin{enumerate}
\item $A \vee \neg A$ (always true)
\item $A \wedge \neg A$ (never true)
\item $A \vee B$ (sometimes true and sometimes false, depends on $A$ and $B$)
\item $A \wedge F$ (never true)
\end{enumerate}
Statements that are
always true are called {\em tautologies}.
Statements that can be true (or are always true) are
said to be {\em satisfiable}, and otherwise they
are said to be {\em unsatisfiable}.
Exercise:
For each of the following expressions,
determine if it is satisfiable or not
satisfiable. If it is
satisfiable, determine if it is a tautology.
\begin{enumerate}
\item
$(A \wedge B) \rightarrow A$ \\
(Answer: tautology)
\item
$(A \wedge B) \rightarrow \neg A$ \\
(Answer: satisfiable (A = B = {\bf F})
but not a tautology (A = B = {\bf T}))
\item
$(A \wedge B) \leftrightarrow A$ \\
(Answer: satisfiable (A = B = {\bf T}) but not a tautology
(A = {\bf T} and B = {\bf F})
\item
$(A \rightarrow B) \wedge A \wedge \neg B$ \\
(Answer: not satisfiable, so never true)
\item
$A \rightarrow \neg A $ \\
(Answer: satisfiable (A = {\bf F}) but
not a tautology (A = {\bf T}))
\end{enumerate}
\paragraph{Truth Tables}
We (sometimes) use truth tables to check our
analyses. Here's an example of a very simple
truth table
for the expression $A \wedge B$:
\begin{center}
\begin{tabular}{|c|c||c|}
\hline
$A$ & $B$ & $A \wedge B$ \\
\hline
\hline
T & T & T \\
\hline
T & F & F \\
\hline
F & T & F \\
\hline
F & F & F \\
\hline
\end{tabular}
\end{center}
\paragraph{A more complicated truth table}
Consider the expression $[(A \rightarrow B) \wedge \neg B ] \rightarrow A$.
Is this always true? Sometimes true and sometimes false?
Always false?
Let's use a truth table to answer this.
\begin{center}
\begin{tabular}{|c|c||c|c|}
\hline
$A$ & $B$ & $(A \rightarrow B) \wedge \neg B$ & $[(A \rightarrow B) \wedge \neg B ] \rightarrow A$ \\
\hline
\hline
T & T & F & T \\
\hline
T & F & F & T\\
\hline
F & T & F & T\\
\hline
F & F & T & F\\
\hline
\end{tabular}
\end{center}
So the answer is that it is sometimes true and sometimes false.
Note that we also showed
$[(A \rightarrow B) \wedge \neg B ] \rightarrow A \equiv A \vee B$.
\paragraph{Conjunctive Normal Form (CNF)}
A logical expression of the form
$$A_1 \vee A_2 \vee A_3 \vee ... \vee A_k$$
where the $A_i$ are literals (statement letters or
their negations)
is called a {\em disjunctive clause}.
Then
$$C_1 \wedge C_2 \wedge C_3 \wedge \ldots \wedge C_p,$$
where each $C_i$ is a disjunctive clause, is
said to be in {\em conjunctive normal form}, or CNF.
CNF is very popular in computer science!
\paragraph{Two-satisfiability}
A special case of CNF is where
each clause has at most
two literals!
That is, expression
that are written in the
form $(A_1 \vee B_1) \wedge (A_2 \vee B_2) \wedge \ldots (A_k \vee B_k)$.
Which of the following CNF expressions are satisfiable?
\begin{enumerate}
\item
$(x \vee y) \wedge (\neg x \vee \neg y)$
\item
$(x \vee y) \wedge (\neg x \vee \neg y) \wedge x$
\item
$(x \vee y) \wedge (\neg x \vee \neg y) \wedge x \wedge y $
\item
$(x \vee y) \wedge (\neg x \vee \neg z) \wedge (\neg y \vee z) \wedge
(\neg x \vee z)$
\item $(\neg x \vee y) \wedge (\neg y \vee z) \wedge (\neg z \vee x) \wedge (x \vee z)$
\end{enumerate}
\paragraph{A logic puzzle}
In a particular village in the deep valleys in some far-away country, everyone is either a liar (and never tells the truth) or a truth-teller (and never lies). \\
You are in this village and meet Henry and Allen. \\
\begin{itemize}
\item
Henry says ``Allen is a truth teller"
\item
Allen says ``Only one of us is a truth teller"
\end{itemize}
Is either a truth teller? If so, who?
\end{document}