Skip to main content

Subsection 8.6.1 Introduction

It often makes sense to divide complex problems into two or more simpler/smaller ones. We call this approach divide and conquer.

Divide and conquer can be a useful technique in constructing proofs.

Suppose that we are asked to prove: P  (Q  R)

We can divide it into two parts: We can prove that P  Q and, separately, possibly using different techniques, prove that P  R.

We use divide and conquer all the time when we write nontrivial programs.

Consider the chess-playing robot REEM-A.

REEM-A has cameras. It can see the board and observe the moves made by its opponent. It has a problem-solving engine that knows how to play winning chess. And it has actuators that enable it to move its own piece (and push the timer) once it has chosen a move.

To design REEM-A, it makes sense to break the problem down into at least these three pieces:

  1. Scan the physical board and build an internal representation of which pieces are where.

  2. Analyze the current board configuration and choose a next move.

  3. Move the chosen piece to the correct location and then push the timer.

Very different algorithms (techniques) can then be used to solve each of those (slightly) smaller problems.

Exercises Exercises

1.

Suppose that we want to prove that Tracy can get a job. We have the following premises (involving the ability to graduate first):

[1] ∀x (Graduate(x) → Job(x))

[2] ∀x ((FinancialOK(x) ∧ ReqsOK(x)) → Graduate(x))

[3] ∀x ((LibOK(x) ∧ TuitionOK(x) ∧ FeesOK(x) ∧ AthlOK(x)) → FinancialOK(x))

[4] ∀x ((¬Borrowed(x) ∨ AllPaid(x)) → LibOK(x))

[5] ∀x ((StudentPaid(x) ∨ ScholarshipPaid(x)) → TuitionOK (x))

[6] ∀x ((AthPaid(x) ∨ ¬AthCard(x)) → AthlOK x))

[7] ∀x ((Science(x) ∧ Rhetoric(x) ∧ Math(x) ∧ Social(x) ∧ Major(x)) → ReqsOK(x))

[8] ∀x (EnglishMajReqs(x) → Major(x))

[9] ∀x (CSMajReqs(x) → Major(x))

……

There are likely hundreds of rules that could play a part in determining whether we can prove our goal:

Job(Tracy)

Imagine trying to find a proof by reasoning backward from our goal. Very early in this process, there’s a chance to apply the Divide and Conquer strategy. There will be other opportunities as well. Which premise first (assuming reasoning backwards from the goal) suggests the use of Divide and Conquer?

  1. Premise [1]

  2. Premise [2]

  3. Premise [3]

  4. Premise [4]

  5. Premise [7]

Answer.
Correct answer B.
Solution.
Explanation: We observe that premise [1] would allow us to prove Job(Tracy) if we could first prove Graduate(Tracy). But there’s no opportunity to split the process there. But then we get to premise [2]. Now it’s clear that we can attempt to prove (separately) that the financial requirements have been met and that the academic requirements have been met. We set those two up as subgoals.