В статті проведено огляд логічної системи MSSG-логіки, спочатку розробленої автором для представлення певної теорії в аналітичній філософії мови. Цю теорію запропонував філософ Пол Грайс, який пропонував вважати намір власника мовлення важливим контекстом для визначення справжнього значення його акта мовлення. MSSG-логіка пропонує використовувати спеціальні набори символів для додаткового тлумачення логічних формул, а також надмножини цих наборів («дерева повідомлень») із визначеними алгебрами для більш складних випадків. Стаття пропонує модифікувати «мовну» MSSG-логіку для представлення відомих булевих задач задоволення умов (SAT) у галузі комп’ютерних наук за допомогою подібних інструментів. Також обговорюються наслідки для комп’ютерних наук та філософії мови
Логічна семантика на основі повідомлень для SAT проблем
Анотація
Ключові слова
SAT; boolean satisfiability; комп’ютерні науки; логіка для комп’ютерних наук; Пол Грайс; формальна мова; аналітична філософія мови
[1] Abadi, M., & Lamport, L. (2008). The existence of refinement mappings. Theoretical Computer Science, 319 (1-3), 437-449.
[2] 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.
[3] 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), 845-871.
[4] Goranko, V., & Passy, S. (2007). Algorithmic correspondence for dynamic logics: Complexity and expressiveness. Journal of Logic, Language, and Information, 16(4), 397-422.
[5] Graham, G. (1928). The Logics and the Social Sciences. Social Forces, 7(1), 24-32.
[6] Grice, H. (1972). Intention and Uncertainty. Oxford University Press.
[7] Jonsson, B. (1984). Maximal Algebras of Binary Relations. Contributions to Group Theory. Contemporary Mathematics, Vol. 33. Providence/RI: American Mathematical Society. Pp. 299-307.
[8] Manquinho, V.M., & Marques-Silva, J. (2004). Satisfiability-based algorithms for Boolean optimization. Annals of Mathematics and Artificial Intelligence, 40, 353-372.
[9] Petik, I. (2022). Message-based logic semantics and intentional linguistic semantics of Paul Grice. Humanitarian Vision, 8(1), 19-24.
[10] Russell, S., & Norvig, P. (2010). Artificial intelligence: A modern approach. New Jersey: Prentice Hall.
[11] Sipser, M. (2008). A complexity-theoretic perspective on formal languages. Communications of the ACM, 51(7), 76-83.
[12] Vardi, M.Y., & Wolper, P. (2008). An automata-theoretic approach to automatic program verification. A Decade of Concurrency: Reflections and Perspectives, 317-331.
[13] Wybraniec-Skardowska, U. (2020). What is the sense in logic and philosophy of language. Bulletin of the Section of Logic, 49(2), 185-211.