Способы задания фал.
1. Табличный способ. Из определения ФАЛ следует, что всякая функция алгебры логики задается таблицей истинности, определяющей какое значение (0 или 1) принимает данная функция на всех наборах аргументов.
2. Графический способ. Если набору значений аргументов сопоставить точки n-мерного пространства, то произвольная ФАЛ отn аргументов будет определяться двумя непересекающимися множествами вершинn-мерного куба: множеством вершинТ0, где функция принимает значение 0, и множеством вершин Т1, где она равна 1.
3. Аналитический способ. Для перехода от табличного задания ФАЛ к более удобной аналитической записи используются совершенные дизъюнктивные и совершенные конъюнктивные нормальные формы представления ФАЛ (ДСНФ иКСНФ). Любая ФАЛ может быть записана вДСНФ иКСНФ.
Для получения ДСНФ функции алгебры логики, заданной таблично, необходимо:
1) отметить все наборы аргументов, на которых функция принимает значение 1;
2) выписать конъюнкции аргументов для каждого отмеченного набора. При этом, если аргумент имеет в отмеченном наборе значение 1, он выписывается в соответствующую конъюнкцию без отрицания, в противном случае - с отрицанием;
3) соединить полученные конъюнкции знаком дизъюнкции.
П р им е р 3.1. Пусть табл.3.3. задает некоторую ФАЛ от трех аргументов.
Таблица3.3
|
x1 |
x2 |
x3 |
f(x1x2x3) |
x1 |
x2 |
x3 |
f(x1x2x3) |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
Чтобы получить ДСНФ этой ФАЛ:
1) отмечаются наборы аргументов, где f(x1x2x3)=1;
2) выписываются конъюнкции
;
;
;
.
3) полученные конъюнкции соединяют
знаком дизъюнкции: f(x1,x2,x3)=
.
Полученная аналитическая записьf(x1,
x2,
х3)
называетсянормальной, так как
знак инверсии применяется только к
аргументам, а не к функциям от них, исовершенной, так как каждый ее
конъюнктивный член содержит все n
аргументов.
Обратный переход - от аналитического задания ФАЛ к табличному - выполняется следующим образом:
1) составляется таблица всех возможных наборов аргументов;
2) значения аргументов из каждого набора подставляют непосредственно аналитическую запись ФАЛ, и на основе определений элементарных ФАЛ вычисляется ее значение на каждом наборе;
3) вычисленное значение заносится в таблицу в строку, соответствующую рассмотренному набору.
Все три способа задания ФАЛ взаимно-однозначны. В каждом конкретном случае используются те способы, которые оказываются удобнее в этом случае.
Набор функций алгебры логики называется функционально полным, если любая ФАЛ может быть представлена суперпозицией этого набора. Функционально полный набор ФАЛ обычно называетсябазисом. Минимальным базисом называется такой базис, для которого удаление хотя бы одной из функций, образующих этот базис, лишает его функциональной полноты. Понятие полноты и минимального базиса, является фундаментальными понятиями алгебры логики, имеющими большое теоретическое и прикладное значение. Оказывается, для построения сложных ФАЛ достаточно иметь небольшой набор элементарных функций. Иными словами, устройства ЭВМ, работа которых, как известно, описывается системой ФАЛ, могут быть построены из ограниченного набора элементов, соответствующих некоторому базису. В математической логике разработаны категории полноты, позволяющие определить,является ли данный набор ФАЛ полным, и, следовательно, можно ли из данных элементов построить вычислительную машину или вообще любое
устройство переработки дискретной информации, работа которого может быть описана на языке ФАЛ.
Аппарат алгебры логики позволяет не только находить минимальные наборы полных ФАЛ, но и производить преобразование сложных ФАЛ с целью минимизации количества элементарных базисных ФАЛ, составляющих заданную функцию.Применительно к технике это позволяет строить минимальные по количеству стандартных элементов схемы, способные выполнять требуемые функции.