что а) xϕ 1 =1, xφ 1 = x, xϕ 0 = x, xφ 0 = 0; б) для произвольного элемента x M в М

дистрибутивности, коммутативности, а в качестве элементов 1 и 0 выступают универсальное множество Ωи пустое множество .

Булевой алгеброй является и алгебра логических функций Дадим определение алгебре логических функций.

Пусть Е={0,1}- двухэлементное множество. Обозначим через Р2 множество всех логических функций от п переменных. Рассмотрим на множестве Е следующие бинарные операции: дизъюнкция ( v) и конъюнкция ( ) , а так же унарную операцию дополнение. Зададим эти операции таблицами истинности , а именно:

Тип этой алгебры (2,2,1)

Заметим, что все алгебры типа (2,2,1) являются булевыми, если их операции удовлетворяют законам ассоциативности, коммутативности, дистрибутивности, поглощения и дополнения.

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

Пусть даны две алгебры А = < M, ϕ 1., ϕ 2, …,ϕ m. > и В = < К, φ 1., φ 2, …,φ m. > одинакового типа. Гомоморфизмом алгебры А в алгебру В называется отражение

Г:К→М, при котором независимо от того, выполнена ли сначала операция ϕ в А и

затем произведено отображение Г либо сначала произведено отображение Г, а затем в В выполнена соответствующая операция φ , результат будет одинаковым.

Изоморфизмом алгебры А на алгебру В называется взаимно-однозначный гомоморфизм. В этом случае существует обратное отображение Г-1: М→К.

Алгебры называются изоморфными, если существует изоморфизм А на В и изоморфизм В на А.

Примеры

1.Рассмотрим алгебру < QN, + > на множестве всех целых чисел и алгебру < Q2N, + > на множестве всех четных чисел. Эти алгебры изоморфны, причем изоморфизмом является отображение Г: n →2n, удовлетворяющее условию: 2(a+b)=2a+2b.

2.Если R – множество действительных чисел, R+ - множество положительных действительных чисел, то изоморфизмом между алгебрами < R+, • >и R, + > является отображение Г: а→log(a), обладающее свойством: log(a•в) = log(a) + log(в).

Понятие изоморфизма является одним из важнейших понятий в математике. Распространенное выражение «рассматривать объекты с точностью до изоморфизма» означает, что рассматриваются только те свойства объекта, которые сохраняются при изоморфизме. В частности, изоморфизм сохраняет ассоциативность, коммутативность и дистрибутивность теоретико-множественных

операций и логических операций , ,¬, с которыми будем знакомиться

далее.

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

Рассмотрим множество А = { а1,а2,…, аn }мощности n, элементы которого занумерованы числами от 1 до n. Пусть Вn – множество двоичных векторов длины n, состоящее из символов 1 и 0.

Каждому подмножеству Аэ А поставим в соответствие вектор v = (v1,v2,…,vn)

Вn следующим образом: vi= 0, если аi Aэ и vi=1, если аi Aэ

3. Логические функции (функции алгебры логики ).

3.1Способы представления логических функций.

3.2Суперпозиция и формулы

3.3. Булева алгебра логических функций

3.4Нормальные формы логических функций

3.5Полиномиальная форма Жегалкина логических функций.

3.6.Полнота и замкнутость

3.7Минимизация логических функций

3.8.Визуально-матричный метод минимизации логических функций.

3.1 Способы представления логических функций.

Пусть B = {0,1} – двухэлементное множество, а xi – двоичная переменная,

принимающая значение из В. Наиболее распространенная интерпретация двоичных переменных – логическая: “Да” – “Нет”, “истинно” – “ложно”, “1” – “0”, “и” – “л”.

Алгебра, образованная множеством В, вместе со всеми возможными операциями на нем, называется алгеброй логики. Функцией алгебры логики (или логической функцией) от n переменных называется n-арная операция на В.

Итак, логическая функция f (x1x2,...xn) - эта функция, принимающая значение

0,1, аргументы которой принимают значения из множества В. Другими словами, это функция вида: