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

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

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

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

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

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

( &(х ₂Å x ₃))~().

Решение.

x 1	x 2	x 3	x 2Å x 3	&	x 2 x 3	x 3 x 2	&	Ú x 1

 

Задача 2. Упростим формулы x ₂ x ₃Ú x _{1 2} x ₃ и x ₁Ú ₁ x ₂Ú _{1 2} x ₃Ú _{1 2} x ₃ x ₄.

Решение.

1. x ₂ x ₃Ú x _{1 2} x ₃ = x ₃(x ₂Ú x _{1 2}) = x ₃((x ₂Ú x ₁)&(x ₂Ú ₂)) = (x ₁Ú x ₂) x _3.

2. x ₁Ú ₁ x ₂Ú _{1 2} x ₃Ú _{1 2} x ₃ x ₄ = x ₁Ú ₁(x ₂Ú _{2 3} x ₄) = x ₁Ú ₁(x ₂Ú x ₃Ú _{2 3} x ₄) = (x ₁Ú ₁)(x ₁Ú x ₂Ú x ₃Ú _{2 3} х ₄) = x ₁Ú(x ₂Ú x ₃)Ú() x ₄ = x ₁Ú(x ₂Ú х ₃Ú())(x ₂Ú x ₃Ú x ₄) = x ₁Ú x ₂Ú x ₃Ú x _4.

Задача 3. Пусть функция f (x ₁, x ₂, x ₃) задана таблицей истинности.

x 1	x 2	x 3	f

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

Решение.

Наборов, на которых функция равна 1, три: (0, 1, 0), (1, 0, 0) и (1, 1, 1), поэтому f (x ₁, x ₂, x ₃) = x ₁⁰ & x ₂¹ & x ₃⁰ Ú x ₁¹ & x ₂⁰ & x ₃⁰ Ú x ₁¹& x ₂¹ & x ₃¹=

= & x ₂& Ú x ₁& & Ú x ₁& x ₂& x _3.

Задача 4. Пусть f (x ₁, x ₂, x ₃) = x ₁ (x ₂ (x ₃ ~ x ₁)). Представить ее в виде СКНФ.

Решение.

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

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 ₁ x ₂ x ₃)= x ₁ Ú x ₂ Ú x ₃ = x ₁⁰Ú x ₂⁰Ú x ₃¹= Ú Ú x ₃.

 

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

а) ¦(х₁,х₂,х₃)= ;

б) ¦(x,y,z)=

Решение.

(4 24)

a)¦(х₁,х₂,х₃)= =

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

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

Решение.

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

 

 

 

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

 

Задача 7. Запишем с неопределенными коэффициентами полином Жегалкина для функции трех переменных f (x ₁, x ₂, x ₃) = (01101001) = а ₀ Å а ₁ х ₁Å Å а ₂ х ₂ Å а ₃ х ₃ Å b ₁ x ₁ x ₂ Å b ₂ x ₂ x ₃ Å b ₃ x ₁ x ₃ Å cx ₁ x ₂ x ₃. Затем находим коэффициенты, используя значения функции на всех наборах. На наборе (0, 0, 0) f (0, 0, 0) = 0, с другой стороны, подставив этот набор в полином, получим f (0, 0, 0) = а ₀, отсюда а ₀ = 0. f (0, 0, 1) = 1, подставив набор (0, 0, 1) в полином, получим: f (0, 0, 1) = а ₀ Å а ₃, т.к. а ₀ = 0, отсюда а ₃ = 1. Аналогично, f (0, 1, 0) = 1 = а ₂, f(0, 1, 1) = 0 = а ₂ Å а ₃ Å b ₂ = b ₂ = 0; а ₁ = 1; 0 = а ₁ Å а ₃ Å b ₃ = b ₃ = 0; 0 = а ₁ Å а ₂ Å b ₁ = b ₁ = 0; 1 = 1 Å 1 Å 1 Å c; c = 0; f (x ₁, x ₂, x ₃) = x ₁ Å x ₂ Å x ₃.