2023

AI, P03 – LOGIC EXERCIS

CAROLINA BERNALDO DE QUIRÓ S DE CAL
AITOR gARMENDIA AIERDI
 EXERCISE 1.1
• False ⊨ True:

This statement is correct, due to the definition of entailment. When we have the following
sentence: 𝐾𝐵 ⊨ 𝛼, we say that the entailment knowledge base 𝐾𝐵 entails sentence 𝛼 𝑖𝑓𝑓 𝛼
is true in all worlds where 𝐾𝐵 is true, so in our case, as we do not have any world which is
true, we can say that the sentence is correct. So this statement is True.

• True ⊨ False:

This statement is incorrect, because it doesn’t fulfill the definition of entailment. This
sentence to be correct, in all the worlds in which the left term is true, the right term should be
true, and this doesn’t occur in our case, due to the fact that the right term is false when the
left term is true, so that True does not entail False. So this statement is False.

• (A ∧ B) ⊨ (A ⇔ B).

(A ∧ B) is true when A is true and B is true.

(A ⇔ B) is true iff A ⇒ B is true and B ⇒ A is true.

A ⇒ B is false only when A is true and B is false.

B ⇒ A is false only when B is true and A is false.

A B (A ∧ B) (A ⇔ B)

T T T T

T F F F

F T F F

F F F T

Since the right side is true for all the cases the left side is this statement is True.

1
• A ⇔ B ⊨ A ∨ B.

(A ⇔ B) is true iff A ⇒ B is true and B ⇒ A is true.

A ⇒ B is false only when A is true and B is false.

B ⇒ A is false only when B is true and A is false.

A ∨ B is true when at least A or B ar true.

A B A⇔B A∨B

T T T T

T F F T

F T F T

F F T F
Since the right side is not true for all cases the left side is, this statement is False.

• A ⇔ B ⊨ ￢A ∨ B.

(A ⇔ B) is true iff A ⇒ B is true and B ⇒ A is true.

A ⇒ B is false only when A is true and B is false.

B ⇒ A is false only when B is true and A is false.

A ∨ B is true when at least A or B ar true.

￢A makes A be false when it is true and true when it is false.

A B A⇔B ￢A ∨ B

T T T T

T F F F

F T F T

F F T T

Since the right side is true for all the cases the left side is, this statement is True.

2
• (A ∧ B) ⇒ C ⊨ (A ⇒ C) ∨ (B ⇒ C).

(A ∧ B) is true when A is true and B is true.

(A ∧ B) ⇒ C is false only when (A ∧ B) is true and C is false.

C ⇒ (A ∧ B) is false only when C is true and (A ∧ B) is false.

A ⇒ C is false only when A is true and C is false.

B ⇒ C is false only when B is true and C is false.

(A ⇒ C) ∨ (B ⇒ C) is true when at least (A ⇒ C) or (B ⇒ C) are true.

A B C (A ∧ B) ⇒ C (A ⇒ C) ∨ (B ⇒ C)

T T T T T

T T F F F

T F T T T

T F F T T

F T T T T

F T F T T

F F T T T

F F F T T

Since the right side is true for all the cases the left side is, this statement is True.

3
• (C ∨ (￢A ∧ ￢B)) ≡ ((A ⇒ C) ∧ (B ⇒ C)).

C ∨ (￢A ∧ ￢B) is true when at least C or (￢A ∧ ￢B) are true.

￢A makes A be false when it is true and true when it is false.

￢B makes B be false when it is true and true when it is false.

￢A ∧ ￢B is true when both are true.

A ⇒ C is false only when A is true and C is false.

B ⇒ C is false only when B is true and C is false.

(A ⇒ C) ∧ (B ⇒ C) is true when both are true.

A B C C ∨ (￢A ∧ ￢ (A ⇒ C) ∧ (B ⇒ C)
B)

T T T T T

T T F F F

T F T T T

T F F F F

F T T T T

F T F F F

F F T T T

F F F T T

Since when the right side is true the left side is true and when the right side is false the left side
is false as well (both are equal ≡), this statement is True.

4
• (A ∨ B) ∧ (￢C ∨￢D ∨ E) ⊨ (A ∨ B).

A B C D E (A ∨ B) ∧ (￢C ∨￢D ∨ E) (A ∨ B)

T T T T T F T

