Существенная и несущественная переменные. 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Существенная и несущественная переменные.



Пусть задана булева функция

f(x1,x2,…,xi-1,xi,xi+1,…xn).

Будем говорить, что функция f существенно зависит от переменной xi, если:

f(x1,x2,…,xi-1,xi,xi+1,…xn)¹ f(x1,x2,…,xi-1,xi+1,…xn).

Переменная называется существенной, если при ее отсутствии меняется значение функции.

Будем говорить, что функция f не существенно зависит от переменной xi, если:

f(x1,x2,…,xi-1,xi,xi+1,…xn)=f(x1,x2,…,xi-1,1,xi+1,…xn).

В случае если одна из переменных является не существенной, то функция зависит от n-1 переменных и соответственно:

f(x1,x2,…,xi-1,xi,xi+1,…xn)=g(x1,x2,…,xi-1,xi+1,…xn).

Не существенная (фиктивная) переменная может быть удалена.

Аналогично, если добавить не существенную переменную в некоторую функцию, то из функции n-1 переменных можно получить функцию n переменных, которая является результатом добавления не существенной переменной; удаление или добавление фиктивных переменных является эффективным приемом для преобразования функций к одинаковому виду, то есть все функции можно записать в виде функций n переменных.

Например f(x1x2x3)=g(x1x2)

 

Примеры логических функций.

Функции одной переменной:

х ноль один тожд. обратн.
         
         

Ф-ция 0 и 1 задает константы, поэтому для них х – несущественная переменная. Тождественная ф-ция возвращает х, а обратная – обратное значение х.

Функции 2-х переменных

Ф-ция переменная х        
переменная х        
название обозначение        
ноль          
конъюнкция ×, Ù, &        
           
х          
           
у          
сложение по модулю 2 +, D, Å        
дизъюнкция Ú        
стрелка Пирса ¯        
эквивалентность ~, º        
не у          
           
не х          
имплекация ®, Þ, É        
штрих Шеффера |        
один          

 

Представление булевых функций формулами.

Функции называются выражением, описывающие суперпозицию элементарных функций.

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

f(x1x2). Функция зависящая от переменных формулой глубины 1. Соответственно функция f(f1,f2..fn) будет иметь глубину k если она зависит от функций глубины k-1.

Для записи формул используют знаки операций(конъюнкция, сложение по модулю 2, Стрелка Пирса, импликация и тд).

Обычно для булевых функций используется инфиксная запись.

Функция каждому набору аргументов ставит в соответствие значение и следовательно может служить способом описания функции. Табличное представление функции является единственным способом. Для задания функции формулой можно использовать различные записи.

 

Представление булевых функций формулами. Примеры.

Функции называются выражением, описывающие суперпозицию элементарных функций.

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

f(x1x2). Функция зависящая от переменных формулой глубины 1. Соответственно функция f(f1,f2..fn) будет иметь глубину k если она зависит от функций глубины k-1.

Для записи формул используют знаки операций(конъюнкция, сложение по модулю 2, Стрелка Пирса, импликация и тд).

Обычно для булевых функций используется инфиксная запись.

Функция каждому набору аргументов ставит в соответствие значение и следовательно может служить способом описания функции. Табличное представление функции является единственным способом. Для задания функции формулой можно использовать различные записи.



Поделиться:


Последнее изменение этой страницы: 2017-02-21; просмотров: 509; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.198.34.207 (0.005 с.)