2.1. Propositional Logic

We humans use a natural language when we speak, such as Dutch, English or Flemish. Natural languages are ambiguous and often vague. To start modelling them we first consider propositional logic. This form of logic is arguably the easiest to work with, but also has limited expressive power. However even with this form we can already encapsulate many arguments and power a number of applications, for instance digital logic in chip design.

2.1.1. Propositions

A proposition is a statement which is either true or false. In propositional logic, we reason only about propositions and see what we can do with them. Since this is mathematics, we need to be able to talk about propositions without saying which particular propositions we are talking about, so we use symbolic names to represent them. We will always use lowercase letters such as \(p\), \(q\) and \(r\) to represent propositions. A letter used in this way is called a propositional variable. Remember that when we say something like ‘’Let \(p\) be a proposition’’, we mean ‘’For the rest of this discussion, let the symbol \(p\) stand for some particular statement, which is either true or false (although we’re not at the moment making any assumption about which it is).’’ The discussion has mathematical generality in that \(p\) can represent any statement, and the discussion will be valid no matter which statement it represents.

Application

Propositional variables are a little bit like variables in a programming language such as Java. A basic Java variable such as int x can take any integer value. There is ‘a little bit’ of similarity between the two notions of variables—don’t take the analogy too far at this point in your learning!

2.1.2. Logical operators

What we do with propositions is combine them with logical operators, also referred to as logical connectives. A logical operator can be applied to one or more propositions to produce a new proposition. The truth value of the new proposition is completely determined by the operator and by the truth values of the propositions to which it is applied.^[1] In English, logical operators are represented by words such as ‘and’, ‘or’ and ‘not’. For example, the proposition ‘’I wanted to leave and I left’’ is formed from two simpler propositions joined by the word ‘and’. Adding the word ‘not’ to the proposition ‘’I left’’ gives ‘’I did not leave’’ (after a bit of necessary grammatical adjustment).

But English is a little too rich for mathematical logic. When you read the sentence ‘’I wanted to leave and I left’’, you probably see a connotation of causality: I left because I wanted to leave. This implication does not follow from the logical combination of the truth values of the two propositions ‘’I wanted to leave’’ and ‘’I left’’. Or consider the proposition ‘’I wanted to leave but I did not leave’’. Here, the word ‘but’ has the same logical meaning as the word ‘and’, but the connotation is very different. So, in mathematical logic, we use symbols to represent logical operators. These symbols do not carry any connotation beyond their defined logical meaning. The logical operators corresponding to the English words ‘and’, ‘or’ and ‘not’ are \(\wedge\), \(\vee\) and \(\lnot\).^[2]

Definition 2.1

Let \(p\) and \(q\) be propositions. Then \(p\vee q\), \(p \wedge q\), and \(\lnot p\) are propositions, whose truth values are given by the rules:

• \(p\wedge q\) is true when both \(p\) is true and \(q\) is true, and in no other case

• \(p\vee q\) is true when either \(p\) is true, or \(q\) is true, or both \(p\) and \(q\) are true, and in no other case -\(\lnot p\) is true when \(p\) is false, and in no other case

The operators \(\wedge\), \(\vee\) and \(\lnot\) are referred to as conjunction, disjunction and negation, respectively. (Note that \(p\wedge q\) is read as ‘\(p\) and \(q\)’, \(p\vee q\) is read as ‘\(p\) or \(q\)’, and \(\lnot p\) is read as ‘not \(p\)’.)

Example

Consider the statement ‘’I am a CSE student or I am not a TPM student.’’ Taking \(p\) to mean ‘’I am a CSE student’’ and \(q\) to mean ‘’I am a TPM student’’, you can write this as \(p \vee \lnot q\).

2.1.3. Precedence rules