T T T T F F T

T T T F T T T

T T T F F T T

T T F T T F T

T T F T F F T

T T F F T T T

T T F F F T T

T F T T T F T

T F T T F F T

T F T F T T T

T F T F F T T

T F F T T F T

T F F T F F T

T F F F T T T

T F F F F T T

F T T T T F T

F T T T F F T

F T T F T T T

F T T F F T T

F T F T T F T

F T F T F F T

F T F F T T T

F T F F F T T

F F T T T F F

F F T T F F F

5
 F F T F T F F

F F T F F F F

F F F T T F F

F F F T F F F

F F F F T F F

F F F F F F F

Since the right side is true for all the cases the left side is, this statement is True.

• (A ∨ B) ∧ (￢C ∨￢D ∨ E) ⊨ (A ∨ B) ∧ (￢D ∨ E).

A B C D E (A ∨ B) ∧ (￢C ∨￢D ∨ (A ∨ B) ∧ (￢D ∨ E)

E)

T T T T T F F

T T T T F F F

T T T F T T T

T T T F F T T

T T F T T F F

T T F T F F F

T T F F T T T

T T F F F T T

T F T T T F F

T F T T F F F

T F T F T T T

T F T F F T T

T F F T T F F

T F F T F F F

T F F F T T T

T F F F F T T

F T T T T F F

6
 F T T T F F F

F T T F T T T

F T T F F T T

F T F T T F F

F T F T F F F

F T F F T T T

F T F F F T T

F F T T T F F

F F T T F F F

F F T F T T T

F F T F F T T

F F F T T F F

F F F T F F F

F F F F T T T

F F F F F T T

Since the right side is true for all the cases the left side is, this statement is True.

7
• (A ∨ B)∧ ￢(A ⇒ B) is satisfiable.

A sentence is satisfiable (SAT) if it is true in some model. Again, we could prove this with a
truth table:

A B (A ∨ B)∧ ￢(A ⇒ B)

T T F

T F T

F T F

F F F

Since we have one model that is true this sentence is Satisfiable (SAT).

• (A ⇔ B) ∧ (￢A ∨ B) is satisfiable.

A sentence is satisfiable (SAT) if it is true in some model.

We should remember that:

(A ⇔ B) is true iff A ⇒ B is true and B ⇒ A is true.

A ⇒ B is false only when A is true and B is false.

B ⇒ A is false only when B is true and A is false.

A B (A ⇔ B) ∧ (￢A ∨ B)

T T T

T F F

F T F

F F T

Since we have one model that is true this sentence is Satisfiable (SAT).

8
• (A ⇔ B) ⇔ C has the same number of models as (A ⇔ B) for any fixed set of
proposition symbols that includes A, B, C.

We should remember that:

(A ⇔ B) is true iff A ⇒ B is true and B ⇒ A is true.

A ⇒ B is false only when A is true and B is false.

B ⇒ A is false only when B is true and A is false.

With the use of a truth table:

A B C (A ⇔ B) (A ⇔ B) ⇔ C

T T T T T

T T F T F

T F T F F

T F F F T

F T T F F

F T F F T

F F T T T

F F F T F

Yes, (A ⇔ B) ⇔ C has the same number of models as (A ⇔ B) for any fixed set of
proposition symbols that includes A, B, C (there are four models T).

9
 EXERCISE 1.2
1.2 Decide whether each of the following sentences is satisfiable or unsatisfiable.
Verify your decisions using truth tables or the equivalence rules (see V06a).

• Smoke ⇒ Smoke

Smoke ⇒ Smoke is false only when Smoke is true and Smoke is false.

Smoke Smoke ⇒ Smoke

T T

F T

• Smoke ⇒ Fire

Smoke ⇒ Fire is false only when Smoke is true and Fire is false.

Smoke Fire Smoke ⇒ Fire

T T T

T F F

F T T

F F T

• (Smoke ⇒ Fire) ⇒ (￢Smoke ⇒ ￢Fire)

Smoke ⇒ Fire is false only when Smoke is true and Fire is false.

￢Smoke ⇒ ￢Fire is false only when ￢Smoke is true and ￢Fire is false

￢Smoke is true only when Smoke is false

￢Fire is true only when Fire is false

