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

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

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

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

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

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

x1	x2	f(x1, x2)

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

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

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

x	f0(x)

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

x	f1(x)

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

x	f2(x)

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

x	f3(x)

функция записывается f₃(x) 1 и называется константой 1. Если стандартным расположением переменной x считать 0 в первой строке и 1 во второй, то функции f₀, f₁, f₂, f₃ определяются однозначно наборами значений: f₀=(0, 0), f₁=(0, 1), f₂=(1, 0) и f₃=(1, 1). Наборы значений функций составляют множество E₂´ Е₂, поэтому количество функций одной переменной равно |E₂ E₂|=4. Для удобства функции пронумерованы так, что двоичный код номера совпадает с набором значений функции.

Рассмотрим функции двух переменных f(x₁, x₂). Функции двух переменных определены на множестве Е ={(0 0), (0 1), (1 0), (1 1)}, эти наборы переменных из Е можно тоже рассматривать как двоичные коды чисел 0, 1, 2, 3, именно такой порядок расположения наборов (x₁, x₂) будем считать стандартным. Тогда функции f(x₁, x₂) определяются однозначно наборами значений (b₁, b₂, b₃, b₄), где каждое b_iÎ E₂, поэтому (b₁, b₂, b₃, b₄)Î Е . Следовательно, число функций двух переменных равно 2⁴=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) f₁(x₁, x₂) = (x₁& x₂), читается «конъюнкция х₁ и х₂», иногда вместо знака & употребляют знак или вообще его опускают, пишут (х₁х₂). (х₁& х₂) совпадает с обычным произведением х₁х₂ и совпадает с min(x₁, x₂). Эту операцию называют также логическим умножением.

2) f₆(x₁, x₂) = (x₁Å x₂) – сложение х₁ и х₂ по модулю два, иногда пишут (х₁+х₂)_mod2.

3) f₇(x₁, x₂) = (x₁Ú x₂), читается «х₁ дизъюнкция х₂», она совпадает с max(x₁, x₂), ее называют логическим сложением.

4) f₈(x₁, x₂) = (x₁ x₂), читается «х₁ стрелка Пирса х₂» и совпадает с отрицанием дизъюнкции, другие названия: функция Вебба, функция Даггера.

5) f₉(x₁, x₂) = (x₁~x₂), читается «х₁ эквивалентно х₂».

6) f₁₃(x₁, x₂) =( x₁ x₂), читается «х₁ импликация х₂», иногда обозначается (х₁É х₂), т. е. х₁ влечет х₂.

7) f₁₄(x₁, x₂) = (x₁|x₂), читается «х₁ штрих Шеффера х₂», она является отрицанием конъюнкции.

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

Рассмотрим функции f(x₁...x_n), где (x₁...x_n)Î Е , тогда число наборов (x₁...x_n), где функция f(x₁...x_n) должна быть задана, равно |Е |=2ⁿ. Обозначим множество всех функций двузначной алгебры логики Р₂. Обозначим через Р₂(n) число функций, зависящих от n переменных. Очевидно, Р₂(n)=2^{2 n}.

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

Определение 3. Функция f(x₁,..., x_i–1, x_i, x_i+1,..., x_n) существенно зависит от х_i, если существуют такие значения a₁, ...a_i–1, a_i+1, ...a_n переменных x₁, ...x_i–1, x_i+1, ...x_n, что f(a₁, ...a_i–1, 0, a_i+1...a_n)¹ f(a₁...a_i–1, 1, a_i+1...a_n). Тогда переменная х_i называется существенной переменной. В противном случае х_i называется фиктивной переменной.

Пример 2.

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

x1	x2	(x1& x2)	f3	f15

Покажем, что (х₁& x₂) существенно зависит от х₁. Рассмотрим наборы (0, 1) и (1, 1), здесь a₂=1, f(0, a₂)=0 и не равно f(1, a₂)=1. Покажем, что х₂ тоже существенная переменная. Рассмотрим наборы (1, 0) и (1, 1). Здесь a₁=1, f(1, 0)=0 и не равно f(1, 1)=1. Для функции f₃(x₁, x₂) покажем, что х₂ – иктивная переменная, т.е. надо показать, что не существует наборов (a₁, 0) и (a₁, 1) таких, что f₃(a₁, 0)¹ f₃(a₁, 1). Пусть a₁=0, т.е. рассмотрим наборы (0, 0) и (0, 1), f(0, 0)=f(0, 1)=0. Пусть a₁=1, но f(1, 0)=f(1, 1)=1.

