Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

 

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

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

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

Пример 1. Пусть , тогда Е = {(0 0), (0 1), (1 0), (1 1)}, отображение Е ÞE₂ задано, например, так: (0 0)Þ0; (0 1)Þ1;  (1 0)Þ1; (1 1)Þ1. Тем самым задана функция, для которой мы будем использовать стандартное обозначение f(x₁, x₂), записывая эту функцию в виде табл. 3.1.

 

Таблица 3.1

x1	x2	f(x1, x2)
0 0 1 1	0 1 0 1	0 1 1 1

 

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

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

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

 

 

Таблица 3. 2

x	f0(x)
0 1	0 0

 

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

 

Таблица 3. 3

x	f1(x)
0 1	0 1

 

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

 

Таблица 3. 4

x	f2(x)
0 1	1 0

 

Функция называется «не x» и записывается .

 

Таблица 3.5

x	f3(x)
0 1	1 1

 

Функция записывается f₃(x) 1 и называется константой 1.

Если стандартным расположением переменной x считать 0 в первой строке и первом – во второй, то функции 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 так, чтобы двоичный код номера совпадал с набором значений функции (табл. 3.6).

 

Таблица 3. 6

x1x2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
0 0 0 1 1 0 1 1	0 0 0 0	0 0 0 1	0 0 1 0	0 0 1 1	0 1 0 0	0 1 0 1	0 1 1 0	0 1 1 1	1 0 0 0	1 0 0 1	1 0 1 0	1 0 1 1	1 1 0 0	1 1 0 1	1 1 1 0	1 1 1 1

 

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

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

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

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

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

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

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

7) f₁₄(x₁, 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 переменных. Очевидно, .

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

Определение. Функция 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_1, ..., a_i–1, 1, a_i+1, . . ., a_n).

Тогда переменная х _i называется существенной переменной. В противном случае х _i называется фиктивной переменной.

Пример 2. Рассмотрим несколько функций двух переменных (табл. 3.7).

 

Таблица 3.7

x1	x2	(x1&x2)	f3	f15
0 0 1 1	0 1 0 1	0 0 0 1	0 0 1 1	1 1 1 1

 

Покажем, что (x₁&x₂) существенно зависит от х₁. Рассмотрим наборы (0, 1) и (1, 1), здесь a₂ = 1, f(0, a₂) = 0 и не равно f(1, a₂) = 1. Покажем, что x₂ – тоже существенная переменная. Рассмотрим наборы (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. Aналогично доказывается, что  тоже фиктивная переменная.

Пусть х _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 (табл. 3.8).

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

Пример 3.

 

Таблица 3.8

x1	x2	f3
0 0 1 1	0 1 0 1	0 0 1 1

 

Вычеркнув строки типа (a, 1), т. е. (0, 1) и (1, 1) и столбец для х₂,. получим f₃ (x₁x₂) = g(x₁) = x₁.

Пример 4. Пусть функция g(x₁x₂) задана в табл. 3.9 и существенно зависит от обеих переменных.

 

Таблица 3.9

x1	x2	g
0 0 1 1	0 1 0 1	0 0 0 1

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

Таблица 3. 10

x1	x2	x3
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 0 0 0 0 0 1 1

 

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

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

 

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

 

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

Определение. Пусть  тогда:

1) каждая функция  называется формулой над

2) пусть  – либо переменные, либо формулы над

3) если , то  – называется формулой над M.

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

 – формулы, участвовавшие в построении , называются подформулами.

Пример 5. Пусть  тогда  – формула над M.

Cопоставим каждой формуле  функцию  Cопоставление будем производить в соответствии с индуктивным определением формулы.

1) Пусть  тогда формуле  сопоставим функцию

2) Пусть  – формула над M и пусть ей по индуктивному предположению сопоставлена функция . Если – переменная, т. е. , то ей сопоставим функцию

Таким образом, каждой подформуле  сопоставлена функция

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

3) Тогда

Cопоставим формуле  функцию  следующим образом: пусть  – произвольный набор переменных, пусть  тогда

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

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

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

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

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

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

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

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

 

Пример 6. Доказать эквивалентность формул (табл. 3.11).

 ~ ( ) .

 

Таблица 3.11

x1	x2	x3	x2Åx3	&	x2 x3	x3 x2	&	Úx1	–
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 1 1 0 0 1 1 0	0 1 1 0 0 0 0 0	1 1 0 1 1 1 0 1	1 0 1 1 0 0 1 1	1 0 0 1 1 0 0 1	1 0 0 1 1 1 1 1	0 1 1 0 0 0 0 0