Composition of functions.

Given: f: Aè B and g: Bè C.

The composition of functions f and g is a function from A to C, which is denoted and defined so: (g∙ f): Aè C; where (g∙ f)(a) = g(f(a)) for all elements aÎ A.

f g

g·f

Ex: Let A={a, b, c}, B={1, 2, 3, 4} and C={a, 2, -6}.

Let f: Aè B be defined by: f(a)=2, f(b)=2, f(c)=1.

Led g: Bè C be defined by: g(1)=a, g(2)=-6, g(3)=-6, g(4)=a.

Then (g∙ f): Aè C is the function given by:

(g∙ f)(a) = g(f(a)) = g(2) = -6;

(g∙ f)(b) = g(f(b)) = g(2) = -6;

(g∙ f)(c) = g(f©) = g(1) = a;

Ex: Let S be a finite set and x be an element not in S.

Let f: P(S) è P(SÈ {x}) be the function defined by:

f(T) È {x},

for all T in P(S). Let g: P(SÈ {x}) è N be the function defined by: g(V) = |V| for all V in P(SÈ {x}).

In such a case, the composition (g∙ f): P(S) è N is given by (g∙ f)(T) = g(f(T)) = g(TU{x}) = |TU{x}| = |T|+1, for all T in P(S).

Topic: Boolean functions

A function y = f(, , …, ) where y, , , …, є{0; 1} is called an n-place Boolean function.

There exist four 1 – place Boolean functions of the type f_i (x).

x

Notation used in formulas:

(x) = 0(constant); (x) = x;

(x)= (negation); (x) = 1(constant).

There exist 16 2-place Boolean functions of the type (x, y).

Notation used in formulas:

(x, y) = 0(count)

= xÙ y (conjuction, logical and)

(x, y) = (not y implication x)

(x, y) = x (duplicate x)

(x, y) = (not x implication y)

(x, y) = y

(x, y) = xÅ y (exclusive or)

(x, y) = xÚ y (disjunction, logical or)

(x, y) = x↓ y (Pierce operation)

(x, y)=x¯ y (equivalence)

(x, y) = (not y)

(x, y) = y→ x (y implication x)

(x, y) = (not x)

(x, y) = x→ y (x implication y)

(x; y) = x|y (Sheffer operation)

(x; y) = 1 (constant)

It is possible to construct a truth table for a boolean function by its number and the number of arguments n.

x	(x)

(x) è

x	y	(x, y)
		0

H/a: prove that a Boolean function f(, , …, ) has exactly different sets of argument values.

H/a: prove that there exist different Boolean functions of the form f(, , …, ).

I remind you: algebra = set of objects + set of operations.

2-element Boolean algebra = {0, 1) + {Ù, Ú, ˉ }. Any Boolean function can be presented by its table.

Ex: (x, y, z):

(n=3, function №27è 27(decimal) = 11011(binary), 2³ = 8 sets of argument values)

x	y	z	(x, y, z)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

Any Boolean function can be presented by a formula (an expression consisting of Boolean functions and their compositions).

Priority of Boolean functions in formulas: (), ˉ, Ù, Ú;

Note: in formulas we may omit ‘ Ù ’. So x Ù y = xy.

(x, y, z) = yz Ú x Ú xy Ú xyz = yz Ú x Ú xy= (x Ú y Ú z)(x Ú y Ú )(x Ú Ú z)(Ú ˇ y Ú ).

Note: the same Boolean function can be presented by many equivalent formulas