25-26-2-离散数学-期中

1. [10 points]

Please determine whether the following sentence is a proposition, and if it is a proposition, give its truth value.

1. If 2+1 = 5, then tomorrow is a sunny day. 【显示答案】 Yes, T
2. Open the window. 【显示答案】 No
3. 5+x = 8. 【显示答案】 No
4. The square root of 2 is rational. 【显示答案】 Yes, F
5. This statement is false. 【显示答案】 No

2. [4 points]

Express the following sentences in propositional logic using the propositions $p$ : “You can get the scholarship”, $q$ : “You get an A on the final exam.” and logical connectives.

1. You can get the scholarship only if you get an A on the final exam.

› 答案 / 解析

$p \to q$

2. You can get the scholarship unless you didn’t get an A on the final exam.

› 答案 / 解析

$q \to p$

3. [8 points]

1. Prove or disprove that $q \to (\neg p \land (p \lor q))$ is a tautology.
2. Show that $(p \land q) \to \neg r$ and $q \to \neg(p \land r)$ are logically equivalent by developing a series of logical equivalences.

4. [10 points]

1. Find the principal disjunctive normal form for $(\neg p \lor q) \to r$.
2. Find the principal conjunctive normal form for $(p \to q) \to r$ using logical equivalences.

5. [6 points]

Suppose that the universe for $x$ and $y$ is {1, 2, 3, 4}. Assume that $P(x, y)$ is a predicate that is true in the following cases and false otherwise: $P(1,4)$, $P(2,1)$, $P(2,2)$, $P(3,4)$, $P(4,1)$, $P(4,4)$. Determine whether each of the following is true or false and give your reason.

1. $\forall x \exists y P(x, y)$
2. $\forall y \exists x P(x, y)$
3. $\exists x \forall y P(x, y)$

6. [6 points]

Translate each of these statements into logical expressions in three different ways by varying the domain and by using predicates with one and with two variables.

1. Any player in games has two roles.
2. Some cities in North China implement the odd-even number-plate restrictions.

7. [10 points]

Let $S(x)$, $C(x)$, and $T(x, y)$ be the statements ”$x$ is a student,” ”$x$ is a course,” and ”$x$ is taking $y$,” respectively. Express each of these statements using quantifiers, logical connectives, and $S(x)$, $C(x)$, and $T(x, y)$.

1. Every course is being taken by at least one student.
2. Some student is taking every course.
3. No student is taking all courses.
4. There is a course that all students are taking.
5. Some students are taking no course.

8. [10 points]

Put these statements in prenex normal form.

1. $\forall x F(x) \to (\exists y Q(y) \to \forall x H(x))$
2. $(\exists x F(x, y) \to \forall y Q(y)) \lor \forall x H(x, y)$

9. [6 points]

There is a special set that has no elements. This set is called the empty set, or null set, and is denoted by $\emptyset$. Two sets are equal if and only if they have the same elements. Therefore, if $A$ and $B$ are sets, then $A$ and $B$ are equal if and only if $\forall x (x \in A \leftrightarrow x \in B)$. Give a direct proof and a proof by contraposition of the statement: “If $\emptyset_1$ , $\emptyset_2$ are any two empties, then $\emptyset_1 = \emptyset_2$.“

10. [6 points]

1. Disprove that if $\sqrt{2}$ is irrational, then for every real number $x$, $\sqrt[3]{x}$ is irrational.
2. Prove if $\sqrt{2}$ is irrational, then $\sqrt[3]{2}$ is irrational.

11. [3 points]

Prove the statement: “There is no smallest positive rational number.”

12. [3 points]

Prove the statement: “For every integer $n$, the integer $n^2+n$ is even.”

13. [8 points]

Show that the premises: “Xiao Wang has studied English or Japanese”, “If Xiao Wang has studied English, then he has been to the UK.” and “If Xiao Wang has been to the UK, then he has also been to Japan.” imply the conclusion “Xiao Wang has studied Japanese or has been to Japan.”

14. [10 points]

Show that the premises: “All monkeys can climb trees”, “All animals that can climb trees can pick peaches”, “There exists an animal that cannot pick peaches.” imply the conclusion “There exists an animal that is not a monkey.”