Translate between different representations to illustrate a concept.
Translating between symbolic and English versions of statements using precise mathematical language
Translating between truth tables (tables of values) and compound propositions
Use precise notation to encode meaning and present arguments concisely and clearly
Listing the truth tables of atomic boolean functions (and, or, xor, not, if, iff)
Defining functions, predicates, and binary relations using multiple representations
Know, select and apply appropriate computing knowledge and problem-solving techniques. Reason about computation and systems. Use mathematical techniques to solve problems. Determine appropriate conceptual tools to apply to new situations. Know when tools do not apply and try different approaches. Critically analyze and evaluate candidate solutions.
Evaluating compound propositions
Judging logical equivalence of compound propositions using symbolic manipulation with known equivalences, including DeMorgan’s Law
Writing the converse, contrapositive, and inverse of a given conditional statement
Determining what evidence is required to establish that a quantified statement is true or false
Evaluating quantified statements about finite and infinite domains
Schedule your Test 1 Attempt 1, Test 2 Attempt 1 times at PrairieTest (http://us.prairietest.com)
You must present a physical university-issued or government-issued ID. Copies, photos, or digital IDs are not accepted, and students without verifiable ID will not be permitted to test.
Pockets must be empty upon entry. Students may bring only their ID and a pen or pencil into the testing center.
Review quizzes based on Week 2 and Week 3 class material (due Monday 01/26/2026)
Homework 2 due on Gradescope https://www.gradescope.com/ (Thursday 01/29/2026)
Start reviewing for Test 1: Test1 Attempt 1 is next week. The test covers material in Weeks 1 through Week 5, corresponding to RQ1, RQ2, RQ3, and RQ4. To study for the exam, we recommend reviewing class notes (e.g. annotations linked on the class website, supplementary videos from the class website) and working multiple variants of review quiz questions. You could also find that reviewing homework (and its posted sample solutions)and extra examples (in lecture notes and discussion examples) and getting feedback (office hours and Piazza) is helpful.
(Some) logical equivalences
Can replace \(p\) and \(q\) with any compound proposition
| \(\lnot ( \lnot p) \equiv p\) | Double negation | |
| \(p \lor q \equiv q \lor p\) | \(p \land q \equiv q \land p\) | Commutativity Ordering of terms |
| \((p \lor q) \lor r \equiv p \lor (q \lor r)\) | \((p \land q) \land r \equiv p \land (q \land r)\) | Associativity Grouping of terms |
| \(p \land F \equiv F\) \(p \lor T \equiv T\) | \(p \land T \equiv p\) \(p \lor F \equiv p\) | Domination aka short circuit evaluation |
| \(\lnot (p \land q) \equiv \lnot p \lor \lnot q\) | \(\lnot (p \lor q) \equiv \lnot p \land\lnot q\) | DeMorgan’s Laws |
| Input | Output | |||||
| Conjunction | Exclusive or | Disjunction | Conditional | Biconditional | ||
| \(p\) | \(q\) | \(p \wedge q\) | \(p \oplus q\) | \(p \vee q\) | \(p \to q\) | \(p \leftrightarrow q\) |
| \(T\) | \(T\) | \(T\) | \(F\) | \(T\) | \(T\) | \(T\) |
| \(T\) | \(F\) | \(F\) | \(T\) | \(T\) | \(F\) | \(F\) |
| \(F\) | \(T\) | \(F\) | \(T\) | \(T\) | \(T\) | \(F\) |
| \(F\) | \(F\) | \(F\) | \(F\) | \(F\) | \(T\) | \(T\) |
| “\(p\) and \(q\)” | “\(p\) xor \(q\)” | “\(p\) or \(q\)” | “if \(p\) then \(q\)” | “\(p\) if and only if \(q\)” | ||
The only way to make the conditional statement \(p \to q\) false is to
| The hypothesis of \(p \to q\) is | The antecedent of \(p \to q\) is | ||
| The conclusion of \(p \to q\) is | The consequent of \(p \to q\) is | ||
The converse of \(p \to q\) is
The inverse of \(p \to q\) is
The contrapositive of \(p \to q\) is
We can use a recursive definition to describe all compound propositions that use propositional variables from a specified collection. Here’s the definition for all compound propositions whose propositional variables are in \(\{p, q\}\).
\[\begin{array}{ll} \textrm{Basis Step: } & p \textrm{ and } q \textrm{ are each a compound proposition} \\ \textrm{Recursive Step: } & \textrm{If } x \textrm{ is a compound proposition then so is } (\lnot x) \textrm{ and if } \\ & x \textrm{ and } y \textrm{ are both compound propositions then so is each of }\\ &(x \land y), (x \oplus y), (x \lor y), (x \to y), (x \leftrightarrow y) \end{array}\]
Order of operations (Precedence) for logical operators:
Negation, then conjunction / disjunction, then conditional / biconditionals.
Example: \(\lnot p \lor \lnot q\) means \((\lnot p) \lor (\lnot q)\).
(Some) logical equivalences
| \(p \to q \equiv \lnot p \lor q\) | ||
| \(p \to q \equiv \lnot q \to \lnot p\) | Contrapositive | |
| \(\lnot (p \to q) \equiv p\land \lnot q\) | ||
| \(\lnot( p \leftrightarrow q) \equiv p \oplus q\) | ||
| \(p \leftrightarrow q \equiv q \leftrightarrow p\) | ||
Extra examples:
\(p \leftrightarrow q\) is not logically equivalent to \(p \land q\) because
\(p \to q\) is not logically equivalent to \(q \to p\) because
Common ways to express logical operators in English:
Negation \(\lnot p\) can be said in English as
Not \(p\).
It’s not the case that \(p\).
\(p\) is false.
Conjunction \(p \land q\) can be said in English as
\(p\) and \(q\).
Both \(p\) and \(q\) are true.
\(p\) but \(q\).
Exclusive or \(p \oplus q\) can be said in English as
\(p\) or \(q\), but not both.
Exactly one of \(p\) and \(q\) is true.
Disjunction \(p \lor q\) can be said in English as
\(p\) or \(q\), or both.
\(p\) or \(q\) (inclusive).
At least one of \(p\) and \(q\) is true.
Conditional \(p \to q\) can be said in English as
2
if \(p\), then \(q\).
\(p\) is sufficient for \(q\).
\(q\) when \(p\).
\(q\) whenever \(p\).
\(p\) implies \(q\).
\(q\) follows from \(p\).
\(q\) is necessary for \(p\).
\(p\) only if \(q\).
Biconditional
\(p\) if and only if \(q\).
\(p\) iff \(q\).
If \(p\) then \(q\), and conversely.
\(p\) is necessary and sufficient for \(q\).
Translation: Express each of the following sentences as compound propositions, using the given propositions.
2 “A sufficient condition for the warranty to be good is that you bought the computer less than a year ago" \[\begin{align*} w &\text{ is ``the warranty is good"} \\ b &\text{ is ``you bought the computer less than a year ago"} \\ \end{align*}\]
2 “Whenever the message was sent from an unknown system, it is scanned for viruses." \[\begin{align*} s &\text{ is ``The message is scanned for viruses"} \\ u &\text{ is ``The message was sent from an unknown system"} \\ \end{align*}\]
2 “I will complete my to-do list only if I put a reminder in my calendar" \[\begin{align*} d &\text{ is ``I will complete my to-do list"} \\ c &\text{ is ``I put a reminder in my calendar"} \\ \end{align*}\]
Definition: A collection of compound propositions is called consistent if there is an assignment of truth values to the propositional variables that makes each of the compound propositions true.
Consistency:
Whenever the system software is being upgraded, users cannot access the file system. If users can access the file system, then they can save new files. If users cannot save new files, then the system software is not being upgraded.
Translate to symbolic compound propositions
Look for some truth assignment to the propositional variables for which all the compound propositions output \(T\)
Definition: A predicate is a function from a given set (domain) to \(\{T,F\}\).
A predicate can be applied, or evaluated at, an element of the domain.
Usually, a predicate describes a property that domain elements may or may not have.
Two predicates over the same domain are equivalent means they evaluate to the same truth values for all possible assignments of domain elements to the input. In other words, they are equivalent means that they are equal as functions.
To define a predicate, we must specify its domain and its value at each domain element. The rule assigning truth values to domain elements can be specified using a formula, English description, in a table (if the domain is finite), or recursively (if the domain is recursively defined).
| Input | Output | ||
| \(V(x)\) | \(N(x)\) | \(Mystery(x)\) | |
| \(x\) | \([x]_{2c,3} > 0\) | \([x]_{2c,3} < 0\) | |
| \(000\) | \(F\) | \(T\) | |
| \(001\) | \(T\) | \(T\) | |
| \(010\) | \(T\) | \(T\) | |
| \(011\) | \(T\) | \(F\) | |
| \(100\) | \(F\) | \(F\) | |
| \(101\) | \(F\) | \(T\) | |
| \(110\) | \(F\) | \(F\) | |
| \(111\) | \(F\) | \(T\) | |
The domain for each of the predicates \(V(x)\), \(N(x)\), \(Mystery(x)\) is .
Fill in the table of values for the predicate \(N(x)\) based on the formula given.
Definition: The truth set of a predicate is the collection of all elements in its domain where the predicate evaluates to \(T\).
Notice that specifying the domain and the truth set is sufficient for defining a predicate.
The truth set for the predicate \(V(x)\) is \(\underline{\phantom{\{ x ~\mid~ V(x) = T\} = \{ 001, 010, 011 \}}}\).
The truth set for the predicate \(N(x)\) is \(\underline{\phantom{\{ x ~\mid~ N(x) = T\} = \{ 101, 111 \}}}\).
The truth set for the predicate \(Mystery(x)\) is \(\underline{\phantom{\{ x ~\mid~ Mystery(x) = T\} = \{ 000, 001, 010, 101, 111 \}}}\).
The universal quantification of predicate \(P(x)\) over domain \(U\) is the statement “\(P(x)\) for all values of \(x\) in the domain \(U\)” and is written \(\forall x P(x)\) or \(\forall x \in U ~P(x)\). When the domain is finite, universal quantification over the domain is equivalent to iterated conjunction (ands).
The existential quantification of predicate \(P(x)\) over domain \(U\) is the statement “There exists an element \(x\) in the domain \(U\) such that \(P(x)\)” and is written \(\exists x P(x)\) for \(\exists x \in U ~P(x)\). When the domain is finite, existential quantification over the domain is equivalent to iterated disjunction (ors).
An element for which \(P(x) = F\) is called a counterexample of \(\forall x P(x)\).
An element for which \(P(x) = T\) is called a witness of \(\exists x P(x)\).
Statements involving predicates and quantifiers are logically equivalent means they have the same truth value no matter which predicates (domains and functions) are substituted in.
Quantifier version of De Morgan’s laws: \(\boxed{\neg \forall x P(x) ~\equiv~ \exists x \left( \neg P(x) \right)}\) \(\boxed{\neg \exists x Q(x) ~\equiv~ \forall x \left( \neg Q(x) \right)}\)
Examples of quantifications using \(V(x), N(x), Mystery(x)\):
True or False: \(\exists x~ (~V(x) \land N(x)~)\)
True or False: \(\forall x~ (~V(x) \to N(x)~)\)
True or False: \(\exists x~ (~N(x) \leftrightarrow Mystery(x)~)\)
Rewrite \(\lnot \forall x~(~V(x) \oplus Mystery(x)~)\) into a logical equivalent statement.
Notice that these are examples where the predicates have finite domain. How would we evaluate quantifications where the domain may be infinite?
Recall the definitions: The set of RNA strands \(S\) is defined (recursively) by: \[\begin{array}{ll} \textrm{Basis Step: } & \texttt{A}\in S, \texttt{C}\in S, \texttt{U}\in S, \texttt{G}\in S \\ \textrm{Recursive Step: } & \textrm{If } s \in S\textrm{ and }b \in B \textrm{, then }sb \in S \end{array}\] where \(sb\) is string concatenation.
The function rnalen that computes the length of RNA strands in \(S\) is defined recursively by: \[\begin{array}{llll} & & \textit{rnalen} : S & \to \mathbb{Z}^+ \\ \textrm{Basis Step:} & \textrm{If } b \in B\textrm{ then } & \textit{rnalen}(b) & = 1 \\ \textrm{Recursive Step:} & \textrm{If } s \in S\textrm{ and }b \in B\textrm{, then } & \textit{rnalen}(sb) & = 1 + \textit{rnalen}(s) \end{array}\]
The function basecount that computes the number of a given base \(b\) appearing in a RNA strand \(s\) is defined recursively by: \[\begin{array}{llll} & & \textit{basecount} : S \times B & \to \mathbb{N} \\ \textrm{Basis Step:} & \textrm{If } b_1 \in B, b_2 \in B & \textit{basecount}(~(b_1, b_2)~) & = \begin{cases} 1 & \textrm{when } b_1 = b_2 \\ 0 & \textrm{when } b_1 \neq b_2 \\ \end{cases} \\ \textrm{Recursive Step:} & \textrm{If } s \in S, b_1 \in B, b_2 \in B &\textit{basecount}(~(s b_1, b_2)~) & = \begin{cases} 1 + \textit{basecount}(~(s, b_2)~) & \textrm{when } b_1 = b_2 \\ \textit{basecount}(~(s, b_2)~) & \textrm{when } b_1 \neq b_2 \\ \end{cases} \end{array}\]
Example predicates on \(S\), the set of RNA strands (an infinite set)
\(H: S \to \{T, F\}\) where \(H(s) = T\) for all \(s\).
Truth set of \(H\) is
\(L_{\texttt{A}}: S \to \{T, F\}\) defined recursively by:
Basis step: \(L_{\texttt{A}}(\texttt{A}) = T\), \(L_{\texttt{A}}(\texttt{C}) = L_{\texttt{A}}(\texttt{G}) = L_{\texttt{A}}(\texttt{U}) = F\)
Recursive step: If \(s \in S\) and \(b \in B\), then \(L_{\texttt{A}}(sb) = L_{\texttt{A}}(s)\).
Example where \(L_{\texttt{A}}\) evaluates to \(T\) is
Example where \(L_{\texttt{A}}\) evaluates to \(F\) is
Using functions to define predicates:
Example where \(L\) evaluates to \(T\): \(\underline{\phantom{(\texttt{A}, 1)\hspace{1in}}}\) Why?
Example where \(BC\) evaluates to \(T\): \(\underline{\phantom{(\texttt{A}, \texttt{A}1)\hspace{1in}}}\) Why?
Example where \(L\) evaluates to \(F\): \(\underline{\phantom{(\texttt{A}, 2)\hspace{1in}}}\) Why?
Example where \(BC\) evaluates to \(F\): \(\underline{\phantom{(\texttt{A}, \texttt{C}, 1)\hspace{1in}}}\) Why?
New predicates from old
Define the new predicate with
domain \(S \times B\) and rule \[basecount(~(s,b)~) = 3\] Example domain
element where predicate is \(T\):
Define the new predicate with
domain \(S \times \mathbb{N}\) and rule
\[basecount(~(s,\texttt{A})~) = n\]
Example domain element where predicate is \(T\):
Define the new predicate with
domain \(S \times B\) and rule \[\exists n \in \mathbb{N} ~(basecount(~(s,b)~) =
n)\] Example domain element where predicate is \(T\):
Define the new predicate with
domain \(S\) and rule \[\forall b \in B ~(basecount(~(s,b)~) =
1)\] Example domain element where predicate is \(T\):
Notation: for a predicate \(P\) with domain \(X_1 \times \cdots \times X_n\) and a \(n\)-tuple \((x_1, \ldots, x_n)\) with each \(x_i \in X\), we can write \(P(x_1, \ldots, x_n)\) to mean \(P( ~(x_1, \ldots, x_n)~)\).
Nested quantifiers
Alternating nested quantifiers