Алгебраические системы - раздел Информатика, ПРОГРАММА КУРСА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕРИЯ АЛГОРИТМОВ Часто Объектом Изучения В Математике Служит Множество Вместе С Определенной Н...
Часто объектом изучения в математике служит множество вместе с определенной на нем структурой. Например, поля, формирующие основу обычной арифметики, линейные пространства, обеспечивающие связь геометрических объектов с операциями над числами, множества с выделенными на них бинарными отношениями. Все эти структуры образуют алгебраические системы, представляющие собой некоторые миры с определенными на них законами. Перейдем к точному определению алгебраической системы.
Напомним, что п-местным предикатом (отношением) на множестве А называется любое подмножество множества Аn; п-местной алгебраической операцией на множестве А называется функция F:An→A, где – n-я декартова степень множества А. Отметим, что поскольку операция F является функцией, для любого набора (x1,…,xn) Anрезультат применения операции F(x1,…,xn) однозначно определен. Так как область значений операции F лежит в множестве А, то будем говорить, что операция F замкнута на множестве А.
Сигнатурой Σ называется совокупность предикатных и функциональных символов с указанием их местности. Константным символом или просто константой называется 0-местный функциональный символ. Если α ‑ функциональный или предикатный символ, то его местность обозначается через μ(α). Часто п-местные предикатные и функциональные символы будем обозначать соответственно через Р(n) и F(n), возможно с индексами. Если в рассматриваемой сигнатуре используются стандартные символы, такие, например, как + для операции сложения, ≤ для отношения порядка, | для отношения делимости, 0для константного символа и другие, то мы просто пишем Σ={≤}, Σ={≤,+, ... , 0} и т.д.
Алгебраической системой сигнатуры Σ называется пара = где А – непустое множество и каждому n-местному предикатному (функциональному) символу из Σ поставлен в соответствие n-местный предикат (соответственно операция) на А. Множество А называется носителем, или универсумом алгебраической системы . Предикаты и функции, соответствующие символам из Σ, называются их интерпретациями. Обозначать интерпретации будем теми же буквами, что и соответствующие символы сигнатуры, возможно с индексом A. Заметим, что интерпретацией любого константного символа является некоторый элемент из А. Если Σ={α1,…, αn} – конечная сигнатура, то в записи фигурные скобки будем опускать.
Пример 1.1) Набор является алгебраической системой с двумя двухместными операциями.
2) Набор не является алгебраической системой, поскольку деление не является операцией на множестве , а элемент не принадлежит .
4) Набор является алгебраической системой, где т.е. множество всех подмножеств множества
Алгебраическая система = называется подсистемой системы = (обозначается ), если выполняются следующие условия:
а) А В;
б) для любого функционального символа F (n)Σ и любых элементов a1,a2,…,an A выполняется равенство FA(a1,a2,…,an)=FB(a1,a2,…,an), т.е. интерпретации символа F действуют одинаково на элементах из А;
в) для любого предикатного символа Р(n)Σсправедливо равенство P=∩An, т.е. предикат содержит в точности те кортежи предиката , которые состоят из элементов множества А.
Теорема 1.Если ‑ алгебраическая система, XВ, X≠Ø, то существует единственная подсистема (Х)= алгебраической системы такая, что X В(Х) и (Х) для любой подсистемы алгебраической системы , для которой XА.
Подсистема (Х) из теоремы 1 называется подсистемой алгебраической системы, порожденной множеством X.
Для описания элементов подсистемы (Х) определим индукцией по построению понятие терма сигнатуры Σ:
1) переменные и константные символы из Σ суть термы;
2) если F Σ ‑ n-местный функциональный символ, t1,t2,…,tn ‑термы, то F(t1,t2,…,tn) ‑ терм;
3) никаких термов, кроме построенных по пп. 1,2, нет. Множество всех термов сигнатуры Σобозначается через Т(Σ).
Под сложностью терма будем понимать число символов, входящих в терм.
Логика это наука о законах мышления Это одна из древнейших наук Основные законы логики были сформулированы еще древнегреческим мыслителем... Современная математическая логика определяется как раздел математики... Данное учебно практическое пособие соответствует учебной программе курса Математическая логика и теория алгоритмов...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Алгебраические системы
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
ПРОГРАММА КУРСА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕРИЯ АЛГОРИТМОВ
Тема 1. «Совершенные дизъюнктивные нормальные формы (СДНФ) и совершенные конъюнктивные нормальные формы (СКНФ) в алгебре высказываний (АВ)». Формулы АВ. Эквивалентность формул АВ.
Формулы алгебры высказываний
Высказыванием называется повествовательное предложение, о котором в данной ситуации можно сказать, что оно истинно или ложно, но не то и другое одновременно.
В качестве примеров выс
Эквивалентные формулы алгебры высказываний
Как показано в примере 1, различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие эквивалентности формул.
Формулы φ и ψ АВ называются
Определение формального исчисления
Введем общее понятие формального исчисления. Будем говорить, что формальное исчисление I определено, если выполняются четыре условия.
1. Имеется некоторое множество
Система аксиом и правил вывода
Используя понятие формального исчисления, определим исчисление высказываний (ИВ).
Алфавит ИВ состоит из букв x,y,z,u,v, возможно с индексами (которые называются про
Высказываний
Теорема 3.Пусть φ, ψ, χ ‑ формулы ИВ. Тогда имеют место следующие эквивалентности:
1) φ∧ φ≡φ, φ∨
Высказываний
Формула φ(x1,…,xn) ИВ называется тождественно истинной (обозначается ⊨φ), если φ(x1,…,xn) – тож
Формулы логики предикатов
Большинство определений этого параграфа будут индуктивными.
Введем понятие атомарной формулы сигнатуры Σ:
1) если t1, t2, T(Σ), то
В алгебраической системе
Дадим индуктивное определение истинности формулы φ(x1,…,xn) сигнатуры Σ на элементах a1,…,an А в алгебраической с
Пренексная нормальная форма в логике предикатов
Формула φ сигнатуры Σ называется бескванторной, если она не содержит кванторов. Бескванторная формула φ является дизъюнктивной (конъюнктивной) нормальной форм
Система аксиом и правил вывода
Зафиксируем некоторую произвольную сигнатуру Σ и определим исчисление предикатов сигнатуры Σ (ИПΣ).
Формулами ИПΣ
Предикатов
Утверждение 2.В ИПΣ выполнимы все эквивалентности ИВ из теоремы 3.
Утверждение 3. Пусть φ
Исчисления предикатов
Теорема 4. Все доказуемые в ИПΣ формулы являются тождественно истинными.
Доказательство проводим индукцией по длине вывода формулы. Очевид
Машины Тьюринга
Машина Тьюринга – это система, работающая в дискретные моменты времени и состоящая из следующих частей:
конечная лента, разбитая на конечное число ячеек. В ка
Примитивно рекурсивные функции
Базисными функциями называются следующие функции: – нулевая функция; – функция следования; – функция выбора.
Оператор суперпозиции (подстановки) ставит в соот
Частично рекурсивные функции
Оператор минимизации ставит в соответствие n+1-местной частичной функции n-местную частичную функцию так, что
и
или определены и не равны 0,
Логическое следствие в алгебре высказываний
Проверить истинность соотношений тремя способами (используя определение логического следствия и пп. 3,4 теоремы 2.
1. ;
2. ;
3. ;
4. ;
5. ;
6.
Исчисление высказываний
Пусть - формулы исчисления высказываний. Построить вывод формулы исчисления высказываний из данного множества гипотез.
1. ;
2. ;
3. ;
4. ;
Алгебраические системы.
Построить подсистему алгебраической системы , порожденную множеством (через обозначен булеан множества B, т.е. множество всех подмножеств множества B):
1.
2.
Формулы логики предикатов
Выписать все подформулы данной формулы сигнатуры
и определить свободные и связанные переменные формулы:
1.
2.
3.
4.
5.
В алгебраической системе
Написать формулу Ф(х), истинную в алгебраической системе тогда и только тогда, когда
1. х=1;
2. х=2n для некоторого натурального
Новости и инфо для студентов