Assignment

Exercise 1 (Set Theory)

Consider the following sets:

• A = {a, b, c, d}
• B = {a, x, y}
• C = {b, c, x}

Compute the following sets:

• A ∩ C
• (A ∩ B) ∪ C
• A - {b, x}
• ((A ∩ X) ∪ {y}) ∩ C

Exercise 2 (Set Theory)

Consider the following sets:

• A = {x∈N : 1 ≤ x ≤ 10}
• B = {x∈N : 0 ≤ x ≤ 2}
• C = {x∈N : x > 2}

Do the following tasks:

• Enumerate all the elements belonging to each set
• Compute the set A ∩ B
• Compute the set A ∪ C
• Compute the set C - B

Exercise 3 (Propositional logic)

For each of the following expression, please say if it is a formula belonging to propositional logic. If not, please explain why.
1. ¬ ( ¬ p ∨ q)
2. p ∨ (q)
3. (p ⇒p) ⇒ (p ⇒ q)
4. ¬ ∧ p

Exercise 4 (Propositional logic)

Formalize in propositional logic the following sentences

• If it rains while the sun shines, a rainbow will appear
• Charles comes if Elsa does and the other way around
• Johan comes just when Peter stays at home
• We are going, unless it is raining
• Charles and Elsa are brother and sister or nephew and niece
• If I have lost, I cannot make a move, then I have lost.

Exercise 5 (Propositional logic)

Is (¬r ∧ (¬p ∨ (¬q ∧ r))) ⇔ (p ∨ q) a tautology?

Notice that in order to prove that a formula is a tautology, you have to check if it is true for all the possible combination of values of the proposition in it (you can check it using the truth table of the formula).

Exercise 6 (Propositional logic, Proof)

Show the following (Hp 1 and Hp 2 are your hypotheses and you want to prove that ‘a' holds):

Hp 1 ¬a ⇒ (b ∧ c)
Hp 2 ¬b
To prove: a

Exercise 7 (Propositional logic, Proof)

Proof the following theorem:

Hp 1: Jim is an architect or a travel agent
Hp 2: If Jim is an architect than Jim is graduated
Hp 3: Jim is not graduated

To prove: Jim is a travel agent

Before proving the theorem validity, transform the sentences in logic formulae.