- •Оглавление
- •Глава 3. Логика высказываний 78
- •Глава 4. Логика предикатов 90
- •Введение
- •I. Системы счисления
- •1.1. Непозиционные системы счисления. Римская система счисления
- •1.2. Позиционные системы счисления
- •1.3. Взаимосвязь систем счисления
- •I. Алгоритм перевода целого числа Aq из q-ичной системы счисления в число Bd d-ичной системы
- •II. Алгоритм перевода целого числа Ad из d-ичной системы счисления в число Bq q-ичной системы
- •III. Алгоритм перевода правильных дробей из q-ичной системы счисления в d-ичную с вычислениями в d-ариф-метике
- •IV. Алгоритм перевода правильных дробей из d-ичной системы счисления в q-ичную с вычислениями в d-арифметике
- •V. Алгоритм перевода чисел из d-ичной системы счисления в dn-ичную систему счисления
- •VI. Алгоритм перевода чисел из dn-ичной системы счисления в d-ичную систему счисления.
- •1.4. Двоичная система счисления
- •1.4.1. Двоичная арифметика
- •1.4.3. Вычитание с использованием двоичного дополнения. Умножение
- •Алгоритм вычитания целых десятичных чисел
- •Алгоритм отыскания двоичного дополнения числа
- •Теория множеств
- •Глава 1. Множества
- •1.1. Основные определения
- •1.2. Основные операции теории множеств
- •Старшинство операций (операции даны по убыванию приоритетов)
- •1.4. Диаграммы Венна
- •1.5. Основные законы теории множеств
- •1.6. Декартово произведение и отношения
- •Глава 2. Бинарные отношения
- •2.1. Основные определения
- •Глава 3.Функции и операции
- •Примеры функций
- •Операции над функциями
- •Свойства бинарных операций
- •Глава 4.Алгебраические структуры
- •III. Математическая логика
- •Глава 1. Переключательные функции
- •1.1. Основные определения
- •Переключательные функции двух аргументов
- •1.2. Основные теоремы (эквивалентные соотношения) переключательных функций
- •Глава 2.Булева алгебра
- •2.1. Основные определения
- •Эквивалентные соотношения в булевой алгебре
- •2.2. Минимизация булевых функций
- •2.3. Аналитические методы нахождения мднф Метод Квайна
- •Формулы метода
- •Алгоритм метода
- •Метод Блейка
- •Формулы метода
- •Алгоритм метода
- •Сравнение методов Квайна и Блейка
- •Построение мднф из Сокр.Днф с помощью таблицы Квайна
- •Алгоритм получения fМднФс помощью таблицы Квайна
- •2.4. Графическая минимизация логических функций
- •Метод карт Карнапа
- •Алгоритм минимизации по карте Карнапа
- •2.5. Полнота систем булевых функций
- •Классы Поста
- •Полиномы Жегалкина
- •Глава 3.Логика высказываний
- •3.1. Основные понятия
- •3.2. Алгебра логики высказываний
- •3.3. Применение к естественному языку
- •Список наиболее часто встречающихся выражений, соответствующих логическим связкам
- •3.4. Исчисление высказываний (ив)
- •Глава 4.Логика предикатов
- •Определения кванторных высказываний
- •4.1. Алгебра логики предикатов
- •4.2. Выполнимость и общезначимость
- •4.3. Равносильность формул
- •Приведенные формулы
- •4.4. Применение логики предикатов к естественному языку
- •4.4.1. Суждения
- •Виды категорических суждений
- •4.4.2. Исчисление одноместных предикатов как исчисление классов. Теория категорических суждений и силлогизмов Аристотеля
- •Законы формальной логики Аристотеля:
- •4.4.3. Умозаключения
- •Наиболее распространенные схемы правильных дедуктивных рассуждений
- •4.4.4. Основные законы формальной логики. Логические основы аргументации
- •4.5. Исчисление предикатов
- •Литература
- •Предметный указатель
Свойства бинарных операций
1) –коммутативна, если для любыхa,b:.
2) –ассоциативна, если для любыхa,b,c:
.
Выполнение свойства ассоциативности означает, что скобки в выражении можно не расставлять;
3) –дистрибутивна слеваотносительно операции, если для любыхa,b,c:, и–дистрибутивна справаотносительно операции, если для любыхa,b,c:;
4) –идемпотентна, если для любыхa:.
Примеры
Арифметические операции сложения и умножения коммутативны и ассоциативны, операция умножения дистрибутивна относительно операции сложения слева и справа.
Операции объединения и пересечения множеств – коммутативны, ассоциативны, идемпотентны, операция пересечения дистрибутивна слева и справа относительно операции объединения.
Операция прямого произведения (см. пример 13) не обладает свойствами коммутативности, ассоциативности, идемпотентности.
Композиция бинарных отношений – ассоциативная, не коммутативная и не идемпотентная операция.
Глава 4.Алгебраические структуры
Множество Aвместе с заданными на нем операциями {1,2, …,m} называетсяалгеброй. Обозначение алгебры:, гдеAназываетсяосновным множеством (несущим множеством, носителем) , а={1,2, …,m} –сигнатурой алгебры .
Множество Aс заданными на нем отношениями {R1,R2, …,Rn} называетсямоделью. Обозначение модели:, гдеA–несущее множество(универсум),={R1,R2, …,Rn} – сигнатура модели .
Множество Aвместе с заданными на нем операциями {1,2, …,m} и отношениями {R1,R2, …,Rn} называетсяалгебраической системой, илиалгебраической структурой . Таким образом, алгебры – это алгебраические структуры с пустым множеством отношений, а модели – алгебраические структуры с пустым множеством операций.
Пусть между двумя множествами A иBустановлено соответствие. Это означает, что каждому элементуaизAпоставлен в соответствиеединственный элементизB, т.е.(a)=. Пусть также на множествеAзадана операция, на множествеBоперация, обе одинаковой арности, например, обе бинарные, так чтои. Мы получили две алгебры (A;) и (B;). Тогда отображениеназываетсягомоморфизмом(греч.homos– равный, одинаковый иmorphe– вид, форма, образ) алгебры (A;) в алгебру (B;), если выполняется условие:
. (*)
Условие гомоморфизма требует, чтобы отображение результата выполнения на множествеAоперациинад элементамиaиb, т.е., совпадало с результатомвыполнения на множествеBоперациинад отображениями этих элементов, т.е. нади.
Если при этом отображение является взаимно однозначным соответствием, оно называетсяизоморфизмом(греч.isos– равный, одинаковый, подобный) алгебры (A;) на алгебру (B;). В этом случае существует и обратное отображение:, также взаимно однозначное:.
Отображение – это, в свою очередь, изоморфизмBна A. Итак, если существует изоморфизмAна B, то существует изоморфизмBна A. При этом алгебры (A;) и (B;) называютсяизоморфными.
В общем случае, если на множествах Aна Bзаданы несколько операций соответственно (A;1,2, …,m) и (B;1,2, …,m), отображениеявляется гомоморфизмом алгебры (A;1,2, …,m) в алгебру (B;1,2, …,m), если условия, аналогичные (*), выполняются для каждой пары операций1и1, …,mиm.
В силу взаимной однозначности соответствия при изоморфизме мощности основных множеств изоморфных алгебр равны. Поэтому проверка алгебр на изоморфизм сводится к проверке условия гомоморфизма для каждой пары операций и установления взаимной однозначности соответствия(равной мощности множествAи B).
Понятие гомоморфизма (изоморфизма) для моделей и алгебраических структур вводится аналогично. Причем условия сохранения должны выполняться и для операций и для отношений.
Понятие изоморфизма – одно из важнейших понятий в современной математике. Так, из условия изоморфизма следует, например, что любое эквивалентное соотношение в алгебре сохраняется в любой изоморфной ей алгебре. Это позволяет, получив такие соотношения в алгебре, автоматически распространить их на все алгебры, изоморфные. В частности, изоморфизм сохраняет свойства ассоциативности, коммутативности, дистрибутивности и идемпотентности операций, а также свойства рефлексивности, иррефлексивности, симметричности, антисимметричности, транзитивности, эквивалентности и порядка отношений.