This tutorial offers corrected exercises on Boolean algebra and Karnaugh diagrams or tables.
Exercise 1
The K-Gaz company decides to recruit employees internally for its subsidiary.
For each employee, we define the following Boolean variables:
- a=1 if he has more than 5 years of seniority in the company
- b=1 if it has a BTS-IG
- c=1 if he is fluent in English
The human resources department decides that employees can apply:
- that meet the three conditions
- or who have less than 5 years of seniority but who master English
- or who do not speak English who have a BTS-IG
Here are the questions:
- Give the HR criteria in Boolean expression
- Represent the expression by a Karnaugh table
- Simplify it
- Find the result by calculation using backspace
- Conclude on the simplified version
Question 1
Question 2
A 1 is marked each time an element of the boolean expression is true.
Question 3
To simplify the expression, we look in the table at the squares of 4 elements or the rectangles of two elements (not necessarily connected) of which at most one literal changes between row and column.
For example, the green rectangle, only the literal b changes, so äc does not change (ä considering the row and c considering both columns). In the red square, in column, only b changes (a changes in rows, and c changes in column).
We deduce the simplified expression.
Question 4
The technique of backtracking consists in going back little by little on the results according to the lack of computational element. For example, after factoring by b, we will have ac + C_barre. In view of the formula, it is obvious that ac + äc + c_barre would be necessary for this expression to be equal to 1.
Thus, each time that a computational element is missing to arrive at its finality, it is possible to transform the preceding calculation lines by adding already existing elements or by multiplying by 1 such as for example b + b_barre to reach its ends.
Here is the final reasoning:
Question 5
Deduces from this that the HR accepts applicants who have a BTS-IG or who have less than 5 years of seniority but master English.
Exercise 2
The person in charge of the computer park of a company considers the acquisition of new computers. To equip himself, this manager goes to a computer equipment sales company that offers predefined configurations (computer and peripherals).
We define the criteria:
a: the configuration includes a DVD burner;
b: the configuration includes a printer;
c: the configuration includes a scanner.
Equipment constraints exclude the configuration with a DVD burner but without a scanner, as well as the configurations without a burner and without a printer.
Here are the questions:
- Give the boolean expression E translating the exclusion conditions
- Set the Karnaugh table of E
- Translate and say if a (b_barre) c is accepted
- Determine an expression of F representing the conditions of acceptance.
- Translate the simplified version of F.
1- The expression is E=a(c_bar)+ä(b_bar)
2- The Karnaugh table of E is
3- the expression means equipped with a DVD burner and a scanner but without a printer. She is not present in the Karnaugh of E so she is allowed
4- Here is the Karnaugh of E
In green c varies. In red b varies.
5- The simplified expression gives either a burner and a scanner; either no burner and a printer.
Exercise 3
The director of human resources (HRD) of a town hall must recruit a person for a job concerning the circulation of cars in the city center.
To make his choice, the HRD sets up three selection criteria concerning knowledge in computer science, experience in the field concerned and the follow-up of a specific training course.
The recruited person must:
- have computer knowledge and experience in the relevant field;
- or not have computer knowledge, but have followed a specific training course;
- or not have experience in the field concerned, but have followed a specific training course.
We define the following three Boolean variables a, b and c:
- a = 1 if the person has computer knowledge, a = 0 otherwise;
- b = 1 if the person has experience in the field concerned, b = 0 otherwise;
- c = 1 if the person has followed a specific training course, c = 0 otherwise.
Here are the questions:
- Describe the situation corresponding to the product ab / c
- Define the Boolean expression E corresponding to the HRD selection criteria.
- Find a simplified writing of the Boolean expression E.
- Explain the simplified version.
1- ab / c means that the person has computer knowledge (a = 1) and experience in the field concerned (b = 1), but has not followed a specific training course (c = 0).
2- E = ab + / ac + bc
3- Karnaugh's table and its simplified model is as follows
4- This means: The person has computer knowledge (a = 1) and experience in the field concerned (b = 1) OR has followed a specific training course (c = 1).
