10 - Deduction as Search

Summary

An intelligent agent must be aware of the world it is operating in. This awareness comes mainly via perception. Human beings use the senses of sight, sound, and touch to update themselves. However, the entire world is not perceptible to any of us. Our senses have limitations. We cannot hear the dog whistle, or see the bacteria living on our skin or the mountain on the other side of the world. But through science and communication we know about the worlds beyond our sensory reach. Telescopes from Galileo to James Webb have delivered spectacular images of the universe, some taken in the infrared band in the spectrum. We augment whatever we know by making inferences. The conclusions we draw may be sound or they may be speculative yet useful. Evolution has preserved in us both kinds of inference making capability.

The world is dynamic and has other agencies making changes in the world too. If we observe something we may guess the cause or intention behind it. This kind of speculation is called abduction. The conclusion is possibly true, maybe even likely. If we see the local bully striding towards us, we may suspect ill intent on his part, and take evasive action. Better safe than sorry. If we develop a cough and fever, we may fear Covid and isolate ourselves from others. When we observe a few white swans, we may conclude that all swans are white. This is called induction. Neither abduction nor induction is always sound. Conclusions we draw may not always hold. But they are eminently useful.

In this chapter we study deduction, a form of inference that is sound. The conclusions that we draw using deduction are necessarily true. The machinery we use is the language of logic and the ability to derive proofs. We highlight the fact that behind deduction the fundamental activity is searching for a proof.

Logic and mathematics are often considered to be synonymous. Both are concerned with truth of statements. In this chapter we confine ourselves to the family of classical logics, also known as mathematical logics, in which every sentence has exactly two possible truth values – true and false. Nothing in between. No fuzzy concepts like tall and dark. Is a person whose height is 176 centimetres tall? What about 175 then? And 174? When does she become not tall? Or modalities like maybe.