25. Классы элементарных логических функций.
Определяется следующие 5 классов:
0
– класс: Функции, которые сохраняют
нулевое значение на нулевом наборе
терминов, то есть
к
этому классу относится все функции
1
– класс: Все функции, которые имеют
значение 1 на единичном значении термов,
то есть
.
К 1 классу относятся все нечетные функции.
2
– класс: Класс линейных функции – все
функции, у которых в полиномиальном
представлении нет слагаемого
.
3
– класс: Класс самодвойственных функций
– функции, для которых выражается
соотношение:
и четыре
,
,
,
.
4
– класс: Класс монотонных функций –
функции, для которых выражается
неравенство:
,
если
,
.
Приведем таблицу принадлежности логических функций тому или иному классу.
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
2 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
3 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
4 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
Зададим: 1 – f принадлежит некоторому классу
0 – f не принадлежит некоторому классу
26. Законы логики Буля.
Существует 2 подхода к доказательству:
1. аксиоматический .
2. конструктивный
а) идемпотентности: а=а∩а; а=аUа
б) коммутативности: а∩b=b∩а; аUb=bUа
в) ассоциативности: (a∩b) ∩c=a∩(b∩c) ; (aUb) Uc=aU(bUc)
г) дистрибутивности: a∩(bUc)=a∩bUb∩c ; aU(b∩c)=(aUb) ∩ (aUc)
д)
законы нуля и единицы:
е) законы поглощения: aU(a∩b)=a; a∩(aUb)=a
7.
Законы де Моргана:
8.
Законы склеивания:
Не все 8 законов независимы друг от друга
Например закон идемпотентности может быть получен из закона поглощения с использованием закона дистрибутивности.
Закон поглощения
а=аU(а∩b)=(aUa) ∩ (aUb)=(a∩ (aUb))(a∩ (aUb))=aUa 1)aUa=a
Закон поглащения может быть выведен из закона 0 и 1
аU(a∩b)=(a∩1)U(a∩b)=a(1Ub)=a∩1=a
Законы идимпотенции относительно дизъюнкции, т.к. можно вывести из закона 0 и 1
аUа=(аUа)
∩1=(аUа)
∩ (аU
)=
а ∩ (аU
)=аU0=а
При доказательстве логических выражений нужно иметь в виду достойность логики Буля
Закон поглощения:
a∩ (aUb)=(aU0) ∩ (aUb)=aU (0∩b)=aU0=a
В качестве независимой системы аксиом используется следующие законы:
-коммутативности;
-ассоциативности;
-дистрибутивности;
-закон 0 и 1;