Propositional logic/Variables and logical connectives/Applied sciences/Introduction/Section

In order to understand the dependence of a compound proposition on the truth values of the propositions involved and the logical connectives, it is useful to work with propositional variables and to represent the connectives by symbols. For a proposition, we just write

p,q,\ldots ,

and we are not interested in the content of ${}p$ , only in the possible truth values (or truth assignments) of ${}p$ , which we denote by ${}t$ (true) or ${}f$ (false) (sometimes we use the truth values ${}1$ and ${}0$ ). In the negation, the truth values are interchanged, which can be expressed by the simple truth table:

Negation

${}p$	${}\neg p$
t	f
f	t

In a given concrete proposition, there are several possibilities to express the negation. To negate the statement "I eat my hat“, we can say:

I do not eat my hat.

It is not the case that I eat my hat.

It is not true that I eat my hat.

The negation applies to a single proposition, it is a monadic operator. Let's have a look at operators which apply to more than one proposition, typically a binary operator. For a binary operation, which applies to two propositions, there are all in all four possible combinations of the truth values, so that every logical connective is determined on how it acts on these combinations. Therefore, there are ${}16$ logical connectives, the most important are the following.

The logical conjunction is the and-connective. It yields true if and only if both propositions involved are true; it is false as soon as one of the propositions involved is false. The truth table of the conjunction is as follows.

Conjunction

${}p$	${}q$	${}p\wedge q$
t	t	t
t	f	f
f	t	f
f	f	f

The logical disjunction is the (inclusive) or-connective. It is true if at least one of the propositions involved is true, it is in particular also true if both statements are true. It is only false in the case when both propositions are false. It is clear that the conjunction and the disjunction are symmetric with respect to the propositions involved.

Disjunction

${}p$	${}q$	${}p\vee q$
t	t	t
t	f	t
f	t	t
f	f	f

The implication is the most important operation in mathematics. Mathematical theorems do usually have the form of a (nested) implication. Examples are (see fact and fact)

If a polynomial has degree

{}d

, then it has at most

{}d

zeroes.

If a sequence converges, then it is bounded.

The logical content of an implication is that the validity of a condition ensures the validity of a conclusion.^[1] An implication is expressed by saying: "if ${}p$ is true, then also ${}q$ is true“ (or short: if ${}p$ , then ${}q$ ). Its truth condition is that if ${}p$ has truth value true, then ${}q$ has also truth value true. This is satisfied whenever ${}p$ is false or if ${}q$ is true.^[2] Its truth table is therefore

Implication

${}p$	${}q$	${}p\rightarrow q$
t	t	t
t	f	f
f	t	t
f	f	t

For an implication, the two propositions involved do not play the same role, the implications ${}p\rightarrow q$ and ${}q\rightarrow p$ are different. An implication has a certain direction.^[3] In the general usage and also in mathematics, implications are used when the premise is the "reason“ for the conclusion, when the implication expresses a causal connection. But this interpretation does not play any role in the context of propositional logic.

If both implications ${}p\rightarrow q$ and ${}q\rightarrow p$ hold, then we express this by saying " ${}p$ is true if and only if ${}q$ is true“. This is called an equivalence of the two propositions, the truth table is

Equivalence

${}p$	${}q$	${}p\leftrightarrow q$
t	t	t
t	f	f
f	t	f
f	f	t

Examples for a mathematical equivalence are:

A natural number

{}n

is even if and only if in its decimal expansion, the last digit is

{}0,2,4,6

or

{}8

.

A triangle is rectangular if and only if there exists a side whose square equals the sum of the squares of the other sides.

The direction from left to right in the second statement is the Pythagorean theorem, but the reverse direction is also true. Caution: There are certain contexts where equivalences are formulated as implications. This usually holds for rewards and penalties but also within mathematical definitions. If one says: "if you behave well today, then we go tomorrow to the zoo“, then one usually means that we only go to the zoo in case you behave well. Mathematical definitions like "a natural number is called even if it is a multiple of ${}2$ “ are to be understood as if and only if.

Using negation, it is possible to express every logical connective by the given connectives, and not even all of them are necessary. E.g., one can express the conjunction (and also the implication and the equivalence) with the help of the disjunction, the truth table^[4]

Conjunction as disjunction

${}p$	${}q$	${}\neg (\neg p\vee \neg q)$
t	t	t
t	f	f
f	t	f
f	f	f

shows that the truth function of ${}\neg (\neg p\vee \neg q)$ and the truth function of ${}p\wedge q$ coincide. Therefore, these expressions are logically equivalent. In such a simple expression it is easy to compute the logical values and hence to show the equivalence. For more complicated, deeply nested expressions it is useful to compute depending on the truth values of the propositions involved the truth values of all intermediate expressions. In the given example, this would yield the table

Conjunction as disjunction

${}p$	${}q$	${}\neg p$	${}\neg q$	${}\neg p\vee \neg q$	${}\neg (\neg p\vee \neg q)$
t	t	f	f	f	t
t	f	f	t	t	f
f	t	t	f	t	f
f	f	t	t	t	f

It is also possible to use more propositional variables instead of two and to get by nested connectives many new propositions. The truth assignments for the compound propositions may also be expressed in larger truth tables.

↑ More precisely, mathematical theorems have very often the form ${}p_{1}\wedge p_{2}\wedge \ldots \wedge p_{n}\rightarrow q$ .
↑ It takes a while to get used to the truth assignment of an implication in the case where the premise is false. The point is that when we prove an implication ${}p\rightarrow q$ , then we assume that ${}p$ is true, and from that we have to show that ${}q$ is true as well. The case that ${}p$ is false does not occur in the proof of an implication. In this case the implication holds anyway, even though it does not contain any "explanatory power“. Consider as an example the mathematical statement that every natural number ${}n$ which is divisible by four has to be even. This is a true statement for all natural numbers and is in particular true for all numbers which are not divisible by four. For the three truth assignments which make the implication true there exist examples of natural numbers which represent this truth assignment, but not for the forth.
↑ If an implication ${}p\rightarrow q$ is given, we also say that ${}p$ is a sufficient condition for ${}q$ and that ${}q$ is a necessary condition for ${}p$ . See also the truth table for contraposition below.
↑ In the following, in order to spare some brackets, we use the convention that the negation is stronger linked than the binary connectives and that the conjunction is stronger linked than the other connectives.

[1] More precisely, mathematical theorems have very often the form ${}p_{1}\wedge p_{2}\wedge \ldots \wedge p_{n}\rightarrow q$ .

[2] It takes a while to get used to the truth assignment of an implication in the case where the premise is false. The point is that when we prove an implication ${}p\rightarrow q$ , then we assume that ${}p$ is true, and from that we have to show that ${}q$ is true as well. The case that ${}p$ is false does not occur in the proof of an implication. In this case the implication holds anyway, even though it does not contain any "explanatory power“. Consider as an example the mathematical statement that every natural number ${}n$ which is divisible by four has to be even. This is a true statement for all natural numbers and is in particular true for all numbers which are not divisible by four. For the three truth assignments which make the implication true there exist examples of natural numbers which represent this truth assignment, but not for the forth.

[3] If an implication ${}p\rightarrow q$ is given, we also say that ${}p$ is a sufficient condition for ${}q$ and that ${}q$ is a necessary condition for ${}p$ . See also the truth table for contraposition below.

[4] In the following, in order to spare some brackets, we use the convention that the negation is stronger linked than the binary connectives and that the conjunction is stronger linked than the other connectives.

[1]

[2]

[3]

[4]