If you walk your dog, he'll be happy. If you don't walk him, he'll chew up your furniture. If he's happy or if he chews your furniture, he'll mess up your apartment. If he messes up your apartment, you'll be annoyed. Does your dog mess up your apartment? Are you annoyed at him?

  1. Write the knowledge base given above in propositional logic.
  2. Convert the knowledge base into conjunctive normal form.
  3. Use resolution to prove by contradiction that your dog made a mess. Connect the two clauses to a new clause that the can be collapsed into (see the example figure).

Example figure: Example figure


This is a homework for first order logic. The task itself is easy. Only the third point on the list “prove by contradiction” is a bit more difficult to interpret, as the term prove is not defined exactly in a mathematical context.

In the domain of game theory, to prove something means to find a walk-through for the game. If something was proven, a plan was found to bring the system from the initial state into the goal state. In the case of propositional logic the possible numbers of plans is low, so in most cases it is easy to find a plan. In a real life problem, finding the plan is equal to search in the state space.

At first, the sentences have to converted into boolean expressions:

  • A: Owner walks with dog
  • B: Dog is happy
  • C: Dog chews up the furniture
  • D: Dog mess up the apartment
  • E: Owner is annoyed

Then the rules of the game have to be formalized:

  1. if A then B
  2. if not A then C
  3. if (B or C) then D
  4. if D then E

The rules are equal to the game-mechanics, that means the game engine calculates the future state for a given input. As mentioned above, to prove is equal to finding a plan. That means we have a goal state ("Dog made a mess"), and now it is possible to search with backtracking for a plan which will produce “D=true”.

| improve this answer | |
  • $\begingroup$ I think you're over-complicating this! It's just a list of predicates, which describe a state, and you can show that the dog made a mess without needing a game engine or a planning algorithm. Rules 1 and 2 can be combined to "B or C" (either A is true, then B, or C otherwise), that triggers rule 3 (as "B or C" is true), so D is true, and the fourth rule then leads to E being true, so the dog messes up and the owner is annoyed. $\endgroup$ – Oliver Mason Dec 4 '18 at 17:42
  • $\begingroup$ @OliverMason Rules which are triggering each other are called a forward simulation. It's a term from system theory for describing interconnection between logic elements. The idea of a forward simulation is to feed the system with an input value and the system calculates the output by applying the rules. $\endgroup$ – Manuel Rodriguez Dec 4 '18 at 18:43
  • $\begingroup$ Just for clarification, the predicates you have suggested here do not constitute a first order logic knowledge base. These are simple predicate logic literals. $\endgroup$ – MikeKatz45 Dec 1 '19 at 3:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.