Logic for Programmers

Right at the start of studying any programming language, we run into the word “logic”. It is usually used to refer to the process of designing an algorithm, or to the conditional structures of the language, or to operators such as AND and OR. In these last two contexts, we are referring to what is called mathematical logic. In this article, I cover the basics of mathematical logic for programming students.

Introduction

#

This article is meant as a short introductory text on the study of mathematical logic. I tried to include what I consider the minimum starting material for those who want to go deeper later with other sources. It is built from my own notes, taken while I was studying to better understand logical operators as I learned Python. Corrections and suggestions are welcome. Those who want a more in-depth study can look for the book Filho, E. A. Iniciação à lógica matemática (in Portuguese), Editora Nobel, 2002.

Mathematical logic (also called symbolic logic or propositional logic) is the study of declarative sentences, also known as propositions. A proposition is any set of words or symbols that expresses a thought with complete meaning. For example, “The Moon is a satellite of the Earth” is a proposition, as is “π > √ 5 ”.

Propositions must satisfy the following two fundamental principles:

• Law of the excluded middle: a proposition can only be true or false, with no other alternative.
• Law of non-contradiction: a proposition cannot be true and false at the same time.

We then say that a true proposition has truth value T (true) and a false proposition has truth value F (false). Truth values are also commonly represented by 0 (zero) for false propositions and 1 (one) for true propositions.

The two propositions used as examples above are true, but the proposition “The number π is rational” is false.

Some of you will already recognize aspects that appear when we start studying a programming language. Most languages have a data type called Boolean, a name derived from the mathematician George Boole, which is precisely a type that takes only two possible values.

Just to illustrate, let’s look at some simple examples in Python:

3 > 2

True

2 > 3

False

a = 2
b = 2

a == b

True

Note that the comparisons above result in True or False. We can assign such values to a variable:

t = True

type(t)

bool

Note that the type is bool, short for Boolean.

An immediate application of Boolean return values is the flow control of conditional structures. Take this simple example:

people = {'João': 17,
          'Maria': 20,
          'Tibúrcio': 18}

adult_age = 18

for person, age in people.items():
    if age >= adult_age:
        print(f'{person} can drink alcohol.')
    else:
        print(f'{person} can NOT drink alcohol.')

João can NOT drink alcohol.
Maria can drink alcohol.
Tibúrcio can drink alcohol.

Note that we created a dictionary with people’s names and ages and checked whether each person is at least 18 years old. If so, that person can drink alcohol. Note that there is a check age >= adult_age. The output of that check is a Boolean, which can only be True or False. The result determines the flow the program will follow, entering the if block or the else block. Let’s see the result of the check for each entry in the dictionary:

for person, age in people.items():
    print(age >= adult_age)

False
True
True

Some symbols used in mathematical logic

#

We have already seen that the subject is related to programming. Let’s go a little deeper. Whatever language you come across, there will be the concept of logical operators, the best known being AND and OR. The symbol for each operator varies from language to language. In Python, for example, AND and OR are represented by the words and and or, respectively. In the study of logic, they are called conjunction and disjunction.

Operators build new propositions from other ones. In logic books and materials, the following symbols are used for the main logical operators:

Consider the proposition “The number 6 is even and the number 8 is a perfect cube”. In bold we see a conjunction of two propositions: “The number 6 is even”, “The number 8 is a perfect cube”. It is common to represent simple propositions by lowercase letters. So, we could express the compound proposition of this example as p ^ q. But how do we determine the truth value of a given compound proposition?

Truth tables

#

With the operators above, compound propositions can be created. Consequently, it is of interest to check the logical validity of a given compound proposition. That is what truth tables are for.

There are many online materials and books on mathematical logic for those who want a more formal presentation of the subject. In this article I want to show it in a more practical way, which the reader can easily replicate and can even use to check the results of simple logic exercises. So I will use a small Python package, ttg - truth-table-generator, which, as the name says, lets us build truth tables.

Installation is very simple: pip install truth-table-generator

To use ttg, the following terms are used as symbols. They are in single quotes to make explicit that the program receives them as strings.

We need to import the package’s table builder, called Truths:

from ttg import Truths

Suppose you would like to build a truth table by hand. If a compound proposition is made of \(n\) simple propositions, its truth table will have \(2^n\) rows. In the first column, supposing it has x rows, put T (or any other mark for the true value) in the first \(\frac{x}{2}\) rows and F (or any other mark for the false value) in the rest. In the second column, put T in the first \(\frac{x}{4}\) rows, F in the next \(\frac{x}{4}\), and keep alternating like this until the end of the rows. The same line of reasoning continues for the following columns. Practice, for example, with 4 simple propositions.

