Цель семинара:
Изучить практическое применение алгебры логики в принятии управленческих решений.
План занятия:
Семинар посвящен темам алгебра логики булева алгебра и полнота и замкнутость. На практическое освоение материала выделяется 2 часа.
Задача 1. Доказать эквивалентность формул:
(
&(х 2Å x 3))~(
).
Решение.
| x 1 | x 2 | x 3 | x 2Å x 3 | & | x 2  x 3
| x 3 x 2
| & | Ú x 1 |
|
Задача 2. Упростим формулы x 2 x 3Ú x 1 
2 x 3 и x 1Ú 
1 x 2Ú 
1 
2 x 3Ú 
1 
2 x 3 x 4.
Решение.
1. x 2 x 3Ú x 1 2 x 3 = x 3(x 2Ú x 1 
2) = x 3((x 2Ú x 1)&(x 2Ú 2)) = (x 1Ú x 2) x 3.
2. x 1Ú 1 x 2Ú 1 2 x 3Ú 1 2 x 3 x 4 = x 1Ú 1(x 2Ú 
2 3 x 4) = x 1Ú 
1(x 2Ú x 3Ú 
2 3 x 4) = (x 1Ú 1)(x 1Ú x 2Ú x 3Ú 
2 
3 х 4) = x 1Ú(x 2Ú x 3)Ú(
) x 4 = x 1Ú(x 2Ú х 3Ú(
))(x 2Ú x 3Ú x 4) = x 1Ú x 2Ú x 3Ú x 4.
Задача 3. Пусть функция f (x 1, x 2, x 3) задана таблицей истинности.
| x 1 | x 2 | x 3 | f |
Запишем ее в виде СДНФ.
Решение.
Наборов, на которых функция равна 1, три: (0, 1, 0), (1, 0, 0) и (1, 1, 1), поэтому f (x 1, x 2, x 3) = x 10 & x 21 & x 30 Ú x 11 & x 20 & x 30 Ú x 11& x 21 & x 31=
= 
& x 2& 
Ú x 1& 
& Ú x 1& x 2& x 3.
Задача 4. Пусть f (x 1, x 2, x 3) = x 1 (x 2 (x 3 ~ x 1)). Представить ее в виде СКНФ.
Решение.
Для этого получим таблицу истинности.
| x 1 | x 2 | x 3 | x 3~ x 1 |  x 2 (x 3~ x 1)
| f |
| 1 | 1 | 1 | 1 1 | 1 | 1 |
Функция равна нулю только на наборе (1, 1, 0), поэтому
f (x 1 x 2 x 3)= x 1 
Ú x 2 Ú x 3 
= x 10Ú x 20Ú x 31= Ú Ú x 3.
Задача 5. Упростить булевы формулы:
а) ¦(х1,х2,х3)= 
;
б) ¦(x,y,z)= 
Решение.
|
= 
б)¦(x,y,z)= = 
Задача 6. Представить булеву формулу 
в базисе {&,ù } и (Ú,ù }.
Решение.
Представим формулу базиса {&,Ú,ù} в базисах {&,ù} и {Ú,ù}, последовательно используя правила де Моргана, а также правило двойного отрицания:
Булев базис { &,Ú,ù } в некотором смысле "избыточен" - при удалении из него операции & или v функциональная полнота полученных систем {&,ù} и {Ú,ù} сохраняется. Однако в представлении { &, Ú, ù} логические функции выражаются более простыми формулами, как это видно из примера. За неизбыточность базисов операций приходится платить избыточностью формул: каждая замена одной операции на другую вносит в формулу лишние отрицания.
Задача 7. Запишем с неопределенными коэффициентами полином Жегалкина для функции трех переменных f (x 1, x 2, x 3) = (01101001) = а 0 Å а 1 х 1Å Å а 2 х 2 Å а 3 х 3 Å b 1 x 1 x 2 Å b 2 x 2 x 3 Å b 3 x 1 x 3 Å cx 1 x 2 x 3. Затем находим коэффициенты, используя значения функции на всех наборах. На наборе (0, 0, 0) f (0, 0, 0) = 0, с другой стороны, подставив этот набор в полином, получим f (0, 0, 0) = а 0, отсюда а 0 = 0. f (0, 0, 1) = 1, подставив набор (0, 0, 1) в полином, получим: f (0, 0, 1) = а 0 Å а 3, т.к. а 0 = 0, отсюда а 3 = 1. Аналогично, f (0, 1, 0) = 1 = а 2, f(0, 1, 1) = 0 = а 2 Å а 3 Å b 2 = b 2 = 0; а 1 = 1; 0 = а 1 Å а 3 Å b 3 = b 3 = 0; 0 = а 1 Å а 2 Å b 1 = b 1 = 0; 1 = 1 Å 1 Å 1 Å c; c = 0; f (x 1, x 2, x 3) = x 1 Å x 2 Å x 3.
