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

1. 

   идемпотентность

2. 

   коммутативность

3. 

   дистрибутивность

4. 

Законы де Моргана

Свойства констант

Законы двойного отрицания

Законы противоречия

5. 

   ассоциативность

6. 

7. 

8. 

9. 

   Законы «исключенного третьего» Методические указания к заданию №3.

Пусть А и В – два множества.

Бинарным отношением R из множества А в множество В называется подмножество декартова произведения множеств А и В. R  А*В. Если а, b находится в отношении

R(a, b)R.

Пример:

Отношение на множестве N (натуральных чисел) x R y : x y

Пары (3; 10), (4; 4) принадлежит R

Пары (10, 3), (0; -1) R

Бинарные отношения можно задавать любым способом задания множеств (например, список пар, для которых данное отношение выполняется).

Пример:

А = {1; 2; 3}, В{-2; 4}

aRb : ab

R = {(1;4), (2;4), (3; 4)}

Так же отношения на конечных отношениях можно задавать матрицей.

Матрица бинарного отношения на множестве М = {а₁, а₂, … ,а_m} – это квадратная матрица порядка m, в которой элемент C_ij , стоящий на пересечении i –ой строки и j-го столбца определяется следующим образом:

C_ij =

Пример:

М = {1; 2; 3; 4; 5; 6}, aRb, х

Зададим матрицей данное бинарное отношение

Свойство отношений:

Определение: Бинарное отношение R называется рефлексивным, если для любого а  М имеет место: (а,а) R.

Пример: M =N; xRy : x y R - рефлексивное

Определение: Бинарное отношение R называется антирефлексивным, если не для какого элемента а  М не выполняется условие (а,а) R.

Пример: M =N; xRy : x<y R – антирефлексивное, так как в множестве натуральных чисел нет такого числа, которое было бы меньше самого себя.

Определение: Бинарное отношение R называется симметричным, если для любого (а, b) М из того что (а,b) R  (b, а) R

Определение: Бинарное отношение R называется антисимметричным, если для любого (а, b)  М из того что (а,b) R  (b, а) R следует что а = b.

Пример: xRy : x y

Определение: Бинарное отношение R называется транзитивным, если для любого а,b, c  М (а, b) R, (b, c) R (a, c) R

Пример: R : x y

Определение: Бинарное отношение R называется отношением эквивалентности, если оно симметрично, рефлексивно, транзитивно.

Пример: Определить, будет ли данное отношение R отношением эквивалентности. М = (-; +), xRy : x-y 3

1. Рефлексивность.

Возьмем любое аМ, подставим вместо х и y а-а 3, 0 3 – выполняется при любом а, значит пара (а,а) R. R – рефлексивное.

2. Симметричность.

Любые (а, b) М, такие что (а, b) R, то есть выполняется а-b 3.

Составим разность: b-a=-(a-b)=-1a-b=a-b 3.

(b-a) 3  (b; a)R

2. Транзитивность.

Любые (a, b, c)M такие что (а, b)R, a-b 3, ( b, c)R, b-c 3.

Составим а-с=(а-b)+(b-c)=а-b+b-c

а-с 6

R – не транзитивно.

П

i

усть на множестве М задано отношение эквивалентности R. Осуществим следующее построение. Выберем элемент а₁М и образуем класс (подмножество М ) С₁, состоящее из а₁ и всех элементов, эквивалентных а₁; затем выберем элемент а₂С₁ и образуем класс С₂, состоящий из а₂ и всех элементов эквивалентных а₂ и т. д. Получится система классов С₁, С₂ … (возможно, бесконечная) такая что любой элемент из М входит хотя бы в один класс, т. е. . Эта система классов обладает следующими свойствами:

1. Она образует разбиение, т. е. классы попарно не пересекаются;

2. Любые два элемента из одного класса эквивалентны;

3. Любые два элемента из разных классов неэквивалентны.

Все эти свойства немедленно вытекают из рефлексивности, симметричности и транзитивности R. Действительно, если бы классы, например С₁ и С₂, пересекались, то они имели бы общий элемент b, эквивалентный а₁ и а_2, но тогда из-за транзитивности R было бы а₁Ra₂, что противоречит построению С₂. Аналогично доказываются другие два свойства.

Построенное разбиение, т. е. система классов, называется системой классов эквивалентности по отношению R. Мощность этой системы называется индексом разбиения. С другой стороны, любое разбиение М на классы определяет некоторое отношение эквивалентности, а именно, отношение «входить в один и тот же класс данного разбиения».

Пример:

Разбиение множества N по отношению «иметь общий остаток от деления на 7». Образуется 7 классов:

K₀ – класс натуральных чисел, которые при делении на 7 имеют остаток 0.

K₀ ={7;14;21;28; … }

К₁ - класс натуральных чисел, которые при делении на 7 имеют остаток 1.

К₁={1;8;15;22; …}

К₂ - класс натуральных чисел, которые при делении на 7 имеют остаток 2.

К₂={2;9;16;23; …}

К₃ - класс натуральных чисел, которые при делении на 7 имеют остаток 3.

К₃ = {3;10;17;24; …}

К₄ - класс натуральных чисел, которые при делении на 7 имеют остаток 4.

К₄ = {4;11;18;25; …}

К₅ - класс натуральных чисел, которые при делении на 7 имеют остаток 5.

К₅ ={5;12;19;26; …}

К₆ - класс натуральных чисел, которые при делении на 7 имеют остаток 6.

К₆ = {6;13;20;27; …}

Объединение всех этих классов – есть множество натуральных чисел N.

Никакие два класса попарно не пересекаются.

Отношение порядка.

Отношение называется отношением нестрогого порядка, если оно рефлексивно, антисимметрично, транзитивно.

xRy: x y

Отношение называется строгого порядка, если оно антирефлексивно, антисимметрично, транзитивно.

XRy: x<y