(Smoke ⇒ Fire) ⇒ (￢Smoke ⇒ ￢Fire) is false only when (Smoke ⇒ Fire) is true and (￢Smoke ⇒
￢Fire) is false.

Smoke Fire Smoke ⇒ Fire ￢Smoke ⇒ ￢ (Smoke ⇒ Fire) ⇒ (￢Smoke ⇒ ￢Fire)

Fire

T T T T T

10
 T F F T T

F T T F F

F F T T T

• Smoke ∨ Fire ∨ ￢Fire

Smoke ∨ Fire ∨ ￢Fire is true when at least one of the three members is true.

Smoke Fire Smoke ∨ Fire ∨ ￢Fire

T T T

T F T

F T T

F F T

• ((Smoke ∧ Heat) ⇒ Fire) ⇔ ((Smoke ⇒ Fire) ∨ (Heat ⇒ Fire))

(Smoke ∧ Heat) is true just when both Smoke and Heat are true

Smoke Heat Fire Smoke (Smoke Smoke Heat ⇒ (Smoke Result

∧ Heat ∧ Heat) ⇒ Fire Fire ⇒ Fire)
⇒ Fire ∨ (Heat
⇒ Fire)

T T T T T T T T T

T T F T F F F F T

T F T F T T T T T

T F F F T F T T T

F T T F T T T T T

F T F F T T F T T

F F T F T T T T T

F F F F T T T T T

11
• (Smoke ⇒ Fire) ⇒ ((Smoke ∧ Heat) ⇒ Fire)

Smoke Fire Heat Smoke ⇒ Smoke ∧ (Smoke ∧ Result

Fire Heat Heat) ⇒
Fire

T T T T T T T

T T F T F T T

T F T F T F T

T F F F F T T

F T T T F T T

F T F T F T T

F F T T F T T

F F F T F T T

• Big ∨ Dumb ∨ (Big ⇒ Dumb)

Big Dumb Big ⇒ Dumb Big ∨ Dumb ∨ (Big ⇒ Dumb)

T T T T

T F F T

F T T T

F F T T

As we saw in theory: A sentence is satisfiable (SAT) if it is true in some model, and a

sentence is unsatisfiable if it is true in no models.
In our case, all the sentences are satisfiable, because as we can see in the truth tables, all
of them have at least one true model, and there is no sentence which all the models are
false.

12
 EXERCISE 1.3
Suppose an agent has progressed to the following point, having perceived nothing in [1,1], a
breeze in [2,1], and a stench in [1,2], and is now concerned with the contents of [1,3], [2,2],
and [3,1]:

Each of these can contain a pit, and at most one can contain a wumpus. Following the
example the slide “Entailment in the wumpus world, contd.”, construct the set of possible
worlds (you should find 32 of them).
Mark the worlds in which the KB is true and those in which each of the following sentences is
true:

● α2 = “There is no pit in [2,2].”

● α3 = “There is a wumpus in [1,3].”

Hence show that KB ⊨ α2 and KB ⊨ α3.

13
The possible scenarios for the Wumpus World Navigation for the squares [1,3], [2,2] and
[3,1] are: having a pit, an empty square, a wumpus and a pit and a wumpus in the same one.
Hence, we have the following truth table with 32 possible worlds:

[1,3] [2,2] [3,1] α2 α3 KB

P P P F F F

P P E F F F

P E P T F F

P E E T F F

E P P F F F

E E P T F F

E P E F F F

E E E T F F

W P P F T F

W P E F T F

W E P T T T

W E E T T F

P W P T F F

P W E T F F

E W P T F F

E W E T F F

P P W F F F

P E W T F F

E P W F F F

E E W T F F

W,P P P F T F

P W,P P F F F

P P W,P F F F

W,P E E T T F

14
 W,P E P T T F

W,P P E F T F

E E W,P T F F

P E W,P T F F

E P W,P F F F

E W,P E F F F

P W,P E F F F

E W,P P F F F

The table shows that the statement α2 = “There is no pit in [2,2].” is true for some of the combinations
as well as the statement α3 = “There is a wumpus in [1,3].” Therefore, KB ⊨ α2 and KB ⊨ α3 are
true for the world where [1,3] = Wumpus, [2,2] = Empty, [3,1] = Pit. It is the optimal solution since
[1,2] has Stench ([1,3] could have a Wumpus) and [2,1] has Breeze ([3,1] should have a Pit).

15