Description

1 Propositional Logic 1
We ask a logician (who only tells the truth) about his sentimental life, and he answers the following two statements:
• I love Ann or I love Beth.
• If I love Ann, then I love Beth.
What can we conclude? Answer the following questions by ”yes”, ”no”, ”unsure”.
1. Does he love Ann?
2. Does he love Beth?
3. Does he love both?
Sample Answer: no,no,no
2 Propositional Logic 2
Which of the following are correct?
a. False |= True.
b. True |= False.
c. (A ∧ B) |= (A ⇔ B).
d. A ⇔ B |= A ∨ B.
e. A ⇔ B |= ¬A ∨ B.
f. (A ∧ B) ⇒ C |= (A ⇒ C) ∨ (B ⇒ C).
g. (C ∨ (¬A ∧ ¬B)) ≡ ((A ⇒ C) ∧ (B ⇒ C).
h. (A ∨ B) ∧ (¬C ∨ ¬D ∨ E) |= (A ∨ B).
i. (A ∨ B) ∧ (¬C ∨ ¬D ∨ E) |= (A ∨ B) ∧ (¬D ∨ E).
j. (A ∨ B) ∧ ¬(A ⇒ B) is satisfiable.
k. (A ⇔ B) ∧ (¬A ∨ B) is satisfiable.
l. (A ⇔ B) ⇔ C has the same number of models as A ⇔ B for any fixed set of proposition symbols
that includes A,B,C.
1
a,b,c,d
3 Propositional Logic 3
We denote L0 the set of propositional logic sentences built from a set X of n propositional symbols. we consider the following new formal languages, where some logical connectives are not allowed:
• L1 is defined as follows:
True and False are sentences of L1. All symbols of X are sentences of L1. If s,s0 are two sentences of L1, then ¬s, (s ∧ s0), (s ∨ s0), and (s ⇒ s0) are four sentences of L1.
• L2 is defined as follows:
True and False are sentences of L2. All symbols of X are sentences of L2. If s,s0 are two sentences of L2, then ¬s, (s ∧ s0), and (s ∨ s0) are three sentences of L2.
• L3 is defined as follows:
True and False are sentences of L3. All symbols of X are sentences of L3. If s,s0 are two sentences of L3, then ¬s and (s ∧ s0) are two sentences of L3.
• L4 is defined as follows:
True and False are sentences of L4. All symbols of X are sentences of L4. If s are two sentences of L4, then ¬s is a sentence of L4.
We consider the following binary relation between languages: L ⊆ L’ iff any sentences that can be expressed in L can equivalently be expressed in L’.
Answer ”yes” or ”no” the following questions.
1. L1 ⊆ L0
2. L2 ⊆ L0
3. L3 ⊆ L0
4. L4 ⊆ L0
5. L0 ⊆ L1
6. L0 ⊆ L2
7. L0 ⊆ L3
8. L0 ⊆ L4
Sample Answer: no,no,no,no,no,no,no,no
4 First-Order Logic 1
Are the following are valid (necessarily true) sentences?
a. (∃x x = x) ⇒ (∀y∃z y = z).
b. ∀x P(x) ∨ ¬P(x).
c. ∀x Smart(x) ∨ (x = x).
Answer ”Valid” or ”Invalid” the following questions.
Valid,Valid,Valid
5 First-Order Logic 2
This exercise uses the function Map Color and predicates In(T,y), Borders(x,y), and Country(x), whose arguments are geographical regions, along with constant symbols for various regions. In each of the following we give an English sentence and a number of candidate logical expressions.
a. Paris and Marseilles are both in France.
(i) In(Paris ∧ Marseilles,France).
(ii) In(Paris,France) ∧ In(Marseilles,France). (iii) In(Paris,France) ∨ In(Marseilles,France).
b. There is a country that borders both Iraq and Pakistan.
(i) ∃c Country(c) ∧ Border(c,Iraq) ∧ Border(c,Pakistan).
(ii) ∃c Country(c) ⇒ [Border(c,Iraq) ∧ Border(c,Pakistan)].
(iii) [∃c Country(c)] ⇒ [Border(c,Iraq) ∧ Border(c,Pakistan)].
(iv) ∃c Border(Country(c),Iraq ∧ Pakistan).
c. All countries that border Ecuador are in South America.
(i) ∀c Country(c) ∧ Border(c,Ecuador) ⇒ In(c,SouthAmerica).
(ii) ∀c Country(c) ⇒ [Border(c,Ecuador) ⇒ In(c,SouthAmerica)]. (iii) ∀c [Country(c) ⇒ Border(c,Ecuador)] ⇒ In(c,SouthAmerica).
(iv) ∀c Country(c) ∧ Border(c,Ecuador) ∧ In(c,SouthAmerica).
d. No region in South America borders any region in Europe.
(i) ¬[∃c,d In(c,SouthAmerica) ∧ In(d,Europe) ∧ Borders(c,d)].
(ii) ∀c,d [In(c,SouthAmerica) ∧ In(d,Europe)] ⇒ ¬Borders(c,d)].
(iii) ¬∀c In(c,SouthAmerica) ⇒ ∃d In(d,Europe) ∧ ¬Borders(c,d).
(iv) ∀c In(c,SouthAmerica) ⇒ ∀d In(d,Europe) ⇒ ¬Borders(c,d).
e. No two adjacent countries have the same map color.
(i) ∀x,y ¬Country(x) ∨ ¬Country(y) ∨ ¬Borders(x,y) ∨ ¬(MapColor(x) = MapColor(y)).
(ii) ∀x,y (Country(x)∧Country(y)∧Borders(x,y)∧¬(x = y)) ⇒ ¬(MapColor(x) = MapColor(y)).
(iii) ∀x,y Country(x) ∧ Country(y) ∧ Borders(x,y) ∧ ¬(MapColor(x) = MapColor(y)).
(iv) ∀x,y (Country(x) ∧ Country(y) ∧ Borders(x,y)) ⇒ MapColor(x 6= y).
For each of the logical expressions, state whether it…
1 correctly expresses the English sentence;
2 is syntactically invalid and therefore meaningless;
3 is syntactically valid but does not express the meaning of the English sentence.
233
2333
1222
1333
3222