АЛГЕБРАИЧЕСКОЕ ПРЕДСТАВЛЕНИЕ ЛОГИЧЕСКИХ ФУНКЦИЙ

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

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

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

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

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

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

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.

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

Аналогично можно рассмотреть функцию ИЛИ (дизъюнкцию) 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 .}

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

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

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

_____ ____________________ ________________

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

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

_____ ___________________ ________________

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