Полезная книги (02Глава21-22)

Посмотреть архив целиком

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


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


Рассмотрим набор < x1, x2,…, xn>, где xi принимает значения 0 или 1: <011010…1>. Число различных наборов такого вида при 1≤in конечно и равно 2n.

Два различных набора < x1, x2,…, xn> и < y1, y2,…, yn>, где xi и yi принимают значения 0 или 1, называются сравнимыми, если для любого i выполняется соотношение xi yi (или xi yi ), и несравнимыми во всех остальных случаях.

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

Если две булевых функции f1(x1 x2xn) и f2(x1 x2xn) принимают на всех возможных наборах значений аргументов одинаковые значения, то функции f1 и f2 называются равными:

f1(x1 x2 … xn) = f2(x1 x2 … xn).

Функция f(x1 x2xi-1 xi xi+1… xn) существенно зависит от аргумента xi, если имеет место соотношение:

f(x1 x2… xi-1 1 xi+1… xn) ≠f(x1 x2… xi-1 0 xi+1… xn).

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


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

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


Таблица 1.


x1 x2 … xn f1(x1 x2 … xn)


0 0 . . . 0 α1

0 0 . . . 1 α2

. . . . . . . . . . .

1 1 . . . 0 α2n-1

1 1 . . . 1 α2n


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

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

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

An=- Cnn-1 An-1- Cnn-1 An-1- Cnn-2 An-2-…- Cn1 A1- A0.


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


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

f0=0, f1=1, A0=2.

При n=1 (табл.2) f1 и f2 зависят от x существенно, а для f0 и f3 аргумент x является фиктивным.


Таблица 2.


x f0(x) f1(x) f2(x) f3(x)


0 0 0 1 1

1 0 1 0 1


При n=2:

A2= - C21 A1- A0=10.

При n=3:

A3= - C32 A2- C31 A1- A0=218.

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


x1 x2 xn-1 xn

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

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

… … … … … ……..

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


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


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

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




Таблица 3.


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

f0(x) 0 0 Константа 0

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

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

f3(x) 1 1 Константа 1.

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

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


Таблица 4.


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


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


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

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

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

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

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

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

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

f6(xy) 0 1 1 0 xy, yx Функция суммы по мо-

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

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

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

дизъюнкция,

f8(xy) 1 0 0 0 xy Операция (стрелка)

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

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

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

f10(xy) 1 0 1 0 Инверсия y, не y

f11(xy) 1 0 1 1 yx Импликация от y к x

f12(xy) 1 1 0 0 Инверсия x, не x

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

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

Шеффера

f15(xy) 1 1 1 1 1 Константа единица

При n=2, A2=10, функции f0, f3, f5, f10, f12 и f15 имеют фиктивные аргументы.


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


  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 - (2n-1)–й набор.

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


Пример. Запись функции f248(АВС) = приведена в табл.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)=[(CD)~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

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


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


Случайные файлы

Файл
114449.rtf
36252.rtf
50317.rtf
99366.rtf
35144.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.