Глава 2. Основы алгебры логики.

§1. Функции алгебры логики и их основные свойства.

Рассмотрим набор < x₁, x₂,…, x_n>, где x_i принимает значения 0 или 1: . Число различных наборов такого вида при 1≤i≤n конечно и равно 2ⁿ.

Два различных набора < x₁, x₂,…, x_n> и < y₁, y₂,…, y_n>, где x_i и y_i принимают значения 0 или 1, называются сравнимыми, если для любого i выполняется соотношение x_i ≥ y_i (или x_i ≤ y_i ), и несравнимыми во всех остальных случаях.

Функция f(x₁, x₂,…, x_n) называется булевой или переключательной функцией, если она, так же как и ее аргументы, может принимать только два значения: 0 и 1.

Если две булевых функции f₁(x₁ x₂… x_n) и f₂(x₁ x₂… x_n) принимают на всех возможных наборах значений аргументов одинаковые значения, то функции f₁ и f₂ называются равными:

f₁(x₁ x₂ … x_n) = f₂(x₁ x₂ … x_n).

Функция f(x₁ x₂… x_i-1 x_i x_i+1… x_n) существенно зависит от аргумента x_i, если имеет место соотношение:

f(x₁ x₂… x_i-1 1 x_i+1… x_n) ≠f(x₁ x₂… x_i-1 0 x_i+1… x_n).

В противном случае говорят, что от x_i функция зависит несущественно и x_i является ее фиктивным аргументом.

Теорема. Число различных функций алгебры логики, зависящих от n аргументов, конечно и равно 2ⁿ.

Для доказательства составляем таблицу значений произвольной функции n параметров (табл.1).

Таблица 1.

x₁ x₂ … x_n f₁(x₁ x₂ … x_n)

0 0 . . . 0 α₁

0 0 . . . 1 α₂

. . . . . . . . . . .

1 1 . . . 0 α₂ⁿ_-1

1 1 . . . 1 α₂ⁿ

Задавая тот или иной двоичный набор < α₁ α₂ … α₂ⁿ >, будем описывать одну из возможных функций. Но число таких наборов = . Теорема доказана.

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

Теорема. Число всех функций алгебры логики, существенно зависящих от n аргументов, определяется следующим рекуррентным соотношением:

A_n= - C_n^n-1 A_n-1- C_n^n-1 A_n-1- C_n^n-2 A_n-2-…- C_n¹ A₁- A₀.

Здесь A_i – число функций, существенно зависящих от i аргументов. Правая часть соотношения есть разность между числом всех функций от n аргументов и суммой всех функций, существенно зависящих от любого числа аргументов меньше n. Справедливость очевидна.

Пример. При n=0:

f₀=0, f₁=1, A₀=2.

При n=1 (табл.2) f₁ и f₂ зависят от x существенно, а для f₀ и f₃ аргумент x является фиктивным.

Таблица 2.

x f₀(x) f₁(x) f₂(x) f₃(x)

0 0 0 1 1

1 0 1 0 1

При n=2:

A₂= - C₂¹ A₁- A₀=10.

При n=3:

A₃= - C₃² A₂- C₃¹ A₁- A₀=218.

Область определения любой булевой функции конечна, поэтому все булевы функции можно задать таблицей значений на различных наборах. Так как набор – двоичное число, то принято каждому набору аргументов приписывать номер, равный соответствующему двоичному числу. Причем порядок записи аргументов совпадает с порядком переменных в записи функции:

x₁ x₂ … x_n-1 x_n

0 0 … 0 0 0-й набор

0 0 … 0 1 1-й набор

… … … … … ……..

1 1 … 1 1 (2ⁿ-1)–й набор.

Обычно при задании таблицы наборы идут в порядке возрастания номеров.

Пример. n=0: две функции, существенно не зависящие ни от одного переменного, - константа 0 и 1.

Для n=1 функции сведены в табл.3.

Таблица 3.

x 0 1 Название функции

f₀(x) 0 0 Константа 0

f₁(x) 0 1 Переменная x

f₂(x) 1 0 Инверсия x, не x

f₃(x) 1 1 Константа 1.

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

Для n=2 переключательные функции приведены в табл.4.

Таблица 4.

x 0 0 1 1 Обозначение Название

y 0 1 0 1 функции функции

f₀(xy) 0 0 0 0 0 Константа нуль

f₁(xy) 0 0 0 1 xy, xΛy Логическое произведе-

ние, конъюнкция, Λ

f₂(xy) 0 0 1 0 xΔy Функция запрета по y

f₃(xy) 0 0 1 1 x Переменная x

f₄(xy) 0 1 0 0 yΔx Функция запрета по x

f₅(xy) 0 1 0 1 y Переменная y

f₆(xy) 0 1 1 0 x y, y x Функция суммы по мо-

дулю 2, логическая не-

равнозначность

f₇(xy) 0 1 1 1 x+y, x y Логическая сумма,

дизъюнкция,

