Negation, conjunction, and disjunction

Logic: Propositional logic

Negation, conjunction, and disjunction

Now that we know what statements qualify as a proposition in a mathematical sense, we will define operations to construct new propositions from existing ones. These operations are so-called logical operations, and they are indicated by logical operators. We will look at three types of logical operators. First we consider the operator that reverses the assignment of true or false to a proposition.

Negation

The negation of a proposition is the opposite of the original proposition. The negation is true exactly when the original proposition is false, and false exactly when the original proposition is true.

Negation is denoted by the not-operator: $\neg$ . So, if $\blue p$ stands for a proposition then its negation is denoted by $\neg{\blue p}$ .

Example

The negation of the proposition $\blue {\textrm{"It is raining"} }$ is given by $\blue{ \textrm{"It is} \textit{ not } \textrm{raining"} }$ .
If $\blue {\textrm{"It is raining"}}$ is true, then $\blue {\textrm{"It is }\textit{not} \textrm{ raining"}}$ is false.
If $\blue {\textrm{"It is raining"}}$ is false, then $\blue {\textrm{"It is }\textit{not} \textrm{ raining"}}$ is true.
Operator notation: $\neg\blue {\textrm{"It is raining"}}$

Brackets
Brackets are used to group parts of statements in such a way that it becomes clear to which parts operators apply. So, if $\blue p$ stands for a proposition then its negation $\neg{\blue p}$ can also be written as $\neg({\blue p})$ .

In the proposition ${\blue p} = \blue {\neg(\textrm{"It is raining and there is no sunshine"})}$ the brackets make clear that the reach of $\neg$ is the whole statement $\blue {\textrm{"It is raining and there is no sunshine"}}$ rather than only the first part, as in $\blue {\neg(\textrm{"It is raining"})\textrm{ "and there is no sunshine"}}$ . Of course, the double quotes also help in this case.

It is not true that ...
The example shows that some insight is needed where to insert the word "not" in the statement to get the negation. But there is an automatic way to change the proposition to its negation: simply put the words $\blue{\textit{"It is not true that"}}$ in front of the proposition. Thus, negating the proposition $\blue{\textrm{"It is raining"}}$ would lead to $\blue{\textit{"It is not true that } \textrm{it is raining"}}$ . The proposition $\blue{\textrm{"It is }\textit{not} \textrm{ raining"}}$ can be seen as a shorter version of it.

The use of $\blue{\textit{"It is not true that"}}$ still requires some caution. The proposition $\blue{ \text{"I like apples and I like bananas"} }$ has the negation $\blue{ \textit{"It is not true that} \textrm{ I like apples and I like bananas"} }$ . But this can simplify to either $\blue{ \textrm{"I do }\textit{not} \textrm{ like apples and I do }\textit{not} \textrm{ like bananas" } }$ or $\blue{\textrm{"I do }\textit{not} \textrm{ like apples and I like bananas"}}$ . Brackets are a good way to deal with these ambiguities.

Variables
We often use letters for propositions in order to make concise statements. When saying that $\blue p$ stands for a proposition, we interpret $\blue p$ as the shorthand for a proposition. Later we will go into greater detail about variables.

Next we consider the composition of two propositions corresponding to the usual conjunctive "and".

Conjunction

The conjunction of two propositions is a proposition that is true exactly when both original propositions are true. If at least one of these propositions is false, the conjunction is also false.

Conjunction is denoted by the and-operator: $\land$ . So, if $\blue {p}$ and $\blue q$ stand for propositions, then their conjunction is denoted ${\blue p}\land {\blue q}$ .

Example

The conjunction $\blue {\textrm{"I like beans }\textit{and} \textrm{ carrots"}}$ is precisely true when the propositions $\blue {\textrm{"I like beans"}}$ and $\blue {\textrm{"I like carrots"}}$ are both true.
If at least one of them is false, then $\blue {\textrm{"I like beans }\textit{and} \textrm{ carrots"}}$ is false.
Operator notation: $\blue {\textrm{"I like beans"}} \land \blue{\text{"I like carrots"}}$ .

Infix
The and-operator, $\land$ , is what is known as an infix operator.

We say that an operator is infix if it is written in between the arguments. The most common way of writing an operator $f$ on two arguments $\blue p$ and $\blue q$ is $f({\blue p},{\blue q})$ , but by saying that the operator is infix we mean that we will write the effect of $f$ on $\blue p$ and $\blue q$ as ${\blue p}f{\blue q}$ . Here, with $f = \land$ , the result becomes ${\blue p}\land {\blue q}$ .

Other examples of infix operators are the usual " $+$ " and " $\times$ " from arithmetic.