These operators can be used in more complicated expressions, such as \(p\wedge \lnot q\) or \((p\vee q)\wedge(q\vee r)\). A proposition made up of simpler propositions and logical operators is called a compound proposition. Just like in mathematics, parentheses can be used in compound expressions to indicate the order in which the operators are to be evaluated. In the absence of parentheses, the order of evaluation is determined by precedence rules. For the logical operators defined above, the rules are that \(\lnot\) has higher precedence than \(\wedge\), and \(\wedge\) has precedence over \(\vee\). This means that in the absence of parentheses, any \(\lnot\) operators are evaluated first, followed by any \(\wedge\) operators, followed by any \(\vee\) operators.

For example, the expression \(\lnot p \vee q \wedge r\) is equivalent to the expression \((\lnot p)\vee (q\wedge r)\), while \(p\vee q \wedge q \vee r\) is equivalent to \(p \vee (q \wedge q) \vee r\).

This still leaves open the question of which of the \(\wedge\) operators in the expression \(p\wedge q \wedge r\) is evaluated first. This is settled by the following rule: When several operators of equal precedence occur in the absence of parentheses, they are evaluated from left to right. Thus, the expression \(p\wedge q\wedge r\) is equivalent to \((p\wedge q)\wedge r\) rather than to \(p\wedge(q\wedge r)\). In this particular case, as a matter of fact, it doesn’t really matter which \(\wedge\) operator is evaluated first, since the two compound propositions \((p\wedge q)\wedge r\) and \(p\wedge (q\wedge r)\) always have the same value, no matter what logical values the component propositions \(p\), \(q\), and \(r\) have. We say that \(\wedge\) is an associative operation. We’ll see more about associativity and other properties of operations in the next section.

Important

In practice however you should always add parentheses in places where ambiguity may arise. In fact some textbooks even add them to single operators as well, e.g., writing \((p \wedge q)\) instead of \(p \wedge q\). Although for this course we do not require them around single operators, we should never need the precedence rules outlined above. Your parentheses should make clear the order of operations!

Every compound proposition has a main connective. The main connective is the connective that is evaluated last, according to the precedence rules and parentheses. There should be no ambiguity over which is the main connective in a compound proposition.

2.1.4. Logical equivalence

Suppose we want to verify that, in fact, \((p\wedge q)\wedge r\) and \(p\wedge (q\wedge r)\) do always have the same value. To do so, we have to consider all possible combinations of values of \(p\), \(q\), and \(r\), and check that for all such combinations, the two compound expressions do indeed have the same value. It is convenient to organize this computation into a truth table. A truth table is a table that shows the value of one or more compound propositions for each possible combination of values of the propositional variables that they contain. We call each such combination a situation. Table 2.1 is a truth table that compares the value of \((p\wedge q)\wedge r\) to the value of \(p\wedge (q\wedge r)\) for all possible values of \(p\), \(q\), and \(r\). There are eight rows in the table because there are exactly eight different ways in which truth values can be assigned to \(p\), \(q\), and \(r\).^[3] In this table, we see that the last two columns, representing the values of \((p\wedge q)\wedge r\) and \(p\wedge (q\wedge r)\), are identical.

Table 2.1 A truth table that demonstrates the logical equivalence of \((p\wedge q)\wedge r\) and \(p\wedge(q\wedge r)\). The fact that the last two columns of this table are identical shows that these two expressions have the same value for all eight possible combinations of values of \(p\), \(q\), and \(r\).

\(p\)	\(q\)	\(r\)	\(p\wedge q\)	\(q\wedge r\)	\((p\wedge q)\wedge r\)	\(p\wedge (q\wedge r)\)
0	0	0	0	0	0	0
0	0	1	0	0	0	0
0	1	0	0	0	0	0
0	1	1	0	1	0	0
1	0	0	0	0	0	0
1	0	1	0	0	0	0
1	1	0	1	0	0	0
1	1	1	1	1	1	1

Video

I discuss the creation of truth tables for statements written in propositional logic in more detail in one of the pencasts of this course: youtu.be/oua_nvpFECQ.

