10.16 Propositions and Quantifiers

Exercise 1 Workshop 1 - BCM.pdf

“If it rains, Abel takes an umbrella. Beatrice never takes an umbrella if it is not raining and always takes one when it is raining.” What can we deduce from these statements in the different situations below? Carefully justify your answers by introducing 3 logical propositions: \(P\): “it’s raining”, \(Q\): “Abel has an umbrella”, \(R\): “Beatrice has an umbrella”.

We know that \(P\Rightarrow Q\), \(P\Leftrightarrow R\)

Abel walks with an umbrella.

Since \(P\Rightarrow Q\), then \(Q\) cannot implies \(P\) or \(\neg P\).

Thus we can know neither it is raining or it is not raining.
Abel walks without an umbrella.

Since \(P\Rightarrow Q\), then \(\neg Q\Rightarrow \neg P\) which means if Abel walks without an umbrella, it is not raining.

Thus we can know it is not raining.
Beatrice walks with an umbrella.

Since \(P\Leftrightarrow R\), then we can know it is raining if and only if Beatrice walks with an umbrella.

Thus we can know it is raining.
Beatrice walks without an umbrella.

Since \(P\Leftrightarrow R\), then \(\neg P\Leftrightarrow \neg R\).

Then we can know it is not raining if and only if Beatrice walks without an umbrella.

Thus we can know it is not raining.
It is not raining.

Since we know \(\neg P\), then \(\neg P\Leftrightarrow \neg R\) and \(\neg Q\Rightarrow \neg P\).

Thus we can know Beatrice walks without an umbrella but we don't know whether Abel walks with an umbrella.
It is raining.

Since we know \(P\), then \(P\Rightarrow Q\), \(P\Leftrightarrow R\)

Thus we can know Abel walks with an umbrella and Beatrice walks with an umbrella.

‍

Exercise 2

Determine which of the following propositions are true:

136 is a multiple of 17 and 2 divides 167.

Since \(136=8\times 17\) and \(167\div2=83.5\), then true and false we can know the proposition is false.
136 is a multiple of 17 or 2 divides 167.

Since \(136=8\times 17\) and \(167\div2=83.5\), then true or false we can know the proposition is true.
\(\exists x \in \mathbb{R}, (x+ 1 = 0 \land x+ 2 = 0)\).

If \(x+1=0\Rightarrow x=-1\) but if \(x+2=0\Rightarrow x=-2\)

Thus it is false
\(\left( \exists x \in \mathbb{R}, x+ 1 = 0 \right) \land \left( \exists x \in \mathbb{R}, x+ 2 = 0 \right)\).

If \(x+1=0\Rightarrow x=-1\) or if \(x+2=0\Rightarrow x=-2\)

Thus it is true
\(\exists x \in \mathbb{R}^*, \forall y \in \mathbb{R}^*, \forall z \in \mathbb{R}^*, z - xy = 0\).

\(z-xy=0\Rightarrow z=xy\Rightarrow x=\frac{z}{y}\in \R^*\)

Thus it is false
\(\forall y \in \mathbb{R}^*, \exists x \in \mathbb{R}^*, \forall z \in \mathbb{R}^*, z - xy = 0\).

False

Take any non-zero real number \(y\). We would like to find some \(x\in \R^*\) such that for every \(z\in \R^*\)

We have \(z=xy\). So we can't find such \(z\)
\(\forall y \in \mathbb{R}^*, \forall z \in \mathbb{R}^*, \exists x \in \mathbb{R}^*, z - xy = 0\).

\(z-xy=0\Rightarrow z=xy\Rightarrow x=\frac{z}{y}\in \R^*\)

Thus it is true
\(\exists a \in \mathbb{R}, \forall \epsilon > 0, |a| < \epsilon\).

True, take \(a=0\)

找到一个a之后任意的epsilon都要满足
\(\forall \epsilon > 0, \exists a \in \mathbb{R}, |a| < \epsilon\).

Since the density of \(\R\), then it is true.

选取任意一个epsilon后, 都能找到一个a

也就是说a受epsilon的变化而变化

‍

Exercise 3

