Concepts of Logic and Data Structures that are essential

Programming is based on logic. Many of the challenges we face in life often find parallels in programming. While the problems may differ, they can often be solved using similar patterns. Statements, problems, and solutions can be expressed using symbols that belong to specific languages.

Language and Meta-Language Difference

Declarative Sentence

Every proposition can be viewed as a declaratory sentence. Abstracting its meaning, we can define a declaratory sentence as an association-statement that can be either TRUE or FALSE.

Logical Connectives

At the core of language and programming languages are logical connectives. Logical connectives serve to link two sentences together. There are various logical connectives, each with a distinct meaning. In mathematics and computer science, symbols are used to represent them.

Logical connectives combine two sentences. Each sentence is evaluated to extract a value known as the truth value. The process ultimately yields a result: either TRUE or FALSE.

Truth Tables

Two sentences combined by a logical operator form a compound proposition. To determine whether the compound proposition is true or false, truth tables are used. Each connective has a table that specifies the truth value of the compound proposition.

Logic often uses truth tables, which represent in binary form information that was originally analog in nature.

Conceptually, every statement in real life can be verified mathematically, thus precisely and unambiguously. To do this, it is necessary to analyze the statement and break it down into atomic propositions.

Once the atomic propositions are identified, truth tables can convert them into numbers, creating a kind of network that starts from the bottom, that is, from the atomic propositions, and gradually grows, forming a pyramid that analyzes increasingly complex statements.

These statements are converted into 0 (false) and 1 (true), eventually reaching the final proposition, which is then represented numerically and can be converted back into its analog form.

Only with a numerical model stored in these truth tables is it possible to carry out this process.

Parsing

To analyze a compound proposition, an abstraction process is followed. Essentially, a compound proposition is divided into layers, each with a lower level of complexity.

This abstraction refers to a tree. The tree represents the entire abstraction with the different layers of difficulty.

At the base, we find the root, which is the formula itself. We may also find various branches connecting the leaves, which are the atomic propositions. Once these elements are identified, we can use the truth table to determine an output.

There are 3 branches, technically called atomic propositions. With 3 atomic propositions, there are 8 possible cases in the truth table. This means, in mathematical terms, that if we have n atomic propositions, the formula will be 2 raised to the power of n, so the number of cases increases sequentially.

Short Circuit

A short circuit shortens the path of the electric current. Essentially, a short circuit is a procedure that allows the processor to skip steps to reach the result more quickly.

Equivalent Propositions

There is a symbol similar to the equals sign, which indicates that in all cases, two variables have the same truth value. This means that either both are true or both are false. There are also properties derived from this symbol that apply to logical operators.

De Morgan's Laws

De Morgan, a British mathematician, discovered that when working with logical operators, one often encounters identical patterns in different situations. This means that there are various ways to reach the same result.

De Morgan's procedures can significantly simplify the interpretation of a compound proposition. Here is an example of how, using De Morgan's laws, a proposition simplifies. Below, you will find the demonstration.

Implication

There is another type of logical operation. Essentially, we can relate two logical propositions, stating that if one is true, then the other must also be true. The first proposition is called the antecedent, and the second is called the consequent.

The output is false only if the antecedent is true and the consequent is false. In all other cases, the output is true.

Logical Equivalences

Two logical propositions are said to be equivalent if they have the same truth value in every possible situation.

Exclusive OR (XOR)

This logical operator is somewhat complex to understand and easy to confuse. XOR (Exclusive OR) differs from OR in that it returns true only when one of the two propositions is true, but not both. If both propositions are true, XOR returns false.