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
Review quiz based on class material each day (due Friday April 26, 2024)
Start reviewing for Test 1, in class next week on Friday May 3, 2024.
| 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
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 |
| \(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\).
\(p\) is sufficient for \(q\).
\(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{aligned} w &\text{ is ``the warranty is good"} \\ b &\text{ is ``you bought the computer less than a year ago"} \\ \end{aligned}\]
2 “Whenever the message was sent from an unknown system, it is scanned for viruses." \[\begin{aligned} s &\text{ is ``The message is scanned for viruses"} \\ u &\text{ is ``The message was sent from an unknown system"} \\ \end{aligned}\]
2 “I will complete my to-do list only if I put a reminder in my calendar" \[\begin{aligned} d &\text{ is ``I will complete my to-do list"} \\ c &\text{ is ``I put a reminder in my calendar"} \\ \end{aligned}\]
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
\(F_{\texttt{A}}: S \to \{T, F\}\) defined recursively by:
Basis step: \(F_{\texttt{A}}(\texttt{A}) = T\), \(F_{\texttt{A}}(\texttt{C}) = F_{\texttt{A}}(\texttt{G}) = F_{\texttt{A}}(\texttt{U}) = F\)
Recursive step: If \(s \in S\) and \(b \in B\), then \(F_{\texttt{A}}(sb) = F_{\texttt{A}}(s)\).
Example where \(F_{\texttt{A}}\) evaluates to \(T\) is
Example where \(F_{\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
Logical equivalence
For each of the following propositions, indicate exactly one of:
There is no assignment of truth values to its variables that makes it true,
There is exactly one assignment of truth values to its variables that makes it true, or
There are exactly two assignments of truth values to its variables that make it true, or
There are exactly three assignments of truth values to its variables that make it true, or
All assignments of truth values to its variables make it true.
\((p \leftrightarrow q) \oplus (p \land q)\)
\((p \to q) \vee (q \to p)\)
\((p \to q) \land (q \to p)\)
\(\lnot (p \to q)\)
Translating propositional logic
Express each of the following sentences as compound propositions, using the given propositions.
“If you try to run Zoom while your computer is running many applications, the video is likely to be choppy and laggy." \(t\) is “you run Zoom while your computer is running many applications”, \(c\) is “the video is likely to be choppy”, \(g\) is “the video is likely to be laggy”
2
\(t \to (c \land g)\)
\((c \land g) \to t\)
\((c \land g) \leftrightarrow t\)
\(t \oplus (c \land g)\)
“To connect wirelessly on campus without logging in you need to use the UCSD-Guest network." \(c\) is “connect wirelessly on campus”, \(g\) is “logging in”, and \(u\) is “use UCSD-Guest network”.
2
\(c \land \lnot g \land u\)
\((c \land \lnot g) \lor u\)
\((c \land \lnot g) \oplus u\)
\((c \land \lnot g) \to u\)
\(u \to (c \land \lnot g)\)
\(u \leftrightarrow (c \land \lnot g)\)
For each of the following system specifications, identify the compound propositions that give their translations to logic and then determine if the translated collection of compound propositions is consistent.
Specification: If the computer is out of memory, then network connectivity is unreliable. No disk errors can occur when the computer is out of memory. Disk errors only occur when network connectivity is unreliable.
Translation: \(M =\) “the computer is out of memory"; \(N =\) “network connectivity is unreliable"; \(D =\) “disk errors can occur".
3
\[\begin{aligned} &\neg M \to N \\ & \neg D \to M \\ & D \to N \end{aligned}\]
\[\begin{aligned} &M \to \neg N \\ & \neg D \wedge M \\ & N \to D \end{aligned}\]
\[\begin{aligned} &M \to N \\ & M \to \neg D \\ & \neg N \to \neg D \end{aligned}\]
Specification: Whether you think you can, or you think you can’t - you’re right. 1
Translation: \(T =\) “you think you can"; \(C =\) “you can".
3
\[\begin{aligned} &T \to C \\& \neg T \to \neg C \end{aligned}\]
\[\begin{aligned} &T \wedge C \\ & \neg T \wedge \neg C \end{aligned}\]
\[\begin{aligned} &T \to \neg T \\ & C \to \neg C \end{aligned}\]
Specification: A secure password must be private and complicated. If a password is complicated then it will be hard to remember. People write down hard-to-remember passwords. If a password is written down, it’s not private. The password is secure.
Translation: \(S =\) “the password is secure"; \(P =\) “the password is private"; \(C =\) “the password is complicated"; \(H =\) “the password is hard to remember"; \(W =\) “the password is written down".
3
\[\begin{aligned} &\neg (P \wedge C) \to \neg S \\ & C \to H \\ & W \wedge H \\ & W \to \neg P \\ & S \end{aligned}\]
\[\begin{aligned} &(P \wedge C) \to S \\ & C \to H\\ & W \to H \\ & W \to P \\ & S \end{aligned}\]
\[\begin{aligned} & S \to (P \wedge C) \\ & C \to H\\ & H \to W \\ & W \to \neg P \\ & S \end{aligned}\]
Evaluating predicates
Recall the predicates \(V(x)\), \(N(x)\), and \(Mystery(x)\) on domain \(\{000,001,010,011,100,101,110,111\}\) from class. Which of the following is true? (Select all and only that apply.)
\(\left( \forall x ~V(x) \right) \lor \left( \forall x ~N(x) \right)\)
\(\left( \exists x ~V(x) \right) \land \left( \exists x~N(x) \right) \land \left( \exists x~Mystery(x)\right)\)
\(\exists x ~(~V(x) \land N(x) \land Mystery(x)~)\)
\(\forall x ~(~V(x) \oplus N(x)~)\)
\(\forall x ~(~Mystery(x) \to V(x)~)\)
Consider the following predicates, each of which has as its domain the set of all bitstrings whose leftmost bit is \(1\)
\(E(x)\) is \(T\) exactly when \((x)_{2}\) is even, and is \(F\) otherwise
\(L(x)\) is \(T\) exactly when \((x)_2 < 3\), and is \(F\) otherwise
\(M(x)\) is \(T\) exactly when \((x)_2 > 256\) and is \(F\) otherwise.
What is \(E(110)\)?
Why is \(L(00)\) undefined?
Because the domain of \(L\) is infinite
Because \(00\) does not have \(1\) in the leftmost position
Because \(00\) has length 2, not length 3
Because \((00)_{2,2} = 0\) which is less than \(3\)
Is there a bitstring of width (where width is the number of bits) \(6\) at which \(M(x)\) evaluates to \(T\)?
For this question, we will use the following predicate.
\(F_{\texttt{A}}\) with domain \(S\) is defined recursively by:
Basis step: \(F_{\texttt{A}}(\texttt{A}) = T\), \(F_{\texttt{A}}(\texttt{C}) = F_{\texttt{A}}(\texttt{G}) = F_{\texttt{A}}(\texttt{U}) = F\)
Recursive step: If \(s \in S\) and \(b \in B\), then \(F_{\texttt{A}}(sb) = F_{\texttt{A}}(s)\)
Which of the following is true? (Select all and only that apply.)
\(F_\texttt{A}( \texttt{A}\texttt{A})\)
\(F_\texttt{A}( \texttt{A}\texttt{C})\)
\(F_\texttt{A}( \texttt{A}\texttt{G})\)
\(F_\texttt{A}( \texttt{A}\texttt{U})\)
\(F_\texttt{A}( \texttt{C}\texttt{A})\)
\(F_\texttt{A}( \texttt{C}\texttt{C})\)
\(F_\texttt{A}( \texttt{C}\texttt{G})\)
\(F_\texttt{A}( \texttt{C}\texttt{U})\)
Evaluating nested predicates
Recall the predicate \(L\) with domain \(S \times \mathbb{Z}^+\) from class, \(L(~(s,n)~)\) means \(rnalen(s) = n\). Which of the following is true? (Select all and only that apply.)
\(\exists s \in S ~\exists n \in \mathbb{Z}^+ ~L(~(s,n)~)\)
\(\exists s \in S ~\forall n \in \mathbb{Z}^+ ~L(~(s,n)~)\)
\(\forall n \in \mathbb{Z}^+ ~\exists s \in S ~L(~(s,n)~)\)
\(\forall s \in S ~\exists n \in \mathbb{Z}^+ ~L(~(s,n)~)\)
\(\exists n \in \mathbb{Z}^+ ~\forall s \in S ~L(~(s,n)~)\)
Recall the predicate \(BC\) with domain \(S \times B \times \mathbb{N}\) from class, \(BC(~(s,b,n)~)\) means \(basecount(~(s,b)~) = n\). Match each sentence to its English translation, or select none of the above.
\(\forall s \in S ~\exists n \in \mathbb{N} ~\forall b \in B ~basecount(~(s,b)~) = n\)
\(\forall s \in S ~\forall b \in B ~\exists n \in \mathbb{N} ~basecount(~(s,b)~) = n\)
\(\forall s \in S ~\forall n \in \mathbb{N} ~\exists b \in B ~basecount(~(s,b)~) = n\)
\(\forall b \in B ~\forall n \in \mathbb{N} ~\exists s \in S ~basecount(~(s,b)~) = n\)
\(\forall n \in \mathbb{N} ~\forall b \in B ~\exists s \in S ~basecount(~(s,b)~) = n\)
For each RNA strand and each possible base, the number of that base in that strand is a nonnegative integer.
For each RNA strand and each nonnegative integer, there is a base that occurs this many times in this strand.
Every RNA strand has the same number of each base, and that number is a nonnegative integer.
For every given nonnegative integer, there is a strand where each possible base appears the given number of times.
For every given base and nonnegative integer, there is an RNA strand that has this base occurring this many times.
Challenge: Express symbolically
There are (at least) two different RNA strands that have the same number of \(\texttt{A}\)s.
Henry Ford↩︎