Check your answer against the following table generated by ttg for 4 simple propositions p, q, r and s:

print(Truths(['p', 'q', 'r', 's']))

+-----+-----+-----+-----+
|  p  |  q  |  r  |  s  |
|-----+-----+-----+-----|
|  1  |  1  |  1  |  1  |
|  1  |  1  |  1  |  0  |
|  1  |  1  |  0  |  1  |
|  1  |  1  |  0  |  0  |
|  1  |  0  |  1  |  1  |
|  1  |  0  |  1  |  0  |
|  1  |  0  |  0  |  1  |
|  1  |  0  |  0  |  0  |
|  0  |  1  |  1  |  1  |
|  0  |  1  |  1  |  0  |
|  0  |  1  |  0  |  1  |
|  0  |  1  |  0  |  0  |
|  0  |  0  |  1  |  1  |
|  0  |  0  |  1  |  0  |
|  0  |  0  |  0  |  1  |
|  0  |  0  |  0  |  0  |
+-----+-----+-----+-----+

Notice that ttg uses 1 as the symbol for true and 0 for false by default. If we pass a parameter called ints (meaning integers: 0 and 1) as False, the table shows the words True and False instead:

print(Truths(['p', 'q', 'r', 's'], ints=False))

+-------+-------+-------+-------+
|   p   |   q   |   r   |   s   |
|-------+-------+-------+-------|
| True  | True  | True  | True  |
| True  | True  | True  | False |
| True  | True  | False | True  |
| True  | True  | False | False |
| True  | False | True  | True  |
| True  | False | True  | False |
| True  | False | False | True  |
| True  | False | False | False |
| False | True  | True  | True  |
| False | True  | True  | False |
| False | True  | False | True  |
| False | True  | False | False |
| False | False | True  | True  |
| False | False | True  | False |
| False | False | False | True  |
| False | False | False | False |
+-------+-------+-------+-------+

This last form of representation will be the one used in the rest of the article.

Logical operations

#

Let’s check the truth table for each binary operator available in ttg.

print(Truths(['p', 'q'], 
             ['p and q', 'p or q', 'p => q', 'p = q', 'p xor q',
              'p nand q', 'p nor q'],
             ints=False))

+-------+-------+-----------+----------+----------+---------+-----------+------------+-----------+
|   p   |   q   |  p and q  |  p or q  |  p => q  |  p = q  |  p xor q  |  p nand q  |  p nor q  |
|-------+-------+-----------+----------+----------+---------+-----------+------------+-----------|
| True  | True  |   True    |   True   |   True   |  True   |   False   |   False    |   False   |
| True  | False |   False   |   True   |  False   |  False  |   True    |    True    |   False   |
| False | True  |   False   |   True   |   True   |  False  |   True    |    True    |   False   |
| False | False |   False   |  False   |   True   |  True   |   False   |    True    |   True    |
+-------+-------+-----------+----------+----------+---------+-----------+------------+-----------+

These small tables are the ones usually shown in materials on logical operators for programming. We have already seen in this article that the short-circuit behavior of operators can be understood from these truth tables. Likewise, they are essential for understanding digital circuits and the so-called bitwise operations.

ttg can present the tables in a more visually pleasant way in Jupyter Notebooks, since it uses pandas internally. Below, two functions are declared to apply colors to the truth tables. You can change the functions if you want different colors or other effects that are not implemented. You are invited to make changes and share them.

def color_false_red(val):
    """Color red False (0) and green True (1) values"""
    
    color = 'red' if (val == False) else 'green'
    return 'color: %s' % color


def df_style(logic, hl_rows=[], hl_cols=[]):
    """Applies style to logical expression (logic) pandas truth table. 
    Text: center. Table: no index column. Highlight yellow rows and columns in 
    lists (hl_rows and hl_cols). At the end applies color_false_red function"""
    
    d = logic.as_pandas().style.set_table_styles(
        [{'selector':'th', 
          'props': [('font-size', '12pt')]}]).set_properties(
        **{'text-align': 'center', 'font-size': '115%'}).apply(
        lambda x: ['background: lightyellow' if x.name in hl_rows else '' for i in x],
        axis=1).apply(lambda x: ['background: lightyellow' if x.name in hl_cols else '' for i in x],
                      axis=0).hide_index()
    d = d.applymap(color_false_red)
    return d

Let’s see how to use these functions and take the chance to have more examples of logic. Suppose you want to build a truth table for the proposition \((p \land q) \rightarrow (p \lor q)\). To practice, build the table by hand before continuing.

Using the form we have already seen, but declaring a variable so that it is easier to reproduce the table:

