Элементы общей алгебры. Алгебра логики. Понятия алгебры логики, страница 2

При n =2. Получается N=2²=4 набора переменных и соответствующие им  2⁴=16 функции.

х1	х2	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15	f16
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

f₁ – константа «0»;

f₂ = – логическое умножение конъюнкция;

f₃ = –  запрет по х₂ (отрицание импликации ); истинно, когда х₁=1, а х₂=0;

f₄ = х₁ – переменная х₁;

f₅ = –  запрет по х₁ отрицание импликации ;

f₆ = х₂ – переменная х₂;

f₇ = –  сумма по модулю 2 (логическая неравнозначность);

f₈ = –  логическое сложение дизъюнкция;

f₉ = –  эквивалентность (логическая равнозначность);

f₁₀ = стрелка Пирса;

f₁₁ =  – инверсия х₂ (отрицание х₂);

f₁₂ =  – импликация х₂ в х₁ (дополнение к разности х₂\ х₁);

f₁₃ =  – инверсия х₁ (отрицание х₁);

f₁₄ =  – импликация х₁ в х₂ (дополнение к разности х₁\ х₂);

f₁₅ = х₁/ х₂= штрих Шефера;

f₁₆ – константа «1».

Существует тесная связь между логическими функциями и множествами. Логические функции определяют отношения между двумя видами множеств – универсальным и пустым. Поэтому все правила и законы теории множеств имеют место и для логических функций с учетом того, что таких множеств только два.

Если мы говорим, что функция логического суммирования двух переменных f =  при равенстве  тоже равняется 1, то мы понимаем, что происходит объединение двух идентичных универсальных множеств в одно. По законам теории множеств результатом будет это же самое универсальное множество. Если объединим два пустых множества, то получим тоже пустое множество.

Аналогично можно пояснить и другии операции.

Перечисленные выше 16 функций Булевой алгебры для двух переменных носят название элементарных.

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

	Базисные логические     функции

 

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

Каждая из приведенных 16 функций имеет инверсию. Например: f₁ и f₁₆ (константа 0 и константа 1),  f₄ и f₁₃ (х₁ и  ), f₂ и f₁₅ (конъюнкция и штрих Шефера).

Формулы для элементарных функций.

1.  Правило де Моргана

 или

Доказываются правила при помощи таблиц истинности.

А	В							А	В
0	0	1	1	1	0	0		0	0	1	1	1	0	0
0	1	1	0	1	0	0		0	1	1	0	0	1	1
1	0	0	1	1	0	0		1	0	0	1	0	1	1
1	1	0	0	0	1	1		1	1	0	0	0	1	1

Т. к. в двух последних колонках получаем одинаковые равенства, то правило де Моргана – доказано.

А	В
0	0	1	1	1
0	1	1	1	1
1	0	0	0	0
1	1	0	1	1

2.

 

3.

4.   –  двойное отрицание

А           В

5.

6.

7.

8.

9.   

                           стрелка Пирса

10.

Штрих Шефера

Суперпозиция функций – это функция f=f(f₁, … , f_n), которая получена из функций  f₁, … , f_n  путем их подстановки вместо аргументов  х₁, … , х_n  в функцию

f(х₁, … , х_n). Пример: дана f=(х₁, х₂, х₃, х₄)=((( и функция f₁=;    f₂=
橢橢쿽쿽Й鐮ꖟꖟᚏŔ￿￿￿lʶʶʶʶ͎͎

х1	х2	х3				[    ]
0	0	0	1	0	1	1
0	0	1	1	1	1	1
0	1	0	1	0	0	0
0	1	1	1	1	0	1
1	0	0	0	1	0	1
1	0	1	0	0	0	0
1	1	0	0	1	0	1
1	1	1	0	0	0	0