2.4.2 Примеры решения задач

Задача 1. Какая из функций является операцией на соответствующем множестве? Определить арность операции. Рассмотреть следующие функции:

а) транзитивное замыкание бинарного отношенияR(на множестве бинарных отношений);

б) (на множестве положительных действительных чиселR₊; на множестве действительных чиселR; на множестве отрицательных действительных чиселR_ );

в) векторное произведение векторов пространства (на множестве векторов пространства);

г) скалярное произведение векторов пространства (на множестве векторов пространства).

Решение. а) транзитивное замыканиебинарного отношенияRявляется унарной операцией на множестве бинарных отношений, поскольку любому бинарному отношению ставит в соответствие бинарное отношение;

б) функция является унарной операцией на множествах положительных действительных чиселR₊и действительных чиселR, так как любому положительному действительному числу ставит в соответствие также положительное действительное число, а любому действительному числу ставит в соответствие действительное число. Вместе с тем, функцияне замыкает множество отрицательных действительных чиселR_,поскольку любому отрицательному действительному числу ставит в соответствие положительное действительное число, не принадлежащее множествуR _-;

в) векторное произведение векторов является бинарной операцией на множестве векторов пространства. В самом деле, векторным произведением двух произвольных векторов также является вектор;

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

Задача 2. Проиллюстрировать на примере некоммутативность операций: а) композиции преобразований типаконечного множества А; б) композиции элементарных функций.

Решение. а) Проиллюстрируем некоммутативность операции преобразования конечного множества на примере задачи 2 из пункта 2.3.2. В самом деле, для преобразований множества:

;

композициями являются преобразования

;.

Очевидно, что .

б) Рассмотрим функции и. Пусть обе функции имеют типR→R. Тогда их композиции возможны в любом порядке.

Композиция функций представляет собой подстановку функцииfв функциюg, т.е..

Композиция есть функция, полученная подстановкой функцииgв функциюf, т.е..

Таким образом, , а композиция функций – некоммутативная операция.

Задача 3. Доказать, что бинарная логическая операция «штрих Шеффера» не обладает свойством:

а) ассоциативности;

б) идемпотентности.

Решение.а) Логическая операция «штрих Шеффера» определяется следующей таблицей истинности (таблица 2).

Таблица 2 – Таблица истинности операции «штрих Шеффера»

х	у	х|y
0	0	1
0	1	1
1	0	1
1	1	0

Докажем, что не выполняется равенство . С этой целью сравним таблицы истинности формули(таблица 3):

Таблица 3 – Таблица истинности формули

х	у	z			х|y
0	0	0	1	1	1	1
0	0	1	1	1	1	0
0	1	0	1	1	1	1
0	1	1	0	1	1	0
1	0	0	1	0	1	1
1	0	1	1	0	1	0
1	1	0	1	0	0	1
1	1	1	0	1	0	1

Результаты, полученные в пятом и седьмом столбцах (выделены жирным шрифтом) предыдущей таблицы, не совпадают, следовательно, .

Тем самым, доказано, что «штрих Шеффера» не является ассоциативной бинарной операцией.

б) «Штрих Шеффера» не обладает свойством идемпотентности. В этом легко убедиться, сравнивая таблицы истинности логических формул и х:

х	х|х
0	1
1	0

В самом деле, х|хх.