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 j= T rue.

b. T rue j= F alse.

c. (A ^ B) j= (A , B).

d. A , B j= A _ B.

e. A , B j= :A _ B.

f. (A ^ B) ) C j= (A ) C) _ (B ) C).

g. (C _ (:A ^ :B)) ((A ) C) ^ (B ) C).

h. (A _ B) ^ (:C _ :D _ E) j= (A _ B).

i. (A _ B) ^ (:C _ :D _ E) j= (A _ B) ^ (:D _ E).

j. (A _ B) ^ :(A ) B) is satis able.

k. (A , B) ^ (:A _ B) is satis able.

l. (A , B) , C has the same number of models as A , B for any xed 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 de ned 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 de ned 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 de ned 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 de ned 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’ i 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

• First-Order Logic 1

Are the following are valid (necessarily true) sentences?

a. (9x x = x) ) (8y9z y = z).

b. 8x P (x) _ :P (x).

c. 8x 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

• 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) 9c Country(c) ^ Border(c; Iraq) ^ Border(c; P akistan).

(ii) 9c Country(c) ) [Border(c; Iraq) ^ Border(c; P akistan)].

(iii) [9c Country(c)] ) [Border(c; Iraq) ^ Border(c; P akistan)].

(iv) 9c Border(Country(c); Iraq ^ P akistan).

c. All countries that border Ecuador are in South America.

(i) 8c Country(c) ^ Border(c; Ecuador) ) In(c; SouthAmerica).

(ii) 8c Country(c) ) [Border(c; Ecuador) ) In(c; SouthAmerica)].

(iii) 8c [Country(c) ) Border(c; Ecuador)] ) In(c; SouthAmerica).

(iv) 8c Country(c) ^ Border(c; Ecuador) ^ In(c; SouthAmerica).

d. No region in South America borders any region in Europe.

(i) :[9c; d In(c; SouthAmerica) ^ In(d; Europe) ^ Borders(c; d)].

(ii) 8c; d [In(c; SouthAmerica) ^ In(d; Europe)] ) :Borders(c; d)].

(iii) :8c In(c; SouthAmerica) ) 9d In(d; Europe) ^ :Borders(c; d).

(iv) 8c In(c; SouthAmerica) ) 8d In(d; Europe) ) :Borders(c; d).

e. No two adjacent countries have the same map color.

(i) 8x; y :Country(x) _ :Country(y) _ :Borders(x; y) _ :(M apColor(x) = M apColor(y)).

(ii) 8x; y (Country(x)^Country(y)^Borders(x; y)^:(x = y)) ) :(M apColor(x) = M apColor(y)).

(iii) 8x; y Country(x) ^ Country(y) ^ Borders(x; y) ^ :(M apColor(x) = M apColor(y)).

(iv) 8x; 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