Discrete Mathematics(II) Spring 2012 Lecture 8: Soundness and Completeness of Propositional logic Lecturer. yil 1 Overview Syntax and semantics are two parts of mathematics logic. Soundness and completeness theorem bridge this two components. Soundness guarantees that our proof always yields valid proposition Completeness makes sure that there is definitely a proof to prove the validity of a valid proposition 2 Syntax and Semantics We first consider some example in linguistic. Especially, the word of a language with very long history may has several meanings. Consider the following example, which is Example1. Give you two Chinese characters”更衣”,uhat' s it mean? It means change clothes in modern Chinese It means go to washroom in ancient Chines If we consider acronyms in science documents, we can find many examples like the following Example 2. Give an acronym"IP", what's it mean? Internet protocol in network Integer Programming in operation research. Interactive Proof in complexity These two examples just shows that the same symbols represent different meaning, which would be known in the context We can also find examples in our experiences. Consider different programming languages Example 3. Give you the following programming segments 1. in C, printf("Hello World!"); 2. in Java, system. print("Hello World! ); 3. in C++, cout<<"Hello World! All of them just output "Hello World! on e screenDiscrete Mathematics (II) Spring 2012 Lecture 8: Soundness and Completeness of Propositional Logic Lecturer: Yi Li 1 Overview Syntax and semantics are two parts of mathematics logic. Soundness and completeness theorem bridge this two components. Soundness guarantees that our proof always yields valid proposition. Completeness makes sure that there is definitely a proof to prove the validity of a valid proposition. 2 Syntax and Semantics We first consider some example in linguistic. Especially, the word of a language with very long history may has several meanings. Consider the following example, which is Example 1. Give you two Chinese characters ”➁➓”, what’s it mean? • It means change clothes in modern Chinese. • It means go to washroom in ancient Chines. If we consider acronyms in science documents, we can find many examples like the following: Example 2. Give an acronym ”IP”, what’s it mean? • Internet Protocol in network. • Integer Programming in operation research. • Interactive Proof in complexity. These two examples just shows that the same symbols represent different meaning, which would be known in the context. We can also find examples in our experiences. Consider different programming languages. Example 3. Give you the following programming segments: 1. in C, printf(”Hello World!”); 2. in Java, system.print(”Hello World!”); 3. in C++, cout<<”Hello World!”; All of them just output ”Hello World!” on the screen. 1