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

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

f₁=0; f₂=1.

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

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

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

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

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

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

		x1 Ú x2	x1 & x2	x1 ~ x2	x1 ® x2	x1 ¯ x2	x1 / x2	x1 x2
x 1	x 2	f 5	f 6	f 7	f 8	f 9	f 10	f 11

Функция f₅(x_1,x₂) = x₁ Ú 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₁ v x₂.

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

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

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

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

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

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

Функцию, полученную из функций f _{1, f 2, f 3}, …, f _k путем применения этих правил будем называть суперпозицией функции f _{1, f 2, f 3}, …, f _k.

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

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

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

f (x₁,x₂,x₃)={[( ~ x₂) Ú (x₁ ¯ x₂)] (x₁ x₂)} ® x₃.

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

x1	x 2	x 3		~ x2	x1 ¯ x2	[ ]	x1 Ú x2	{ }	f (x1,x2,x3)

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

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

x₁ > x₂= Ú x ₂.

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

x1	x 2		Ú x 2

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

x 1	x 2	x1 ~ x2
x 1	x 2			Ú x 2	x1 Ú	( Ú x2)&(x 1 Ú )

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

x 1	x 2	x1 x2	x1 ~ x2

или

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

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

4. = x

x

5. x₁& x₂=

x 1	x 2

6. x₁ x₂=

x 1	x 2	x1 x2

x 1	x 2			&

7. x₁ x₂=

x 1	x 2	x1 x2

x 1	x 2			x2	x1