Аналитическое представление ФАЛ.




 

Существует несколько способов заданий логических функций. Табличный метод не является компактным. Проще выглядит аналитическая запись в виде формул. Пусть мы имеем двоичный набор < >, на котором задана ФАЛ. Сопоставим ему число i, определяемое следующим образом:

i=

Число i будем называть номером набора < >.

Рассмотрим функцию , определяемую следующим соотношением:

(1.22)

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

Теорема 1.3 Любая таблично заданная ФАЛ может быть задана в следующей аналитической форме:

(1.23)

где - множество номеров наборов, на которых функция обращается в единицу.

Действительно, если на каком-либо наборе функция ¦=()=1, то вследствие того, что в правой части 1.23 всегда найдется элемент, равный единице (), у которого соответствует номеру рассматриваемого набора. Если же на наборе i функция ¦=()=0, то в правой части не найдется ни одного элемента, равного единице, т.к. 0v0v... v 0=0. Т.о. каждому набору i, для которого =1 соответствует элемент =1, а наборам i, на которых =0 не соответствует ни одного элемента =1. Поэтому таблица истинности однозначно отображается аналитической записью вида 1.23 (дизъюнкция минтермов).

В теории мы воспользовались дизъюнкцией минтермов. Посмотрим, нельзя ли вместо дизъюнкции использовать какую-либо другую функцию. Для того чтобы выполнялось соотношение 1.23, необходимо чтобы при обращении любого в 1 все выражение обращалось в 1, а при обращении всех в 0 все выражения также становились равными 0. Сформулированные условия можно записать в виде таблицы:

 

Ñ
     
     
     
    ?

 

где значком Ñ условно обозначена некоторая неизвестная операция.

Знак "?" в последней строке таблицы соответствует такой комбинации значений , которая никогда не может встретиться (i¹j). Поэтому искомая функция (операция) Ñ может быть определена двумя различными способами.

Если в определяющую таблицу вместо “?” поставить ‘1’, то Ñ будет дизъюнкцией (Ñ=V). Этот случай рассматривался в теореме 1.3. Если же знак “?” заменить нулем (имеется в виду логическая переменная равная нулю), то Ñ будет функцией сложения по модулю два (Ñ= ).

Следствие Любая таблично заданная ФАЛ может быть представлена в следующей аналитической форме:

(1.24)

Представление функции в виде 1.23 называется дизъюнктивным представлением, а в виде 1.24- полиноминальным представлением.

Для получения представления другого типа рассмотрим функцию и определяется как:

(1.25)

Такие функции называют характеристическими функциями нуля, или макстермы. Из соотношения 1.22 и 1.25 видно, что

=

 

Теорема 1. 4 Любая таблично заданная ФАЛ может быть задана в следующей аналитической форме:

(1.26)

где - количество номеров наборов, на которых функция ¦ обращается в 0. Доказательство этой теоремы аналогично доказательству теоремы теореме 1.3

Вместо конъюнкции в соотношении 1.26 можно взять любую функцию, которая удовлетворяет следующим условиям:

 

Ñ
    ?
     
     
     

 

При записи в первой строке вместо "?" нуля, получаем конъюнкцию, рассмотренную в теореме 1.4 (Ñ=&), а при замене "?" единицей - функцию эквивалентности (Ñ= º)

 

Следствие Любая таблично заданная ФАЛ может быть представлена в аналитической форме:

(1.27)

Представление ФАЛ в виде 1.26 называется конъюнктивным представлением.

 

Определение. Логические переменные, объединенные знаком V или & называются термом.

Определение. Ранг терма r определяется количеством переменных, входящих в данный терм.

Введем в рассмотрение степень аргумента х, которую будем обозначать

(1.28)

при этом

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-02-16 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: