×

Weakly complete axiomatization of exogenous quantum propositional logic. (English) Zbl 1116.03021

This paper apparently builds on earlier work by the same authors who have already proposed “a new logic (EQPL – exogenous quantum propositional logic) for modelling and reasoning about quantum systems, embodying all that is stated in the postulates of quantum physics” (p. 771). The logic was designed “from the semantics upwards starting with the key idea of adopting superpositions of classical models as the models of the proposed quantum logic” (ibid.). So in contrast to “quantum logic” in the tradition of von Neumann and Birkhoff, where the lattice operations of Hilbert Space generate new quantum propositional connectives, here classical logic is extended by valuation structures that are derived from “a finitary Hilbert calculus for EQPL” (p. 772).
At heart is the notion that unit vectors \(|\Psi\rangle\) representing quantum states are acted on by classical valuations \(v\) to produce “logical amplitudes of \(|\Psi\rangle\) for \(v\)” given by the inner product of \(v\) and \(|\Psi\rangle\). Section 2, “Key design ideas”, gives a clear informal discussion of the “quantum postulates” derived from Hilbert space, and uses this discussion to introduce key features of the semantics. By loose analogy with Kripke methods, valuations of EQPL are derived from a “quantum intepretation structure” \(w = (V,S,|\Psi\rangle,v)\). \(V\) contains “admissable” classical valuations, \(S\) is a finite partition over \(V\), \(|\Psi\rangle\) is a quantum state, i.e., a unit vector of the Hilbert space, and \(v\) is a mapping defined so as to provide the means for interpreting amplitude terms, “even when they are physically undefined”, avoiding the need for “partial interpretation structures” (p. 775). A finite probability space is then associated with each such interpretation structure in a way that allows probabilities to be assigned in a given quantum state, to the truth of classical propositions (p. 776).
The structures introduced informally in Section 2 are elaborated and developed in Part 3, “Language and semantics”. Unfortunately the symbolism may be unfamiliar to traditional logicians, who would have been helped by a few key definitions. Part 4, “Axiomatisation”, introduces the notion of quantum tautology and provides a finitary axiomatisation of the computational logic using two rules and fifteen axiom schemas, including an analytical oracle. Finally in Part 5 the proof of bounded weak completeness is presented “using a non-trivial extension of the Fagin-Halpern-Megiddo technique together with three Henkin like completions” (p. 791).

MSC:

03B60 Other nonclassical logic
81P10 Logical foundations of quantum mechanics; quantum logic (quantum-theoretic aspects)
81P68 Quantum computation

Software:

ALGOL 60
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] P. Mateus, A. Sernadas, Exogenous quantum logic, in: W.A. Carnielli, F.M. Dionísio, P. Mateus (Eds.), Proceedings of CombLog’04, Workshop on Combination of Logics: Theory and Applications, Departamento de Mátematica, Instituto Superior Técnico, 1049-001 Lisboa, Portugal, 2004, pp. 141-149, extended abstract.; P. Mateus, A. Sernadas, Exogenous quantum logic, in: W.A. Carnielli, F.M. Dionísio, P. Mateus (Eds.), Proceedings of CombLog’04, Workshop on Combination of Logics: Theory and Applications, Departamento de Mátematica, Instituto Superior Técnico, 1049-001 Lisboa, Portugal, 2004, pp. 141-149, extended abstract.
[2] Mateus, P.; Sernadas, A., Reasoning about quantum systems, (Alferes, J.; Leite, J., Logics in Artificial Intelligence, Ninth European Conference, JELIA’04. Logics in Artificial Intelligence, Ninth European Conference, JELIA’04, Lecture Notes in Artificial Intelligence, vol. 3229 (2004), Springer: Springer Berlin), 239-251 · Zbl 1111.81304
[3] Cohen-Tannoudji, C.; Diu, B.; Laloë, F., Quantum Mechanics (1977), Wiley: Wiley New York
[4] Nielsen, M. A.; Chuang, I. L., Quantum Computation and Quantum Information (2000), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1049.81015
[5] Foulis, D. J., A half-century of quantum logic. What have we learned?, (Quantum Structures and the Nature of Reality. Quantum Structures and the Nature of Reality, Einstein Meets Magritte, vol. 7 (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 1-36 · Zbl 1356.81010
[6] Chiara, M. L.D.; Giuntini, R.; Greechie, R., Reasoning in Quantum Theory (2004), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 1059.81003
[7] Birkhoff, G.; von Neumann, J., The logic of quantum mechanics, Annals of Mathematics, 37, 4, 823-843 (1936) · JFM 62.1061.04
[8] S.A. Kripke, Semantical analysis of modal logic. I. Normal modal propositional calculi, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 9 (1963) 67-96.; S.A. Kripke, Semantical analysis of modal logic. I. Normal modal propositional calculi, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 9 (1963) 67-96. · Zbl 0118.01305
[9] Carnielli, W. A.; Lima-Marques, M., Society semantics and multiple-valued logics, (Advances in Contemporary Logic and Computer Science (Salvador, 1996). Advances in Contemporary Logic and Computer Science (Salvador, 1996), Contemporary Mathematics, vol. 235 (1999), AMS), 33-52 · Zbl 0942.03034
[10] Carnielli, W. A., Possible-translations semantics for paraconsistent logics, (Frontiers of Paraconsistent Logic (Ghent, 1997). Frontiers of Paraconsistent Logic (Ghent, 1997), Studies in Logic and Computation, vol. 8 (2000), Research Studies Press), 149-163 · Zbl 1002.03525
[11] Nilsson, N. J., Probabilistic logic, Artificial Intelligence, 28, 1, 71-87 (1986) · Zbl 0589.03007
[12] Nilsson, N. J., Probabilistic logic revisited, Artificial Intelligence, 59, 1-2, 39-42 (1993) · Zbl 1507.68015
[13] F. Bacchus, Representing and Reasoning with Probabilistic Knowledge, MIT Press Series in Artificial Intelligence, MIT Press, 1990.; F. Bacchus, Representing and Reasoning with Probabilistic Knowledge, MIT Press Series in Artificial Intelligence, MIT Press, 1990.
[14] F. Bacchus, On probability distributions over possible worlds, in: Uncertainty in Artificial Intelligence, 4, Machine Intelligence and Pattern Recognition, vol. 9, North-Holland, 1990, pp. 217-226.; F. Bacchus, On probability distributions over possible worlds, in: Uncertainty in Artificial Intelligence, 4, Machine Intelligence and Pattern Recognition, vol. 9, North-Holland, 1990, pp. 217-226.
[15] Fagin, R.; Halpern, J. Y.; Megiddo, N., A logic for reasoning about probabilities, Information and Computation, 87, 1-2, 78-128 (1990) · Zbl 0811.03014
[16] Abadi, M.; Halpern, J. Y., Decidability and expressiveness for first-order logics of probability, Information and Computation, 112, 1, 1-36 (1994) · Zbl 0799.03017
[17] Dishkant, H., Semantics of the minimal logic of quantum mechanics, Studia Logica, 30, 23-32 (1972) · Zbl 0268.02018
[18] P. Mateus, A. Sernadas, C. Sernadas, Exogenous semantics approach to enriching logics, in: G. Sica (Ed.), Essays on the Foundations of Mathematics and Logic, Advanced Studies in Mathematics and Logic, vol. 1, Polimetrica, 2005, pp.165-194.; P. Mateus, A. Sernadas, C. Sernadas, Exogenous semantics approach to enriching logics, in: G. Sica (Ed.), Essays on the Foundations of Mathematics and Logic, Advanced Studies in Mathematics and Logic, vol. 1, Polimetrica, 2005, pp.165-194. · Zbl 1151.03324
[19] van der Meyden, R.; Patra, M., A logic for probability in quantum systems, (Baaz, M.; Makowsky, J. A., Computer Science Logic. Computer Science Logic, Lecture Notes in Computer Science, vol. 2803 (2003), Springer: Springer Berlin), 427-440 · Zbl 1116.03324
[20] van der Meyden, R.; Patra, M., Knowledge in quantum systems, (Tennenholtz, M., Theoretical Aspects of Rationality and Knowledge (2003), ACM), 104-117
[21] Naur, P., Revised report on the algorithmic language Algol 60, The Computer Journal, 5, 349-367 (1963)
[22] Bridges, D. S., Computability—A Mathematical Sketchbook, Graduate Texts in Mathematics (1994), Springer: Springer Berlin
[23] Henkin, L., Completeness in the theory of types, Journal of Symbolic Logic, 15, 81-91 (1950) · Zbl 0039.00801
[24] A. Baltag, S. Smets, The logic of quantum programs, in: P. Selinger (Ed.), Proceedings of the 2nd Workshop on Quantum Programming Languages, Turku Centre for Computer Science, 2004, pp. 39-56.; A. Baltag, S. Smets, The logic of quantum programs, in: P. Selinger (Ed.), Proceedings of the 2nd Workshop on Quantum Programming Languages, Turku Centre for Computer Science, 2004, pp. 39-56.
[25] C. Karp, Languages with Expressions of Infinite Length, North-Holland, 1964.; C. Karp, Languages with Expressions of Infinite Length, North-Holland, 1964. · Zbl 0127.00901
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.