Week 9: Propositional Logic - Exercises

Instructions: Complete the following exercises. Show your work for each step.

Part I: Translation from English to Logic

Exercise 1:
If it rains, the sky is cloudy.
Your Answer: ________________
Exercise 2:
If An had a lot of money, she would go shopping.
Your Answer: ________________
Exercise 3:
Monkeys are not literate.
Your Answer: ________________
Exercise 4:
The server is online and the database is accessible.
Your Answer: ________________
Exercise 5:
Either the model overfits or the dataset is too small.
Your Answer: ________________
Exercise 6:
If the lecture starts late, the lab session will be shorter.
Your Answer: ________________
Exercise 7:
The patient has a fever if and only if the thermometer reads above 38°C.
Your Answer: ________________
Exercise 8:
It is not the case that both the code compiles and the tests fail.
Your Answer: ________________
Exercise 9:
If the assignment is submitted, then the checker runs, and if it runs, a report is generated.
Your Answer: ________________
Exercise 10:
Either the network is down or the credentials are incorrect, but not both.
Your Answer: ________________

Part II: Convert to CNF

Exercise 11:
Convert to CNF: (P ⇒ (Q ∧ R)) ∨ (S ⇒ Q)
Your Answer: ________________
Exercise 12:
Convert to CNF: ((P ∨ Q) ⇒ (R ∧ S))
Your Answer: ________________
Exercise 13:
Convert to CNF: (P ⇔ (Q ∨ R)) ∧ (¬R ∨ S)
Your Answer: ________________
Exercise 14:
Convert to CNF: ¬(P ⇒ (Q ⇒ R)) ∨ S
Your Answer: ________________
Exercise 15:
Convert to CNF: (P ⇔ Q) ⇒ (R ∨ S)
Your Answer: ________________

Part III: Resolution and Inference

Exercise 16:
Use resolution to prove: Given premises P ⇒ Q, Q ⇒ R, ¬R, prove ¬P
Your Answer: ________________
Exercise 17:
Use resolution to prove: Given premises P ∨ Q, ¬P ∨ R, ¬Q ∨ S, prove R ∨ S
Your Answer: ________________
Exercise 18:
Use Modus Ponens: If P ⇒ Q and P, then what can we conclude?
Your Answer: ________________
Exercise 19:
Use Modus Tollens: If P ⇒ Q and ¬Q, then what can we conclude?
Your Answer: ________________
Exercise 20:
Use Resolution: From P ∨ Q and ¬P ∨ R, what can we derive?
Your Answer: ________________

Part IV: Truth Tables

Exercise 21:
Construct a truth table for: (P ⇒ Q) ∧ (Q ⇒ R) ⇒ (P ⇒ R)
Your Answer: ________________
Exercise 22:
Construct a truth table for: P ⇔ (Q ∧ ¬R)
Your Answer: ________________
Exercise 23:
Construct a truth table for: (P ∨ Q) ∧ (¬P ∨ R) ∧ (¬Q ∨ S)
Your Answer: ________________
Exercise 24:
Construct a truth table for: ¬(P ∧ Q) ∨ (P ⇒ Q)
Your Answer: ________________

Part V: Logical Equivalences

Exercise 25:
Show that P ⇒ Q is logically equivalent to ¬P ∨ Q
Your Answer: ________________
Exercise 26:
Show that ¬(P ∧ Q) is logically equivalent to ¬P ∨ ¬Q (De Morgan's Law)
Your Answer: ________________
Exercise 27:
Show that P ⇔ Q is logically equivalent to (P ⇒ Q) ∧ (Q ⇒ P)
Your Answer: ________________
Exercise 28:
Show that ¬(P ∨ Q) is logically equivalent to ¬P ∧ ¬Q (De Morgan's Law)
Your Answer: ________________

Part VI: Real-World Applications

Exercise 29:
Translate to logic and convert to CNF: "If a user is authenticated and not banned, then the action is permitted or the action is audited."
Your Answer: ________________
Exercise 30:
Translate to logic and convert to CNF: "Either the API returns 200 or, if it returns 500, then alerts trigger."
Your Answer: ________________
Exercise 31:
Translate to logic and convert to CNF: "If the build passes, then deployment proceeds if and only if approvals are granted."
Your Answer: ________________
Exercise 32:
Translate to logic and convert to CNF: "Unless the battery is charged, the device powers off."
Your Answer: ________________
Exercise 33:
Translate to logic and convert to CNF: "The dataset is large if and only if the sample size is above 10k and the features exceed 100."
Your Answer: ________________
Exercise 34:
Translate to logic and convert to CNF: "The lab is open implies the TA is present or the sign shows remote support, and the TA being present implies the lab is open."
Your Answer: ________________
Exercise 35:
Translate to logic and convert to CNF: "It is not the case that if the server is down or the firewall blocks traffic, then the website is reachable."
Your Answer: ________________

Course Information

Introduction to Artificial Intelligence

EP15.TOKT11121 (DS) & EP16.TOKT11121 (AI)

National Economics University

Instructors: Dr. Trong-Nghia Nguyen & Dr. Nguyen Thi Kim Ngan