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

Основы алгебры логики

Основные определения

Определение. Функцией алгебры логики (логической функцией, булевой функцией) n переменных f(x1,…, xn) называется функция, принимающая значения 0 или 1, аргументы которой также принимают значения 0 или 1. Константу 1 по-другому называют истиной, а константу 0 − ложью.

Аргументы логической функции называют логическими (булевыми)

переменными.

Итак, если Существенные и несущественные переменные - student2.ru , то Существенные и несущественные переменные - student2.ru - это логическая функция n переменных.

Булеву функцию n переменных можно задать таблицей истинности вида (табл. 1)

Таблица 1

x1 x2 ... xn-1 xn f(x1,…, xn)
... 0 или 1
... 0 или 1
... 0 или 1
... ... ... ... ... 0или 1
... 0 или 1

Таблица истинности функции n переменных содержит Существенные и несущественные переменные - student2.ru строк, в которых записаны Существенные и несущественные переменные - student2.ru разных возможных наборов значений аргументов функции (такие наборы называются двоичными наборами длины n). Число Существенные и несущественные переменные - student2.ru получается по принципу умножения: чтобы задать двоичный набор длины n нужно выполнить n действий, каждое из которых можно выполнить двумя способами – приписать очередной переменной значение 0 или 1.

Каждому набору значений аргументов можно поставить в соответствие два варианта значений функции на этом наборе – 0 или 1. Таким образом, число различных булевых функций n переменных равно Существенные и несущественные переменные - student2.ru и очень быстро растет с ростом n.

Если n=1, то Существенные и несущественные переменные - student2.ru = 22 = 4; если n = 2, то Существенные и несущественные переменные - student2.ru = 16; если n = 3, то Существенные и несущественные переменные - student2.ru = 256.

Итак, двоичный набор – это упорядоченная энка, элементы которой – цифры 0 или 1. В записи двоичного набора их можно не разделять запятыми.

Всякий двоичный набор Существенные и несущественные переменные - student2.ru можно рассматривать как натуральное число, записанное в двоичной системе счисления, это число называется номером набора. Например, Существенные и несущественные переменные - student2.ru

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

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

Говорят, что функция f(x1,...,xn) существенно зависит от переменной xi ,если существует такой набор Существенные и несущественные переменные - student2.ru значений других аргументов, что Существенные и несущественные переменные - student2.ru . В этом случае переменная xi называется существенной переменной, в противном случае xi называется несущественной (фиктивной) переменной.

Пример. Пусть булевы функции f1(x,y) и f2(x,y), f3(x,y), f4(x,y) заданы таблицей истинности (табл. 2)

Тогда y – фиктивная переменная функции f1, x - фиктивная переменная функции f2, как x, так и y – несущественные переменные функции f3, а

функция f4 существенно зависит от обоих своих аргументов.

Таблица 2

x y f1(x,y) f2(x,y) f3(x,y) f4(x,y)

Наши рекомендации