proposition01 = Truths(['p', 'q'], ['(p and q) => (p or q)'], ints=False)

print(proposition01)

+-------+-------+-------------------------+
|   p   |   q   |  (p and q) => (p or q)  |
|-------+-------+-------------------------|
| True  | True  |          True           |
| True  | False |          True           |
| False | True  |          True           |
| False | False |          True           |
+-------+-------+-------------------------+

Now using the view with a pandas DataFrame table:

df_style(proposition01)

Suppose you would like to highlight the last column:

df_style(proposition01, hl_cols=['(p and q) => (p or q)'])

Now, suppose you would like to highlight the last row:

df_style(proposition01, hl_rows=[4])  # the header row is counted as zero

It is possible to highlight rows and columns at the same time:

df_style(proposition01, hl_rows=[4], hl_cols=['(p and q) => (p or q)'])

Worked exercise

#

Let’s solve an exercise where the previous ways of viewing the tables will prove useful. To practice, do the exercises by hand and compare with the result shown by ttg below.

If \(p\) is a true proposition and \(q\) is a false proposition, what is the truth value of the compound proposition \((p \land \neg q) \rightarrow q\)?

Solution: Let’s start by declaring a variable and showing a simple table with print:

exercise01 = Truths(['p', 'q'], ['(p and (~q)) => q'], ints = False)

Attention: Note the care with the parentheses, especially with the negation operator.

print(exercise01)

+-------+-------+---------------------+
|   p   |   q   |  (p and (~q)) => q  |
|-------+-------+---------------------|
| True  | True  |        True         |
| True  | False |        False        |
| False | True  |        True         |
| False | False |        True         |
+-------+-------+---------------------+

The statement assigned specific truth values to the simple propositions. We can use the visual resources presented earlier to highlight the table row for those values and find the answer to the exercise:

df_style(exercise01, hl_rows=[2])

Therefore, the truth value of the compound proposition in the given context is False.

Tautologies, contradictions and contingencies

#

A tautology is any compound proposition whose truth value is always true, whatever the truth values of its simple component propositions. That is, in any context.

A contradiction is any compound proposition whose truth value is always false, whatever the truth values of its simple component propositions. That is, in any context.

A contingency is any compound proposition that is neither a tautology nor a contradiction.

ttg has the valuation method which, by default, analyzes the last column of a truth table and evaluates whether it is a tautology, a contradiction or a contingency. It is possible to pass parameters to valuation for tables with several columns; see the documentation for details if you are interested.

print(proposition01)

+-------+-------+-------------------------+
|   p   |   q   |  (p and q) => (p or q)  |
|-------+-------+-------------------------|
| True  | True  |          True           |
| True  | False |          True           |
| False | True  |          True           |
| False | False |          True           |
+-------+-------+-------------------------+

proposition01.valuation()

'Tautology'

proposition02 = Truths(['p'], ['p and (~p)'], ints=False)

print(proposition02)

+-------+--------------+
|   p   |  p and (~p)  |
|-------+--------------|
| True  |    False     |
| False |    False     |
+-------+--------------+

proposition02.valuation()

'Contradiction'

proposition03 = Truths(['p', 'q', 'r'], ['(p and q) or r'], ints=False)

print(proposition03)

+-------+-------+-------+------------------+
|   p   |   q   |   r   |  (p and q) or r  |
|-------+-------+-------+------------------|
| True  | True  | True  |       True       |
| True  | True  | False |       True       |
| True  | False | True  |       True       |
| True  | False | False |      False       |
| False | True  | True  |       True       |
| False | True  | False |      False       |
| False | False | True  |       True       |
| False | False | False |      False       |
+-------+-------+-------+------------------+

proposition03.valuation()

'Contingency'

Worked exercise

#

Show that the following compound propositions are tautologies.

a. \( (p \land q) \rightarrow p \)

b. \( p \rightarrow (p \lor q) \)

c. \( [p \land (p \rightarrow q)] \rightarrow q \) (known as modus ponens)

d. \( [(p \rightarrow q) \land (\neg q)] \rightarrow (\neg p) \) (known as modus tollens)

Note: These tautologies are known as rules of inference.

exercise02 = Truths(
    ['p', 'q'], 
    ['(p and q) => p', 'p => (p or q)',
     '(p and (p => q)) => q', '((p => q) and (~q)) => (~p)'],
    ints=False)

print(exercise02)

