Файл: Учебное пособие по изучению курса Дискретная математика для студентов направления 230100 Информатика и вычислительная техника.pdf

2.3. Алгебры с одной операцией
Самой простой структурой является алгебра с одной операцией.
Рассмотрим алгебру с одной бинарной операцией :
Алгебра с одной ассоциативной бинарной операцией называется
полугруппой.
Полугруппа с
единичным элементом называется
моноидом.
Единичным называется такой элемент, для которого выполняется e а=а для всех а.
Примеры.
1. Множество слов в алфавите А с операцией конкатенации
(присоединения) образует полугруппу.
2. Множество слов в алфавите А вместе с пустым символом λ образует моноид.
Группа – это моноид, в котором существует обратный элемент.
Элемент называется обратным, если
Пример.

36
Множество квадратных матриц порядка n
образуют группу относительно операции умножения матриц. Единицей группы является единичная матрица, обратным элементом является обратная матрица.
Группа, в которой выполняется коммутативный закон, называется
абелевой группой.
Примеры.
1. - множество целых чисел образует абелеву группу относительно сложения. Нулем группы является 0, обратным элементом является число с противоположным знаком.
2. - множество целых чисел не образует группу по умножению, т.
к. может не существовать обратного элемента.
3. - множество положительных рациональных чисел образует абелеву группу относительно операции умножения. Нулем группы является
1, обратным элементом является обратное число, например, для числа 5
обратным числом будет 1/5.
4.
- булеан образует абелеву группу относительно симметрической разности. Нулем группы является пустое множество,
обратным элементом является дополнение.
Свойства групп
1.
2.
3.
4.
2.4. Алгебры с двумя операциями
Рассмотрим алгебры с двумя бинарными операциями, которые условно будем называть сложением ( ) и умножением ( ).
Кольцо – это множество М с двумя бинарными операциями и
, в котором:
1. Сложение ассоциативно:
2. Существует нуль:
3. Существует обратный элемент:
4. Сложение коммутативно:
Таким образом, кольцо – это абелева группа по сложению.
5. Умножение ассоциативно:
Таким образом, кольцо – это полугруппа по умножению.
6. Умножение дистрибутивно слева и справа:
7. Если выполняется коммутативный закон для умножения
,
то кольцо называется коммутативным.
8. Если в коммутативном кольце существует единица
, то оно называется кольцом с единицей.
Таким образом, кольцо с единицей – это моноид по умножению.
Примеры.

37 1. , где Z – множество целых чисел, + - операция сложения, * - операция умножения - коммутативное кольцо с единицей.
2. n
,+,*> , где Z
n
– множество натуральных чисел, + - операция сложения, * - операция умножения - коммутативное кольцо с единицей.
3. Множество квадратных матриц порядка n относительно операций сложения и умножения матриц есть кольцо с единицей,
где единицей является единичная матрица. При n>1 оно некоммутативно.
4. Пусть К – произвольное коммутативное кольцо. Рассмотрим всевозможные многочлены с переменной х и коэффициентами из К. Относительно алгебраических операций сложения и умножения многочленов это коммутативное кольцо. В качестве К
может, например, выступать множество целых, рациональных или действительных членов.
Свойства кольца
1.
2.
3.
Поле – это множество М с двумя бинарными операциями и
, в котором:
1. Сложение ассоциативно:
2. Существует нуль:
3. Существует обратный элемент:
4. Сложение коммутативно:
Таким образом, кольцо – это абелева группа по сложению.
5. Умножение ассоциативно:
6. Существует единица:
7. Существует обратный элемент по умножению:
8. Умножение коммутативно:
Таким образом, кольцо – это абелева группа по умножению.
9.
Умножение дистрибутивно относительно сложения:
Примеры.
1. , где R – множество вещественных чисел, + - операция сложения, * - операция умножения.
2. , где Q – множество рациональных чисел, + - операция сложения, * - операция умножения.
3. Пусть Е={0,1}. Определим операцию
:
следующим образом:
. Определим операцию
:
следующим образом:
. , > является полем и называется двоичной арифметикой.
Свойства поля.
1.

