This paper outlines the logical system of MSSG-logic originally developed by the author to represent a particular theory in analytic philosophy of language. That was a theory by philosopher Paul Grice that proposed to consider the intention of the speaker as an important context for the definition of the true meaning of his speech act. MSSG-logic proposes to use special sets of symbols for the additional interpretation of the logical formulas as well as the supersets of these sets ("trees of messages") with defined algebras on them for more complex cases. This particular paper proposes to modify the "linguistic" MSSG-logic to represent the famous computer science boolean satisfiability problems (SAT) with the similar tools. The consequences for computer science and philosophy of language are also discussed
Message-based semantica for sat problems
Abstract
Keywords
SAT; boolean satisfiability; computer science; logic for CS; Paul Grice; formal language; analytic philosophy of language
[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.