The Language of Propositional Logic
Summary
This note reviews the language of propositional logic as a metalanguage used to obtain valid expressions from the base language formed by two symbols. It explains the syntax rules, the concepts of propositional variables and connectors, and also introduces joint negation, the use of parentheses, and reordering to facilitate the reading of expressions. Additionally, the vocalization of propositional logic expressions is mentioned. Finally, the language of propositional logic is synthesized as a fundamental tool in mathematics and logic, and the possibility of finding a “base language of the base” from which everything else could be reconstructed is reflected upon.
Learning Objectives:
Upon completing this section, the student is expected to be able to:
- Understand the concept of metalanguage and its application in propositional logic.
- Comprehend the syntax rules of the language of propositional logic.
- Know the concept of propositional variables and their use in constructing expressions.
- Understand the use of the connector and joint negation in the language of propositional logic.
- Learn to use parentheses and reordering to facilitate the reading of expressions.
- Know the vocalizations of propositional logic expressions.
- Synthesize the language of propositional logic as a fundamental tool in mathematics and logic.
- Reflect on the possibility of finding a “base language of the base” from which everything else could be reconstructed.
- Apply the learned concepts in constructing propositional logic expressions.
- Use the language of propositional logic to understand and solve mathematical and logical problems.
Table of Contents
THE LANGUAGE OF PROPOSITIONAL LOGIC: ALPHABETS AND SYMBOL CHAINS
LET’S START WITH A SINGLE SYMBOL
LET’S THEN ADD A SECOND SYMBOL
THE LANGUAGE OF PROPOSITIONAL LOGIC: SYNTAX
EXAMPLES OF SYNTAX REVIEW
NOTATION CONVENTIONS
METAVARIABLES AND THE CONNECTOR \downarrow
EXAMPLES OF THE USE OF JOINT NEGATION
REORDERING AND PARENTHESES
DERIVED CONNECTORS
VOCALIZATION OF PROPOSITIONAL LOGIC EXPRESSIONS
SYNTHESIS AND REFLECTIONS ON THE LANGUAGE OF PROPOSITIONAL LOGIC
THE MATRIX BEHIND THE MATRIX BEHIND THE UNDERSTANDING OF ALL THINGS
The Language of Propositional Logic: Alphabets and Symbol Chains
Let’s Start with a Single Symbol
To build the Language of Propositional Logic, we will start our study with the simplest alphabet: one that has a single symbol. The shape of the symbol doesn’t matter; the important thing is that it’s unique. If we write using such an alphabet, the only thing that distinguishes one symbol chain from another is the number of times that symbol is repeated. Therefore, if we can write symbol chains of up to length N, we can only write N different chains. As you can see, this alphabet is quite limited, and there’s not much more to say about it.
Let’s Then Add a Second Symbol
If we add a second symbol to our alphabet, the writing becomes richer than in the previous alphabet. Now we can appreciate the way the symbols are arranged; for example, if 0 and 1 are our symbols, we can distinguish between 01 and 10. Both chains involve the same symbols but in different orders. If the longest chain we can write is of length N =1,2,3,\cdots, then we can write 2^1=2 chains of length 1, 2^2=4 chains of length 2, 2^3=8 chains of length 3, and so on, in general 2^N distinct chains of length N.
Exercise: Write on a sheet of paper all the different chains that can be written with between 1 and N symbols. How many chains are written in total?
Solution:
If S_N is the sum of all chains, of lengths 1, 2, 3, and so on up to N, then we have already seen that:
\displaystyle S_N=2^1 + 2^2 + \cdots +2^{N-1} + 2^N
Multiplying the previous expression by 2, we have:
\displaystyle 2 S_N=2^2 + 2^3 + \cdots + 2^N + 2^{N+1}
And therefore:
\displaystyle S_N=2 S_N - S_N = 2^N-1
As a result, the total number of chains written on the sheet will be 2^N-1.
The Language of Propositional Logic: Syntax
We have seen that, with two symbols, we can distinguish one chain from another by their length and by the order in which they are arranged. This is important because it allows us to define a syntax for the alphabet we have built. A syntax is a set of rules that separates symbol chains into two categories: Expressions and Non-Expressions. If \mathcal{L}_2 is the set of all chains that can be constructed with the symbols 0 and 1, then the syntax of \mathcal{L}_2 is a subset \mathcal{SL}_2\subset\mathcal{L}_2.
We can define the set \mathcal{SL}_2 with the following recursive rules:
- 00, 11 \in \mathcal{SL}_2
- If \alpha, \beta \in \mathcal{SL}_2, then 01\alpha\beta \in \mathcal{SL}_2
With these two rules, we can construct expressions of the language and verify whether a given chain is an expression of the language. A language is an alphabet with an associated syntax. The language presented here will be called the “Base Language of Two Symbols,” or \mathcal{B}_2.
Examples of Syntax Review
To make these ideas easier to understand, let’s review the following examples:
Example: Given that 0000 and 1111 are contained in \mathcal{SL}_2, it follows that 01000001001101110000 and 0111111111 are in \mathcal{SL}_2; therefore, they are expressions of \mathcal{B}_2. This is demonstrated by applying the rules we have just introduced.
End of the example \blacksquare
Exercise: In the previous example, we have seen how to construct expressions from two elementary expressions. While this is not a particularly complicated task, the reverse process, which involves demonstrating whether a certain expression is an expression, might be a bit more challenging.
Determine, using the syntax rules, whether the following chains are expressions of \mathcal{B}_2:
012100
101100
0100010000
0101000011
01010000010000
01010010000100101000011
Solution: Before looking at the solution, I recommend that you try it on your own first and then compare the results. If you’ve already done that, then go ahead 👍
012100.
As we can see, this includes the symbol 2, which is not contained in \mathcal{L}_2; therefore, this chain cannot be contained in \mathcal{SL}_2 and is not an expression of \mathcal{B}_2.
101100.
Here, we see that this chain starts with 10. From the syntax rules, we can infer that all chains longer than 2 must, by necessity, start with 01; therefore, it cannot be an expression of \mathcal{B}_2.
0100010000
This chain starts with 01, so it passes the first test. To be an expression of \mathcal{L}_2, it is necessary that the part marked in blue can be uniquely decomposed into two expressions.
0100010000
If the decomposition is not unique even while complying with the syntax laws, then the defined syntax is ambiguous and needs to be corrected.
Analyzing the blue part, the following possible separations are obtained:
00010000 00010000 00010000 00010000 00010000 00010000 00010000 In this part, we must note that if the golden part is not 0000 or 1111, then the corresponding blue part must start with 01 for the entire chain to be an expression. Therefore, the following eliminations can be made:
00010000❌ 00010000✅ 00010000❌ 00010000❌ 00010000❌ 00010000❌ 00010000❌ This is why the only separation that survives this analysis is 00010000, where the golden part is an expression and the blue part is uniquely and consistently separated according to the syntax. Finally, the chain 0100010000 admits a unique and consistent decomposition with the syntax, which is 0100010000, and therefore is an expression of the language \mathcal{B}_2.
0101000011
For this chain, we can make the following separation, which I will mark with colors:
010100001111
According to the syntax rules, for a chain longer than 2 to be an expression, it must begin with 01, and after that, there must follow two expressions, which I have marked in blue and gold. It is easy to see that this separation is unique because if the blue or gold areas change length, any such change would mean that both parts would no longer be expressions simultaneously.
01010000010000
Reviewing from right to left, we can find the following separation:
\underbrace{01\underbrace{01\overbrace{00}\overbrace{00}}_{{expression}}\underbrace{01\overbrace{00}\overbrace{00}}_{{expression}}}_{{expression}}
01010010000100101000011
A sharp eye will notice that this chain has a length of 23 and that it is impossible to construct a chain of odd length through the syntax laws of \mathcal{L}_2, which constructs expressions by juxtaposing chains of even length. All chains of \mathcal{SL}_2 have an even length; therefore, 01010010000100101000011 is not an expression of \mathcal{B}_2.
End of the exercise \blacksquare
Notation Conventions
Working with zeros and ones can be confusing to our perception and can lead us to make mistakes. To make the process more friendly to the way humans interpret things, we can use notation conventions and some metasymbols.
Metavariables and the Connector \downarrow
A metasymbol is a symbol used to represent chains of symbols from a target language. For example, when defining the syntax \mathcal{SL}_2 of \mathcal{L}_2, the symbols \alpha and \beta were used to represent expressions of \mathcal{B}_2. These symbols are called metavariables of \mathcal{B}_2: metasymbols that, when all replaced by expressions of the language, generate another expression of the language through syntax, as established by the second rule on the elements of \mathcal{SL}_2:
If \alpha,\beta \in \mathcal{SL}_2, then 01\alpha\beta \in\mathcal{SL}_2
For this reason, these metavariables are called metaexpressions of \mathcal{B}_2.
To facilitate our writing from now on, we will use the metasymbol \downarrow to represent the chain 01. This metasymbol is what we call a connector and is known as Joint Negation for semantic reasons.
With this, we can express the syntax \mathcal{SL}_2 in a metalanguage through the following recursive rules:
All metavariables of \mathcal{B}_2 are metaexpressions of \mathcal{B}_2.
If \alpha and \beta are metavariables of \mathcal{B}_2, then \downarrow\alpha\beta is a metaexpression of \mathcal{B}_2.
With these rules, we can write metaexpressions that, when all their metavariables are replaced by expressions and connectors in their form represented by zeros and ones, yield an expression of \mathcal{B}_2. Each metaexpression of this type refers to an infinite family of expressions of \mathcal{B}_2: the set of all expressions of \mathcal{B}_2 that can be represented by that structure. This is precisely what it means to have a formal language.
Examples of the Use of Joint Negation
Example: From the metaexpression \downarrow\alpha\downarrow\beta\gamma, the following expressions can be obtained through substitutions:
Replacing \alpha := 00, \beta := 011100 and \gamma := 010011
Leads to the expression:
010001011100010011
If we substitute \alpha := 011100, \beta := 0111011100 and \gamma := 0111010011
It generates:
010111000101110111000111010011
The metaexpression \downarrow\alpha\downarrow\beta\gamma is not only easier to assimilate than any other expression that satisfies its form, but it also represents all the expressions that can be obtained by replacing its metavariables with expressions.
End of the example \blacksquare
When replacing a metavariable, it is replaced in all places where it appears.
Example: Consider the metaexpression \downarrow\downarrow\alpha\beta\downarrow\alpha\gamma.
- If we replace \alpha:=11, we get:
\downarrow\downarrow 11\beta\downarrow 11\gamma
- If we now set \beta:=011100, the result will be:
\downarrow\downarrow 11011100\downarrow 11\gamma
- And if we now make the change \gamma:=011111, we will have:
\downarrow\downarrow 11011100\downarrow 11011111
- Finally, by changing \downarrow:=01, we will conclude with this expression:
0101110111000111011111
End of the example \blacksquare
Reordering and Parentheses
Verifying that this is a metaexpression is not particularly difficult, but it does require constant attention to the number of metasymbols and the scope of the connector \downarrow. This difficulty rapidly increases with the length of the metaexpression. This raises the valid question of whether there is a way to represent these things in a way that is easier to verify, and the answer is yes; indeed, we can use parentheses and appropriate reordering for the metaexpression that better aligns with our natural way of grouping things. To establish this point, let’s examine the following metaexpression:
\downarrow\alpha\downarrow\downarrow\alpha\beta\alpha
It turns out that, while it is not particularly difficult to verify that this is a metaexpression, it is not something we can do without having to count symbols and risking losing track in the process, and the risk grows rapidly as the length of the metaexpression increases. Is there a way to represent the same thing in a more readable manner? The fact is that such a method exists and it aligns with our natural way of grouping things. For this, we introduce parentheses and reordering through the following notation convention:
\downarrow\alpha\beta:=(\alpha\downarrow\beta)
Example: Consider the metaexpression \downarrow\alpha\downarrow\downarrow\beta\gamma\delta. If we apply the introduction of parentheses and reordering, then it will transform as follows:
| \downarrow\alpha\downarrow\downarrow\beta\gamma\delta | := | \downarrow\alpha\downarrow(\beta\downarrow \gamma)\delta |
| \downarrow\alpha\downarrow(\beta\downarrow \gamma)\delta | := | \downarrow\alpha((\beta\downarrow \gamma)\downarrow\delta) |
| \downarrow\alpha((\beta\downarrow \gamma)\downarrow\delta) | := | (\alpha \downarrow((\beta\downarrow \gamma)\downarrow\delta)) ✅ |
This final metaexpression is much easier to read and verify than the original, because each block of parentheses is a metaexpression that is composed of easily distinguishable elements: a joint negation in the center and a metaexpression on each side.
End of the example \blacksquare
Derived Connectors
Both in logic and in the rest of mathematics, certain combinations of connectors are frequently used. For this reason, to make writing even more convenient (for humans), derived connectors are introduced through the following notation conventions:
| Negation: | \neg \alpha | := | (\alpha\downarrow\alpha) |
| Inclusive Disjunction: | (\alpha \vee \beta) | := | \neg(\alpha\downarrow\beta) |
| Conjunction: | (\alpha \wedge \beta) | := | \neg(\neg\alpha\vee \neg\beta) |
| Implication: | (\alpha \rightarrow \beta) | := | (\neg\alpha\vee \beta) |
| Biconditional: | (\alpha \leftrightarrow \beta) | := | ((\alpha\rightarrow \beta)\wedge(\beta \rightarrow \alpha)) |
| Exclusive Disjunction: | (\alpha \veebar \beta) | := | \neg(\alpha\leftrightarrow \beta) |
This metalanguage we have constructed on the base language of two symbols is what is known as the Zero-Order Language of Propositional Logic. Through this language, all expressions of propositional logic are represented in a precise and unambiguous manner.
Vocalization of Propositional Logic Expressions
Although it is not necessary for doing logic, it is important to remember that our communication is not based solely on written symbols; we also have a natural tendency to vocalize things in our natural language. Therefore, for the expressions of the language of propositional logic, there are vocalizations that evoke ideas similar to those treated by their counterparts in propositional logic. These vocalizations are as follows:
| (\alpha \downarrow \beta) | Neither \alpha nor \beta |
| \neg \alpha | Negation of \alpha |
| (\alpha \vee \beta) | \alpha or \beta |
| (\alpha \wedge \beta) | \alpha and \beta |
| (\alpha \rightarrow \beta) | \alpha implies \beta |
| (\alpha \leftrightarrow \beta) | \alpha if and only if \beta |
| (\alpha \veebar \beta) | Either \alpha or \beta, but not both |
Synthesis and Reflections on the Language of Propositional Logic
With this final part, the construction of the language of propositional logic concludes, which we can summarize as a metalanguage that allows us to obtain valid expressions in the base language of two symbols. The language of propositional logic is a formal language since it defines the structure (or form) of the expressions in the base language, and each of its expressions determines the form of an infinite family of expressions in the base language. As mentioned earlier, the syntax of a formal language is extremely rigid, but in exchange, it is precise and exact: it has no ambiguity.
The Matrix Behind the Matrix Behind the Understanding of All Things
One last thing. Propositional logic and mathematics rely heavily on propositional logic, which, in turn, is built upon a base language formed by ones and zeros. Does this mean that through this, we have reached the “Matrix” behind logic and mathematics? It is possible. But it is also possible to consider a base language for the base language, from which it would be possible to reconstruct everything else; however, to find such a language, we would need to find notions even more fundamental than the concepts of order and quantity (which were used to establish the first base language). Finding a base language for the base involves reflecting on the most fundamental aspects of what it means to “understand things.” If you dig deeper, if you manage to reach the bottom, we could say that you have managed to see “the Matrix behind the Matrix behind the understanding of all things,” and it is possible that this foundational process can be continued infinitely, providing a new layer of depth of knowledge with each foundational step.