Discrete Maths for Devs: An brief introduction to Mathematical Logic

Understanding discrete mathematics is crucial to acquiring in-depth knowledge in various areas of Computer Science, such as algorithms, data structures, computing theory, and cryptography. Unlike Continuous Mathematics, which deals with infinite and continuous structures, discrete mathematics focuses on the study of finite and discrete processes.

At the heart of discrete mathematics lies mathematical logic, which investigates the principles of valid reasoning. Using symbols and precise rules, mathematical logic allows the systematic and rigorous representation and manipulation of propositions (statements). This approach provides a precise and detailed analysis of systems, constituting a fundamental basis for several fields of Computer Science.

In this article we will present basic concepts of mathematical logic, such as propositions, connectives and truth tables.

Proposition

A proposition is a statement that can be either true or false. For example:

• The sky is blue.
• The earth is not flat.
• HTTP is a text transfer protocol used on the web.
• GraphQL is a language for querying APIs.

Note that not every sentence is a proposition:

• As we are?
• Hello, how are u?
• Let's start.

Simple propositions, which cannot be further decomposed, are known as atomic propositions, while compound propositions are constructed from these atomic elements linked by connectives. The truth value of a compound proposition is determined by the truth values assigned to its individual atomic propositions.

Conjunction

A conjunction is a compound proposition in the form p ∧ q, where p and q are propositions. The truth value of this proposition is true only if both propositions are true.

In programming, we use generally use the && symbol to control the program flow with conjuntions.

The truth table of the connective ∧ is:

A truth table is a representation that shows the different combinations of logical values for each component of a proposition. In a truth table, the columns represent the simple component propositions and a compound proposition, while the rows represent the various possible combinations of true and false for these propositions. We can use the truth table to summarize how a connective behaves.

Disjunction

A disjunction is a compound proposition in the form p ∨ q, where p and q are propositions. The truth value of this proposition is true if at least one of the propositions is true.

The truth table of the connective ∨ is:

In programming, we use generally use the || symbol.

Exclusive disjunction

This disjunction is called exclusive in the sense that it allows only one proposition to be true so that it results in the true logical value. We use the ⊕ operator to generate this disjunction. See the truth table:

This is also called eXclusive OR (XOR).

Negation

The negation of a proposition generates a new proposition with the opposite logical value to the original. In this way, if the proposition is true, the new one will be false and vice versa. We have the ¬ operator (we generally use ! in programming). See the truth table for this operator:

In languages like JavaScript we use double negation to convert a truthy value into a boolean: !!p

Implication

A proposition of the form p → q is called an implication or conditional, where p is a proposition called an antecedent and q is a proposition called a consequent. This proposition will be false only if the antecedent is true but the consequent is not. We can see this operator in the truth table:

Programming languages have a conditional structure similar to this, called if.

Biconditional

A proposition in the form p ↔ q is called biconditional or equivalence, also used as "if and only if". It is true only if both propositions have the same logical value. See the truth table:

Conclusion

Through propositions, connectives, and truth tables, we have only scratched the surface of mathematical logic, which enables precise reasoning and system analysis. A solid understanding of mathematical logic not only enhances your analytical skills in programming but also helps in problem-solving and bug fixing effectively.