Базовые логические операции.

Операция	Название операции	Обозначение операции
И (AND)	Логическое умножение — конъюнкция	. ^
ИЛИ (OR)	Логическое сложение — дизъюнкция	+ v V
НЕ (NOT)	Логическое отрицание — инверсия	— ¬

При выполнении операций применяются отношение эквивалент­ности «=» и скобки «()», которые определяют порядок выполне­ния операций. Если скобок нет, то операции выполняются в следу­ющей последовательности: логическое отрицание, логическое умножение и логическое сложение.

39. Основные законы и постулаты алгебры логики. Аксиомы (постулаты) алгебры логики:

1. Дизъюнкция двух переменных равна 1, если хотя бы одна из них равна 1 и равна 0, если обе переменные равны 0:

0 + 0 = 0;

0 + 1 = 1;

1 + 0 = 1;

1 + 1 = 1.

2. Конъюнкция двух переменных равна 0, если хотя бы одна пе­ременная равна 0 и равна 1, если обе переменные равны 1:

0 * 0 = 0;

0 * 1 = 0;

1 * 0 = 0;

1 * 1 = 1.

3. Инверсия одного значения переменной совпадает с ее другим значением:

= 0;

= 1.

Законы алгебры логики:

1. Законы однопарных элементов:

а) универсального множества:

x + 1 = 1;

x * 1 = x;

б) нулевого множества:

х + 0 = х;

х * 0 = 0.

2. Законы отрицания:

а) двойного отрицания:

= х;

б) дополнительности:

х + = 1;

x = 0.

в) двойственности (де Моргана):

= ;

= + .

3. Комбинационные законы:

а) тавтологии:

х + х = х;

х * х = х.

б) коммутативные

х₁ + х₂ = х₂ + х₁;

х₁ * х₂ = х₂ * х₁.

в) ассоциативные (сочетательные):

х₁ + (х₂ + х₃) = (х₁ + х₂) + х₃;

х₁(х₂х₃) = (х₁х₂)х₃.

г) дистрибутивные (распределительные):

х₁(х₂ + х₃) = х₁ * х₂ + х₁ * х₃;

х₁ + х₂ * х₃ = (х₁ + х₂)(х₁ + х₃).

д) закон абсорбции (поглощения):

х₁ + х₁х₂ = х₁;

х₁(х₁ + х₂) = х_1.

е) склеивания:

х₁х₂ + х₁ = х₁;

(х₁ + х₂)(х₁ + ) = х₁.

39. Определение булевой функции. Булевы функции двух

переменных.

Булевой (переключательной, двоичной) функцией называется двоичная переменная у, значение которой зависит от значений дру­гих двоичных переменных (x₁, x₂,..., х_n), именуемых аргументами:

y = y(x₁, х₂,..., х„).

Задание булевой функции означает, что каждому из возможных сочетаний аргументов поставлено в соответствие определенное зна­чение у.

Для алгебры логики установлено, что если y = y(z₁, z₂), где z₁ и z₂ — двоичные функции, т. е. z₁ = z₁(x₁, x₂), z₂ = z₂(x₃, x₄), то y = у(х₁, х₂, х₃, х₄).

Операцию замены одной функции другими функциями называ­ют суперпозицией. Эта операция дает возможность с помощью функций малых аргументов получить функции большего числа аргументов. Так, при помощи суперпозиции молено получить фун­кцию с требуемым числом аргументов, используя только функцию диух аргументов.

Рассмотрим функцию двух аргументов.

По определению существует 16 функций двух аргументов.

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

На практике используют не все функции, а лишь те из них, ко­торые методом суперпозиции обеспечивают представление любой другой функции. Набор таких функций называют функционально полным набором (ФПН).

Существует несколько ФПН. В качестве ФПН применяются дизъюнкция, конъюнкция и инверсия. Этот набор называют основ­ным ФПН (ОФПН).