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

Декартово произведение множеств

Свойства операций

1. А Ç А=А - идемпотентность операции пересечения.

2. А Ç В = В ÇА - коммутативность операции пересечения.

3. А Ç(В Ç С) = (А ÇВ) ÇС - а ссоциативность операции пересечения.

4. Свойства 1-3 имеет также операция È.

5. А Ç (В È С) = (А Ç В) È (А Ç С) - дистрибуция операции пересечения по отношению к операции объединения. Справедливо также свойство дистрибуции для операции объединения относительно операции пересечения.

6. Дополнение дополнения множества равно множеству, т.е. ~ ~ А=А.

7. Равенства де Моргана ~(А Ç В) = ~ А È ~В, ~ (А È В) = ~А Ç ~В.

8. Для любого множества А Ç U = А, А Ç Æ = Æ, A È Æ = A, A È U = U,
А Ç ~A = Æ; A È ~A = U; A \ A = Æ.

Представленные в свойствах равенства используют для преобразования формул. Если в формуле заменить множество равным ему множеством, получится формула, равносильная исходной. Таким образом, можно в формулах удалять одинаковые члены (свойство 1), выносить за скобки или раскрывать скобки (свойство 4) и т.п.

Пример. (А Ç В Ç С) È(А Ç В Ç~ С) = (А Ç В) Ç(~ C È C) = A Ç B.

Декартовым произведением множеств А и В называют множество М, содержащее все возможные пары, в которых на первом месте стоит элемент из А, на втором – элемент из В. Формально АхВ = М,
М ={(a_i, b_j)| a _i Î A, b_j Î B }. Элементы декартова произведения являются кортежами.

Пример. Пусть А={1,2,b} и B={a, b, 2}, тогда AxB={(1, a), (2, a), (b, a),(1, b), (2, b), (b, b), (1, 2), (2, 2), (b, 2)}.

Если |A| =na и |B|=nb, то |AxB|=na×nb

Аналогично вводится произведение трех, четырех и т.д. множеств как множество троек, четверок и так далее, в которых на первом месте записан элемент первого множества, на втором - элемент второго и т.д.. Если все сомножители в произведении одинаковы, оно называется декартовой степенью: А = А ¹; АхА=А ²; АхАхА=А ³; АхАх А...А = А ^k, k>0.

Результат декартова произведения не является подмножеством универсального множества.

Для декартова произведения не выполняются условия коммутативности и ассоциативности. Действительно, множество АхВ содержит в качестве элементов пары (а_i,b_j), а множества ВхА — пары (b_i,a_j), т.е. результирующие множества содержат различные элементы. Элементы произведения (АхВ)х С - пары ((a_i,b_j), c _k), а Ах(ВхС)пары (a_i, (b_j,c_k)). Элементами множества АхВхС являются тройки (a_i,b_j,c_k). Значит, (АхВ)х С ¹ А х (В х С) ¹ А х В х С.

Булевой (логической) переменной называют переменную, принимающую значение из множества {0,1}. Название «логическая» следует из того, что её значения трактуются чаще всего как «истина» (для 1) и «ложь» (для 0).

Функцией алгебры логики (переключательной или булевой функцией) от n переменных называют однозначное отображение множества всевозможных наборов значений n булевых переменных в множество {0,1}.

Такую функцию можно представить в виде таблицы из n +1столбцов и 2 ⁿ строк. Эта таблица называется таблицей истинности.

Наборы значений переменных располагают в лексикографическом порядке (в порядке возрастания), как в примере в табл. 1.1 для n = 3.

Число всевозможных наборов значений переменных составляет N= 2 ⁿ. Число различных функций, которые могут быть записаны в таблице, равно 2 ^N.

Таблица 1.1

x1	x2	x3	f

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

Для приведённого примера функцию можно представить как Т1={001,010,100, 111}.

Третий способ описания – представление функций в виде вектора. Так как порядок перечисления наборов входных переменных установлен, то достаточно указать только столбец функции. Для приведенного примера это будет вектор <01101001>.

Определение. Булева функция существенно зависит от переменной х_i, если найдутся два набора значений переменных, отличающиеся только i -й компонентой, на которых значения функции не совпадают. Переменная, от которой функция существенно не зависит, называется несущественной или мнимой для данной функции.

Пример. Пусть функция на наборах значений переменных <00110> и <01110> равна, соответственно, 1 и 0. Эта функция существенно зависит от второй переменной, потому что её значение на этих наборах определяется только значением этой переменной.

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

Таблица 1.2

x		x	`x

Среди четырех функций одной переменной, приведенных в табл.1.2, две функции, первая и последняя, являются константами (не зависящими ни от одной переменной). Их обозначают соответственно как 0 и 1. Вторая функция повторяет переменную. Третья противоположна ей, называется инверсией и обозначается ` x.

Пусть [ n ] – число функций, существенно зависимых от n переменных. Тогда [1] = 2, [0] = 2. Для любого n это число можно подсчитать по рекуррентной формуле

[ n ] = 2 ^N - [0] - C_n ¹[1] - C_n ²[2] -.... C_n^{n -1}[ n -1].

Здесь N=2 ⁿ, первая компонента – число функций от n переменных, из которого последовательно для i =0,1,..., n -1 вычитаются произведения числа функций, существенно зависимых от i переменных, на число способов, которыми можно выбрать i переменных из n.

Так, для n = 2 [2]=16-2-2×2=10. Для n =3 [3]=256-2-3×2-3×10=218.

Дата добавления: 2014-01-07