Понятие о минтермах и макстермах

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 10Следующая ⇒

Для получения этих форм (СКНФ и СДНФ) вводятся понятия минтермов (конституанта 1) и макстермов (конституанта 0).

Для представления логической функции F в виде СДНФ необходимо составить сумму произведений значений логической функций F_i и минтермов - m _i, причем число слагаемых n равно числу строк в таблице истинности, т. е.

F =

Минтерм (m_i), — это логическое произведение всех переменных, причем переменные, равные нулю, записываются с инверсией.

Минтерм — это функция n переменных, равная единице только на одном на­боре.

Минтерм получают как конъюнкцию (логическое умножение) n переменных, которые входят в него в прямом виде (без изменения), если значение данной переменной в наборе X_i = 1, и с отрицанием (инверсное значение), если Х_i = 0.

При n переменных имеется 2ⁿ минтермов т₀, т₁,..., m_R, где R = 2ⁿ - 1.

Все минтермы двух переменных приведены в табл. 3.10

Таблица 3.10- Минтермы для двух переменных F9 = X1 X2
X1	Х2	F9	fi	Минтермы	Макстермы
			f0=1	m0 =	M0 = X1 v X2
			f1=0	m1 = Х2	М1 = X1 v
			f2=0	m2 = Х1	М2 = v X2
			f3=1	m3 = X1 Х2	M3 = v

Значения функции F₉, соответствующие, согласно таблице истинности, каждо­му i - му набору, обозначены как f₀, f₁, f₂, f₃.

Напоминание. F₉ = X₁ X₂ -тождественность переменных. Функция имеет значение 1, когда обе переменные имеют одинаковое значение и 0 когда обе переменные имеют разные значения.

Представление функции F₉ в СДНФ явля­ется дизъюнктивной суммой минтермов, соответствующих наборам переменных, для которых f_i = 1:

т.е. F₉ = f₀∙m₀ + f₁∙m₁ + f₂∙m + f₃∙m = 1 ∙m₀ + 0 ∙m₁ + 0 ∙m₂ + 1 ∙m₃ = m₀ ∙ m₃ = ∙ + X₁ ∙Х₂

Пример 3.6 Запись логической функции F в виде СДНФ для f(x_l,x₂,x₃)=x₁x₂x₃+(x_l+x₂)(x_l+ ₃)

Таблица 3.11

m₁ = _{1 2 3}; m₂ = _{1 2} x₃; m₃ = ₁ х_{2 3}; m₄ = ₁ х₂ х₃;

m₅ = х_{1 2 3}; m₆ = x_{l 2} x₃; m₇ =x₁ х_{2 3}; m₈ = x₁ x₂ x₃.

Следовательно, логическая функция F, заданная таблицей истинности 3.11, имеет следующую СДНФ: F = m_l f₁ + m₂ f₂ + m₃ f₃ + m₄ f₄ + m₅ f₅ + m₆ f₆ + m₇ f₇ + m₈ f₈ =

= m_l 0 + m₂ 0 + m₃ 1 + m₄ 0 + m₅ 1 + m₆ 1 + m₇ 1 + m₈ 1 = m₃ 1 + m₅ 1 + m₆ 1 + m₇ 1 + m₈ 1 =

= ₁ x_{2 3} + x_{1 2 3} + x_{1 2} x₃ + x₁ x_{2 3} + x₁ x₂ x₃ -запись функции F в СДНФ

Таким образом, для записи функции в виде СДНФ можно использовать следующее правило: следует записать столько дизъюнктивных членов, представляющих собой конъюнкции (произведения) всех переменных, сколько раз функция принимает значение 1, причем переменные, равные нулю, записываются с инверсией.

Для представления логической функции F в виде СКНФ необходимо составить произведение сумм значений логической функции F_i и макстермов - М _i причем число произведений n равно числу строк в таблице истинности, т. е.

F =

Макстерм М _i — это логическая сумма всех переменных, причем переменные, равные 1, записываются с инверсией.

Макстерм — это функция n переменных, равная нулю только на одном наборе.

Макстерм получают как дизъюнкцию (суммирование) всех переменных, которые входят в него в пря­мом виде, если значение X_i = 0, или в инверсном виде, если значение Х_i = 1.

Число макстермов равно 2ⁿ, для функции двух переменных они приведены в табл. 3.10.

Представление функции F₉ в СКНФ записывается в виде:

F₉ = (f₀ + M₀)(f₁ + M₁)(f₂ + M₂)(f₃ + M₃) = (1 + M₀)(0 + M₁)(0 + M₂)(1 + M₃) =

= M₁M₂ = (X₁ + )( + X₂)

Поясним на примере табл. 3.12 аналитическую запись функции трех перемен­ных в СДНФ и СКНФ.

Для записи функции Р в СДНФ требуется дизъюнктивно сло­жить те минтермы, для которых функция равна единице:

Используем строки -2, 4, 5, 7 и 8, тогда P = X₃ X₃ X₁ X₁ X₂ X₁ X₂ X₃

Для записи функции Р в СКНФ необходимо записать конъюнкцию макстермов, для которых функция равна нулю:

Используем строки -1, 3 и 6, тогда P = (X₁ X₂ X₃) (X₁ X₃) ( X₂ )

По этому способу производится запись в СДНФ и СКНФ функций с произволь­ным числом переменных.

Пример 3.7 Запись логической функции F в виде СКНФ для f(x_l,x₂,x₃)=x₁x₂x₃+(x_l+x₂)(x_l+ ₃).

Для таблицы 3.12 можно записать следу­ющие макстермы:

М₁ = х₁ + х₂ + х₃; М₂ = х₁ + х₂ + ₃; М₃ = х₁ + ₂ + х₃; М₄ = х₁+ ₂ + ₃

М₅ = ₁ + х₂ + х₃ М₆ = ₁ + х₂ + ₃ М₇ = ₁ + ₂ + х₃ М₈ = ₁+ ₂+ ₃

Следовательно, логическая функция F, заданная табли­цей истинности, описывается следующей СКНФ:

F = (М_l+f₁)(М₂ +f₂)(М₃+f₃)(М₄+f₄)(М₅+f₅)(М₆+f₆)(М₇+f₇)(М₈+f₈) =

=(х₁+х₂+х₃+0)∙(х₁+ х₂+ ₃+0)∙(х₁+ ₂+x₃+1)∙(х₁+ ₂+ ₃+0)∙

∙( ₁+х₂+х₃+1)∙( ₁+х₂+ ₃+1)∙( ₁+ ₂+х₃+1)∙( ₁+ ₂+ ₃+1) =

= (х₁ + х₂ + х₃)∙(х₁ + х₂ + ₃)∙(х₁+ ₂ + ₃) - запись функции F в СKНФ

Таким образом, для записи функции в виде СКНФ ис­пользуют следующее правило: следует записать столько конъюнктивных членов, представляющих собой дизъюн­кции (суммы) всех переменных, сколько раз функция при­нимает значение 0, причем переменные, равные единице, записываются с инверсией.

Познавательные статьи:



Формы дистанционного обучения

Передача мяча двумя руками снизу

Значение правильной осанки для жизнедеятельности человека

Основные ошибки при выполнении передач мяча на месте