$29.99
Homework 10 Electronic
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. F alse |= T rue.
b. T rue |= F alse.
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
VE 492 : Electronic #10 (Due July 31st, 2020 at 11:59pm)
Sample Answer:
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 ∧ s
0
), (s ∨ s
0
), and (s ⇒ s
0
) 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 ∧ s
0
), and (s ∨ s
0
) 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 ∧ s
0
) 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.
2
VE 492 : Electronic #10 (Due July 31st, 2020 at 11:59pm)
Sample Answer:
Valid,Valid,Valid
5 First-Order Logic 2
This exercise uses the function M ap 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(P aris ∧ M arseilles, F rance).
(ii) In(P aris, F rance) ∧ In(M arseilles, F rance).
(iii) In(P aris, F rance) ∨ In(M arseilles, F rance).
b. There is a country that borders both Iraq and Pakistan.
(i) ∃c Country(c) ∧ Border(c, Iraq) ∧ Border(c, P akistan).
(ii) ∃c Country(c) ⇒ [Border(c, Iraq) ∧ Border(c, P akistan)].
(iii) [∃c Country(c)] ⇒ [Border(c, Iraq) ∧ Border(c, P akistan)].
(iv) ∃c Border(Country(c), Iraq ∧ P akistan).
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) ∨ ¬(M apColor(x) = M apColor(y)).
(ii) ∀x, y (Country(x)∧Country(y)∧Borders(x, y)∧¬(x = y)) ⇒ ¬(M apColor(x) = M apColor(y)).
(iii) ∀x, y Country(x) ∧ Country(y) ∧ Borders(x, y) ∧ ¬(M apColor(x) = M apColor(y)).
(iv) ∀x, y (Country(x) ∧ Country(y) ∧ Borders(x, y)) ⇒ M apColor(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.
3
VE 492 : Electronic #10 (Due July 31st, 2020 at 11:59pm)
Sample Answer:
233
2333
1222
1333
3222
4