Video

In another pencast of this course, we discuss how you should formulate your answer when using truth tables to test for equivalence: youtu.be/sWu0fUu7s5c.

Tip

You can write the rows in a truth table in any order you like. We suggest you write them in a sorted order, as in Table 2.1. This helps you to be systematic in writing out the table. It also helps us to provide feedback on your answers!

More generally, we say that two compound propositions are logically equivalent if they always have the same value, no matter what truth values are assigned to the propositional variables that they contain. If the number of propositional variables is small, it is easy to use a truth table to check whether or not two propositions are logically equivalent.

Application

When writing a piece of code you will often have your code make decisions. For instance in a bit of Java code—such as in your Object-Oriented Programming course—you might encounter an if-statement to check if the user has inputted the right type of data. Since the input you expect can be rather difficult, the if-statement is a complex combination of many simple checked chained together by &&’s and ||’s. After taking a look at the code, you believe it can be simplified to a much smaller expression. Using a truth table you can prove that your simplified version is equivalent to the original.

2.1.5. More logical operators

There are other logical operators besides \(\wedge\), \(\vee\), and \(\lnot\). We will consider the conditional operator, \(\rightarrow\), the biconditional operator, \(\leftrightarrow\), and the exclusive or operator, \(\oplus\).^[4] These operators can be completely defined by a truth table that shows their values for the four possible combinations of truth values of \(p\) and \(q\).

Definition 2.2

For any propositions \(p\) and \(q\), we define the propositions \(p\rightarrow q\), \(p\leftrightarrow q\), and \(p\oplus q\) according to the truth table:

\(p\)	\(q\)	\(p\rightarrow q\)	\(p\leftrightarrow q\)	\(p\oplus q\)
0	0	1	1	0
0	1	1	0	1
1	0	0	0	1
1	1	1	1	0

Note

When these operators are used in expressions, in the absence of parentheses to indicate order of evaluation, we use the following precedence rules: The exclusive or operator, \(\oplus\), has the same precedence as \(\vee\). The conditional operator, \(\rightarrow\), has lower precedence than \(\wedge\), \(\vee\), \(\lnot\), and \(\oplus\), and is therefore evaluated after them. Finally, the biconditional operator, \(\leftrightarrow\), has the lowest precedence and is therefore evaluated last. For example, the expression \(p\rightarrow q \wedge r \leftrightarrow \lnot p \oplus s\) is evaluated as if it were written \((p\rightarrow (q\wedge r))\leftrightarrow((\lnot p) \oplus s)\). But again you should always include the parentheses!

In order to work effectively with the logical operators, you need to know more about their meaning and how they relate to ordinary English expressions. To that end we first consider the conditional operator in more detail in the next section.

2.1.6. Implications in English

The proposition \(p\rightarrow q\) is called an implication or a conditional. It is usually read as ‘\(p\) implies \(q\)’. In such an implication \(p\) and \(q\) also get special names of their own. \(p\) is called the hypothesis or antecedent and \(q\) is called the conclusion or consequent.

Furthermore we say that if the implication \(p \rightarrow q\) holds, then \(p\) is sufficient for \(q\). That is if \(p\) is true that is sufficient to also make \(q\) true. Conversely we say that \(q\) is necessary for \(p\). Without \(q\) being true, it is impossible for \(p\) to be true. That is if \(q\) is false, then \(p\) also has to be false.

In English, \(p\rightarrow q\) is often expressed as ‘if \(p\) then \(q\)’. For example, if \(p\) represents the proposition ‘’Karel Luyben is Rector Magnificus of TU Delft’’ and \(q\) represents ‘’Prometheus is blessed by the gods’’, then \(p\rightarrow q\) could be expressed in English as ‘’If Karel Luyben is Rector Magnificus of TU Delft, then Prometheus is blessed by the gods.’’ In this example, \(p\) is false and \(q\) is also false. Checking the definition of \(p\rightarrow q\), we see that \(p\rightarrow q\) is a true statement. Most people would agree with this, even though it is not immediately obvious.