Для функции f₁₅ и x₁ и x₂ являются фиктивными переменными. x₁ – фиктивная переменная, если не существует наборов (0, a₂) и (1, a₂), таких, что f(0, a₂)¹ f(1, a₂). Если a₂=0, то f(0, 0)=f(1, 0)=1. Пусть a₂=1, тогда f(0, 1)=f(1, 1)=1.

Пусть х_i является фиктивной переменной для функции f(x₁, ..., x_i, ..., x_n). Тогда ее можно удалить из таблицы истинности, вычеркнув все строки вида: (a₁, ...a_i–1, 1, a_i+1, ...a_n) или, наоборот, все строки вида: (a₁, ..., a_i–1, 0, a_i+1, ...a_n) и столбец для переменной х_i. При этом получим таблицу для некоторой функции g(x₁, ..., x_i–1, x_i+1, ...x_n). Будем говорить, что функция g(x₁, ...x_i–1, x_i+1, ...x_n) получена из функции f(x₁, ..., x_i, ...x_n) путем удаления фиктивной переменной х_i или f получена из g путем введения фиктивной переменной х_i.

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

Пример 3.

x1	x2	f3

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

Получили f₃(x₁ x₂) = g(x₁) = x₁.

Пример 4.

x1	x2	g

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

x1	x2	x3	f

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

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

 

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

 

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

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

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

2) пусть g(x₁, ..., x_m)Î M, G₁, ..., G_m – либо переменные, либо формулы над M. Тогда выражение g(G₁...G_n) – формула над M.

Формулы будем обозначать заглавными буквами: N[f₁, ..., f_s], имея в виду функции, участвовавшие в построении формулы, или N(х₁, ..., x_k) имея в виду переменные, вошедшие в формулу. G_i – формулы, участвовавшие в построении g(G₁, ..., G_n), называются подформулами.

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

Сопоставим каждой формуле N(x₁, ..., x_n) функцию f(x₁, ..., x_n)Î P₂. Сопоставление будем производить в соответствии с индуктивным определением формулы.

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

2) Пусть N(x₁, ..., x_n)=g(G₁, ..., G_m), где каждое G_i – либо формула над M, либо переменная, тогда по индуктивному предположению каждому G_i сопоставлена либо функция f_iÎ P₂, либо переменная х_i, которую можно считать тождественной функцией. Таким образом, каждой формуле G_i сопоставлена функция f_i( ), причем: { }Í {x₁, ..., x_n}, т.к. в формуле N(x₁, ..., x_n) перечислены все переменные, участвовавшие в построении формулы. Можно считать, что все функции f_i зависят от переменных (x₁, ..., x_n), причем какие-то переменные могут быть фиктивными. Тогда N(x₁, ..., x_n) = g(G₁, ..., G_m) = g( f₁(x₁, ..., x_n), ..., f_m(x₁,.., x_n)). Сопоставим этой формуле функцию h(x₁, ..., x_n) следующим образом: пусть (a₁, ..., a_n) – произвольный набор переменных (x₁, ..., x_n). Вычислим значение каждой функции f_i на этом наборе, пусть f(a₁, ..., a_n)=b_i, затем найдем значение функции g(x₁, ..., x_m) на наборе (b₁, ..., b_m) и положим h(a₁, ..., a_n) = g(b₁, ..., b_m) = g(f₁(a₁, ..., a_n), ..., f_m(a₁, ..., a_n)). Так как каждое f_i(x₁, ..., x_n) есть функция, то на любом наборе (a₁, ..., a_n) она определяется однозначно, g(x₁, ..., x_m) – тоже функция, следовательно, на наборе (b₁, ..., b_n) она определяется однозначно, где h(x₁, ..., x_n) есть функция, определенная на любом наборе (a₁, ..., a_n).

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

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

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

( & (х₂Å x₃))~( ).

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

 

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

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

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

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

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

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

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Популярное:

1. III. Полномочия и функции Комиссии
2. Аналитические абстрактные функции и ряды Тейлора.
3. Банковская система. Центр. и ком-кие банки, их задачи и функции.
4. Билет 1. Сущность финансов, их функции
5. Билет № 5. Рынок в системе общественного производства: природа и функции.
6. Биологические мембраны клетки их строение химический состав и функции.
7. Биосфера. Экологические функции.
8. Булева алгебра высказываний (алгебра логики)
9. Бюджетный дефицит: понятие, функции, виды, пути сокращения
10. ВЗЯТИЕ ЖЕЛУДОЧНОГО СОДЕРЖИМОГО ДЛЯ ИССЛЕДОВАНИЯ СЕКРЕТОРНОЙ ФУНКЦИИ ЖЕЛУДКА
11. Виды РНК. Строение и функции РНК
12. ВНУТРЕННИЕ ФУНКЦИИ ГОСУДАРСТВА