Week 4 at a glance

We will be learning and practicing to:

TODO:

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.

Week 4 Monday: Conditionals and Logical Equivalence

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

Conjunction \(p \land q\) can be said in English as

Exclusive or \(p \oplus q\) can be said in English as

Disjunction \(p \lor q\) can be said in English as

Conditional \(p \to q\) can be said in English as

2

Biconditional

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.

  1. Translate to symbolic compound propositions

  2. Look for some truth assignment to the propositional variables for which all the compound propositions output \(T\)

Week 4 Wednesday: Predicates and Quantifiers

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?

Week 4 Friday: Evaluating Nested Quantifiers

New predicates from old

  1. Define the new predicate with domain \(S \times B\) and rule \[basecount(~(s,b)~) = 3\] Example domain element where predicate is \(T\):

  2. Define the new predicate with domain \(S \times \mathbb{N}\) and rule \[basecount(~(s,\texttt{A})~) = n\] Example domain element where predicate is \(T\):

  3. 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\):

  4. 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

Review Quiz

  1. Logical equivalence

    For each of the following propositions, indicate exactly one of:

    1. \((p \leftrightarrow q) \oplus (p \land q)\)

    2. \((p \to q) \vee (q \to p)\)

    3. \((p \to q) \land (q \to p)\)

    4. \(\lnot (p \to q)\)

  2. Translating propositional logic

    1. Express each of the following sentences as compound propositions, using the given propositions.

      1. “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

        1. \(t \to (c \land g)\)

        2. \((c \land g) \to t\)

        3. \((c \land g) \leftrightarrow t\)

        4. \(t \oplus (c \land g)\)

      2. “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

        1. \(c \land \lnot g \land u\)

        2. \((c \land \lnot g) \lor u\)

        3. \((c \land \lnot g) \oplus u\)

        4. \((c \land \lnot g) \to u\)

        5. \(u \to (c \land \lnot g)\)

        6. \(u \leftrightarrow (c \land \lnot g)\)

    2. 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.

      1. 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

        1. \[\begin{aligned} &\neg M \to N \\ & \neg D \to M \\ & D \to N \end{aligned}\]

        2. \[\begin{aligned} &M \to \neg N \\ & \neg D \wedge M \\ & N \to D \end{aligned}\]

        3. \[\begin{aligned} &M \to N \\ & M \to \neg D \\ & \neg N \to \neg D \end{aligned}\]

      2. 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

        1. \[\begin{aligned} &T \to C \\& \neg T \to \neg C \end{aligned}\]

        2. \[\begin{aligned} &T \wedge C \\ & \neg T \wedge \neg C \end{aligned}\]

        3. \[\begin{aligned} &T \to \neg T \\ & C \to \neg C \end{aligned}\]

      3. 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

        1. \[\begin{aligned} &\neg (P \wedge C) \to \neg S \\ & C \to H \\ & W \wedge H \\ & W \to \neg P \\ & S \end{aligned}\]

        2. \[\begin{aligned} &(P \wedge C) \to S \\ & C \to H\\ & W \to H \\ & W \to P \\ & S \end{aligned}\]

        3. \[\begin{aligned} & S \to (P \wedge C) \\ & C \to H\\ & H \to W \\ & W \to \neg P \\ & S \end{aligned}\]

  3. Evaluating predicates


    1. 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.)

      1. \(\left( \forall x ~V(x) \right) \lor \left( \forall x ~N(x) \right)\)

      2. \(\left( \exists x ~V(x) \right) \land \left( \exists x~N(x) \right) \land \left( \exists x~Mystery(x)\right)\)

      3. \(\exists x ~(~V(x) \land N(x) \land Mystery(x)~)\)

      4. \(\forall x ~(~V(x) \oplus N(x)~)\)

      5. \(\forall x ~(~Mystery(x) \to V(x)~)\)


    2. 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.

      1. What is \(E(110)\)?

      2. Why is \(L(00)\) undefined?

        1. Because the domain of \(L\) is infinite

        2. Because \(00\) does not have \(1\) in the leftmost position

        3. Because \(00\) has length 2, not length 3

        4. Because \((00)_{2,2} = 0\) which is less than \(3\)

      3. Is there a bitstring of width (where width is the number of bits) \(6\) at which \(M(x)\) evaluates to \(T\)?


    3. 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.)

      1. \(F_\texttt{A}( \texttt{A}\texttt{A})\)

      2. \(F_\texttt{A}( \texttt{A}\texttt{C})\)

      3. \(F_\texttt{A}( \texttt{A}\texttt{G})\)

      4. \(F_\texttt{A}( \texttt{A}\texttt{U})\)

      5. \(F_\texttt{A}( \texttt{C}\texttt{A})\)

      6. \(F_\texttt{A}( \texttt{C}\texttt{C})\)

      7. \(F_\texttt{A}( \texttt{C}\texttt{G})\)

      8. \(F_\texttt{A}( \texttt{C}\texttt{U})\)

  4. Evaluating nested predicates


    1. 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.)

      1. \(\exists s \in S ~\exists n \in \mathbb{Z}^+ ~L(~(s,n)~)\)

      2. \(\exists s \in S ~\forall n \in \mathbb{Z}^+ ~L(~(s,n)~)\)

      3. \(\forall n \in \mathbb{Z}^+ ~\exists s \in S ~L(~(s,n)~)\)

      4. \(\forall s \in S ~\exists n \in \mathbb{Z}^+ ~L(~(s,n)~)\)

      5. \(\exists n \in \mathbb{Z}^+ ~\forall s \in S ~L(~(s,n)~)\)


    2. 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.

      1. \(\forall s \in S ~\exists n \in \mathbb{N} ~\forall b \in B ~basecount(~(s,b)~) = n\)

      2. \(\forall s \in S ~\forall b \in B ~\exists n \in \mathbb{N} ~basecount(~(s,b)~) = n\)

      3. \(\forall s \in S ~\forall n \in \mathbb{N} ~\exists b \in B ~basecount(~(s,b)~) = n\)

      4. \(\forall b \in B ~\forall n \in \mathbb{N} ~\exists s \in S ~basecount(~(s,b)~) = n\)

      5. \(\forall n \in \mathbb{N} ~\forall b \in B ~\exists s \in S ~basecount(~(s,b)~) = n\)

      1. For each RNA strand and each possible base, the number of that base in that strand is a nonnegative integer.

      2. For each RNA strand and each nonnegative integer, there is a base that occurs this many times in this strand.

      3. Every RNA strand has the same number of each base, and that number is a nonnegative integer.

      4. For every given nonnegative integer, there is a strand where each possible base appears the given number of times.

      5. 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.


  1. Henry Ford↩︎