Browse course

Tutorial 6. Logical conditionals

Exercise sheet
Boolean conditional

We’ve interpreted the conditional symbol Implication using the Booleans NOT and OR. But we could also have directly defined a Boolean function IF with the following truth-table:

Note that X IF Y is the conditional from the value of X to the value of Y to make the reading of the Boolean align with its natural reading.

Find a representation of this Boolean function using only NOT and AND. That is find a Boolean expression exp in the two variables X and Y, which contains only the Boolean functions NOT and AND, and which meets the specification that for all values of X and Y, we have:

exp = X IF Y.

Verify your work! That is don’t just provide an expression, but show that for all values of X and Y the above equation holds.

Equivalence

Remember the truth-table for XNOR from the last exercises set:

Find a formula representation of this Boolean truth-function using only the propositional variables p and q and the connectives Conjunction and Implication ! That is, find such formula satisfying these constraints, which meets the assignments v of truth-values to p and q, we have:

v(A) = v(p) XNOR v(q).

Verify your work! That is don’t just provide a formula, but show that for each assignment the above equation holds.

Conditional inferences

Check the following conditional inferences for deductive validity using SAT-solving. You can use truth-tables or resolution, as you prefer.

  1. (RAIN Implication WIND), Negation RAIN Therefore () Negation WIND

  2. (RAIN Implication WIND) Therefore ( Negation WIND Implication Negation RAIN)

  3. ( Negation RAIN Implication RAIN) Therefore RAIN

  4. (RAIN Implication ( SUN Implication RAINBOW)) Therefore ((RAIN Conjunction SUN) Implication RAINBOW)

  5. Negation (RAIN Implication WIND) Therefore RAIN

Document your work carefully, that is explain each step you’re carrying out, and why the work you did shows that the inference in question is valid or invalid.

Valid inference and conditionals

There’s a deep connection between deductively valid inference in Boolean logic and material conditionals, which is given by the following important equivalence:

P₁, P₂, … vDash C  if and only if   not-SAT{(P₁ Conjunction P₂ Conjunction … ) Implication C}

  1. A logical formula A is called a logical truth iff for all assignments v of truth-values to its propositional variables, the formula is true, i.e. v(A) = 1. Verify that the simple formula

    (RAIN Disjunction Negation RAIN)
    is a logical truth in this sense.

  2. Rephrase the right-hand side of above equivalence in terms of the logical truth rather than unsatisfiability.

  3. Give an argument that the above equivalence is true.

    Hint: To do so, you need to use the general form of the reduction of valid inference to unsatisfiability, which we’ve discussed in the lecture

    P₁, P₂, … vDash C  if and only if   not-SAT { P₁, P₂, … , Negation C }
    Think about what the latter condition means for the truth of the corresponding conditional.

Chaining

Consider the following KB:

  • RAIN Implication CLOUDS
  • (CLOUDS Conjunction SNOW) Implication STORM
  • RAIN Implication PUDDLES
  • PUDDLES Implication HUMID
  • HUMID Implication CLOUDS
  • SUN Implication DRY
  • (WIND Conjunction SNOW) Implication DRIFTING

We add to this KB the following two facts:

RAIN, SNOW

  1. Run the forward-chaining and the backward-chaining algorithm to show that we can derive STORM from the KB. That is, describe the steps you’d take for each algorithm one-by-one, and why at some point you hit the termination condition.

  2. Use the example to illustrate how forward-chaining can find shorter derivations than backward-chaining.

  3. Use both forward and backward-chaining to show that we can’t derive DRIFTING from the KB using the facts. Does one algorithm outperform the other?

Planning

We’ve made things a more difficult for IA   by introducing a third block into the puzzle:

Adjust our planning solution to accommodate the more complicated setup. That is:

  1. Determine how we need to adjust the language to accommodate the third block.

  2. Which rules do we need to add to our a KB to accommodate the third block.

  3. Represent the initial setup state and the goal state in the language.

  4. Find a model that satisfies the KB, as well as the setup and goal state. Then read off a course o action. You don’t need to do this formally—using resolution or chaining—but just find such a model using human intelligence.

Discussion

Check out the Wason selection task on Wikipedia.

Some researchers have argued that the experiment shows that people don’t reason with the material conditional in this case. Do you agree? Why?