Let \(f: \mathbb{R} \to \mathbb{R}\) be a function. Write the negation of the following assertions:

\(\forall x \in \mathbb{R}, f(x) \neq 0\).

\(\exists x\in \R, f(x)=0\)
\(\forall M > 0, \exists A > 0, \forall x \geq A, f(x) > M\). (quantifier 的大于小于不要改)

\(\exists M>0,\forall A>0,\exists x\geq A,f(x)\leq M\)
\(\forall x \in \mathbb{R}, f(x) > 0 \Rightarrow x \leq 0\).

\(\exists x\in\mathbb{R},f(x)>0\wedge x>0\)

‍

Exercise 4

Let \(f: \mathbb{R} \to \mathbb{R}\) be a function. Write with quantifiers the following assertions:

\(f\) is constant.

\(\forall x_1,x_2\in\R,f(x_1)=f(x_2)\)
\(f\) is not constant.

\(\exists x_1,x_2\in\R,f(x_1)\neq f(x_2)\)
\(f\) has a zero.

\(\exists x\in\R,f(x)=0\)
\(f\) is periodic.

\(\exists T\in \R,\forall x\in \R,f(x)=f(x+T)\)

‍

Exercise 5

Determine for which reals \(x\) the following assertion is true:

\(\forall y \in [0, 1], x \geq y \Rightarrow x \geq 2y\).

If \(x<0\), true

If \(x=0\), if \(y=0\), true

if \(y\neq 0\), true

If \(x\in(0,2)\), false

Choose \(y = x\), which is within \([0, 1]\) since \(x < 1\) or pick \(y = \frac{x}{2}\) if \(x \geq 1\).
\(x \geq y\) is true.
\(x \geq 2y\) simplifies to \(x \geq 2x\), which is \(x \geq 2x\) or \(0 \geq x\).
Since \(x > 0\), this is false. Thus, the assertion fails in this interval.

If \(x\geq 2\), true

Thus \(x\in\left(-\infty,0\right\rbrack\cup\left\lbrack2,+\infty\right)\)

(Hint: Consider the following cases \(x \geq 2\), \(x\in[0,2]\), \(x = 0\), and \(x < 0\).)

‍

Exercise 6

A logical operator is said to be universal if it allows us to reconstruct all the other logical operators. In practice, it is sufficient to verify that we can reconstruct the three logical operators NOT, OR, and AND to show that an operator is universal. Show that the following two operators are universal:

The main idea(Analysis): Not A=Not (A and A)=Not (A or A), A And B=Not(Not(A And B), A Or B=Not((Not A) And (Not B))...

The operator NAND, defined by \(A \text{ NAND } B = \text{NOT}(A \text{ AND } B)\);

\(\text{NOT } A=A\text{ NAND } A\)

\(A\text{ AND } B=\text{NOT(NOT(A AND B))}=\text{NOT (A NAND B)}=\text{(A NAND B) NADN (A NAND B)}\)

\(A \text{ OR } B=\text{NOT((NOT A) AND (NOT B))}\)

Let's break it down, we need to express \(\text{(NOT A) AND (NOT B)}\), which is \(\text{(A NAND A) AND (B NAND B)}=\text{NOT((A NAND A) NAND (B NAND B)}\)

Then, \(\text{A OR B}=\text{(A NAND A) NAND (B NAND B)}\)
The operator NOR, defined by \(A \text{ NOR } B = \text{NOT}(A \text{ OR } B)\).

\(\text{NOT A}=\text{NOT (A OR A)}=\text{A NOR A}\)

\(\text{A OR B}=\text{NOT(NOT(A OR B))}=\text{NOT(A NOR B)=(A NOR B) NOR (A NOR B)}\)

\(\text{A AND B}=\text{NOT((NOT A) OR (NOT B))}\)

Then, we need to express \(\text{(NOT A) OR (NOT B)}\)

\(\text{(NOT A) OR (NOT B)}=\text{(A NOR A) OR (B NOR B)}=\text{NOT((A NOR A) NOR (B NOR B))}\)

Then, \(\text{A AND B}=\text{(A NOR A) NOR (B NOR B)}\)

‍