38 2.
3. Если
, то
4. Если
, то а=0 или b=0.
2.5. Морфизмы
Рассмотрим отображение (функциональное, всюду определенное соответствие) множества А в множество В (рис. 19 )
А
А
1
А
2
В
1
В
2
ρ
f f
φ
Рис. 19. Гомоморфное отображение
Отображение f называется отображением гомоморфизма или
гомоморфным отображением, или просто морфизмом, если для элементов множества А выполняется А
1
ρ
А
2
, а для образов выполняется В
1
ϕ
В
2
. То есть f(А
1
ρ
А
2
) = f(А
1
)
ϕ
f(А
2
) , где f(А
1
) = В
1
, f(А
2
) = В
2
Пусть существуют две алгебры и
. Если существует функция такая, что
, то говорят, что f - гомоморфизм из в
. Действие этих функций можно изобразить с помощью диаграммы на рис. 20.
А
А
B
B
f
ρ
f
φ
Рис. 20. Пример гомоморфизма
Пусть f – гомоморфизм. Тогда, если взять конкретное значение и
двигаться по двум различным путям на диаграмме, то получится один и тот же элемент
. Такая диаграмма называется коммутативной, т. к. условие гомоморфизма можно переписать следующим образом:
Пример.
Пусть А=, B=10
,+
10
>, где N – множество натуральных чисел, +
- операция сложения, N
10
={0,1,2,3,4,5,6,7,8,9}, +
10
– сложение по модулю 10.

39
Тогда функция f=a mod 10 – гомоморфизм из A в В, т. к. , например,
(1+15)mod 10=6, 1 mod 10+15 mod 10=6.
Гомоморфизмы, обладающие дополнительными свойствами имеют специальные названия:
•
Инъективный гомоморфизм называется мономорфизмом.
•
Сюръективный гомоморфизм называется эпиморфизмом.
•
Гомоморфизм,
который является биекцией называется
изоморфизмом.
•
Если А=В, то гомоморфизм называется эндоморфизмом, а изоморфизм называется автоморфизмом.
Понятие изоморфизма является одним из центральных понятий,
обеспечивающих применимость алгебраических методов в различных областях.
Пусть
, где N – множество натуральных чисел,
- набор операций,
, где В - множество четных чисел,
- набор операций.
Пусть А и В изоморфны. Пусть в алгебре А установлено свойство R
1
=R
2
, где
R
1
и R
2
– некоторые формулы в сигнатуре
. Т. к. А и В изоморфны, то отсюда следует, что в алгебре В справедливо свойство Ф1=Ф2, где Ф1 и Ф2 –
формулы, полученные из формул R1 и R2 заменой операций из сигнатуры на соответствующие операции из сигнатуры
. Таким образом достаточно установить какое-то свойство в одной алгебре и оно автоматически распространяется на все изоморфные алгебры.

40
Контрольные вопросы
1. Что такое алгебраическая структура (алгебра)?
2. Что такое сигнатура алгебраической структуры?
3. Какое подмножество является замкнутым относительно операции
ϕ
?
4. Что такое подалгебра алгебраической структуры? Привести примеры алгебраических структур и подалгебр.
5. Привести примеры:
a. ассоциативных и неассоциативных операций;
b. коммутативных и некоммутативных операций;
c. дистрибутивных и недистрибутивных операций;
6. Что такое полугруппа? Привести примеры.
7. Что такое моноид? Привести примеры.
8. Что такое группа? Привести примеры.
9. Какая группа является абелевой?
10.Какими свойствами обладает группа?
11.Что такое кольцо? Привести примеры.
12.Какими свойствами обладает кольцо?
13.Что такое поле? Привести примеры.
14.Какими свойствами обладает поле?
15.Какое отображение называется гомоморфным? Привести примеры.
16.Что такое изоморфизм? Привести примеры изоморфных алгебр.

41
3. Математическая логика
3.1. Основные определения
3.1.1. Понятие высказывания
Рассмотрим логику высказываний, которая лежит в основе всех других разделов математической логики и необходима для их понимания.
Логика высказываний строится также как и другие математические теории. В качестве основных понятий берется некоторый класс объектов, а также некоторые свойства, отношения и операции над этими объектами.
Основным объектом логики высказываний служат простые высказывания. Высказывание – это предложение, о котором можно сказать истинно оно или ложно.
Примеры.
1. Число 100 делится на 5.
2. Число 3 больше числа 5.
3. Луна больше Земли.
4. Сегодня светит солнце.
5. Вечером мы пойдем в кино.
Из простых высказываний с помощью некоторого числа логических операций можно построить сложные высказывания.
Примеры.
1. Число 100 делится на 5 и число 100 делится на 10.
2. Неверно, что 3 больше 5.
3. Сегодня мы пойдем в кино или мы пойдем в театр.
При изучении логики высказываний не обращают внимание на содержание простых высказываний, а интересуются только их истинностью или ложностью.
Сложные высказывания, получаемые из простых, будут также истинными или ложными. Их истинность или ложность будет зависеть от истинности образующих их простых высказываний.
3.1.2. Логические операции
Для изучения логических операций введем следующую систему обозначений:
•
простые высказывания будем обозначать буквами a, b, c, …, x, y ,z;
•
значения истинности будем обозначать 1 – истинно, 0 – ложно.
Действия логических операций будем представлять в виде таблиц истинности.