+-------+-------+------------------+-----------------+-------------------------+-------------------------------+
|   p   |   q   |  (p and q) => p  |  p => (p or q)  |  (p and (p => q)) => q  |  ((p => q) and (~q)) => (~p)  |
|-------+-------+------------------+-----------------+-------------------------+-------------------------------|
| True  | True  |       True       |      True       |          True           |             True              |
| True  | False |       True       |      True       |          True           |             True              |
| False | True  |       True       |      True       |          True           |             True              |
| False | False |       True       |      True       |          True           |             True              |
+-------+-------+------------------+-----------------+-------------------------+-------------------------------+

We see that they are all tautologies. We can pass each column to the valuation method and check with ttg as well:

print(exercise02.valuation(3))
print(exercise02.valuation(4))
print(exercise02.valuation(5))
print(exercise02.valuation(6))

Tautology
Tautology
Tautology
Tautology

Logical equivalence

#

Let \(p\), \(q\) and \(r\) be any three simple propositions. Below, the symbol \(\Leftrightarrow\) is used to mean equivalence between the proposition before and the one after the symbol. Two propositions are equivalent if they have identical truth tables. So, the reader can practice by building tables for the propositions before and after the equivalence symbol in each case below and checking that they are equal.

• Idempotent laws

  • \(p \land p \Leftrightarrow p\)
  • \(p \lor p \Leftrightarrow p\)

• Commutative laws

  • \(p \land q \Leftrightarrow q \land p\)
  • \(p \lor q \Leftrightarrow q \lor p\)

• Identity laws

  • \(p \land V \Leftrightarrow p\)
  • \(p \land F \Leftrightarrow F\)
  • \(p \lor V \Leftrightarrow V\)
  • \(p \lor F \Leftrightarrow p\)

• Complement laws

  • \(\neg (\neg p) \Leftrightarrow p\)
  • \(p \land \neg p \Leftrightarrow F\)
  • \(p \lor \neg p \Leftrightarrow V\)
  • \(\neg V \Leftrightarrow F\)
  • \(\neg F \Leftrightarrow V\)

• Associative laws

  • \((p \land q) \land r \Leftrightarrow p \land (q \land r)\)
  • \((p \lor q) \lor r \Leftrightarrow p \lor (q \lor r)\)

• Distributive laws

  • \(p \land (q \lor r) \Leftrightarrow (p \land q) \lor (p \land r)\)
  • \(p \lor (q \land r) \Leftrightarrow (p \lor q) \land (p \lor r)\)

• Absorption laws

  • \(p \land (p \lor q) \Leftrightarrow p\)
  • \(p \lor (p \land q) \Leftrightarrow p\)

• De Morgan’s laws

  • \(\neg (p \land q) \Leftrightarrow \neg p \lor \neg q \)
  • \(\neg (p \lor q) \Leftrightarrow \neg p \land \neg q \)
  • \(\neg (p \land q \land r) \Leftrightarrow \neg p \lor \neg q \lor \neg r \)
  • \(\neg (p \lor q \lor r) \Leftrightarrow \neg p \land \neg q \land \neg r \)

• Negation of the conditional

  • \(\neg (p \rightarrow q) \Leftrightarrow p \land \neg q\)

• Negation of the biconditional

  • \(\neg (p \leftrightarrow q) \Leftrightarrow (p \land \neg q) \lor (\neg p \land q)\)

In addition, the following terms are used in the study of conditionals:

The conditional and the contrapositive are equivalent: \((p \rightarrow q) \Leftrightarrow (\neg q \rightarrow \neg p)\)

Let’s check the first two De Morgan’s laws presented and the negation of the conditional with ttg.

de_morgan01 = Truths(['p','q'], ['~(p and q)', '(~p) or (~q)'])
de_morgan02 = Truths(['p','q'], ['~(p or q)', '(~p) and (~q)'])
conditional_negation = Truths(['p','q'], ['~(p => q)', 'p and (~q)'])

print(de_morgan01)

+-----+-----+--------------+----------------+
|  p  |  q  |  ~(p and q)  |  (~p) or (~q)  |
|-----+-----+--------------+----------------|
|  1  |  1  |      0       |       0        |
|  1  |  0  |      1       |       1        |
|  0  |  1  |      1       |       1        |
|  0  |  0  |      1       |       1        |
+-----+-----+--------------+----------------+

print(de_morgan02)

+-----+-----+-------------+-----------------+
|  p  |  q  |  ~(p or q)  |  (~p) and (~q)  |
|-----+-----+-------------+-----------------|
|  1  |  1  |      0      |        0        |
|  1  |  0  |      0      |        0        |
|  0  |  1  |      0      |        0        |
|  0  |  0  |      1      |        1        |
+-----+-----+-------------+-----------------+

print(conditional_negation)