f₈(xy) 1 0 0 0 x↓y Операция (стрелка)

Пирса, операция Вебба

f₉(xy) 1 0 0 1 x~y Логическая

равнозначность

f₁₀(xy) 1 0 1 0 Инверсия y, не y

f₁₁(xy) 1 0 1 1 y→x Импликация от y к x

f₁₂(xy) 1 1 0 0 Инверсия x, не x

f₁₃(xy) 1 1 0 1 x→y Импликация от x к y

f₁₄(xy) 1 1 1 0 x | y Операция (штрих)

Шеффера

f₁₅(xy) 1 1 1 1 1 Константа единица

При n=2, A₂=10, функции f₀, f₃, f₅, f₁₀, f₁₂ и f₁₅ имеют фиктивные аргументы.

Основные соотношения алгебры логики для функций Λ, и инверсии.

1. Основные законы алгебры логики:

а) ассоциативный (сочетательный) закон

(xy)z=x(yz)=xyz;

(x+y)+z=x+(y+z)=x+y+z;

б) коммутативный (переместительный) закон:

xy=yx;

x+y=y+x;

в) дистрибутивный (распределительный) закон:

(x+y)z=xz+yz;

(x+y)(y+z)=xz+y.

1. Основные соотношения для инверсии:

1. Основные соотношения для дизъюнкции:

1. Основные соотношения для конъюнкции:

1. Основные соотношения для системы функций:

а) операция поглощения:

x+xy=x;

x(x+y)=x;

б) операция склеивания:

в) формулы де Моргана:

Диаграммы Венна.

Наглядная интерпретация основных соотношений булевых переменных представлена на диаграммах Венна.

Класс булевых переменных определяется как класс, включающий все области внутри квадрата (рис.1).

рис.1.

Любой элемент А этого класса представлен областью, ограниченной замкнутой кривой. - совокупность точек квадрата, не входящих в область А.

Здесь 0 представлен как класс, совсем не имеющий точек, а 1 – как класс всех точек квадрата.

А+В – наименьшая область, содержащая одновременно А и В.

АВ – наибольшая область, содержащаяся одновременно и в А, и в В. Диаграм-мы Венна для элементарных булевых функций изображены на рис.2:

а) б) в) г) д) рис.2.

§2. Формы записи булевых функций.

Табличная запись.

Одним из распространенных способов записи булевой функции является ее задание с помощью таблицы соответствия (таблицы истинности), которая сопоставляет всем двоичным наборам аргументов значения функции на этих наборах. Буквы и наборы в таблице могут располагаться в любом порядке, однако практически целесообразно осуществлять запись следующим образом:

1. порядок записи букв в таблице совпадает с порядком аргументов в записи функции;

2. наборы, представляющие собой двоичные числа, располагаются в таблице в порядке их возрастания. Каждому набору приписывается номер соответственно представляемому им числу:

000…00 – нулевой набор;

000 …01 – 1-й набор;

. . . . . . . . . . . . . . . . . . .

111 … 11 - (2ⁿ-1)–й набор.

Функция, записанная в табличном виде, имеет индекс, равный двоичному числу, образованному значениями этой функции, записанными слева направо, начиная со значения на нулевом наборе.

Пример. Запись функции f₂₄₈(АВС) = приведена в табл.5.

Таблица 5.

A B C B↓C

0 0 0 1 0 1

0 0 1 0 1 1

0 1 0 0 1 1

0 1 1 0 1 1

1 0 0 1 0 1

1 0 1 0 1 0

1 1 0 0 1 0

1 1 1 0 1 0

При задании булевых функций при 3≤n≤10 иногда используют прямоугольные таблицы, т.е. те же таблицы соответствия, но в несколько ином начертании, позволяющем получить более компактную запись. Для функции от n переменных такая таблица имеет строк и столбцов, где - целая часть числа n/2.

Пример. Запись функции f(ABCD)=[(C→D)~B] [A |0] дана в табл.6.

Пример. Запись функции f(ABCD)= приведена в табл.7.

Таблица 6. Таблица 7.

CD BC

А

AB 00 01 10 11 00 01 10 11

00 1 1 1 1 0 1 1 1 1

01 1 1 1 1 1 1 0 0 0

10 0 0 1 0

11 1 1 0 1

Аналитическая запись.

Произведение булевых переменных называется булевым произведением. Булево произведение называется элементарным, если переменные в него входят только один раз в прямой или инверсной форме.

Пример. - элементарные произведения, - эти произведения не являются элементарными.

Число переменных, образующих элементарное произведение, называется длиной или рангом элементарного произведения.

Пример. - ранг 3.

Минтермом или конституентой единицы n переменных называется элементарное произведение ранга n.

Аналогичные определения существует и для булевых сумм.

Пример. - элементарная сумма ранга 2; не является элементарной суммой.

Макстермом или конституентой нуля n переменных называется элементарная булева сумма ранга n.

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

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

Пример. =m₅.