To learn how to represent knowledge using propositional and first-order logic.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Assignment 1

Logic-based KR & Logic Programming

• To learn how to represent knowledge using propositional and first-order logic.

• To become skilled in reasoning using natural deduction and resolution.

• To gain experience in logic programming using Prolog.

2. Learning Outcomes

• Analyse in depth a variety of established logic-based knowledge representation languages and use them to formulate sound and complete reasoning.

• Apply logic programming techniques to solve a significant problem requiring knowledge representation and reasoning.

3. Assessment Brief

Part 1 (40%)

Exercise 1: Propositional Logic Representation [5%]

Express the following declarative sentences in propositional logic; in each case state what your respective propositional symbols p, q, etc. mean:

a) [0.5%] The contract is not valid unless it has been signed by all parties and validated by a public authority.

b) [0.5%] Tomorrow we will either visit the museum or walk down the pier, but not both.

c) [0.5%] If the parliament approves the no-confidence motion, the government must resign or ask for a snap election.

For each of the following invalid inferences, give examples of declarative sentences in natural language for the atoms p and q, such that the premises are true, but the conclusion false.

d) [0.5%] 𝑝 ∨ 𝑞 ⊢ 𝑝 𝖠 𝑞

e) [0.5%] 𝑝 → 𝑞 ⊢ 𝑝 ∨ 𝑞

Exercise 2: Conjunctive Normal Form [5%]

Construct formula 𝜙𝜙 in Conjunctive Normal Form based on the following truth table. Make the formula as simple as possible using known equivalences of propositional logic.

p q r 𝝓𝝓

T T T F

T T F T

T F T F

F T T F

T F F T

F T F F

F F T F

F F F T

Exercise 3: Natural Deduction for Propositional Logic [5%]

Use natural deduction to prove the validity of the following inference:

(𝑝 𝖠 𝑞) ∨ (𝑝 𝖠 𝑟) ⊢ 𝑝 𝖠 (𝑞 ∨ 𝑟)

Exercise 4: First-Order Logic Representation [10%]

Consider an interpretation ⟨𝐷, 𝐼⟩, where D is the set of natural numbers and I is a mapping as follows:

𝐼(𝑎) = 0

𝐼(𝑏) = 1

𝐼(𝑐) = 3

𝐼(𝑓𝑓): 𝑛 → 𝑛2

𝐼(𝑔): (𝑚, 𝑛) → 𝑚 + 𝑛

𝐼(𝑃) = "is an even number"

𝐼(𝑄𝑄) = {(𝑚, 𝑛) | 𝑚 𝑑𝑑𝑑𝑣𝑑𝑑𝑑𝑒𝑠 𝑛}

Decide if the following formulas are true or false under interpretation ⟨𝐷, 𝐼⟩, showing the full decision proof:

a) [2%] 𝑃�𝑓𝑓(𝑏)�

b) [2%] 𝑃�𝑔(𝑎, 𝑏)�

c) [2%] 𝑄𝑄(𝑐, 𝑏)

d) [2%] ∀𝑥 𝑄𝑄(𝑥, 𝑥)

e) [2%] ∃𝑥 𝑄𝑄�𝑥, 𝑓𝑓(𝑥)�

Exercise 5: Resolution [15%]

a) [10%] Use (standard) resolution to determine whether the following set of premises entails 𝑄𝑄. In your answer you should show the resolution tree.

{𝑃 → ¬𝑅 𝖠 𝑉 , 𝑃 ∨ 𝑄𝑄 , ¬𝑅 → ¬𝑈 , 𝑉 → 𝑈}

b) [5%] Is it possible to apply SLD resolution for the same problem? Justify your answer. 5

Part 2 (60%)

For this part you will implement the well-known game of Blackjack (or Twenty-One) in Prolog. All source files need to be submitted in a separate zipped file.

We consider a simplified version of Blackjack, where there is only one (human) player and an AI dealer, playing without bets. In each round, the winner is the player whose cards (their hand) sum up to the highest amount of points, without exceeding 21. Dealer or player bust when their hand exceeds 21.

In Brightspace, you can find a partial implementation to get you started. You are free to modify it in any way you see fit, or even to create your own implementation from scratch.

 

Exercise 6: Representing the Deck [5%]

Blackjack is played with a standard 52-card deck, containing four suits (diamonds, clubs, hearts and spades), with each suit containing thirteen ranks (ace, 2 through 10, jack, queen and king). Write Prolog code (deck.pl) that implements the following:

a) [3%] Represent possible suits, ranks and cards.

b) [2%] Create a standard 52-card deck.

Exercise 7: Dealing Hands [10%]

In a Blackjack round, two cards are dealt to each player from the top of the deck in an alternating manner as follows: one card to the player, one card to the dealer, second card to the player, second card to the dealer. All cards dealt collectively constitute the table of each round. The player is then asked if they want to hit (get another card) or stand (accept no more cards). If they hit, a new card is dealt from the top of the deck. Based on these, write Prolog code (deck.pl) that implements the following:

a) [3%] Given a deck (as created in Exercise 6b), deal initial cards to player and dealer, resulting in an updated deck and the table (dealt cards).

b) [3%] Ask player if they want another card (print message on screen), resulting in the player’s answer (yes or no).

c) [4%] Given a deck and a table, deal a card to the player, resulting in updated deck and table.

Attachments:

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. Develop a program to emulate a purchase transaction at a retail store. This  program will have two classes, a LineItem class and a Transaction class

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme