- •Ф.К. Алиев, и.А. Юров
- •Введение
- •Основные способы задания двоичных функций
- •1.1. Табличный способ задания
- •1.2. Геометрический способ задания
- •1.3. Задание двоичных функций формулами
- •Основные способы задания двоичных функций (продолжение)
- •2.1. Нормальные формы двоичных функций
- •2.2. Многочлен Жегалкина и действительный многочлен двоичной функции
- •2.3. Теорема о разложении в ряд Фурье
- •Полнота и замкнутость. Критерий полноты системы. Функционально полные системы. Замкнутые классы булевых функций
- •3.1. Полнота и замкнутость. Функционально полные системы
- •3.2. Замкнутые классы булевых функций
- •3.3. Критерий полноты системы булевых функций
- •4.1. Псевдобулевы функции
- •4.2. Функции k-значной логики
- •5.1 Минимизация двоичных функции
- •5.2. Геометрическая интерпретация минимизации днф
- •6.1. Метод Квайна — Мак-Класки нахождения сокращённой днф двоичной функции
- •6.2. Метод нахождения тупиковых днф
- •6.3. Метод Петрика нахождения тупиковых днф
- •Алгебраические системы
- •7.1. Алгебраические системы. Булевы алгебры
- •7.2. Изоморфизм алгебраических систем
- •Алгебры высказываний. Предикаты и операции над ними
- •8.1. Основные логические операции и их свойства
- •8.2. Предикаты и операции над ними
- •Исчисление предикатов
- •9.1. Общее понятие о логическом исчислении
- •9.2. Формулы алгебры предикатов
- •9.3. Равносильность формул. Основные отношения равносильности
- •9.4. Использование равносильностей для упрощения формул
- •9.5. Построение исчисления предикатов
- •9.6. Выводимость и доказуемость формул
- •9.7. Семантика исчисления предикатов
- •Понятие о теории моделей
- •Элементы теории алгоритмов
- •11.1. Основные требования к алгоритмам
- •11.2. Машина Тьюринга и функции, вычислимые по Тьюрингу
- •11.3. Машины произвольного доступа и вычислимые функции
- •Частично рекурсивные функции и их вычислимость
- •Вычислимость суперпозиции
- •Вычислимость рекурсии
- •Вычислимость минимизации
- •Нумерация наборов чисел и слов
- •Нормальные алгоритмы
- •Нумерация алгоритмов
- •1. Нумерация машин Тьюринга
- •2. Нумерация мпд-программ
- •Универсальные функции
- •Алгоритмически неразрешимые проблемы
- •16.1. Алгоритмически неразрешимые проблемы
- •16.2. Примечательные алгоритмически неразрешимые проблемы
- •Характеристики сложности вычислений
- •Характеристика сложности вычислительных задач
- •18.1. Классы сложности p и np и их взаимосвязь
- •18.3. Основные np-полные задачи. Сильная np-полнота
- •Список Литературы
7.2. Изоморфизм алгебраических систем
В математике при изучении алгебраических систем их обычно классифицируют по темам и по свойствам. Так получаются классы полугрупп, групп, колец, полей, булевых алгебр и т.д. В каждом таком классе алгебраические системы изучаются с точностью до изоморфизма.
Определение 7.13. Алгебраические системы A, B одной и той же сигнатуры типа <n1, …, nk; m1, …, ml> называются изоморфными, если существует биективное отображение :A B, такое, что:
1) для любой операции и любых элементовA выполняется равенство: ;
2) для любого отношения и любых элементовA:
.
При этом само отображение называется изоморфизмом системы A на систему B.
Пример 7.14. Пусть B1 — булева алгебра всех подмножеств множества M = {a1, …, an}, B2 — булева алгебра всех делителей числа m = p1 p2 … pn, где p1 p2 … pn — различные простые числа. Определим отображение :B1 B2, положив и. Легко видеть, что,;, а также,, для любых подмножествA, B множества M. Это и означает, что есть изоморфизм булевой алгебры B1 на булеву алгебру B2.
Замечание 7.15. Легко видеть, что отношение изоморфизма является отношением эквивалентности на любом множестве алгебраических систем одной сигнатуры и потому все такие системы разбиваются на классы изоморфных систем. Из определения 7.13 видно, что изоморфные алгебраические системы сигнатуры с точки зрения свойств операций и отношений отличаются лишь обозначениями элементов. Отождествив в системах из определения 7.13 элементыa и (a), мы получим одну и ту же алгебраическую систему. Тем самым достигается существенная экономия сил и времени при изучении всего многообразия алгебраических систем.
Замечание 7.16. Понятие изоморфизма естественным образом распространяется на алгебраические системы различных, но однотипных сигнатур. При этом необходимо только предварительно установить между операциями (а также между отношениями) систем взаимно однозначное соответствие, сохраняющее арности. Так, если операции fi соответствует операция , то условие 1 определения 7.13 запишется в виде:
.
В частности, если fi — бинарная операция «», аf — бинарная «», то последнее равенство будет иметь вид:
.
Пример 7.17. Рассмотрим алгебры R+()и R(+), где R+ — множество всех положительных действительных чисел; R — множество всех действительных чисел. Положим , для любогоx R+, где a — некоторое положительное число, a1. Тогда условие 1 определения 7.13 гарантируется в этом случае известным свойством логарифмов: .
Замечание 7.18. Пример 7.17 показывает, что в некоторых случаях переход к изоморфной алгебре позволяет существенно упростить вычисления. В этом проявляется ещё одна положительная роль понятия изоморфизма.
Л е к ц и я 8
Алгебры высказываний. Предикаты и операции над ними
8.1. Основные логические операции и их свойства
В математической логике изучаются высказывания и различные связи между ними. При этом понятие высказывания считается основным, неопределяемым понятием. В качестве пояснения говорят лишь, что высказывание — это утверждение, относительно которого известно, истинно оно или ложно.
Если высказывание а истинно или ложно, то говорят, что оно имеет значение «и» или «л» и пишут
а и или а л.
Высказывания а и b, имеющие одинаковые значения, называются равносильными, что обозначается в виде
а b.
Очевидно, что отношение равносильности высказываний является отношением эквивалентности на любом множестве высказываний М, и потому М разбивается на два класса высказываний — на класс истинных и класс ложных высказываний.
В обычной речи мы из определенных высказываний а, b с помощью различных связок можно образовывать новые высказывания, например «а и b» «а или b» «если а, то b», «неверно, что а». В математической логике эти высказывания обозначаются в виде
a b (a b), a b, a b, a ( a)
и называются конъюнкцией, дизъюнкцией, импликацией и отрицанием высказывания а (табл.8.1).
В высказываниях a b, a b, a и b называются членами, или компонентами, соответственно конъюнкции и дизъюнкции; в высказывании а -> b а называют посылкой, b — заключением импликации.
Обозначим через = {и, л}. Тогда табл.8.1 может служить определением операций , , , на множестве .
Таблица 8.1
a |
b |
a b |
a b |
a b |
a |
и |
и |
и |
и |
и |
л |
и |
л |
л |
и |
л |
л |
л |
и |
л |
и |
и |
и |
л |
л |
л |
л |
и |
и |
При этом операции , , обладают следующими свойствами:
1) операции , коммутативны, ассоциативны, идемпотентны, дистрибутивны одна относительно другой и связаны законами поглощения: a (a b) a, a (a b) a;
2) операция отрицания — инволютивна (т.е. ) и связана с операциями, законами де Моргана: и соотношениями а а л, а а и.
Отсюда следует, что алгебра (, , ) является булевой алгеброй. В ней роль 1 и 0 играют соответственно элементы и, л.
Определение 8.1. Двухэлементная булева алгебра (, , ) называется алгеброй высказываний.
Из табл.8.1 видно, что импликация (->) также является операцией на множестве и обладает рядом свойств, связывающих её с другими операциями:
a b b a (закон контрапозиции),
a (b a) и,
ab b и,
a b a b и другие.