Logic for Computer Science/Reasoning

This mathematics module is a stub. You can help Wikibooks by expanding it.

The term "reasoning" is used to denote both a cognitive activity and a formal, mathematical one. Traditionally, mathematical reasoning relies on precise rules leading from a set of well-formed statements to a (set of) well-formed, valid conclusion(s). But, many cognitive behaviors considered reasoning do not fall within the descriptive reach of these classical formalisms. To address these, modal logics and other non-classical mathematical formalisms have been devised.

Classical Reasoning

Deduction

Definition (Deductive reasoning is reasoning from a general premise to conclusions directly implied by that premise. For example, if we accepted the axiom that all cows are white, then it logically follows that when one encounters Bessie the cow, Bessie will be white.)

Induction

Definition (Inductive reasoning is the usage of specific conclusions to draw more general premises. For example, if one saw a black dog, it would be inductive reasoning to argue that all dogs are therefore black.)

Non-Classical Reasoning

Modal Logics

Epistemic Reasoning

The phrase "Reasoning about Knowledge", often refers to the application of epistemic logic to multi-agent systems. It has applications in game theory and economics. An example of reasoning about knowledge can be seen in the following scenario: A father has three sons who are playing in the back yard despite the fact that it is muddy. He announces to them "At least one of you has mud on his face. Raise your hand if you know whether you have mud on your face." The children cannot see whether they have mud on their own face but can see whether their brothers have mud on their face. Some or none of the children raise their hands. The father repeats his statement. By the third time he repeats the statement all the children have raise their hand.

Suppose only one child has mud on his face. In this case the child with the mud will see that his brothers are clean and will know that he is the child with mud on his face and he will thus raise his hand the first round. His two brothers, seeing this will see that he was able to discern that he was able to figure out whether he had mud on his face the first round and thus will know that he is the only child with mud on his face and be able to raise their hands.

Suppose two children have mud on their faces. In this case two of the children will see one brother who is clean and one who has mud on his face, and one child will see both of his brothers have mud on their faces. The first time the father answers the question none of the children raise their hand. Because of this each of the muddy children know that the situation cannot be as described in the previous paragraph and they will know that they each have mud on their faces. The clean child, seeing that they were able to discern this will know that he is clean.

Suppose all the children are muddy. In this case they will each see two brothers with dirty faces. In the first round nobody raises their hand. In the second round nobody raises their hand because the situation in the previous paragraph doesn't hold. In the third round all the children raise their hand because the only remaining possibility is that they all have muddy faces.

What is interesting about this is that no new information is being conveyed directly by the fathers statement after he says it the first time. It is only through reasoning about the knowledge of the other brothers that they are able to come to correct conclusion.

A great many logical systems have been concocted to try to address these situations.