Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



Обозначения: E2={0, 1}; Е = E2´ E2´...´ E2 – прямое произведение n сомножителей; (x ,.., xnE2, | 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), записывая эту функцию в виде таблицы:

x1 x2 f(x1, x2)

Здесь x1 и x2 обозначают названия столбцов, а f – символ, обозначающий отображение. Следует обратить внимание, что функции f(x1, x2) и f(y1, y2) задают одно и то же отображение, и их таблицы отличаются только названиями столбцов.

Определение 2. Таблица, задающая функцию f(x1, x2,..., xn), называется таблицей истинности для этой функции.

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

x f0(x)
   

функция называется константой 0, записывается f0(x) 0;

x f1(x)

функция называется тождественной, записывается f1(x)= x;

x f2(x)

функция называется «не x» и записывается f2 (x)= ;

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 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15
0 0 0 1 1 0 1 1

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

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

2) 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...anf(a1...ai–1, 1, ai+1...an). Тогда переменная хi называется существенной переменной. В противном случае хi называется фиктивной переменной.

Пример 2.

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

x1 x2 (x1& x2) f3 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, a2f(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.

x1 x2 f3

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

Получили f3(x1 x2) = g(x1) = x1.

Пример 4.

x1 x2 g

Пусть функция g(x1 x2) задана таблицей и существенно зависит от обеих переменных. Построим функцию f(x1, x2, x3), которая получается из g(x1, x2) введением фиктивной переменной х3:

x1 x2 x3 f

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

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

 

2.2. Формульное задание функций алгебры логики

 

Дадим индуктивное определение формулы над множеством. Это определение несколько сложное по форме, но будет полезно в дальнейшем. С индуктивным определением мы встречались в математическом анализе при определении n-го дифференциала dnf(x): было введено понятие первого дифференциала df(x), а затем n-й дифференциал определялся как первый дифференциал от d(n–1)f(x).

Определение 1. Пусть МÌ P2, тогда:

1) каждая функция f(x1, ..., xnM называется формулой над M;

2) пусть g(x1, ..., xmM, G1, ..., Gm – либо переменные, либо формулы над M. Тогда выражение g(G1...Gn) – формула над M.

Формулы будем обозначать заглавными буквами: N[f1, ..., fs], имея в виду функции, участвовавшие в построении формулы, или N(х1, ..., xk) имея в виду переменные, вошедшие в формулу. Gi – формулы, участвовавшие в построении g(G1, ..., Gn), называются подформулами.

Пример 1. Пусть N={(x1& x2), (x1Ú x2), (`x )}, тогда ((х1& х2х3) – формула над N.

Сопоставим каждой формуле N(x1, ..., xn) функцию f(x1, ..., xnP2. Сопоставление будем производить в соответствии с индуктивным определением формулы.

1) Пусть N(x1, ..., xn)=f(x1, ..., xn), тогда формуле N(x1, ..., xn) сопоставим функцию f(x1, ..., xn).

2) Пусть N(x1, ..., xn)=g(G1, ..., Gm), где каждое Gi – либо формула над M, либо переменная, тогда по индуктивному предположению каждому Gi сопоставлена либо функция fiÎ P2, либо переменная хi, которую можно считать тождественной функцией. Таким образом, каждой формуле Gi сопоставлена функция fi( ), причем: { }Í {x1, ..., xn}, т.к. в формуле N(x1, ..., xn) перечислены все переменные, участвовавшие в построении формулы. Можно считать, что все функции fi зависят от переменных (x1, ..., xn), причем какие-то переменные могут быть фиктивными. Тогда N(x1, ..., xn) = g(G1, ..., Gm) = g( f1(x1, ..., xn), ..., fm(x1,.., xn)). Сопоставим этой формуле функцию h(x1, ..., xn) следующим образом: пусть (a1, ..., an) – произвольный набор переменных (x1, ..., xn). Вычислим значение каждой функции fi на этом наборе, пусть f(a1, ..., an)=bi, затем найдем значение функции g(x1, ..., xm) на наборе (b1, ..., bm) и положим h(a1, ..., an) = g(b1, ..., bm) = g(f1(a1, ..., an), ..., fm(a1, ..., an)). Так как каждое fi(x1, ..., xn) есть функция, то на любом наборе (a1, ..., an) она определяется однозначно, g(x1, ..., xm) – тоже функция, следовательно, на наборе (b1, ..., bn) она определяется однозначно, где h(x1, ..., xn) есть функция, определенная на любом наборе (a1, ..., an).

Множество всех формул над M обозначим через < M>.

Определение 2. Две формулы N и D из < M> называются равными N=D или эквивалентными N~D, если функции, реализуемые ими, равны.

Пример 2. Доказать эквивалентность формул:

( & (х2Å x3))~( ).

x1 x2 x3 x2Å x3 & x2 x3 x3 x2 & Ú x1

 

Упрощение записи формул:

1) внешние скобки можно отпускать;

2) приоритет применения связок возрастает в следующем порядке: ~, , Ú, &;

3) связка – над одной переменной сильнее всех связок;

4) если связка – стоит над формулой, то сначала выполняется формула, затем отрицание;

5) если нет скобок, то операции ~ и выполняются в последнюю очередь.


Поделиться:



Популярное:

Последнее изменение этой страницы: 2016-04-09; Просмотров: 804; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.046 с.)
Главная | Случайная страница | Обратная связь