Материал: 5540

Определите, чему равны образы и прообразы чисел 2, 3, 4.

Решение. Образом числа 2 np1G (на оси абсцисс) при соответствии G является единственное число 2 np2G (на оси ординат). Образ числа 3 при соответствии G есть множество всех действительных чисел отрезка [1, 3], а образ числа 4 – число 2.

Прообразом числа 2 np2G (на оси ординат) при соответствии G будет множество всех действительных чисел отрезка [2, 4] np1G (на оси абсцисс), прообразом числа 3 при соответствии G – число 3, а прообраза числа 4 при соответствии G не существует.

Пример 1.11. Каковы свойства соответствия между множеством N натуральных чисел и множеством M2n степеней двойки:

Решение. Соответствие G взаимно однозначно:

–всюду определено, так как np1G = N;

–сюръективно, поскольку np2G = M2n ;

–функционально, так как любому n N соответствует единственный

образ 2n 1 M 2n ;

– характеризуется единственностью прообраза, так как для любого

Задача 1.14. Каковы свойства соответствия G между множеством N натуральных чисел и множеством M 2n натуральных чётных чисел:

G N M 2n ; G (n, 2n) | n N , 2n M 2n .

1.5 Функции и отображения

Функцией называется функциональное соответствие. Если функция f устанавливает соответствие между множествами А и В, то говорят, что функция имеет тип А → В (обозначается f : А → В).

Каждому элементу а из области определения функция f ставит в соответствие элемент b из области значений. Это обозначается f(a) = b. Элемент а – аргумент функции, элемент b – значение функции на а.

26

Отображением А в В называется всюду определённая функция f : А → В. Отображением А на В называется всюду определённое при этом сюръективное функциональное соответствие f : А → В.

Отображение типа А → А часто называют преобразованием множества А. Функция типа А → А, являющаяся отображением А на А,

называется перестановкой на А. Функции f и g равны, если:

–их области определения – одно и то же множество А;

–для любого а А f(a) = g(a).

Функция типа f : A1 A2 … An → В называется n-местной. В этом случае принято считать, что функция имеет n аргументов: f(a1, …, an)

Если соответствие, обратное к функции f : А → В, является функциональным, то оно называется функцией, обратной к f (обозначается f--1). Для функции f : А → В обратная функция существует тогда и только тогда, когда f является взаимно однозначным соответствием между своими областями определения и значений.

Пусть даны функции f : А → В и g : B → C. Функция h : А → С называется композицией функции f и g (обозначается f ◦ g), если имеет место равенство

h(x) = g(f(x)), где х А.

Часто говорят, что функция h получена подстановкой f в g. Для многоместных функций f : Аm → В, g : Bn → C возможны различные варианты подстановки f в g, дающие функции различных типов. Например, при m = 3 и n = 4 функция h = g(x1, f(y1, y2, y3), x3, x4) имеет шесть аргументов и тип В А3 В2 → С.

Функция, полученная из f1, ..., fn некоторой подстановкой их друг в друга и переименованием аргументов, называется суперпозицией f1, ..., fn. Выражение, описывающее эту суперпозицию и содержащее

27

функциональные знаки и символы аргументов (и, разумеется, скобки), называется формулой.

Способы задания функции:

–графиком;

–таблицей;

–формулой, описывающей функцию как суперпозицию других (исходящих) функций;

–рекурсивной вычислительной процедурой. Например, функция f(x) = 1 ∙ 2 ∙ 3 ∙ ... ∙ (х – 1) ∙ х = х! описывается рекурсивной вычислительной процедурой, задаваемой следующими правилами:

1) f(0) = 1; 2) f(x + 1) = f(x) ∙ (х + 1).

Пример 1.12. Таблица выигрышей лотереи устанавливает

соответствие G между парами чисел из N N = N2 (серия, номер выигравшего билета) и множеством выигрышей М, т.е. G N2 М. Является ли заданное соответствие функцией?

Решение. Соответствие G N2 М, задаваемое таблицей выигрышей, является функциональным, так как для каждой указанной пары из N2 (серии, номера билета) определён конкретный (единственный) выигрыш из М. Таким образом, данное соответствие есть двухместная функция f: N N → M. Функция такого типа не всюду определена, значит не является отображением. Более того, как правило, число выигравших билетов (мощность области определения np1f) больше перечня наименований выигрышей (мощность области значений np2f), поэтому данная функция не обладает единственностью прообраза. В силу

сказанного f не является взаимно однозначным соответствием.

Пример 1.13. Функции f и g имеют тип f : А3 → В, g: В4 → С. Какой тип имеют функции h1 и h2, являющиеся композициями f и g:

28

Задача 1.15. Функции f и g имеют тип f : А2 → В, g: В5 → С. Какой тип имеют функции h1 и h2, являющиеся композициями f и g:

а) h1 = g(х1, f(y1, y2), f(z1, z2), x4, x5); б) h2 = g(х1, х2, f(y1, y2), x4, f(z1, z2));

в) h3 = g(f(y1, y2), x2, f(z1, z2), f(u1, u2), x5)?

Глава 2. БУЛЕВА АЛГЕБРА

Формальная логика в своём развитии прошла два основных этапа. Основанием деления на эти этапы служит различие применяемых в логике средств и методов исследования. Начало первого этапа связано с работами древнегреческого философа и учёного Аристотеля (384 – 322 гг. до н.э.), в которых впервые дано систематическое изложение логики. Логику Аристотеля и всю доматематическую логику обычно называют «традиционной» формальной логикой.

Второй этап – это появление математической (или символической) логики. Немецкий философ Г. В. Лейбниц (1646 – 1716 гг.) по праву считается основоположником математической (символической) логики.

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

Математическая (или символическая) логика делится на три подраздела: логику Буля, логику высказываний и логику предикатов.

«Логика Буля» основывается на отношении эквивалентности, при котором правая часть равенства всегда содержит ровно столько же «истины», сколько и левая. Строго говоря, в этом случае не происходит приращения нового знания. Два последующих подраздела, «Логика высказываний» и «Логика предикатов», базируется уже на отношении порядка, при котором правая часть выражения (заключение) содержит больше «истины», чем левая (посылки), т.е. «истинность» заключения

29

оказывается выше «истинности» посылок, о чём можно судить, в частности, по количеству единиц в таблице истинности.

2.1 Операции логики Буля

Операции булевой логики удобно ввести используя аналогии с операциями над множествами. Будем рассматривать только счетные множества, т.е. для которых установлено взаимно однозначное соответствие с числами натурального ряда.

Пусть задано некоторое множество U – универсальное множество. Множества А, В – подмножества U. Для удобства будем считать, что элементы множества А обладают свойством А, а элементы множества В – свойством В. В результате получим четыре класса элементов (рисунок 2.1):

С0 – множество, элементы которого не обладают ни свойством А, и свойством В;

С1 – множество, элементы которого обладают только свойством А; С2 – множество, элементы которого обладают только свойством В; С3 – множество, элементы которого обладают одновременно и

свойством А и свойством В.

Рассмотрим сначала операцию объединения. Объединением охватываются три класса элементов С1, С2, С3 (рисунок 2.2). Логически операцию объединения двух множеств можно охарактеризовать словами: «элемент х принадлежит множеству А или множеству В». При этом союз или одновременно означает и союз и.

x A B (x A) (x B),

30