Person

The letter ‘T’ in the TUDelft logo bears a stylized flame on top, referring to the flame that Prometheus brought from Mount Olympus to the people, against the will of Zeus. Because of this, Prometheus is sometimes considered as the first engineer, and he is an important symbol for the university. His bronze statue stands in the Mekelpark at the centre of campus.

Source: en.wikipedia.org/wiki/Delft_University_of_Technology. Image: weblog.library.tudelft.nl/2016/01/04/english-prometheus-is-back/.

It is worth looking at a similar example in more detail. Suppose that I assert that ‘’If Feyenoord is a great team, then I’m the King of the Netherlands’’. This statement has the form \(m\rightarrow k\) where \(m\) is the proposition ‘’Feyenoord is a great team’’ and \(k\) is the proposition ‘’I’m the king of the Netherlands’’. Now, demonstrably I am not the king of the Netherlands, so \(k\) is false. Since \(k\) is false, the only way for \(m\rightarrow k\) to be true is for \(m\) to be false as well. (Check the definition of \(\rightarrow\) in the table, if you are not convinced!) So, by asserting \(m\rightarrow k\), I am really asserting that the Feyenoord is not a great team.

Or consider the statement, ‘’If the party is on Tuesday, then I’ll be there.’’ What am I trying to say if I assert this statement? I am asserting that \(p\rightarrow q\) is true, where \(p\) represents ‘’The party is on Tuesday’’ and \(q\) represents ‘’I will be at the party’’. Suppose that \(p\) is true, that is, the party does in fact take place on Tuesday. Checking the definition of \(\rightarrow\), we see that in the only case where \(p\) is true and \(p\rightarrow q\) is true, \(q\) is also true. So from the truth of ‘’If the party is on Tuesday, then I will be at the party’’ and ‘’The party is in fact on Tuesday’’, you can deduce that ‘’I will be at the party’’ is also true. But suppose, on the other hand, that the party is actually on Wednesday. Then \(p\) is false. When \(p\) is false and \(p\rightarrow q\) is true, the definition of \(p\rightarrow q\) allows \(q\) to be either true or false. So, in this case, you can’t make any deduction about whether or not I will be at the party. The statement ‘’If the party is on Tuesday, then I’ll be there’’ doesn’t assert anything about what will happen if the party is on some other day than Tuesday.

2.1.7. More forms of implication

The implication \(\lnot q\rightarrow\lnot p\) is called the contrapositive of \(p\rightarrow q\). An implication is logically equivalent to its contrapositive. The contrapositive of ‘’If this is Tuesday, then we are in Belgium’’ is ‘’If we aren’t in Belgium, then this isn’t Tuesday’’. These two sentences assert exactly the same thing.

Note that \(p\rightarrow q\) is not logically equivalent to \(q\rightarrow p\). The implication \(q\rightarrow p\) is called the converse of \(p\rightarrow q\). The converse of ‘’If this is Tuesday, then we are in Belgium’’ is ‘’If we are in Belgium, then this is Tuesday’’. Note that it is possible for either one of these statements to be true while the other is false. In English, we might express the fact that both statements are true by saying ‘’If this is Tuesday, then we are in Belgium, and conversely’’. In logic, this would be expressed with a proposition of the form \((p\rightarrow q)\wedge(q\rightarrow p)\).

Similarly \(p \rightarrow q\) is not logically equivalent to \(\lnot p \rightarrow \lnot q\). The implication \(\lnot p \rightarrow \lnot q\) is called the inverse of \(p \rightarrow q\). Although this mistake is commonly made in English, for instance people often assume that when I say: ‘’If it is morning, I drink some coffee’’, I also mean that when it is not morning I do not drink coffee. But my original statement does not tell you anything about what I do when it is not morning.

