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

Обозначения: E2={0,1}; Е = E2´E2´...´E2 – прямое произведение N сомножителей; (X ,..,Xn)Î E2, | E2| – мощность E2, |E2|=2, тогда |Е |=2N.

Определение 1. Функцией алгебры логики называется закон, осуществляющий отображение Е E2, причем отображение всюду определено и функционально.

Так как множество Е конечно, то задать отображение Е Þ E2, означает задать множество наборов из Е и для каждого набора указать его образ в Е 2.

Пример 1. Пусть N=2, тогда Е ={(0 0),(0 1),(1 0),(1 1)}, отображение Е Þ E2 задано, например, так: (0 0) Þ0 ; (0 1) Þ1; (1 0) Þ1 ; (1 1) Þ1.

Тем самым задана функция, для которой мы будем использовать стандартное обозначение F(X1,X2), записывая эту функцию в виде таблицы:

F(X1,X2)

Здесь X1 и X2 обозначают названия столбцов, а F – Символ, обозначающий отображение. Следует обратить внимание, что функции F(X1,X2) и F(Y1,Y2) задают одно и то же отображение, и их таблицы отличаются только названиями столбцов.

Определение 2. Таблица, задающая функцию F(X1,X2,...,Xn), называется таблицей истинности для этой функции.

Рассмотрим функции одной переменной. Их будет всего 4, они задаются следующими таблицами истинности:

F0(X)

Функция называется константой 0, записывается F0(X) 0;

F1(X)

Функция называется тождественной, записывается F1(X)= X;

F2(X)

Функция называется «не X» и записывается F2 (X)= ;

F3(X)

Функция записывается F3(X) 1 и называется константой 1. Если стандартным расположением переменной X считать 0 в первой строке и 1 во второй, то функции F0, f1, F2, F3 определяются однозначно наборами значений: F0=(0,0), F1=(0,1), F2=(1,0) и F3=(1,1). Наборы значений функций составляют множество E2´Е2, поэтому количество функций одной переменной равно |E2 E2|=4. Для удобства функции пронумерованы так, что двоичный код номера совпадает с набором значений функции.

Рассмотрим функции двух переменных F(X1,X2). Функции двух переменных определены на множестве Е ={(0 0),(0 1),(1 0),(1 1)}, эти наборы переменных из Е можно тоже рассматривать как двоичные коды чисел 0,1,2,3, именно такой порядок расположения наборов (X1,X2) будем считать стандартным. Тогда функции F(X1,X2) определяются однозначно наборами значений (B1, B2, B3, B4), где каждое BIÎE2, поэтому (B1, B2, B3, B4)ÎЕ . Следовательно, число функций двух переменных равно 24=16, занумеруем их числами от 0 до 15 так, чтобы двоичный код номера совпадал с набором значений функции.

X1 X2

F10

F11

F12

F13

F14

F15

0 0

0 1

1 0

1 1

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

F1(X1,X2) = (X1&X2), читается «конъюнкция Х1 и Х2», иногда вместо знака & употребляют знак или вообще его опускают, пишут (Х1Х2). (Х1&Х2) совпадает с обычным произведением Х1Х2 и совпадает с min(X1,X2). Эту операцию называют также логическим умножением.

F6(X1,X2) = (X1ÅX2) – сложение Х1 и Х2 по модулю два, иногда пишут (Х1+Х2)Mod2.

3) F7(X1,X2) = (X1ÚX2), читается «Х1 дизъюнкция Х2», она совпадает с max(X1,X2), ее называют логическим сложением.

4) F8(X1,X2) = (X1 X2), читается «Х1 стрелка Пирса Х2» и совпадает с отрицанием дизъюнкции, другие названия: функция Вебба, функция Даггера.

5) F9(X1,X2) = (X1~X2), читается «Х1 эквивалентно Х2».

6) F13(X1,X2) =( X1 X2), читается «Х1 импликация Х2», иногда обозначается (х1Éх2), т. е. х1 влечет х2 .

7) F14(X1,X2) = (X1|X2), читается «Х1 штрих Шеффера Х2», она является отрицанием конъюнкции.

