Комментарии 17
Пробежался по тексту и по крайним главам Вашей книги, и не нашел упоминания реляционной алгебры и Кодда. Кажется, что это прямо первый кандидат на сравнение с Вашей теорией.
Чем отличаются Ваша алгебра и реляционная?
Спасибо за вопрос.
1) В реляционной алгебре Кодда, по сути, нет сжатых структур и нет алгоритмов работы со сжатыми структурами.
2) В ней также отсутствуют многие методы логического анализа, разработанные в алгебре кортежей (см. раздел «Связь АК с логикой»)
Спасибо. Ваш ответ оказался короче, чем ожидал, потому что мне видится здесь благодатное поле для сравнения и обнаружения уникальных свойств Вашей теории.
1.1) если я правильно понял, под сжатыми структурами Вы понимаете символы * (весь домен) и 0 (пустое множество), в то время как в реляционной алгебре необходимо прописывать отношение перечислением элементов. Верно?
1.2) алгебраическая система состоит из набора объектов, алгебраических операций и законов, которым они удовлетворяют. Алгоритмы не являются частью алгебраических систем, это часть реализации системы поддержки / СУБД.
2) доказана связь между реляционной алгеброй и реляционным исчислением, которое обладает теми же свойствами, которые Вы описали в упомянутом разделе.
Я тут увидел в вики, что реляционное исчисление близкородственно (или эквивалентно?) исчислению кортежей. Ваша логика, соответствующая АК, и реляционное исчисление — это одно и то же или разные логические системы?
Отвечаю по порядку.
1.1) Да, верно. Замечу только, что для сжатия структур в АК используются не только * и 0, но и промежуточные компоненты.
1.2) Я не уверен в том, что алгоритмы не являются частью алгебраических систем – они просто не входят в их определения. В АК просто нельзя обойтись без алгоритмов, так как надо доказывать, что определенный алгоритм является корректным для определенной операции со сжатыми структурами.
2) Реляционное исчисление в отличие от алгебры кортежей не является
полноценной логической системой хотя бы потому, что в ней нет операции
дополнения.
Очень хорошая статья. Плюсую.
По сути вопроса: ~80-85% Вашей алгебры - это алгебра отношений (т.н. "реляционная алгебра"), действительно реализованная в "реляционных базах данных", начиная с 1980-х.
Построение там то же: берутся отношения (наборы кортежей), строится их ДП, затем над ним строятся операции алгебры множеств (объединение, пересечение, иключение, ...) и алгебры логики (и, или, эквивалентны, не, ...).
Ваше новшество - это объединение алгебры отношений с алгеброй матриц, классификация (введение) объектов (С, Д, ... кортежи, системы, ...) и математическое описание их свойств. (В литературе такого я не встречал).
Практическая польза для изучения тоже очевидна: изучившие, как минимум, смогут искусно работать с SQL-м, а, значит, на хлеб - заработают (что не маловажно в наше время).
Спасибо за оценку. Что касается процентов, то их трудно определить в знаниях, так как иногда маленькая добавка в систему играет роль катализатора, переводящего ее в качественно иное состояние. В алгебре кортежей такой добавкой является операция дополнение, отсутствие которой в реляционной алгебре не дает ей возможности превратиться в полноценную дедуктивную систему.
Относительно SQL. Я не силен в программировании, но мне кажется, что для алгебры кортежей более подойдет язык объектно ориентированного программирования.
Когда-то давно (конец 90-х) я сделал программу на Турбо Паскале для
решения знаменитой задачи Выполнимость КНФ (заодно считалась и вероятность
системы, заданной булевой функцией) с помощью алгоритмов АК. Хотелось бы с ее
помощью подключиться к соревнованиям алгоритмов по решению этой задачи (они
где-то есть в Интернете). Но сейчас в новых операционных системах эта прога не
работает, а переделывать ее нет ни времени, ни знаний.
ООП - это лишь средство хранения множества и операций над ним в едином контейнере; иное пользование ООП - сомнительно.
SQL - это реализация 80% функций Вашей алгебры "из коробки", при чём всё гениально упаковано в единственную функцию SELECT. Ее конструкция : SELECT Проекция FROM ДП WHERE граф ("цепочка") операций алгебры логики и отношений "больше" "меньше" "равно" "не равно" над компонентами кортежей (векторов) из ДП.
Пример: SELECT c0,c1,c3 FROM R0,R1,R2 WHERE (R0.c0 = R1.c1) and (R2.c3 < 80)
Т.е. это взятие проекции от результата вызова n-местной функции F(R0, ... ,Rn-1)->V, с телом заданным после WHERE, которая на выходе отдаёт вектор векторов (отношение V) для всей области определения функии R0xR1x...xRn-1.
При этом SELECT вкладывается в любой участок FROM и/или WHERE, что позволяет комбинировать алгоритмические графы ("деревья")
Пример: SELECT * FROM (SELECT * FROM R1,R2) WHERE c0 IN (SELECT d0 FROM R3);
В 1 страничку текста это объяснено здесь https://www.tutorialspoint.com/dbms/relational_algebra.htm
Мне кажется, что во всех исполняющих алгоритмах функции SELECT в настоящее время используется представление данных в виде кортежей элементов. Для сжатых структур они явно не годятся. Однако в АК имеются алгоритмы поиска ответа на вопрос для данных, представленных в виде C-систем:
https://libeldoc.bsuir.by/bitstream/123456789/4244/1/Zuyenko_Intellektualnyye.PDF
Разумеется в этой публикации не учтены не все тонкости функции SELECT. Но работу можно продолжить. Но для этого среди авторов должен быть профессионал в программировании. Если Вы не против, давайте сделаем эту работу вместе. Работу можно опубликовать в Хабре или в рецензируемых изданиях (одно другому, как мне кажется, не мешает) Как со мной связаться, найдете в статье.
В вашем решении в итоге также перебор двух вариантов, хотя обещали, что не будет.
Моё решение: т.к. подвыражение "во второй комнате тигра нет" присутствует в обоих первых двух, то оно истинно. Заметив, что первое и второе выражения симметричны относительно 1 и 3 комнаты, и зная, что ровно одно из них истинно - делаем вывод, что в 1 и 3 комнате пусто и тигр (неважно кто где). И соответственно во 2 комнате принцесса.
Спасибо за комментарий. Варианты здесь понадобились не для того, чтобы перечислять состояния комнат, а для того, чтобы решать варианты условий задачи из-за того, что неизвестно, какая из посылок ложная.
Допускаю, что для данной задачи имеется короткий способ решения. Но свою задачу (иллюстрировать свойства декартова произведения множеств) она здесь выполнила.
Ваше решение мне понравилось, хотя не мешало бы пояснить, почему из симметричности посылок следует отсутствие пустого места во второй комнате. А не хотите попробовать найти короткое решение для задач про подруг и про поиск следствий с заданным составом переменных в статье [«Как вычислять интересные следствия»](https://www.ontology-of-designing.ru/article/2023_2(48)/Ontology_Of_Designing_2023_2_160-174_B.A.Kulik_.pdf)? Буду весьма признателен. У меня даже была идея написать работу о методах решения сложных логических задач, например, некоторых задач из книг Смаллиана. Но все дела, дела… И работать не с кем. Все тоже заняты важными делами.
отсутствие пустого места во второй комнате следует из того, что одно из двух выражений ложно. Подвыражение "во второй комнате тигра нет" как мы выяснили истинно в обоих выражениях. Значит ложно одно из двух выражений: "третья комната не пуста" или "первая комната не пуста".
З.Ы.: первое и второе выражение образуют истину по операции XOR (исключающее или), возможно, используя эту формулу, не надо будет рассматривать два выражения.
Алгебру кортежей можно рассматривать как логику в базисе NOT, OR, AND. Ее структуры органично соответствуют этому базису. Операцию XOR в ней, разумеется, можно выразить, но это усложнит систему. Так же, как усложняется система вывода в исчислении высказываний с традиционным базисом NOT и импликация, если в ней использовать операции OR, AND.
Занимаюсь вопросами символического искусственного интеллекта. Ваша работа крайне интересна и ценна для меня. Огромная благодарность за книгу, надо будет найти её в бумажном варианте!
В бумажном вряд ли найдете - она была выпущена в издательстве тиражом всего в 200 экземпляров и все улетели. Зато в электронном варианте нет опечаток, которые есть в бумажном
А что означает символический искусственный интеллект? Мне это не совсем понятно, хотя я и член РАИИ (Российская ассоциация искусственного интеллекта). Спасибо за отзыв о моей книге. А статья Вам не понравилась ? Почему плюсик не поставили?
Как совместить логику и семантику в одной алгебраической системе