+-----+-----+-------------+--------------+
|  p  |  q  |  ~(p => q)  |  p and (~q)  |
|-----+-----+-------------+--------------|
|  1  |  1  |      0      |      0       |
|  1  |  0  |      1      |      1       |
|  0  |  1  |      0      |      0       |
|  0  |  0  |      0      |      0       |
+-----+-----+-------------+--------------+

Notice that the two columns for each of the last three examples are equal, showing the equivalences presented.

Additional exercises

#

Some exercises are suggested below. The answer key is in a notebook in this repository (in Portuguese). In the answer key file, some remarks and discussions are also made along the solutions. I suggest that you solve the exercises by hand on paper, to practice and make sure you understood the content, and then use ttg to check your answers.

Exercise 1: Build the truth table for the propositions and classify them as tautology, contradiction or contingency.

a. \(\neg p \lor \neg q\)

b. \( [ (p \land \neg q) \lor \neg r] \land [ (\neg p \lor q) \land r ] \)

c. \((p \land q) \rightarrow (p \lor q)\)

d. \((p \land q) \lor r\)

e. \((p \land q) \rightarrow p\)

f. \(p \rightarrow (p \lor q)\)

g. \( [ p \land (p \rightarrow q) ] \rightarrow q \)

h. \( [ (p \rightarrow q) \land \neg q ] \rightarrow \neg q \)

i. \( (p \land q) \land \neg p \)

j. \( [ (p \lor \neg q) \land r ] \land [ (p \land q) \lor \neg r ] \)

k. \( [ (p \leftrightarrow q) \rightarrow r ] \leftrightarrow [ \neg (p \land r) \rightarrow q ] \)

Exercise 2: If \(p\) is a proposition with truth value true and \(q\) is a proposition with truth value false, what is the truth value of the compound proposition \(R: (p \land \neg q) \rightarrow q\)?

Exercise 3: Assign a truth value (true or false) to each of the following statements:

a. If Mars is a planet then \(3 = 7 - 4\).

b. The sum of two even numbers is an even number and \(7^2 = 49\).

c. \(3=5\) if and only if the bear is an invertebrate animal.

d. If \(10^2 = 100\) then every integer is a natural number.

e. \(2 = 3^2 - 7\) or the Earth is flat.

f. \(3 > 1\) and \(4 > 2\)

g. \(3 > 1\) or \(3 = 1\)

Exercise 4: Let:

• \(p\): London is the capital of England.
• \(q\): The Eiffel Tower is located in London.
• \(r\): The Greenwich meridian passes through London.

Translate each of the compound propositions below into natural language and determine its truth value.

a. \(\neg q \land \neg p\)

b. \(\neg q \lor \neg p\)

c. \(\neg (p \land q)\)

d. \(\neg p \lor r\)

Exercise 5: Prove that the conditional \(p \rightarrow q\) is equivalent to \(\neg (p \land \neg q)\)

Exercise 6: Show that \(\neg (p \rightarrow q)\) is equivalent to \(p \land \neg q\)

Exercise 7: Show symbolically that the following are logically equivalent: “If a student studies, then he or she passes” and “It is not true that a student studies and does not pass”.

Exercise 8: Show symbolically that the negation of “If a student studies, then he or she passes” is “There are students who study and do not pass”.

Exercise 9: Consider the proposition: “If Edson runs for president, then he will be elected”. In which of the cases below should this conditional proposition be considered false?

a. Edson ran for president and was elected.

b. Edson ran for president and was not elected.

c. Edson did not run for president.

Exercise 10: Consider the conditional: “If your tooth has a cavity, you need a dentist”.

a. Suppose that “your tooth does not have a cavity and you need a dentist”. Does this mean a negation of the previous one?

b. Write a proposition that is not a conditional and that corresponds to the negation of the proposition above.

Exercise 11: Write in symbolic language and check whether the propositions “If my name is John, then I pass the entrance exam” and “I pass the entrance exam or my name is not John” are logically equivalent.

Exercise 12: Given that the proposition \(p \rightarrow (r \lor s)\) is false and the proposition \( (q \land \neg s) \rightarrow p \) is true, classify the statements \(p\), \(q\), \(r\) and \(s\) as true or false.

Exercise 13: Knowing that the propositions \(p\) and \(q\) are true and that the proposition \(r\) is false, determine the truth value of the following proposition: \((\neg p \downarrow q) \land (q \uparrow \neg r)\)

Conclusion

#

In this article we saw the basics of mathematical logic for programmers with the help of the Python package ttg - truth-table-generator. It is a vast subject, and with the basics shown here, those who need to can research further. The notebook for this article and the one with the answers to the proposed exercises can be found in this repository (in Portuguese).

See you next time.