Scribd
Upload
11 views6 pages

CS221 Week 9 Logic Problems and Solutions

Uploaded by

vondacoder223
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
11 views6 pages

CS221 Week 9 Logic Problems and Solutions

Uploaded by

vondacoder223
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

CS221 Problem Workout

Week 9

1) [CA session] Problem 1


Compute the conjunctive normal form (CNF) of the following two formulas and write
every step of your computation:

(a) ¬P → ¬¬(Q ∨ (R ∧ ¬S))


(b) (P → (Q ∨ (R ∧ S))) ∧ (R ∨ (S → Q))

1
2) [CA session] Problem 2: Proof by Resolution
In this question we practice proving by resolution on the following knowledge base:
Either Heather attended the meeting or Heather was not invited. If the boss wanted
Heather at the meeting, then she was invited. Heather did not attend the meeting. If
the boss did not want Heather there, and the boss did not invite her there, then she is
going to be fired. Prove Heather is going to be fired.

2
3) [CA Session] Problem 3
Translate the following English sentences into first-order logic formulas:

(a) Every student takes at least one course.

(b) Every student who takes Analysis also takes Geometry.

(c) No student failed Chemistry but at least one student failed History.

4) Problem 4
Translate each of the following sentences into first order logic using only the predicates
listed below:

• Teacher(x): x is a teacher.
• Student(x): x is a student.
• Test(x): x is a test.
• Passed(x, y): x passed y.

(i) [2 point] Some students are also teachers.

(ii) [3 points] All students have failed a test.

3
(iii) [3 points] There is a test that every student has passed.

4
5) Problem 5
Imagine we are building a knowledge base of propositions in first order logic and want
to make inferences based on what we know. We will deal with a simple setting, where
we only have three objects in the world: Alice, Carol, and Bob. Our predicates are as
follows:

• Employee(x): x is an employee.
• Boss(x): x is a boss.
• Works(x): x works.
• Paid(x): x gets paid.

The knowledge base we have constructed consists of the following propositions:

(a) Boss(Carol)
(b) Employee(Bob)
(c) Paid(Carol) ∧ Works(Carol)
(d) Paid(Alice)
(e) ∀x (Employee(x) ↔ ¬ Boss(x))
(f) ∀x (Employee(x) → Works(x))
(g) ∀x ((Paid(x) ∧ ¬ Works(x)) → Boss(x))

(i) [2 Point] We know from class that one technique we can use to perform infer-
ence with our knowledge base is to propositionalize the statements of first-order
logic into statements of propositional logic. Practice this by propositionalizing
statement (f) from our knowledge base.

(ii) [3 Points] If we translated the statement "Anyone who is not a boss either works
or does not get paid" into first-order logic and added it to our knowledge base,
how would the size of the set of valid models representing our knowledge base
change, and why?

5
(iii) [7 Points] Using only our original knowledge base (not including the statement
from part (ii)), we want to answer the question "Does everyone work?" We first
translate the sentence "everyone works" into first order logic as statement f .
Determine the answer to our query by considering the following questions of sat-
isfiability:
1 [3 points] Is KB ∪ ¬f satisfiable? Answer yes/no. If yes, fill in the following
○
table with T for true and F for false to show that there is a satisfying model.
x Employee(x) Boss(x) Works(x) Paid(x)
Alice
Bob
Carol

2 [3 points] Is KB ∪ f satisfiable? Answer yes/no. If yes, fill in the following


○
table with T for true and F for false to show that there is a satisfying model.
x Employee(x) Boss(x) Works(x) Paid(x)
Alice
Bob
Carol

3 [1 points] Based on your answers to the previous two parts, does our knowl-
○
edge base entail f , contradict f , or is f contingent? And what should the
answer to our original question "Does everyone work?" be?

Common questions

Powered by AI

Translating propositions such as 'No student failed Chemistry' into first-order logic allows precise knowledge base queries and operations. For this statement, it translates as ¬∃x (Student(x) ∧ Failed(x, Chemistry)), ensuring exact predicates for logical consistency, enabling sophisticated inferences and contradiction checks, elevating the accuracy in logical models .

CNF conversion is crucial in automated theorem proving because it simplifies formulas into conjunctive clauses, making them suitable for resolution-based proving techniques. The CNF standardization allows theorem provers to use logical operations systematically. Resolutions can easily connect and discharge clauses, making proof processes more structured and predictable .

The sentence 'There is a test that every student has passed' translates into first-order logic as ∃x (Test(x) ∧ ∀y (Student(y) → Passed(y, x))) where 'Test(x)' represents that x is a test, and 'Passed(y, x)' signifies that student y has passed the test x .

The propositionalized version of '∀x (Employee(x) → Works(x))' translates specific information regarding known objects. For known instances, like an employee Bob, it would be Employee(Bob) → Works(Bob). In logical inference, this helps determine truth values of statements by checking them against known details about individuals .

Introducing 'Anyone who is not a boss either works or does not get paid' would change the constraints in the logical system, possibly reducing the number of valid models. It specifies conditions for non-bosses affecting correlations between being paid and working, which could invalidate models where non-boss individuals exist contrary to this condition, thus decreasing model count .

The proposition 'everyone works' translated as '∀x Works(x)' is contingent. Based on analysis, KB ∪¬f is satisfiable, showing a model where not everyone works, and KB ∪f is also satisfiable, showing a model where everyone works. Thus, from the knowledge base, both scenarios can be true, meaning 'everyone works' is not necessarily entailed and is contingent .

In resolution proofs, 'If the boss does not invite Heather, then she will be fired' is expressed as ¬Invited(Heather) → Fired(Heather). When the knowledge base establishes the negation of Invited as true due to Heather's non-attendance, this results in the conclusion Fired(Heather) becoming true, resolving with existing knowledge statements .

Using resolution, we can conclude that Heather is going to be fired. The knowledge base establishes that Heather either attended the meeting or was not invited, and if the boss wanted Heather at the meeting, then she was invited. Heather did not attend the meeting, implying she wasn't invited, and since uninvited and unwanted equals being fired, Heather is going to be fired .

The statement 'Every student takes at least one course' can be translated into first-order logic as follows: ∀x (Student(x) → ∃y (Course(y) ∧ Takes(x, y))) where 'Student(x)' indicates x is a student, and 'Takes(x, y)' indicates that student x takes course y .

Conjunctive Normal Form (CNF) is a way of structuring logical formulas such that they are a conjunction of one or more clauses, where each clause is a disjunction of literals. To convert ¬P →¬¬(Q ∨(R ∧¬S)) into CNF, we first interpret the implication: ¬P →¬¬(Q ∨(R ∧¬S)) into ¬¬P ∨ ¬(Q ∨(R ∧¬S)). Then, simplify the double negation: P ∨ ¬(Q ∨(R ∧¬S)). Next, apply De Morgan’s laws to distribute the negation: P ∨ (¬Q ∧ ¬(R ∧¬S)). Continue with the distribution: P ∨ (¬Q ∧ (¬R ∨ S)). Finally, distribute the conjunction within the disjunction: (P ∨ ¬Q) ∧ (P ∨ ¬R ∨ S), which is the CNF form.

You might also like