Cимволы ,&,Ú, ,~, ,Å,|, участвующие в обозначениях элементарных функций, называются логическими связками или просто связками. Переменные 0 и 1 называются логическими или булевыми переменными, причем 0 соответствует «лжи» , а 1 – «истине», а функции алгебры логики называются еще и блевыми функциями.

Рассмотрим функции F(X1...XN), где (X1...XN)Î Е , тогда число наборов (X1...XN),где функция F(X1...XN) должна быть задана, равно |Е |=2N. Обозначим множество всех функций двузначной алгебры логики Р2. Обозначим через Р2(N) число функций, зависящих от N переменных. Очевидно, Р2(N)=22 N.

С ростом N число Р2(N) быстро растет: P2(1)=4, P2(2)=16, P2(3)=256, P2(4)=65536 . При больших N табличный способ задания функций становится неприемлемым, используется формульное задание функций. Но прежде чем ввести понятие формулы, дадим определение существенной переменной.

Определение 3. Функция F(X1,...,XI–1,XI,XI+1,...,XN) существенно зависит от ХI, если существуют такие значения A1, ...AI–1, AI+1, ...AN переменных X1, ...XI–1, XI+1, ...XN, что F(A1, ...AI–1, 0, AI+1...AN)¹F(a1...AI–1, 1, AI+1...AN) . Тогда переменная ХI называется существенной переменной. В противном случае ХI называется фиктивной переменной.

Пример 2.

Рассмотрим несколько функций двух переменных

(X1&X2)

F15

Покажем, что (Х1&X2) существенно зависит от Х1. Рассмотрим наборы (0,1) и (1,1), здесь A2=1, F(0,A2)=0 и не равно F(1,A2)=1. Покажем, что Х2 тоже существенная переменная. Рассмотрим наборы (1,0) и (1,1). Здесь A1=1, F(1,0)=0 и не равно F(1,1)=1. Для функции F3(X1,X2) покажем, что Х2 – иктивная переменная, т. е. надо показать, что не существует наборов (A1,0) и (A1,1) таких, что F3(A1,0)¹F3(A1,1). Пусть A1=0, т. е. рассмотрим наборы (0,0) и (0,1), F(0,0)=F(0,1)=0. Пусть A1=1, но F(1,0)=F(1,1)=1.

Для функции F15 и X1 и X2 являются фиктивными переменными. X1 – фиктивная переменная, если не существует наборов (0,A2) и (1,A2), таких, что F(0,A2)¹F(1,A2). Если A2=0, то F(0,0)=F(1,0)=1. Пусть A2=1, тогда F(0,1)=F(1,1)=1.

Пусть Хi является фиктивной переменной для функции F(X1, ..., Xi, ..., Xn). Тогда ее можно удалить из таблицы истинности, вычеркнув все строки вида: (A1, ...AI–1, 1, AI+1, ...AN) или, наоборот, все строки вида: (A1, ..., AI–1, 0, AI+1, ...AN) и столбец для переменной Хi. При этом получим таблицу для некоторой функции G(X1, ..., Xi–1, Xi+1, ...Xn). Будем говорить, что функция G(X1, ...Xi–1, Xi+1, ...Xn) получена из функции F(X1, ..., XI, ...Xn) путем удаления фиктивной переменной Хi Или F получена из G путем введения фиктивной переменной Хi.

Определение 4. Функции F1 и F2 называются равными, если F2 можно получить из F1 путем добавления или удаления фиктивной переменной.

Пример 3.

Вычеркнули строки типа (A,1), т. е. (0,1) и (1,1) и столбец для Х2.

Получили F3(X1 X2) = G(X1) = X1.

Пример 4.

Пусть функция G(X1 X2) задана таблицей и существенно зависит от обеих переменных. Построим функцию F(X1,X2,X3), которая получается из G(X1,X2) введением фиктивной переменной Х3:

К наборам (Х1,Х2) мы добавим Х3=0, получим наборы вида: (A1,A2,0), на этих наборах функцию F положим равной G(A1,A2), затем добавим наборы вида (A1,A2,1), функцию F(A1,A2,1) положим равной G(A1,A2).

Особую роль играют константы 0 и 1, которые не имеют существенных переменных и которые можно рассматривать как функции от пустого множества переменных.

< Предыдущая		Следующая >