2014-02-09
979
Аналитическое представление функции алгебры логики (ФАЛ) в виде дизъюнкции конечного числа минтермов.
Любая таблично заданная ФАЛ может быть представлена аналитически в виде дизъюнкции конечного числа минтермов (конъюнктивных термов – ЛФ, связывающих все переменные в прямой или инверсной форме знаком конъюнкции), т е. нормальной дизъюнктивной формой (НДФ — объединение минтермов различных рангов, включая ранг, равный 1) и совершенной нормальной дизъюнктивной формой (СНДФ — объединение минтермов только максимального ранга); на каждом из минтермов функция равна 1:
f(x1, x2,..., xn) = F1 Ú F2 Ú... ÚFn = S Fi
1
i – номера наборов, на которых функция равна 1, S – знак дизъюнкции, объединяющий все минтермы Fi.
Например, записать в аналитическом виде функцию, заданную таблично:
| x1 | x2 | x3 | f(x1, x2, x3) | x1 | x2 | x3 | f(x1, x2, x3) |
ФАЛ может быть представлена аналитически в виде дизъюнкций конечного числа минтермов, на каждом из которых функция равна 1. СНДФ (дизъюнкция минтермов максимального ранга) находится следующим образом: формируется дизъюнкция произведений (минтермов – конъюнкций) всех аргументов с количеством слагаемых, равным числу наборов, на которых функция равна 1; в каждом минтерме над аргументом, значение которого равно 0, ставится знак отрицания:
f(x1, x2, x3) = F0(0, 0, 0) + F3(0, 1, 1) + F4(1, 0, 0) =`x1×`x2×`x3 +`x1×x2×x3 + x1×`x2×`x3
Любая таблично заданная ФАЛ может быть представлена аналитически в виде конъюнкции конечного числа макстермов (дизъюнктивных термов – ЛФ, связывающих все переменные в прямой или инверсной форме знаком дизъюнкции) т. е. нормальной конъюнктивной формой (объединение макстермов, включающее макстермы различных рангов) и совершенной нормальной конъюнктивной формой (СНДФ — объединение макстермов только максимального ранга); на каждом из макстермов функция равна 0:
f(x1, x2,..., xn) = H1 Ù H2 Ù … Ù Hn = ÕHi.
0
Для ранее рассмотренного примера, используя правила двойственности, СНКФ (конъюнкция макстермов максимального ранга)находится следующим образом: формируется произведение дизъюнкций (макстермов) всех аргументов с количеством сомножителей, равным числу наборов, на которых функция равна 0; в каждом макстерме над аргументом, равным 1 в данном наборе, ставится знак отрицания:
f(x1, x2, x3) = (x1 + x2 +`x3)&(x1 +`x2 + x3)&(`x1 + x2 +`x3)&(`x1 +`x2 + x3) &(`x1 +`x2 +`x3)
H1 H2 H5 H6 H7
Каждая ФАЛ, в общем случае, может иметь несколько НДФ или НКФ, но только одну СНДФ и одну СНКФ. Нормальные формы можно получить из совершенных после возможных упрощении выражений.
Пример 1. Записать в аналитической виде функцию, заданную таблицей истинности:
| x1 | x2 | x3 | f(x1, x2, x3) | x1 | x2 | x3 | f(x1, x2, x3) |
CНДФ, записанная по единицам функции:
f(x1, x2, x3) = F1(0, 0, 0) + F2(0, 0, 1) + F3(0, 1, 1) + F4(1, 0, 0) + F5(1, 1, 0) =`x1 ×`x2 ×`x3 +`x1 ×`x2 × x3 + x1 ×`x2 ×`x3 + x1 ×`x2 ×`x3 +`x1 × x2 ×`x3
Пример 2. Записать в аналитическом виде функцию, заданную таблицей истинности:
| x1 | x2 | x3 | f(x1, x2, x3) | x1 | x2 | x3 | f(x1, x2, x3) |
CНДФ, записанная по единицам функции:
f(x1, x2, x3) = F1(0, 0, 1) + F3(0, 1, 1) + F4(1, 0, 0) + F5(1, 0, 1) =`x1 ×`x2 × x3 +`x1 × x2 × x3 + x1 ×`x2 ×`x3 + x1 ×`x2 × x3
ФАЛ может быть представлена аналитически в виде конъюнкции конечного числа макстермов, на каждом из которых функция равна 0.
СНКФ, записанная по нулям функции:
f(x1, x2, x3) = (x1 + x2 + x3)&(x1 +`x2 + x3)&(`x1 +`x2 + x3)&(`x1 +`x2 +`x3)
H0 H2 H6 H7
