Элементарные функции алгебры логики

Рассмотрим множество элементарных ФАЛ. Начнем со случая, когда длина слова n=0. По формуле, определяющей число функций логики, вычисляем, что при n=0 = 2.

f₁=0; f₂=1.

Эти две функции совпадают с константами.

В случае n=1 мы имеем две функции, существенно зависящие от аргумента x, эти две функции определяются таблицей

x1	f 3	f 4
0	0	1
1	1	0

Эти две функции также относят к элементарным, и они записываются следующим образом

f ₃=x ; f ₄=(читается «не x»).

Функцию f ₄ называют функцией отрицания.

В случае n=2 имеем десять различных функций, существенно зависящих от аргументов x₁ и x₂.

		x1x2	x1&x2	x1~x2	x1x2	x1  x2	x1/x2	x1x2
x 1	x 2	f 5	f 6	f 7	f 8	f 9	f 10	f 11
0	0	0	0	1	1	1	1	1
0	1	1	0	0	1	0	1	0
1	0	1	0	0	0	0	1	1
1	1	1	1	1	1	0	0	0

Функция f₅(x_1,x₂) =x_1x₂ (дизъюнкция).

Функция f₆(x_1,x₂) =x₁&x₂ (конъюнкция).

Вместо символов & часто применяют символ умножения «•» или вообще опускают также, как и в обычной алгебре.

Функция f₇ носит название функции эквивалентности или функции равнозначности

f₇(x_1,x₂) = x1~x2

и f₇(x_1,x₂) = x₁x₂.

Функция f₈ носит название импликации x₁ в x₂. Она обозначается f₈(x_1,x₂) = x₁x₂.

Функция f₉ носит название функции Вебба (или ее называют еще стрелкой Пирса) и обозначается

f ₉(x_1,x₂) = x₁vx₂.

Функция f₉ называется функцией (штрихом) Шеффера и обозначается следующим образом f ₁₀(x_1,x₂) = x₁  x₂.

Функция f ₁₁ обычно называется функцией сложения по модулю 2.

f ₁₁(x_1,x₂) = x₁x₂.

Рассмотрение одиннадцати функций позволяют строить новые функции двумя основными способами:

1. путем перенумерации аргументов;

2. путем подстановки в функцию новых функций вместо аргументов.

Функцию, полученную из функций f ₁, f ₂, f ₃, …, f _k путем применения этих правил будем называть суперпозицией функции f ₁, f ₂, f ₃, …, f _k .

Имея, например, элементарные функции отрицания, дизъюнкции, эквивалентности и импликации, можно составить следующие новые функции ФАЛ.

Используя таблицы, определяющие элементарные функции, можно задать любую функцию ФАЛ, являющуюся суперпозицией этих функций.

Пример. Пусть требуется представить в виде таблицы следующую функцию

f (x₁,x₂,x₃)={[( ~x₂) (x₁  x₂)] (x₁x₂)}x₃.

Будем строить ФАЛ последовательно.

x1	x2	x3		~x2	x1x2	[ ]	x1x2	{ }	f (x1,x2,x3)
0	0	1	1	0	1	1	0	0	1
0	0	0	1	1	1	1	0	0	1
0	1	1	1	0	0	0	1	0	1
0	1	0	1	1	0	1	1	1	1
1	0	1	0	1	0	1	1	1	0
1	0	0	0	0	0	0	1	0	1
1	1	1	0	1	0	1	0	0	1
1	1	0	0	0	0	0	0	0	1

ВЫРАЖЕНИЕ ОДНИХ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ ЧЕРЕЗ ДРУГИЕ

1. Функция f ₈(x_1,x₂) = x₁x₂ (импликация x₁ в x₂) может быть записана посредством функций дизъюнкции и отрицания

x₁>x₂=x ₂.

Доказательство осуществляется посредством таблиц истинности.

x 1	x 2	x1x2
0	0	1
0	1	1
1	0	0
1	1	1

x1	x2		x 2
0	0	1	1
0	1	1	1
1	0	1	0
1	1	1	1

2. Функцию эквивалентности f₇(x_1,x₂)=x₁~x₂ = x₁x₂ выразим посредством других функций x₁~x₂= (x₂)&(x ₁ )

x 1	x 2	x1~x2
0	0	1
0	1	0
1	0	0
1	1	1
x 1	x 2				x 2	x1	(x2)&(x 1 )
0	0	1	1		1	1	1
0	1	1	1		1	0	0
1	0	0	0		0	1	0
1	1	0	0		1	1	1

3. f ₁₁(x_1,x₂) = x₁ x₂=

x 1	x 2	x1x2	x1~x2
0	0	0	1	0
0	1	1	0	1
1	0	1	0	1
1	1	0	1	0

или

f (x_1,x₂) = x₁ x₂=(& x₂) (x₁&)

x 1	x 2	x1x2		(&x2)		(x1&)	(&x2) (x1&)
0	0	0	1	0	1	0	0
0	1	1	1	1	0	0	1
1	0	1	0	0	1	1	1
1	1	0	0	0	0	0	0

4. =x

x
0	1	0
1	0	1

5. x₁& x₂=

x 1	x 2	x1& x2
0	0	0
0	1	0
1	0	0
1	1	1

x 1	x 2
0	0	1	1	1	1
0	1	1	1	1	0
1	0	0	0	0	1
1	1	0	0	1	1

6. x₁ x₂=

x 1	x 2	x1 x2
0	0	0
0	1	1
1	0	1
1	1	1

x 1	x 2			&
0	0	1	1	1	0
0	1	1	0	0	1
1	0	0	1	0	1
1	1	0	0	0	1

7. x₁x₂=

x 1	x 2	x1x2
0	0	0
0	1	1
1	0	1
1	1	0

x 1	x 2			x2	x1
0	0	1	1	1	1	0
0	1	1	0	1	0	1
1	0	0	1	0	1	1
1	1	0	0	1	1	0