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

Мы уже знаем, что логическая функция может быть представлена:

а) словесно: если Х₁=1 и X₂=1, то Y=1;

б) таблично: в виде таблицы истинности, которая содержит n+m столбцов и 2ⁿ строк (n -число входов или аргументов, m -число выходов);

i	X1	X2	Y

в) с помощью карт Карно (или диаграмм Вейча), которые представляют собой разновидность табличной формы задания логической функции;

г) числовым способом: когда функция задается в виде набора (множества) десятичных чисел, соответствующих номерам набора аргументов, при которых функция принимает значение 1;

Например, функция ИЛИ для аргументов Х₁, Х₂;

Y	X1	X2

Y={1,2,3}_X1X2.

=0 Переменные указывают порядок

=1 формирования битов двоичного числа.

=2

=3 Для логической функции И Y={3}_X1X2;

д) аналитически: в виде алгебраического выражения.

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

Введем понятие терма. Термом обозначим функцию:

где: к = 0,1,...,n,

b_k - константа 0 или 1.

При любом фиксированном значении переменной X_k=a_k справедлива формула:

_

Действительно: 0⁰=0=1; 1¹=1;

_

0¹=0; 1⁰= 1=0.

Используя введенное обозначение, запишем функцию И (конъюнкцию) n логических переменных:

Эта функция принимает значение 1 только при одном наборе значений переменных (а₁,а₂,...,а_n), для которого выполняется условие a_k=b_k, для всех остальных наборов функция принимает значение 0.

Например: __ __

F(X₁,X₂,...,X₅)=X₁×X₂×X₃×X₄×X₅=X⁰₁×X¹₂×X⁰₃×X¹₄×X¹₅

принимает значение 1 только при одном наборе переменных (0,1,0,1,1).

Конъюнкция, в которую входят все переменные (аргументы логической функции) в прямой или инверсной форме, называется минтермом.

Минтерм обозначим C¹_i , где i-номер единственного набора, на котором C¹_i=1 (пример выше: 01011₂=11₁₀, следовательно - C¹₁₁).

Алгебраически минтерм представляют в виде конъюнкции, в которую в прямой форме входят все переменные, имеющие в данном наборе значение 1, и в инверсной форме все переменные, имеющие в данном наборе значение 0.

Для логической функции двух переменных можно составить следующие минтермы:

i	X1	X2	__ __ C^10=X1×X2	__ C^11=X1×X2	__ C^12=X1×X2	C^13=X1×X2

Аналогично можно рассмотреть функцию ИЛИ (дизъюнкцию) n логических переменных:

Логическая функция ИЛИ принимает значение F(×)=1, если хотя бы одна переменная Х^bi_i=1. Следовательно, существует только один набор значений переменных, для которых выполняется условие a_k ¹ b_k, при котором функция принимает значение 0.

Например, функция: __ __

F(X₁,X₂,X₃,X₄,X₅)=X₁ÚX₂ÚX₃ÚX₄ÚX₅=X¹₁ÚX¹₂ÚX¹₃ÚX⁰₄ÚX⁰₅

принимает значение 0 только при одном наборе (0,0,0,1,1).

Дизъюнкцию, в которую входят все переменные в прямой или инверсной форме, называют макстермом.

Макстерм имеет обозначение C⁰_i , где i-номер единственного набора, при котором C⁰_i=0.

Рассмотренный выше пример: 00011₂ = 3₁₀, следовательно - C⁰_3.

Рассмотрим макстермы двух переменных:

i	X1	X2	C^00=X1Ú X2	__ C^01=X1ÚX2	__ C^02=X1ÚX2	__ __ C^03=X1ÚX2

Макстерм представляется в виде дизъюнкции, в которую в прямой форме входят все переменные, имеющие на данном наборе (при котором C⁰_i=0) нулевые значения, и в инверсной форме - все переменные, имеющие на данном наборе значение 1.

Аналогично функциям И, ИЛИ можно ввести функцию И-НЕ для n переменных:

_____ ____________________ ________________

Эта функция, являясь инверсией конъюнкции n переменных, принимает значение 0 только на одном наборе переменных, для которого a_k=b_k. Для всех остальных наборов эта функция равна 1.

И, наконец, можно определить функцию ИЛИ-НЕ:

_____ ___________________ ________________

Эта функция принимает значение 1 только на одном наборе значений переменных, для которого a_k¹b_k, на всех остальных наборах эта функция равна 0.

Дата добавления: 2015-07-11