Midterm I

Duration of the test: 1 hour 45 minutes.

Midterm I problems

If not precised otherwise, you can assume that the domain of all variables and predicates is the set of integer numbers. By default, all questions assume an explanation of your answer.

Problem 1 (15 points)

Are the following statements logically equivalent for all (binary) predicates ?

In second-order logic, which of the quantifiers , , , should you put instead of to make the following statement true?

Problem 2 (10 points)

Is the following inference valid?

Problem 3 (15 points)

Consider the following statements:

Circle the number of the statements that are true for all sets , and . Show the remaining statements to be false: a Venn diagram is sufficient in this problem.

Problem 4 (15 points)

Let , and be sets. Prove that .

Note: please be detailed with the proof. A Venn diagram is not sufficient argument: it is not rigorous reasoning.

Problem 5 (25 points)

Recall that is defined as .

For non-zero integer numbers and define the greatest common divisor as

Here is a map on sets with integer elements returning the largest element of the set.

Compute the .

Define . and are called relatively prime. How would you describe the condition to be relatively prime in plain English?

Below is a predicate logic proof (using some words for context!) of some statement. Write in English the statement that is being proved and the technique used. Determine if the proof is valid or invalid. If the proof is invalid, identify and explain the error(s) in the proof. Continue investigating even if erroneous claims have already been made: the goal is to find all logical mistakes in the steps.

Statement: . Proof:

It is obvious that and . Then (as )

But , and we get to

This proves the original statement.

Problem 6 (20 points)

While creating a user interface for your website, you want to encourage the user to create secure passwords for their accounts. You decide to implement a password strength checker that verifies if a password meets the following criteria:

1. The password must contain at least one letter.
2. The password must contain exactly one special character from the set , %, &, *}$.
3. The password must not contain any symbols other than letters, digits, and special characters specified above.
4. No three elements of the password can be the same. Be careful :)
5. Two neighboring elements of the password cannot be from the same set of characters: letters, digits, or special characters.

All passwords are assumed to be exactly characters long. This condition is assumed to be true and does not need to be checked by . Denote by the set of all characters.

The task of this problem is to design a predicate that checks if a password is secure using the following predicates:

• : is a letter.
• : is a digit.
• : is a special character.

For the domain of the predicate , use the set of all maps where is the -th character of the password .

1. Is the password “password” secure? What map corresponds to this password?

2. Is the password “P@ssw0rd” secure?

3. Write down in predicate logic the predicate that checks validity of condition 1.

4. Write down in predicate logic the predicate that checks validity of condition 2.

5. Write down in predicate logic the predicate that checks validity of condition 3.

6. Write down in predicate logic the predicate that checks validity of condition 4.

7. Write down in predicate logic the predicate that checks validity of condition 5.

8. Write down in predicate logic the predicate in terms of the predicates , , , and . Try to be as concise as possible.