ЛОГІЧНА СЕМАНТИКА НА ОСНОВІ ПОВІДОМЛЕНЬ ДЛЯ SAT ПРОБЛЕМ

Ярослав ПЕТІК

ПЕТІК Я. (2024), ЛОГІЧНА СЕМАНТИКА НА ОСНОВІ ПОВІДОМЛЕНЬ ДЛЯ SAT ПРОБЛЕМ.
PHILOSOPHY, ECONOMICS AND LAW REVIEW. Volume 4, no. 1, 67-74

DOI: 10.31733/2786-491X-2024-1-67-74

 

Анотація. В статті проведено огляд логічної системи MSSG-логіки, спочатку розробленої автором для представлення певної теорії в аналітичній філософії мови. Цю теорію запропонував філософ Пол Грайс, який пропонував вважати намір власника мовлення важливим контекстом для визначення справжнього значення його акта мовлення.

MSSG-логіка пропонує використовувати спеціальні набори символів для додаткового тлумачення логічних формул, а також надмножини цих наборів («дерева повідомлень») із визначеними алгебрами для більш складних випадків. Стаття пропонує модифікувати «мовну» MSSG-логіку для представлення відомих булевих задач задоволення умов (SAT) у галузі комп’ютерних наук за допомогою подібних інструментів. Також обговорюються наслідки для комп’ютерних наук та філософії мови.

Ключові слова: SAT, boolean satisfiability, комп’ютерні науки, логіка для комп’ютерних наук, Пол Грайс, формальна мова, аналітична філософія мови.

References

  • Jonsson, B. (1984). Maximal Algebras of Binary Relations. Contributions to Group Theory. Contemporary Mathematics. Vol. 33. Providence/RI: American Mathematical Society. Pp. 299–307.
  • Graham, G. (1928). The Logics and the Social Sciences. Social Forces, 7 (1). Pp. 24-32. Grice, H. (1972). Intention and Uncertainty Oxford Universtiy Press. 19 p.
  • Manquinho V.M., Marques-Silva J. (2004). Satisfiability-based algorithms for Boolean optimization. Annals of Mathematics and Artificial Intelligence. No. 40. Pp. 353-372.
  • Petik, I. (2022). Message-based logic semantics and intentional linguistic semantics of Paul Grice. Humanitarian Vision. 8 (1). Pp. 19-24.
  • Russell, S. & Norvig, P. (2010). Artificial Intelligence: A Modern Approach. New Jersey: Prentice Hall, 1151 p.
  • Wybraniec-Skardowska, U. (2020). What Is the Sense in Logic and Philosophy of Language. Bulletin of the Section of Logic. 49 (2). Pp.185-211.
  • Abadi, M. & Lamport, L. (2008). The existence of refinement mappings. Theoretical Computer Science. 319 (1-3). Pp. 437-449.
  • Biere, A., Cimatti, A., Clarke, E. M. & Zhu, Y. (2003). Symbolic model checking without BDDs. Tools and Algorithms for the Construction and Analysis of Systems. Pp. 193- 207.
  • Clarke, E. M. & Emerson, E. A. (2002). Design and Synthesis of Synchronization Skeletons using Branching Time Temporal Logic. ACM Transactions on Programming Languages and Systems (TOPLAS). 23 (5). Pp. 845-871.
  • Goranko, V. & Passy, S. (2007). Algorithmic Correspondence for Dynamic Logics: Complexity and Expressiveness. Journal of Logic, Language, and Information. 16 (4). Pp. 397-422.
  • Sipser, M. (2008). A Complexity-Theoretic Perspective on Formal Languages. Communications of the ACM. 51 (7). Pp. 76-83.
  • Vardi, M. Y. & Wolper, P. (2008). An automata-theoretic approach to automatic program verification. A Decade of Concurrency: Reflections and Perspectives. Pp. 317-331.
Views: 65