42
1. Отрицание или инверсия (
¬
– НЕ)
Пример.
а: 7 делится на 5 без остатка.
¬
а: Неверно, что 7 делится на 5 без остатка.
а
¬
а
0 1
1 0
Эта таблица и принимается в качестве определения операции отрицания.
2. Конъюнкция (
∧
,
&
, ·, логическое И )
Действие операции определяется следующим образом: сложное высказывание а
&
b истинно только в том случае, когда оба высказывания (а и b) имеют значение истинно.
а b а
&
b
0 0
0 0
1 0
1 0
0 1
1 1
Примеры.
а. 6 делится на 3 без остатка (1);
b. 10 больше 5 (1);
с. 7 делится на 3 без остатка (0);
d. 3 больше 7 (0);
a&b=1
a&c=0
c&d=0
3. Дизъюнкция (
∨
,+,логическое ИЛИ)
Действие операции определяется следующим образом: сложное высказывание а
∨
в ложно только в том случае, когда оба высказывания (а и в)
ложны.
a b a
∨
b
0 0
0 0
1 1
1 0
1 1
1 1
Примеры.
а
∨
b=1
a
∨
c=1

43
c
∨
d=0
4. Импликация (
) “если а, то b”
Действие операции определяется следующим образом: сложное высказывание а b ложно только в том случае, когда а истинно, а b – ложно.
a b a b
0 0
1 0
1 1
1 0
0 1
1 1
А называется антецедентом, а b – консеквентом.
5. Эквивалентность (

)
Действие операции определяется следующим образом: сложное высказывание аb истинно, если а истинно и b истинно, или если а ложно и b ложно.
a b ab
0 0
1 0
1 0
1 0
0 1
1 1
Эквивалентность примерно соответствует употреблению выражения
«тогда и только тогда».
6. Сумма по модулю два (
)
a b a b
0 0
0 0
1 1
1 0
1 1
1 0
7. Штрих Шеффера (

, обратная конъюнкция И – НЕ)
a b a

b
0 0
1 0
1 1
1 0
1 1
1 0

44
8. Стрелка Пирса
( , обратная дизъюнкция ИЛИ – НЕ )
a b a b
0 0
1 0
1 1
1 0
1 1
1 0
Используя эти логические операции можно строить сколь угодно сложные высказывания.
Приоритет выполнения операций:
⌐
&∨


Пример.
Сложное высказывание: «Если вы не пропускаете занятия и успешно занимаетесь, то Вы сдадите экзамен хорошо» можно записать следующим образом. Обозначим:
П – пропускаете занятия;
Y – успешно занимаетесь;
Х – сдадите экзамен хорошо,
тогда все высказывание запишется:
Значение истинности всего выражения будет зависеть от истинности переменных обозначающих простые высказывания.
Пример.
Пусть a=1, b=0, c=0, d=1.
Символы ⌐
&∨


называются пропозициональными связками,
a, b, c, … и т. д. - пропозициональными переменными. Выражение,
построенное из пропозициональных переменных с
помощью пропозициональных связок, называется пропозициональной формой или формулой.
3.1.3. Булевы функции
Функция называется функцией алгебры
логики.
y=f(x
1
,x
2
) – бинарная функция,
y=f(x
1
,x
2
,…., x n
) – n- арная функция.
Пример.

45
Т. о. каждое элементарное высказывание может принимать значение либо 0, либо 1. Каждому набору значений a, b, c соответствует одно значение всего сложного высказывания (0 или 1).
Булеву функцию от n переменных можно задать таблицей истинности x
1
…..
x n-1
x n
f(x
1,
…,
x n)
0 0
0 0
0 1
1 1
1
Переменные, которые принимают значения 0 или 1 называются булевыми переменными.
Некоторые функции всегда принимают значение 1 (на любом наборе переменных). Такие функции называются тавтологиями. Некоторые функции всегда принимают значение 0 (на любом наборе переменных). Такие функции называются противоречиями.
3.1.4. Формулы
Пусть
- множество булевых функций. Формулой над F
называется выражение либо переменная, либо формула над F.
F называется базисом формулы, f – главной (внешней) операцией, t i
–
подформулами.
Всякой формуле однозначно соответствует некоторая функция f. Это соответствие задается алгоритмом интерпретации, который позволяет вычислить значение функции при заданных значениях переменных.
Зная таблицы истинности для функций базиса можно вычислить таблицу той функции, которую реализует данная формула.
Примеры.
1.
x
1
x
2
x
1
x
2 0
0 0
0 0
0 0
1 0
0 1
1 1
0 0
1 0
1 1
1 1
1 1
1
Функция реализует дизъюнкцию на базисе
2.
x
1
x
2
x
1
x
2 0
0 1
0 0
0 1
0 1
1 1
0 0
0 1
1 1
1 0
0

