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

From Wikiversity
Jump to navigation Jump to search

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

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

Negation
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 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
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
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

and )

If a polynomial has degree , then it has at most 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 is true, then also is true“ (or short: if , then ). Its truth condition is that if has truth value true, then has also truth value true. This is satisfied whenever is false or if is true.[2] Its truth table is therefore

Implication
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 and 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 and hold, then we express this by saying " is true if and only if is true“. This is called an equivalence of the two propositions, the truth table is

Equivalence
t t t
t f f
f t f
f f t

Examples for a mathematical equivalence are:

A natural number is even if and only if in its decimal expansion, the last digit is or .
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 “ 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
t t t
t f f
f t f
f f f

shows that the truth function of and the truth function of 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
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.

  1. More precisely, mathematical theorems have very often the form .
  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 , then we assume that is true, and from that we have to show that is true as well. The case that 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 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 is given, we also say that is a sufficient condition for and that is a necessary condition for . 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.