- #1

Stephen Tashi

Science Advisor

- 7,393

- 1,368

## Summary:

- For the purposes of teaching topics in mathematical logic, how can we make examples based on a computer language?

A computer language is not a clear example of a formal language, a formal system, or a formal logic. Can we modify the rules for a computer language to create clear examples?

My non-authoritative classification of topics in mathematical logc is:

1. Formal languages. A formal language is defined by a set of rules that define which strings of symbols are "well formed formulas" (wffs). A wff has no semantic interpretation other than being syntactically correct according the rules of the formal language. Within the context of a formal language, a wff does not represent a statement that is True or False or a mathematical function.

2. Formal systems: A formal system is a formal language plus a set of "production rules". If we write down an initial wff, the production rules describe permissible operations for "deriving" other wffs from the initial wff. Within the context of a formal system, there is no interpretation that wffs involved are True (or False), so the "derivations" are not mathematical proofs that deduce True statements from some initial statement that is assumed to be True.

3. Formal logics: A consistent formal two-valued logic is a formal system with additional requirements. The wffs must each be assigned exactly one of two possible values, either True or False. (As a matter of vocabulary, in a specific formal language, the wffs are assigned specific values. Speaking of "formal language" as a generality, it is a set of specific formal languages. The value assigned to a wff may vary between two different laguages in that set.) The production rules must have the property that (for each specific language in the formal language) if the initial wff is True, all the wffs produced from it are True.

As to turning a computer language into examples, I have the following thoughts.

Consider the C programming language.

1. Formal language: The syntax of programming languages contains the concept of various

2. Formal system: I don't know how to view the C programming language as a set of production rules. Within the syntax of C, there are things resembling production rules that define particular types of wffs. For example a rule could be: If <expression A> and <expression B> are each legal mathematical expressions then "<expression A> + <expression B>" is a legal mathematical expression. However, if we are using entire programs as the examples for wffs, I don't see that C has rules that define how to begin with some initial program and derive other programs.

3. Formal logic: One thought is to define a subset of C programs in which all variables must be boolean and that, in each program, all variables must be defined in terms of a set of constants A,B,C,...,Z. Constants do not change their values within a program. A constant like "A" can be assigned to be 1 in one program and 0 in a different program. The requirement is that the specific set of constants must be declared and assigned values in each program

However, that doesn't fix the problem that C is not a good example of a Formal System. So restricting it to boolean variables doesn't give us production rules.

( Discussions of mathematical logic on the forum resemble discussions about interpretations of quantum mechanics. Experts disagree. It makes me think that the rules of the game are not standardized. Maybe they aren't! )

My non-authoritative classification of topics in mathematical logc is:

1. Formal languages. A formal language is defined by a set of rules that define which strings of symbols are "well formed formulas" (wffs). A wff has no semantic interpretation other than being syntactically correct according the rules of the formal language. Within the context of a formal language, a wff does not represent a statement that is True or False or a mathematical function.

2. Formal systems: A formal system is a formal language plus a set of "production rules". If we write down an initial wff, the production rules describe permissible operations for "deriving" other wffs from the initial wff. Within the context of a formal system, there is no interpretation that wffs involved are True (or False), so the "derivations" are not mathematical proofs that deduce True statements from some initial statement that is assumed to be True.

3. Formal logics: A consistent formal two-valued logic is a formal system with additional requirements. The wffs must each be assigned exactly one of two possible values, either True or False. (As a matter of vocabulary, in a specific formal language, the wffs are assigned specific values. Speaking of "formal language" as a generality, it is a set of specific formal languages. The value assigned to a wff may vary between two different laguages in that set.) The production rules must have the property that (for each specific language in the formal language) if the initial wff is True, all the wffs produced from it are True.

As to turning a computer language into examples, I have the following thoughts.

Consider the C programming language.

1. Formal language: The syntax of programming languages contains the concept of various

*types*of wffs. For example, a legal variable name is a certain type of wff. A mathematical expression is a different type. The goal of defining these types is to define a syntactically correct*program*. So to use the whole language as an example of a formal system, we must consider a wff to be an entire program.2. Formal system: I don't know how to view the C programming language as a set of production rules. Within the syntax of C, there are things resembling production rules that define particular types of wffs. For example a rule could be: If <expression A> and <expression B> are each legal mathematical expressions then "<expression A> + <expression B>" is a legal mathematical expression. However, if we are using entire programs as the examples for wffs, I don't see that C has rules that define how to begin with some initial program and derive other programs.

3. Formal logic: One thought is to define a subset of C programs in which all variables must be boolean and that, in each program, all variables must be defined in terms of a set of constants A,B,C,...,Z. Constants do not change their values within a program. A constant like "A" can be assigned to be 1 in one program and 0 in a different program. The requirement is that the specific set of constants must be declared and assigned values in each program

However, that doesn't fix the problem that C is not a good example of a Formal System. So restricting it to boolean variables doesn't give us production rules.

( Discussions of mathematical logic on the forum resemble discussions about interpretations of quantum mechanics. Experts disagree. It makes me think that the rules of the game are not standardized. Maybe they aren't! )