Логическое представление функций выбора

План лекции №3

1. Представление функций выбора Y=C(X) с помощью логических функций.
2. Оценка количества функций выбора.
3. Аналитическая запись логических функций и их упрощение.
4. Логические представления функций выбора для двухэлементных множеств.
5. Примеры упрощения логических представлений функций «ЧБК»

Логическое представление функции выбора = векторная логическая функция y векторного логического аргумента x
y = F(x)
( Размер векторов = n = число элементов в множестве выбора G )

F_i(x) - скалярная логическая функция векторного логического аргумента x, выражающая (в полной форме) условия выбора варианта № i.

Преобразование предъявления в векторный логический аргумент

Множество выбора : G = {1,2, ... ,n}

Ему соответствует x = g0 = [1 1 1 ... 1]

Пусть предъявление X = {2,3,n-1}, тогда x = [0 1 1 0 ... 1 0].

Преобразование результата выбора Y в векторную логическую форму y : производится аналогично :

Пусть результат выбора Y = {3, n-1, 2}, тогда y = [0 1 1 0 ... 1 0].

Полная и сокращенная формы логического представления функции выбора

y_i = F_i(x) , i = 1..n

F₁(x) = F₁(x₁, x₂,. . .,x_n) = x₁*f₁(x₂, x₃,. . .,x_n)

F_i(x) = F_i(x₁, x₂,. . .,x_n) = x_i*f_i(x₁, x₂, …, x_(i-1),x_(i+1), ..., x_n) , i = 2..n-1

F_n(x) = F_n(x₁, x₂,. . .,x_n) = x_n*f_n(x₁, x₂,. . .,x_n-1)

y_i = x_i * f_i[x₁, x₂, ... , x_(i-1), x_(i+1), ... , x_n] , i = 1..n

Составление таблиц логических функций

Каким логическим вектором отображается пустое множество?

Произвольно выбираются логические функции f_i от (n-1) аргумента (i = 1..n): N(n) = (N_i)ⁿ

N(3) = 2^{3*(2^-2)}

N(3) = 2¹²     N(4) = 2³²

Количество всевозможных комбинаций значений аргументов составляет 2^(n-1).

На каждом из таких наборов функция может принять 2 значения. Количество таких функций: N_i = 2^{(2^(n-1))}.

• Составить таблицу функции
• Записать в виде конъюнкций условия, при которых логическая функция равна "1"
• Произвести дизъюнктивное объединение этих условий
• Произвести упрощение дизъюнктивной формы
• Произвести сокращение поглощающихся дизъюнктов
• (Произвести минимизацию дизъюнктивной нормальной формы)

Правила для сокращения записи логических функций

(z) OR (z) = z     (дублирование)

(g * z) OR (G * z) = z     (объединение)

(g * z) OR (g) = g     (поглощение)

Далее большими буквами обозначается отрицание малых

(G) OR (g * z) = G OR z     (поглощенное объединение)

{ G = (G * z) OR (G) }

Пример составления логического представления функции выбора

Пусть функция выбора C имеет следующее описание:

G = {1, 2, 3, 4}; C({i}) = {i}, C({i,j}) = {min[i,j]}; C({i,j,k}) = {i,j,k}/{max[i,j,k]}; C(G) = {1}.

Табличное лог_представление функции выбора:

Условия выбора первого варианта

Условия выбора второго варианта

Условия выбора третьего варианта

n = 2 : N = [2^(2)]^2 = 16

Функция "хочу пить":
Множество выбора { к, ч, б }
Словесное логическое описание
Если чай есть, то выбираем чай, Если чая нет, но есть кофе, то выбираем кофе.

Пример упрощения логических функций «ЧБК»

Функция "хочу пить":
Множество выбора { к, ч, б }

Формальное логическое представление:

F₁ = abC \/ abc = ab     F₂ = AbC \/ abC \/ Abc \/ abc = b     F₃ = Abc = Abc

f₃(a,b)= Ab = Ab     f₁(b,c) = bC \/ bc = b     f₂(a,c)= AC \/ aC \/ Ac \/ ac = 1

f₁(x,y) = xY \/ xy = x     (x=b, y=c)

f₂(x,y) = 1     (x=a, y=c)

f₃(x,y) = Xy     (x=a, y=b)