Scribd
Upload
32 views9 pages

Evaluative Task 2 Computational Logic 2024 2025

The document outlines an evaluative task for a computational logic course, consisting of multiple exercises focused on definitions, natural deduction, transformation into Conjunctive Normal Form (CNF), and first-order logic. It includes specific exercises requiring the completion of definitions, proof using induction, and evaluation of sentences within given structures. The task is structured with points assigned to each exercise and includes space for answers.

Uploaded by

danigraciaquiroga
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
32 views9 pages

Evaluative Task 2 Computational Logic 2024 2025

The document outlines an evaluative task for a computational logic course, consisting of multiple exercises focused on definitions, natural deduction, transformation into Conjunctive Normal Form (CNF), and first-order logic. It includes specific exercises requiring the completion of definitions, proof using induction, and evaluation of sentences within given structures. The task is structured with points assigned to each exercise and includes space for answers.

Uploaded by

danigraciaquiroga
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

NAME:

SURNAME(S):
NIU:

Computational Logic
Evaluative Task 2
04th December 2024

TFL
Exercise 1 (0’5 points– 5 minutes) Complete the following definitions:
(A) A sentence is in Conjunctive Normal Form (CNF) if it is of the form...

(B) A literal is a...


(All the definitions are very short.)
Answers:

1
Exercise 2 (2’5 points – 20 minutes) Natural Deduction
(A) ⊢ (A → B) ∨ (¬B ∨ A) (0’75 points)
(B) ¬(A ∧ B) ⊢ ¬A ∨ ¬B (0’75 points)
(C) A → ¬(¬B ∧ ¬C) ⊢ (¬A ∨ B) ∨ (A → C) (1 point)

Answer:
(A)

2
(B)

3
(C)

4
Exercise 3. (1 point– 15 minutes)Transform each of the following sentences
into CNF:

(a) A → (¬B ∧ ¬C)


(b) (A∨B) → (B ↔ C)

5
FOL
Exercise 4 (0’5 points– 5 minutes) Define atomic sentences (0’4 points) and
put an example of an atomic sentence (0’1 points). Answer:

6
Exercise 5 (1 point– 15 minutes) Use the principle of induction for sentences
of a first-order language L to prove that given a sentence of L, a variable x, and
a term t, φ has the same number of connectives than φ( xt ). Answer:

7
Exercise 6 (2 points– 15 minutes) Consider a first-order language L with
two predicate symbols P and Q, two binary relations R and S, and two individual
constants c and d. Consider the following structure for L

A = ⟨A, P A , QA , RA , S A , cA , dA ⟩, where:

A = {1, 2, 3, 4, 5, 6},
P A = {1, 4, 5, 6}, QA = {2, 5, 6},
RA = {⟨1, 1⟩, ⟨2, 2⟩, ⟨3, 3⟩, ⟨4, 4⟩, ⟨5, 5⟩, ⟨6, 6⟩},

S A = {⟨1, 2⟩, ⟨2, 1⟩, ⟨2, 3⟩, ⟨3, 2⟩},


cA = 1, and dA = 5.

Which of the following sentences are true in A? Explain your answers.

(A) ∀x(P x → ∃y(¬P y ∧ Qy)).

(B) ∀x∀y((Qx ∨ ¬Sdy) → ¬Qx).


(C) ∀x∀y(Rxx ∧ ¬Sxx).
(D) ∀x(P c → ∃y¬Rxy)

8
Exercise 7 (2’5 points– 20 minutes) Consider a first-order language L with
one predicate symbol P , two binary relations R and S, and three individual
constants c, d, e. Consider also the structure for L,

A = ⟨A, P A , RA , S A , cA , dA , eA ⟩
where:
A is the set of celestial bodies in the Solar System,

P A is the set of planets in the Solar System (i.e., P x is interpreted in A


as x is a planet),
RA is the binary relation to orbit around (i.e., Rxy is interpreted in A as
x orbits around y),

S A is the binary relation to be a satellite of (i.e., Sxy is interpreted in A


as x is a satellite of y),
cA is the Sun,
dA is the Earth, and

eA is the Moon.
Symbolize the following sentences:
(A) Only the Moon orbits around the Sun.
(B) There is at least one planet without satellites.

(C) There is at most one planet without satellites.


(D) No planet is a satellite.
(E) Every planet except the Earth orbits around the Sun.

Answers:

You might also like