46
Функция реализует дизъюнкцию на базисе
Таким образом, каждая формула определяет некоторую логическую функцию, которую можно представить в виде таблицы истинности для этой формулы. Если в формуле имеется n переменных, то возможны 2
n различных истинностных значений для этой формулы. Следовательно, таблица истинности будет иметь 2
n строк.
3.1.5. Равносильные формулы
Одна функция может иметь множество реализаций над данным базисом (т. е. ее можно записать с помощью различных формул). Формулы,
реализующие одну и ту же функцию, называют равносильными. Обозначают
Пример.
Пусть
,
Доказать, что
Равносильность двух формул можно доказать с помощью таблиц истинности. Формулы равносильны, если их значения истинности совпадают на любом наборе значений истинности, входящих в них переменных.
Таблица истинности для формулы А.
x y
z xy xz
A
0 0
0 1
0 0
0 0
1 1
0 0
0 1
0 0
0 1
0 1
1 0
0 1
1 0
0 0
0 1
1 0
1 0
1 1
1 1
0 1
0 0
1 1
1 1
1 1
Таблица истинности для формулы B.
x y
z xz
B
0 0
0 0
0 0
0 0
0 1
0 0
0 0
0 1
0 0
1 0
1 0
1 1
0 1
0 1
1 0
0 1
0 0
1 1
0 1
1 0
1 1
1 1
0 0
0 0
0 1
1 1
0 0
1 1
Тот факт, что равносильность формул логики высказываний можно проверить непосредственно, связан с тем, что переменные, входящие в формулу могут принимать конечное число значений (2
n
).
Но, если в формуле большое количество переменных, то вычисление всех значений истинности для формулы становится очень трудоемкой задачей.

47
Равносильность формул логики высказываний аналогична тождествам элементарной алгебры, известным из средней школы. Но тождественное равенство алгебраических формул нельзя проверить простым перебором значений, т. к. число возможных значений переменных неограниченно,
следовательно, доказательство равносильности никогда не закончится. В
элементарной алгебре тождественные равенства формул устанавливаются с помощью небольшого числа основных тождеств – законов, связывающих между собой арифметические операции.
Для логики имеют место следующие равносильности (рассмотрим только формулы, которые содержат знаки
).
Таблица 6. Основные равносильности алгебры логики
№
Название
& (·)
∨
1
Коммутативный
АВ=ВА
А
∨
В В
∨
А
2
Ассоциативный
А(ВС)=(АВ)С
А
∨
(В
∨
С) (А
∨
В)
∨
С
3
Дистрибутивный
А(В
∨
С)=АВ
∨
АС
А
∨
(ВС) (А
∨
В)(А
∨
С)
4
Идемпотентности
А
·А А
А
∨
А А
5
Поглощения
А(А
∨
В) А
А
∨
АВ А
6
Закон де Моргана
7
Свойство нуля
А
· 0 = 0
А
∨
0 А
8
Свойство единицы
А
·1=А
А
∨
1=1 9
Исключенного третьего
А
⋅
=0
А
∨
=1 10
Двойное отрицание
= А
11. А В
∨
В
12. АВ=А·В
∨
13. А В=
·В
∨
А·
14. А

В = А
∨
В = А·В
15. А
↓
В =
=
∨
3.1.6. Подстановка и замена
Если в формулу входит переменная х, то это можно обозначить как
. Если в формулу входит подформула
, то обозначим это как
Вместо подформулы или переменной можно подставить другую формулу или переменную. В результате получится новая правильно построенная формула.

48
Если подстановка производится вместо всех вхождений заменяемой переменной или подформулы, то результат обозначим:
{
, т. е. все вхождения переменной х заменяем на подформулу
Если подстановка производится вместо некоторых вхождений, то результат обозначим
, т. е. первое вхождение заменяем на

1   2   3   4   5