The biconditional operator is closely related to the conditional operator. In fact, \(p\leftrightarrow q\) is logically equivalent to \((p\rightarrow q)\wedge (q\rightarrow p)\). The proposition \(p\leftrightarrow q\) is usually read as ‘\(p\) if and only if \(q\)’. (The ‘\(p\) if \(q\)’ part represents \(q\rightarrow p\), while ‘\(p\) only if \(q\)’ is another way of asserting that \(p\rightarrow q\).) It could also be expressed as ‘if \(p\) then \(q\), and conversely’. Occasionally in English, ‘if… then’ is used when what is really meant is ‘if and only if’. For example, if a parent tells a child, ‘’If you are good, Sinterklaas will bring you toys’’, the parent probably really means to say ‘’Sinterklaas will bring you toys if and only if you are good’’. (The parent would probably not respond well to the child’s perfectly logical plea ‘’But you never said what would happen if I wasn’t good!’’)

2.1.8. Exclusive or

Finally, we turn to the exclusive or operator. The English word ‘or’ is actually somewhat ambiguous. The two operators \(\oplus\) and \(\vee\) express the two possible meanings of this word. The proposition \(p\vee q\) can be expressed unambiguously as ‘’\(p\) or \(q\), or both’’, while \(p\oplus q\) stands for ‘’\(p\) or \(q\), but not both’’. If a menu says that you can choose soup or salad, it doesn’t mean that you can have both. In this case, ‘or’ is an exclusive or. On the other hand, in ‘’You are at risk of heart disease if you smoke or drink’’, the or is inclusive since you certainly don’t get off the hook if you both smoke and drink. In theoretical computer science and mathematics, the word ‘or’ is always taken in the inclusive sense of \(p\vee q\).

2.1.9. Universal operators

Now, any compound proposition that uses any of the operators \(\rightarrow\), \(\leftrightarrow\), and \(\oplus\) can be rewritten as a logically equivalent proposition that uses only \(\wedge\), \(\vee\), and \(\lnot\). It is easy to check that \(p\rightarrow q\) is logically equivalent to \( \lnot p \vee q\). (Just make a truth table for \(\lnot p \vee q\).) Similarly, \(p\leftrightarrow q\) can be expressed as \(( \lnot p \vee q)\wedge ( \lnot q \vee p)\), So, in a strict logical sense, \(\rightarrow\), \(\leftrightarrow\), and \(\oplus\) are unnecessary. (Nevertheless, they are useful and important, and we won’t give them up.)

Even more is true: in a strict logical sense, we could do without the conjunction operator \(\wedge\). It is easy to check that \(p\wedge q\) is logically equivalent to \(\lnot(\lnot p\vee\lnot q)\), so any expression that uses \(\wedge\) can be rewritten as one that uses only \(\lnot\) and \(\vee\). Alternatively, we could do without \(\vee\) and write everything in terms of \(\lnot\) and \(\wedge\). We shall study some of these rewrite rules in more detail in Section 2.2.

We call a set of operators that can express all operations: functionally complete. More formally we would state the following:

Definition 2.3

A set of logical operators is functionally complete if and only if all formulas in propositional logic can be rewritten to an equivalent form that uses only operators from the set.

Consider for instance the set \(\{\lnot,\vee\}\). As shown above the \(\wedge\), \(\rightarrow\) and \(\leftrightarrow\)-operators can be expressed using only these operators. In fact all possible operations can be expressed using only \(\{\lnot,\vee\}\). To prove this you will show in one of the exercises that all possible formulas in propositional logic can be expressed using \(\{\lnot, \vee, \wedge, \rightarrow, \leftrightarrow\}\). So by showing that we do not need \(\wedge\), \(\rightarrow\), and \(\leftrightarrow\) we can prove that \(\{\lnot,\vee\}\) is also functionally complete.

