Законы универсального множества

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 10Следующая ⇒

▷ Похожие статьи

1∙а = а; 1 + а = 1; 1 + а + b + с + … + w = 1

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

3. Законы идемпотентности (повторения, тавтологии)

а∙а∙а∙ … ∙а = а

а + а +... + а = а

Законы двойной инверсии

= а

т.е. двойную инверсию можно снять.

5. Законы дополнительности:

а) логическое противоречие: а∙ = 0

т.е. конъюнкция любой переменной и её инверсии есть 0.

в) закон исключенного третьего: а + = 1

т.е дизъюнкция любой переменной и её инверсия есть 1

6. Коммутативный закон (переместительный закон)

а ∙ b = b ∙ а; a + b = b + a

т.е. результат выполнения операций конъюнкции и дизъюнкции не зависит от того, в каком порядке следуют переменные.

7. Ассоциативные законы (сочетательные)

a(b ∙c) = (a∙b)c = a∙b∙c; a + (b + c) = (a + b) + c = a + c + b

т.е. для записи конъюнкции или дизъюнкции скобки можно упустить.

8. Дистрибутивные законы (распределительный)

а) конъюнкция относительно дизъюнкции a(b + c) = ab + ac;

в) дизъюнкция относительно конъюнкции a + bc = (a + b)(a + c)

Законы поглощения

a(a + b) = a; a(a + b)(a + c)... (a + z) = a;

a + ab = a; a + ab + ac +... + az = a;

a( + b) = ab; a + b = a + b

10. Законы склеивания (распространения)

ab + a = a (a + b)(a + ) = a

Законы обобщенного склеивания

ab + c + bc = ab + c;

(a + b)( + c) = ac + b;

(a + b)( + c)(b + c) = (a + b)( + c).

12. Законы де Моргана (законы инверсии)

а) для двух переменных

= +

т.е. инверсия конъюнкции есть дизъюнкция инверсий;

=

т.е. инверсия дизъюнкции есть конъюнкция инверсий;

в) для n переменных

= + + +... + ;

= ...

Теорема разложения

F (a, b,... w) = a F (1, b,..., w) + F (0, b,..., w);

F (a, b,... w) = [a + F(0, b,..., w)] ∙ [ + F(1, b,..., w)]

Таковы основные законы алгебры логики. Справедливость любого закона алгебры логики можно доказать разными методами. Так законы 1-5 доказываются прямой подстановкой вместо переменной а значений 0 или 1, что приводит к принятым аксиомам.

Справедливость приведенных законов булевой алгебры проверяется путем подстановки влогическое выражение 0 и 1, как показано в табл. 3.5 для формулы = v -закона де Моргана. Для доказательства построим совмещенную таблицу истинности.

Таблица 3.5 - Проверочная таблица для = v Таблица 1.9
Х1	Х2	Х1 ∙ Х2				v

Совпадение значений обеих частей при одинаковых наборах переменных доказывает справедливость этих законов.

Булевы функции одной переменной представлены в табл. 3.6

Таблица 3.6 – Функции одной переменной
Fi	Xi	Обозна- чение	Выражение	Название операции	Содержание
Fo				Fо = 0 Fо = х∙	Константа 0	Функция никогда не имеет значения 1, каким бы ни было значения переменной
F1			х	F1 = х	Повторение X	Функция повторяет значение переменной
F2				F2 =	Отрицание X	Функция имеет значение обратное значению переменной
F3				F3 = 1 F3 = х +	Константа 1	Функция всегда имеет значение 1, каким бы ни было значение переменной

Как видим, из четырех булевых функций практический интерес вызывает только операция отрица­ния F ₂ = .

Все 16 булевых функций F₀ – F₁₅ двух переменных Х₁ Х₂ представлены в табл. 3.7

