Главная   Онлайн инструменты по математической логике   Мат. логика теория   Как считает компьютер?   Схемы для ЭВМ    

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

Определение булевой функции
Элементарные булевы функции
Задание булевых функций посредством элементарных
Существенные и несущественные переменные
Эквивалентные функции
Основные эквивалентности
Функциональная полнота
Нормальные формы
Совершенные нормальные формы
Минимизация ДНФ методом Квайна
Карты Карно
Полином Жегалкина
Высказывания
Предикаты
Кванторы
Определение формальной теории
Исчисление высказываний
Теорема о дедукции. Полнота ИВ
Автоматическое доказательство теорем
Метод резолюций в ИВ
Определение алгоритма
Машина Тьюринга
Рекурсивные функции
Алгоритмически неразрешимые задачи
Алгоритмы и их сложности



     Булева функция y=f(x1,x2 ... xn) существенно зависит от переменной xk, если существует такой набор значений a1,a2 ... ak-1, ak+1, ak+2 ... an, что f(a1,a2 ... ak-10, ak+1, ak+2 ... an) ≠ f(a1, a2 ... ak-11, ak+1, ak+2 ... an).
     В этом случае xk называют существенной переменной, в противном случае xk называют несущественной (фиктивной) переменной. Другими словами, переменная является несущественной, если ее изменение не изменяет значения функции.
     Пример: Пусть булевы функции f1(x1,x2) и f2(x1,x2) заданы следующей таблицей истинности:

x1x2f1(x1,x2)f2(x1,x2)
0001
0101
1010
1110

     Для этих функций переменная x1 — существенная, а переменная x2 — несущественная.
     Очевидно, что булевы функции не изменяют свои значения путем введения (или удаления) несущественных переменных. Поэтому, в дальнейшем булевы функции рассматриваются с точностью до несущественных переменных (в примере можно записать: f1(x1,x2)=x1, f2(x1,x2)=¬x1).

@ 2010 - 2016 tablica-istinnosti.ru Рейтинг@Mail.ru