6. Матрицы бинарных отношений и их свойства.

Рассмотрим два конечных множества А={a₁, a₂,…, a_m}, B={b₁, b₂,…, b_n} и бинарное отношение . Определим матрицу [P]=(p_ij) размера бинарного отношения Р по следующему правилу:

Основные свойства матриц бинарных отношений:

1. Если , [P]=(p_ij), [Q]=(q_ij), то и ,

2. Если , , то ,

3. [P^-1]=[P]^T.

4. Если , [P]=(p_ij), [Q]=(q_ij), то p_ij≤q_ij.

5. [id_A]=E.

11.Булевы алгебры.

Мн-во М с двумя бинарными операциями, одной унарной операцией с двумя выделенными элементами (0,1) называется булевой алгеброй, если выполняются следующие аксиомы:

1. Ассоциативность:

2. Коммутативность:

3. Дистрибутивность:

4. Поглощение:

5. Закон двойственности(Законы де Моргана):

6. Дополнимость и свойства констант (Законы нуля и единицы: 0=ø, 1=U)

7. Закон двойного отрицания:

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

Поставим в соответствие высказыванию Р логическую переменную х, которая принимает значение 1, если Р истинно, и 0, если Р ложно.

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

Определим понятие формулы алгебры логики:

1. Любая логическая переменная является формулой

2. Если φ и ψ – формулы, то выражения являются формулами;

3. Никаких других формул, кроме построенных нет.

12. Логические операции, их таблицы истинности.

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

Действия логических операций задаются таблицами истинности

φ	ךφ	φ	ψ
0	1	0	0	0	0	1	1
1	0	0	1	0	1	1	0
		1	0	0	1	0	0
		1	1	1	1	1	1

Другие логические операции:

1. штрих Шеффера, или антиконъюнкция;

2. стрелка Пирса, или антидизъюнкция;

3. кольцевая сумма или сложение по модулю 2.

φ	ψ	φ|ψ
0	0	1	1	0
0	1	1	0	1
1	0	1	0	1
1	1	0	0	0

Внешние скобки не пишутся;

Для равносильных связок расстановка скобок выполняется слева направо.

23. Перестановки.

Перестановка элементов множества М- любой порядок (а₁,а₂,..а_n) состоящий из n различных элементов множества М.

Перестановки отличаются друг от друга только порядком входящих в них элементов.

Теорема1: Алгебра Sn является группой. При n>= она некоммутативна.

Теорема2: Каждую подстановку можно однозначно (с точностью до порядка сомножителей) представить в виде произведения независимых циклов.

Теорема3: Каждая подстановка есть произведение транспозиций.