Понятие о логической функции

В математической логике основными понятиями являются логическая переменная и логическая функция.

Логическими переменными называются знаки (символы), которые принимают различные значения из соответствующей области. Такие переменные будем обозначать, например, буквами латинского алфавита: x₁, x₂,..., x_i, или y₁,y₂,..., y_i, или z₁, z₂,..., z_k. Область значений переменных может быть различной: нуль и единица {0,1}; нуль, плюс единица и минус единица {0,+1,-1}; нуль, единица, два {0,1,2} и др. Если область значений логических переменных содержит два значения, то такие логические переменные называют двоичными или булевыми, если же она содержит три значения, то их называют троичными, а если она содержит четыре более значений, то их называют многозначными переменными. Будем рассматривать только двоичные (булевы) переменные и под выражением “двоичные переменные” будем понимать логические двоичные переменные.

Совокупности значений переменных образуют наборы значений переменных, или просто наборы. Наборы значений логических переменных можно представить в виде двоичных чисел или в виде эквивалентов двоичных чисел. Например, переменные x₁, x₂, x₃, x₄ в зависимости от принимаемых значений образуют наборы: 0000, 0001, 0010,0011,0100,0101,0110,0111,1000,...,1111.

В общем виде набор значений переменных запишем как

,

где (j=1,2,...,n) обозначает конкретное значение переменой x_j и равно либо 0, либо 1. Если каждая переменная принимает два значения, а число переменных равно n, то число различных наборов равно 2ⁿ. Переменные и наборы играют важную роль в понятии “логическая функция”.

Логической функцией называют функцию, зависящую от логических переменных и принимающую значения из того же множества, что и переменные, от которых она зависит. Логические функции двоичных (булевых) переменных принимают одно из двух значений: либо 0, либо 1.

Для обозначения логических функций будем пользоваться записями вида f (x), f (x_n, x_n-1,..., x₂, x₁), y_i(x), z(x), u(x) и другими, где в скобках указываются переменные, от которых зависит логическая функция.

Различные значения переменных логической функции образуют наборы значений этой функции. Наборы значений переменных зависят от порядка расположения переменных, поэтому для однозначного задания наборов введем порядок размещения переменных в наборе. Если не оговорено особо, переменные в наборе будем располагать справа налево в порядке возрастания индексов переменных. Например, набор w_i =1101 означает, что переменных в наборе четыре и переменные x₁=1, x₂=0, x₃= x₄=1.

Совокупность наборов, на которых определена логическая функция, образует область отправления (задания) этой функции. Для логической функции от n переменных эта область содержит 2 различных наборов. Множество значений, на которых определена логическая функция, образует область прибытия. Область прибытия булевых функций содержит два значения: “0” и “1”.

Определим число различных логических функций от n переменных. Из n переменных можно образовать 2ⁿ различных наборов.

На каждом наборе логическая функция может принимать значение либо 0, либо 1 независимо от ее значения на других наборах. Отсюда число различных логических функций определяется как произведение 2ⁿ чисел 2, т.е. N=2^{2 n} (таблица 2.1).

Таблица 2.1

Таблица соответствия логических функций, зависящих от n переменных

Число различных логических функций возрастает с увеличением числа переменных и уже для функций пяти переменных составит огромное число - 4 294 966 296.

Всякая функция от меньшего числа переменных автоматически входит в число функций от большего числа переменных. Логическая функция f (x_n,..., x₂,x₁,) существенно зависит от переменной x_i, если имеет место соотношение

f (x_n,..., x_i+1, 0, x_i-1,..., x₁)¹ f (x_n,..., x_i+1, 1, x_i-1,..., x₁,).

В противном случае говорят, что функция f (x_n,..., x₂,x₁,) не зависит существенно от переменной x_i, т.е. x_i есть фиктивная переменная.

Функции n переменных, которые существенно зависят от всех переменных, называются невырожденными функциями от n переменных. Функции n переменных, которые фактически зависят от меньшего числа переменных, называются вырожденными.

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

Наряду с функциями, значения которых определены на всех 2ⁿ наборах, нередко возникает необходимость рассмотрения функций, значения которых определены только для части наборов. Наборы переменных, на которых значение функции не определено, будем называть неопределенными наборами. Логические функции, значения которых определены только на части наборов переменных, будем называть неполностью определенными функциями. Значения функций на условных наборах могут выбираться произвольным образом. В связи с этим неполностью определенную логическую функцию можно рассматривать как семейство полностью определенных логических функций, отличающихся друг от друга значениями на условных наборах. Если логическая функция содержит k условных наборов, то ей соответствует семейство, состоящее из 2^k различных полностью определенных функций, рабочие и запрещенные наборы которых полностью совпадают.