Семинар №3. Алгебра логики

Цель семинара:

Изучить практическое применение алгебры логики в принятии управленческих решений.

План занятия:

Семинар посвящен темам алгебра логики булева алгебра и полнота и замкнутость. На практическое освоение материала выделяется 2 часа.

Задача 1.Доказать эквивалентность формул:

( &(х2Åx3))~( ) .

Решение.

x1 x2 x3 x2Åx3 & x2 x3 x3 x2 & Úx1

Задача 2.Упростим формулы x2x3Úx1 2x3 и x1Ú 1x2Ú 1 2x3Ú 1 2x3x4.

Решение.

1. x2x3Úx1 2x3 = x3(x2Úx1 2) = x3((x2Úx1)&(x2Ú 2)) = (x1Úx2)x3.

2. x1Ú 1x2Ú 1 2x3Ú 1 2x3x4 = x1Ú 1(x2Ú 2 3x4) = x1Ú 1(x2Úx3Ú 2 3x4) = (x1Ú 1)(x1Úx2Úx3Ú 2 3х4) = x1Ú(x2Úx3)Ú( )x4 = x1Ú(x2Úх3Ú( ))(x2Úx3Úx4) = x1Úx2Úx3Úx4.

Задача 3.Пусть функция f(x1, x2, x3) задана таблицей истинности.

x1 x2 x3 f

Запишем ее в виде СДНФ.

Решение.

Наборов, на которых функция равна 1, три: (0, 1, 0), (1, 0, 0) и (1, 1, 1), поэтому f(x1, x2, x3) = x10 & x21 & x30 Úx11 & x20 & x30 Úx11&x21 & x31=

= &x2& Úx1& & Úx1&x2&x3.

Задача 4.Пусть f(x1, x2, x3) = x1 (x2 (x3 ~ x1)). Представить ее в виде СКНФ.

Решение.

Для этого получим таблицу истинности.

x1 x2 x3 x3~x1 x2 (x3~x1) f
1 1 1 1 1 1 1

Функция равна нулю только на наборе (1, 1, 0), поэтому

f(x1 x2 x3)=x1 Úx2 Úx3 =x10Úx20Úx31= Ú Ú x3.

Задача 5.Упростить булевы формулы:

а)¦(х123)= ;

б)¦(x,y,z)=

Решение.

(4 24)
a)¦(х123)= =

б)¦(x,y,z)= =

Задача 6.Представить булеву формулу в базисе {&,ù } и (Ú,ù }.

Решение.

Представим формулу базиса {&,Ú,ù} в базисах {&,ù} и {Ú,ù}, последовательно используя правила де Моргана, а также правило двойного отрицания:

Булев базис { &,Ú,ù } в некотором смысле "избыточен" - при удалении из него операции & или v функциональная полнота полученных систем {&,ù} и {Ú,ù} сохраняется. Однако в представлении { &, Ú, ù} логические функции выражаются более простыми формулами, как это видно из примера. За неизбыточность базисов операций приходится платить избыточностью формул: каждая замена одной операции на другую вносит в формулу лишние отрицания.

Задача 7.Запишем с неопределенными коэффициентами полином Жегалкина для функции трех переменных f(x1, x2, x3) = (01101001) = а0 Å а1х1Å Å а2х2 Å а3х3 Å b1x1x2 Å b2x2x3 Å b3x1x3 Å cx1x2x3. Затем находим коэффициенты, используя значения функции на всех наборах. На наборе (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 Å b2 = b2 = 0; а1 = 1; 0 = а1 Å а3 Å b3 = b3 = 0; 0 = а1 Å а2 Å b1 = b1 = 0; 1 = 1 Å 1 Å 1 Å c; c = 0; f(x1, x2, x3) = x1 Å x2 Å x3.

Наши рекомендации