2.1.10. Classifying propositions

Certain types of proposition will play a special role in our further work with logic. In particular, we define tautologies, contradictions, and contingencies as follows:

Definition 2.4

A compound proposition is said to be a tautology if and only if it is true for all possible combinations of truth values of the propositional variables which it contains.
A compound proposition is said to be a contradiction if and only if it is false for all possible combinations of truth values of the propositional variables which it contains.
A compound proposition is said to be a contingency if and only if it is neither a tautology nor a contradiction.

For example, the proposition \(((p\vee q)\wedge \lnot q)\rightarrow p\) is a tautology. This can be checked with a truth table:

\(p\)	\(q\)	\(p\vee q\)	\(\lnot q\)	\((p\vee q)\wedge \lnot q\)	\(((p\vee q)\wedge \lnot q)\rightarrow p\)
0	0	0	1	0	1
0	1	1	0	0	1
1	0	1	1	1	1
1	1	1	0	0	1

The fact that all entries in the last column are true tells us that this expression is a tautology. Note that for any compound proposition \(P\), \(P\) is a tautology if and only if \(\lnot P\) is a contradiction. (Here and moving forward, we use uppercase letters to represent compound propositions. \(P\) stands for any formula made up of simple propositions, propositional variables, and logical operators.)

Logical equivalence can be defined in terms of tautology:

Definition 2.5

Two compound propositions, \(P\) and \(Q\), are said to be logically equivalent if and only if the proposition \(P\leftrightarrow Q\) is a tautology.

The assertion that \(P\) is logically equivalent to \(Q\) will be expressed symbolically as ‘\(P\equiv Q\)’. For example, \((p\rightarrow q)\equiv(\lnot p \vee q)\), and \(p\oplus q\equiv (p\vee q)\wedge \lnot(p\wedge q)\).

Note

What if \(P\rightarrow Q\) and \(P\) is false? From a false premise we can derive any conclusion (check the truth table of \(\rightarrow\)). So if \(k\) stands for ‘’I’m the King of the Netherlands’’, then \(k\rightarrow Q\) is true for any compound proposition \(Q\). You can substitute anything for \(Q\), and the implication \(k\rightarrow Q\) will hold. For example, it a logically valid deduction that: If I’m the King of the Netherlands, then unicorns exist. Taking this further, from a contradiction we can derive any conclusion. This is called the Principle of Explosion. (No unicorns were harmed by explaining this principle.)

2.1.11. Exercises

Tip

Recall that solutions to some of the exercises start on Section 6. Exercises that have a solution are marked with a dagger (†) symbol. We suggest you attempt the exercise first before looking at the solution!

Exercise (1†)

Give the three truth tables that define the logical operators \(\wedge\), \(\vee\), and \(\lnot\).

Exercise (2†)

Some of the following compound propositions are tautologies, some are contradictions, and some are neither (i.e., , so are contingencies). In each case, use a truth table to decide to which of these categories the proposition belongs:

1. \((p\wedge (p\rightarrow q))\rightarrow q\)

2. \(((p\rightarrow q)\wedge(q\rightarrow r))\rightarrow (p\rightarrow r)\)

3. \(p\wedge\lnot p\)

4. \((p\vee q)\rightarrow(p\wedge q)\)

5. \(p\vee\lnot p\)

6. \((p\wedge q)\rightarrow(p\vee q)\)

Exercise (3†)

Use truth tables to show that each of the following propositions is logically equivalent to \(p\leftrightarrow q\).

1. \((p\rightarrow q)\wedge (q\rightarrow p)\)

2. \(\lnot p\leftrightarrow\lnot q\)

3. \((p\rightarrow q)\wedge(\lnot p\rightarrow\lnot q)\)

4. \(\lnot(p\oplus q)\)

Exercise (4†)

