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

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

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

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

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

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

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

Решение.

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

Задача 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₃) задана таблицей истинности.

x1	x2	x3	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₁)). Представить ее в виде СКНФ.

Решение.

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

x1	x2	x3	x3~x1	x2 (x3~x1)	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₃.