1
The Concept of Logic

CONCEPTS COVERED IN THIS CHAPTER.-

Logic is essential, not only for computer operations, but also for artificial intelligence. The concepts of logic outlined in this chapter are therefore of fundamental importance.

Beginning with syllogistic reasoning, the exploration examines propositional calculus and its fundamental operations: negation, conjunction, disjunction, conditional, biconditional, as well as their combinations.

The last section focuses on the tools of deductive reasoning.

References: [EXE 59, MEN 64, QUI 84, WOO 80, LIP 83].

1.1. Syllogisms

Syllogisms are a type of logical reasoning that dates back to the time of Aristotle in Ancient Greece. They are constructed from logical propositions, known as premises, which are linked by a conclusion. The conclusions are derived from the logical of these propositions, allowing the deduction of a conclusion from the given premises. In what follows, the example of a classic syllogism will be considered:

1. all men are mortal,
2. all Greeks are men,
3. therefore, all Greeks are mortal.

The representation of such a logic is termed "Barbara's syllogism", named after a figure in medieval logic who popularized it. In the above example, there are two premises and a conclusion. The first premise is represented by (i), the second by (ii) and the conclusion by (iii).

The described syllogism is considered valid because it respects the rules of formal logic. The conclusion follows necessarily from the two premises and cannot be false if the premises are true. Indeed, each premise of a syllogism must be evaluated according to its truth value to determine whether the conclusion that follows from it is also true or false. In the example, TRUE or FALSE (a truth value) can be assigned to each premise; then it is said that a proposition is a statement which takes one and only one truth value.

EXAMPLE 1.1.-

Some illustrations:

• "The sky is blue,"
• "Money cannot buy happiness,"
• "The house is burning and the firefighters are not there,"
• "Computer scientists are all crazy,"

are "propositions".

• "Eat your soup!,"
• "Good heavens!"
• "Where are they all running?"

do not correspond to propositions.

A syllogism, such as the one considered above, can be represented by the following notation:

• all Xs are Ys (major premise),
• all Zs are Xs (minor premise),
• so, all Zs are Ys (conclusion).

And especially,

The structure is also known as the "canonical form" of a syllogism. The terms X, Y and Z represent categories or classes of things (identified objects), and the syllogism explores the logical relationship between these categories. The canonical form of a syllogism facilitates highlighting the logical structure of reasoning and verifying its validity using the rules of formal logic. Note that a proposition can be placed in one of the following four categories, as shown in Table 1.1.

Table 1.1. Categories of propositions

A Universal and affirmative e.g. "all men are mortals" E Universal and negative e.g. "no man is mortal" I Particular and affirmative e.g. "some men are mortal" O Particular and negative e.g. "some men are not mortal"

Note that a syllogism is composed of three propositions, each belonging to one of the four classes of propositions (A, E, I and O). The middle term connects the two premises of the syllogism, and there are four possible figures depending on the position of this term. The number of possible categories for a syllogism is 43 = 64 possible combinations (four categories for each of the three propositions). Furthermore, depending on the position of X, Y, Z in the premises, there are four classes of syllogisms (see Figure 1.1). The number of categories of syllogisms then becomes 43x4 = 256. For each possible combination of premises, there are two possible formulations (A implies B or B implies A), effectively doubling the number of categories of syllogisms: 512.

Figure 1.1. Syllogism classes

In summary, there are 512 possible categories of syllogisms, but the number of admissible syllogisms is smaller due to the presence of "rules of reasoning".

EXAMPLE 1.2.-

Some illustrations:

• A syllogism with two negative premises is not valid. In a valid syllogism, if one of the two premises is negative, the conclusion must be negative.
• In a valid syllogism, if both premises are affirmative, then the conclusion must be affirmative.
• A syllogism is not valid if it contains two particular premises.

These rules, some of which are presented above, actually reduce the number of valid forms of syllogisms to 19.

As previously discussed, syllogisms follow a general form:

(premise 1, premise 2) implies (conclusion).

We can generalize and acknowledge that syllogisms can involve more than two premises, as demonstrated in Lewis Caroll's "kangaroo argument".

EXAMPLE 1.3.-

The premises:

1. The only animals in this house are cats.
2. Any animal can become a favorite animal that loves to watch the moon.
3. When I hate an animal, I avoid it.
4. No animal is carnivorous unless it prowls at night.
5. No cat fails to kill mice.
6. No animal pleases me, except those in this house.
7. Kangaroos cannot become pets.
8. Only carnivores kill mice.
9. I hate animals that I do not like.
10. Animals that roam at night always like to look at the moon.

Conclusion: I always avoid kangaroos.

The objective of the chapter is to provide an overview of the mechanisms for reasoning based on the manipulation of mathematical concepts.

According to N. Bourbaki (Elements of the History of Mathematics):

We consider that the intervention of metamathematics in the presentation of logic and mathematics can and must be reduced to the very elementary part which deals with the handling of operator symbols and deductive criteria.

1.2. Elementary operations of propositional calculus

1.2.1. Negation

Consider the following propositions P and Q:

P: Amiens is in France.

Q: it is false that Amiens is in France.

The proposition Q is derived from the proposition P by prefixing the phrase "it is false that" to it. Q is regarded as the negation of P, denoted as ¬P. The symbol "¬" represents negation and can thus be interpreted as "it is false that". The truth table illustrating negation is simple (see Figure 1.2).

Figure 1.2. Negation truth table

Expressing negation in a literary manner often poses difficulties. While the previous example, where ¬P translates to "Amiens is not in France" is straightforward, more complex cases exist. To illustrate such complexity, consideration will be given to a few examples.

Beginning with the first:

EXAMPLE 1.4.-

P: all integers are real numbers.

Q1: some integers are not real numbers.

Q2: no integer is a real number.

Which of Q1 and Q2 represents the negation of P?

After reflection, it becomes evident that P and Q2 can be false simultaneously. Thus, Q2 is not the negation of P. Conversely, Q1 represents ¬P.

Here is a second example:

EXAMPLE 1.5.-

P: all angles can be trisected (i.e. divided into three equal parts) using only the ruler and the compass (notoriously wrong!).

Q1: no angle can be trisected using only the ruler and compass.

Q2: there is at least one angle that cannot be trisected using only the ruler and compass.

What is the negation of P, Q1 or Q2? P is false because it is impossible to trisect an angle of 37° with only a ruler and compass.

Q1 is false because we can trisect an angle of 180° with a ruler and compass (see Figure 1.3).

Figure 1.3. Trisection of an angle of 180°

It is therefore Q2 which is the negation of P.

It should be noted that difficulties often arise when propositions contain words such as "All," "Some" or similar expressions. However, as will be discussed later in this chapter, these difficulties can be resolved by using quantifiers and the rules associated with them.

1.2.2. Conjunction

A conjunction is a logical connector that combines two propositions to form a third one, using the word "and" to link clauses. The conjunction of two propositions P and Q is denoted by P ?...