Brackets
Brackets help to group parts of statements in such a way that it becomes clear to which parts operators apply. For instance, $\blue {(\textrm{"It is not true that it is raining"})\textit{ and } (\textrm{"there is no sunshine"})}$ can be written as
$\blue{(\text{"It is not true that it is raining"}) \land (\text{"there is no sunshine"})}$
where the brackets make clear what the arguments of the and-operator are. By taking out the not-operator from the two arguments we obtain that our conjunction can be written as
$\blue { \neg ( \text{"It is raining"}) \land \neg({\text{"there is sunshine"})}}$
The first not-operator applies to $\blue { \textrm{"It is raining"}}$ and it leaves proposition $\blue { \textrm{"there is no sunshine"}}$ out of its scope. The second not-operator comes from the word ``no" in $\blue { \textrm{``there is no sunshine"}}$ and it applies to $\blue{\textrm{"there is sunshine"}}$ . Thus, the arguments of the and-operator are $\blue{\neg p}$ and $\blue{\neg q}$ where $\blue p$ is $\blue{\textrm{"It is raining"}}$ and $\blue q$ is $\blue {\textrm{"there is sunshine"}}$ . Formally, we can write the conjunction as $\blue{\neg p} \wedge \blue{\neg q}$ .

We must be careful when placing brackets and understanding the scope of the logical operator. We don't want to confuse our initial conjunction with another one expressing something different (for instance $\neg (\blue{p \wedge q})$ ). When we introduce priorities we will obtain a unique way of placing brackets.

As could be expected, next we consider the composition of two propositions which corresponds to the usual disjunctive "or".

Disjunction

The disjunction of two propositions is a proposition that is true when at least one of the original propositions is true. The disjunction is only false when exactly both original propositions are false.

Disjunction is denoted by the or-operator: $\lor$ . So, if $\blue {p}$ and $\blue q$ stand for propositions, then their disjunction is denoted ${\blue p}\lor {\blue q}$ .

Example

The disjunction $\blue{\textrm{"I will travel by car }\textit{or} \textrm{ by train"}}$ is true when at least one of the propositions $\blue{\textrm{"I will travel by car"}}$ or $\blue{\textrm{"I will travel by train"}}$ is true. If both of the propositions are false, the proposition $\blue{\text{"I will travel by car }\textit{or} \textrm{ by train"}}$ is false.
Operator notation: $\blue{\text{"I will travel by car"}} \lor \blue{\text{"I will travel by train"}}$ .

Infix
As for "and", the operator "or" is usually put between the two propositions to which the operator is applied. This makes "or" also an infix operator.

The proposition that results from combining two propositions by "or" is true when at least one of the original propositions is true. In particular, if ${\blue p}$ and ${\blue q}$ are true, then also ${\blue p}\lor {\blue q}$ is true.

The fact that ${\blue p}\lor {\blue q}$ is true when both ${\blue p}$ and ${\blue q}$ are true, means that the "or" we use is not exclusive.

The exclusive or-operator is often denoted by the infix operator $\textrm{xor}$ , also known as $\underline{\lor}$ and $\oplus$ . The proposition $\blue p \underline{\lor} \blue q$ is true when precisely one of $\blue p$ and $\blue q$ is true. In particular $\blue p \underline{\lor} \blue q$ is false when both $\blue p$ and $\blue q$ are true.

Difference with normal language
In our daily language, we often ask questions with the operator "or". However, the meaning in our daily language is different from the use in mathematics.

In normal language, when we ask $\blue{p\textit{ or }q}$ ?, we expect the response to be either $\blue{p}$ or $\blue{q}$ .

In mathematics, the answer will be "true" or "false", depending on whether or not at least one of $\blue p$ and $\blue q$ is true.

For instance, in normal language, the answer to the question

$\blue{\textrm{"Is Beatrice a national of some state }\textit{or} \textrm{ stateless?"}}$

could be $\blue{\textrm{"Beatrice is a national of some state"}}$ or " $\blue{\text{Beatrice is stateless}}$ ".

In mathematics, however, the answer would be $\blue{\textrm{"Yes, Beatrice is a national of some state }\textit{or} \textrm{ stateless"}}$ , since at least one of the expressions $\blue{\textrm{"Beatrice is a national of some state"}}$ and $\blue{\textrm{"Beatrice is stateless"}}$ has to be true.

Brackets
The need for brackets becomes clearer now that we have more operators. For instance, $\blue {\textrm{"It is raining }\textit{and } \textrm{there is no sunshine}\textit{ or } \textrm{it is warm"}}$ is ambiguous as it can be as either $\blue {\left(\textrm{"It is raining"} \land \neg{\textrm{"There is sunshine"}}\right) } \lor \blue{ \textrm{"It is warm"}}$ or
$\blue {\textrm{"It is raining"}} \land \blue{\left(\neg{\textrm{"There is sunshine"}} \lor \textrm{"It is warm"}\right)}$ The two interpretations represent propositions which are inequivalent; this means that there is a situation where one is true while the other is false. Indeed, if it is not raining, there is sunshine and it is warm, then the first interpretation is true while the second is false.

Later we will provide a solution by imposing priorities, an order of operations, which will lead to a unique way of placing brackets.

Which logical operation is used in the following proposition?
$\text{I will travel by train and by bike}$

Conjunction

The proposition "I will travel by train and by bike" contains a conjunction. The two parts are "I will travel by train" and "I will travel by bike", and these two parts are connected by the and-operator.

There is no negation and no disjunction here.

New example