Таблица 3.7 – Функции двух переменных
Х1 0011	Символическое обозначение	Выражение	Название операции	Содержание
Х2 0101
F0			F0 = 0	Константа 0	Функция никогда не имеет значения 1, каким бы ни было значения переменных
F1		Х1 & Х2 Х1 Х2	F1 = Х1 ∙X2	Конъюнкция, Функция И	Функция имеет значение 1, когда обе переменные имеют значение 1
F2		Х1 X2	F2 = X1 ∙	Запрет по Х2	Запрет по Х2. Отрицание импликации
F3		Х1	F3 =X1	Повторение Х1	Функция повторяет значение переменной Х1 не зависимо от значения переменной Х2
F4		Х2 X1	F4 = ∙X2	Запрет по Х1 Отрицание импликации	Функция имеет значение 0, если переменная Х1 имеет значение 1, каким бы ни было значения Х2.
F5		Х2	F5 =X2	Повторение Х2	Функция повторяет значение переменной Х2 не зависимо от значения переменной Х1
F6		X1 X2	F6 = X1 X2	Сумма по модулю 2, Неэквивалентность, Исключающая ИЛИ	Функция имеет значение 1 только тогда, когда одна из переменных имеет значение 1, но не вместе.
F7		X1 + X2	F7 =X1 v X2	Дизъюнкция, Функция ИЛИ	Функция имеет значение 0, когда обе переменные имеют значение 0
F8		Х1 Х2 Х1 Х2	F8 =X1 X2	Отрицание дизъюнкции, Стрелка Пирса, Функция ИЛИ-НЕ	Функция имеет значение 1, когда обе переменные имеют значение 0
F9		X1 X2	F9 = X1 X2	Эквивалентность, Равнозначность	Функция имеет значение 1, когда обе переменные имеют одинаковое значение и 0 когда обе переменные имеют разные значения.
F10			F10 =	Отрицание Х2, Инвертор, Функция НЕ Х2	Функция имеет значение, обратное значению переменной Х2 и не зависит от значения Х1
F11		X1 X2 X1	F11 =X1 X2	Импликация от Х2 к Х1	Функция имеет значение 0 когда переменная Х1 =0, а переменная Х2 =1
F12			F12 =	Отрицание Х1 Инвертор, Функция НЕ Х1	Функция имеет значение, обратное значению переменной Х1 и не зависит от значения Х2
F13		Х1 Х2	F13 =Х1 Х2	Импликация от Х1 к Х2	Функция имеет значение 0 когда переменная Х1 =1, а переменная Х2 =0
F14		X1 / X2	F14 = X1 / X2	Отрицание конъюнкции, Штрих Шеффера, И-НЕ	Функция имеет значение 0, когда обе переменные равны 1
F15			F15 = 1	Константа 1	Функция всегда имеет значения 1, каким бы ни было значения переменных

Как следует из табл.3.6, функции F₀ и F₁₅ — константы, F₃ и F₅ — повторяют, а F₁₀ и F₁₂ — отрицают одну из переменных, F₁ и F₇ — конъюнкция и дизъюнкция, ко­торые рассмотрены ранее. К новым булевым функциям (операциям) относятся сле­дующие.

Исключение (запрет) — двухместная булева операция, результатом которой является значение единицы тогда и только тогда, когда значение одного операнда равно единице, а другого — нулю. Записывается в виде:

F₂ = X₁ или F₄ = X₂.

Сумма по модулю два (исключающее ИЛИ, отрицание эквивалентности) — двухместная булева операция, результатом которой является значение единицы то­гда и только тогда, когда операнды имеют разные значения. Обозначается в виде:

F₆ = X₁ X₂ = Х₂ Х₁

Отрицание дизъюнкции (операция НЕ ИЛИ, стрелка Пирса) — булева опера­ция, результатом которой является значение единицы тогда и только тогда, когда оба операнда равны нулю. Обозначается в виде:

F₈ = X₁ X₂ =

Обобщая для п переменных, имеем:

X₁ X₂ X₃... X_n = ∙ ∙ ∙... =

Эквивалентность (равнозначность) –двухместная булева операция, результатом которой является единица тогда и только тогда, когда операнды принимают одинаковые значения. Обозначается в виде:

F₉ = Х₁ X₂ = Х₁ ∙ Х₂ ∙ .

Импликация (включение) — двухместная булева операция, результатом кото­рой является значение нуль тогда и только тогда, когда значение одного из операн­дов равно нулю, а другого — единице. Обозначается в виде:

F₁₁ = X₁ X₂ = X₁ ; F₁₃ = X₁ X₂ = X₂

Отрицание конъюнкции (операция И-НЕ, штрих Шеффера, отрицание пере­сечения) — булева операция, результат которой равен нулю тогда и только тогда, когда оба операнда равны единице. Обозначается в виде:

F₁₄ = X₁ / X₂ =

Обобщая для п переменных, имеем:

X₁ / X₂ / X₃... / X_n = ... =

Познавательные статьи:



Техника прыжка в длину с разбега

Тактические действия в защите

История Олимпийских игр

История развития права интеллектуальной собственности