Is \(\rightarrow\) an associative operation? This is, is \((p\rightarrow q)\rightarrow r\) logically equivalent to \(p\rightarrow(q\rightarrow r)\)?

Exercise (5†)

Let \(p\) represent the proposition ‘’You leave’’ and let \(q\) represent the proposition ‘’I leave’’. Express the following sentences as compound propositions using \(p\) and \(q\), and show that they are logically equivalent:

1. Either you leave or I do. (Or both!)

2. If you don’t leave, I will.

Exercise (6†)

Suppose that \(m\) represents the proposition ‘’The Earth moves’’, \(c\) represents ‘’The Earth is the centre of the universe’’, and \(g\) represents ‘’Galileo was falsely accused’’. Translate each of the following compound propositions into English:

1. \(\lnot g\wedge c\)

2. \(m\rightarrow\lnot c\)

3. \(m\leftrightarrow\lnot c\)

4. \((m\rightarrow g)\wedge (c\rightarrow \lnot g)\)

Exercise (7†)

Give the converse and the contrapositive of each of the following English sentences:

1. If you are good, Sinterklaas brings you toys.

2. If the package weighs more than one kilo, then you need extra postage.

3. If I have a choice, I don’t eat courgette.

Exercise (8†)

In an ordinary deck of fifty-two playing cards, for how many cards is it true

1. that ‘’This card is a ten and this card is a heart’’?

2. that ‘’This card is a ten or this card is a heart’’?

3. that ‘’If this card is a ten, then this card is a heart’’?

4. that ‘’This card is a ten if and only if this card is a heart’’?

Exercise (9†)

Define a logical operator \(\downarrow\) so that \(p\downarrow q\) is logically equivalent to \(\lnot(p\vee q)\). (This operator is usually referred to as ‘nor’, short for ‘not or’.) Show that each of the propositions \(\lnot p\), \(p\wedge q\), \(p\vee q\), \(p\rightarrow q\), \(p\leftrightarrow q\), and \(p\oplus q\) can be rewritten as a logically equivalent proposition that uses \(\downarrow\) as its only operator.

Exercise (10†)

For our proof that \(\{\lnot,\vee\}\) is functionally complete, we need to show that all formulas in propositional logic can be expressed in an equivalent form using only \(\{\lnot, \wedge, \vee, \rightarrow, \leftrightarrow\}\).

1. How many unique truth tables exist for formulas containing two atoms?

2. Create a function for each of the possible truth tables that uses only the 5 operators listed above.

3. Give an (informal) argument why this means all formulas in propositional logic can be expressed using only these five operators.

---

[1]

It is not always true that the truth value of a sentence can be determined from the truth values of its component parts. For example, if \(p\) is a proposition, then ‘Johan Cruyff believes \(p\)’ is also a proposition, so ‘Cruyff believes’ is some kind of operator. However, it does not count as a logical operator because just from knowing whether or not \(p\) is true, we get no information at all about whether ‘Johan Cruyff believes \(p\)’ is true.

[2]

Other textbooks might use different notations to represent a negation. For instance a bar over the variable (\(\bar{x}\)) or a \(\sim\) symbol (\(\sim{}x\)). In Boolean algebra (and thus in your Computer Organisation course) you will also often find the \(+\) symbol to represent an ‘or’ and a \(\cdot\) (dot) symbol to represent an ‘and’.

[3]

In general, if there are \(n\) variables, then there are \(2^n\) different ways to assign truth values to the variables, i.e., \(2^n\) situations. This might become clear to you if you try to come up with a scheme for systematically listing all possible sets of values. As this should not satisfy you, you’ll find a rigorous proof of the fact later in this chapter.

[4]

Note that the symbols for these operations also differ from textbook to textbook. While \(\rightarrow\) is fairly standard, \(\leftrightarrow\) is sometimes represented by \(\equiv\) or \(\Leftrightarrow\). There is even less standardization of the exclusive or operator, but that operator is generally not so important as the others.