The only connective that takes only one formula as an argument is the negation: it swaps the truth values true and false.
The negation of a proposition is the opposite of the original proposition. The negation is true only if the original proposition is false, and false if the original proposition is true .
Negation is symbolised by the unary operator \(\neg\).
If \(\varphi\) is a formula, then \(\neg \,\varphi\) is a proposition with opposite truth value.
Example
The denial of "It's snowing." is " It's not the case that it's snowing." or simply "It's not snowing."
If "It's snowing." is true, then the negation is "It's not snowing." false.
Propositional notation: \(\neg\,\text{"It snows."}\)
Parentheses may be placed around a logical formula: \(\neg\,\varphi\) and \(\neg(\varphi)\) are formulas with the same meaning.
The double negation of a formula \(\varphi\), denoted \(\neg\neg\,\varphi\), always has the same truth values as the original formula \(\varphi\). These formulas are logically equivalent.
The compound proposition "It's snowing." or "It's not snowing." is a statement that is always true in classical propositional logic as we discuss in this chapter, but not in intuitionistic propositional logic. Every valuation has a value of 1 (true). We call this a tautology. This example fits the law of the excluded third. With the statement "It can freeze or it can thaw" you are always right!
The compound proposition "It's snowing." and "It's not snowing." is a statement that is always false. Every valuation has a value of 0 (false); it is an unsatisfiable proposition, better known among the general public by the name contradiction.
The truth table below can be used with every formula \(\varphi\): \[\begin{array}{c|c} \varphi & \neg\,\varphi\\ \hline 0 & 1\\ 1 & 0\end{array}\]
The rest of the connectives have two arguments. We will discuss the logical operators "and" and "or". The first signs of ambiguity in natural language emerge.
The conjunction of two propositions is a proposition that is true exactly when both original propositions are true.
In all other cases the conjunction is false.
Conjunction is symbolised by the infix operator \(\land\), which represents the conjunction "and" in natural language.
If \(\varphi\) and \(\psi\) are formulas, then \(\varphi\land \psi\) symbolises their conjunction.
Example
"It's snowing and the road is slippery" is true if both "It's snowing." are "The road is slippery" are true statements.
If either statement is false, then the compound statement is also false.
In natural language, sometimes we don't use the word "and" for a conjunction. For example, the sentence "The sun is shining, but it's raining." is more or less another formulation of "The sun is shining and it is raining." Subtle differences in natural language are then swept under the rug.
Sometimes you omit the connective: In the sentence "Red, green and blue are primary colours." you use "and" with three arguments, or you implicitly mean "Red is a primary colour" and "Green is a primary colour" and "Blue is a primary colour".
Converting something from natural language into propositional notation is less easy than you might think at first glance. For example, if you make the following statement "I don't like coffee and tea.", you mean that you just like both drinks. So it should be understood as "I don't like coffee and I don't like tea." You mean the same with the statement "Coffee and tea I don't like.". If \(c\) and \(t\) symbolise "I don't like coffee." and "I don't like tea.", respectively, then become "I don't like coffee and tea." and "Coffee and tea I don't like." are transcribed into \(\neg\,k\land\neg\,t\), but not converted by a more literal transcription into \(\neg(k\land t)\)n.
Sometimes you must use parentheses to indicate exactly what is meant. For example, \(\neg \varphi\land \psi\) by convention means to perform the negation of \(\varphi\) first and then the conjunction of this intermediate result with \(\psi\). The formula \(\neg(\varphi\land \psi)\) on the other hand, means first to perform the conjugation of \(\varphi\) and \(\psi\) and then the negation of this intermediate result.
If \(\varphi\) and \(\psi\) are logical formulas, then the following truth table is applicable: \[\begin{array}{cc|c} \varphi & \psi & \varphi\land \psi \\ \hline 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0\\ 1 & 1 & 1 \end{array}\]
The disjunction of two propositions is a proposition that is true exactly when at least one of the two original propositions is true. Only if both original propositions are false, then the disjunction is false. So also if both original propositions are true, their disjunction is true. This is called the inclusive disjunction.
Conjunction is symbolised by the infix operator \(\lor\), which stands for the connective "and/or" in natural language, but of which usually only the "or" is said.
If \(\varphi\) and \(\psi\) are formulas, then \(\varphi\lor \psi\) symbolises their disjunction.
Example
"You get coffee or tea." is true if you get at least one of the mentioned drinks. The statement is therefore also true if you get both drinks.
"You travel by train or underground." is true if you use at least one of the listed means of transport. The statement is therefore also true if you get both transport options. The statement is false if you do not use any of the mentioned means of transport. Even if you say "You travel by train or underground.", a more precise formulation is "You travel by train and/or by underground."
Consider the disjunction "You travel between Duivendrecht and Amsterdam-Bijlmer by train, bus or underground". Two things stand out in this sentence:
- You sometimes leave out a connective "or" in a list. You can think of this as using "or" with three arguments.
- If you know the situation better, it is clear that you can travel with one of the means of transport only; in between you can no longer change means of transport on the route.
In the second case, there is exclusive disjunction: one possibility excludes the other. In propositional notation, \(\oplus\) usually symbolises the exclusive disjunction. So the formula \(\phi \oplus \psi\) is true if exactly one of the partial formulas is true; the formula is false if both partial formulas are true. In natural language you can indicate the exclusion disjunction with "either ... or ...". In our example, you could have been more precise by saying "You travel between Duivendrecht and Amsterdam-Bijlmer either by train or by bus or by underground."
Strictly speaking, you don't need a new symbol for exclusive disjunction: check for yourself that \(\phi \oplus \psi\) and \((\phi \lor \psi) \land \neg(\phi \land \psi)\) are logically equivalent formulas.
Another example that implies an exclusive disjunction in natural language: "Henk uses all his money either to buy a car or to travel around the world". Henk cannot spend all his money on two separate things; it's one or the other.
If \(\varphi\) and \(\psi\) are logical formulas, then the following truth table is applicable for the inclusive disjunction \(\lor\) and the exclusive \(\oplus\) disjunction: \[\begin{array}{cc|cc} \varphi & \psi & \varphi\lor\psi &\varphi\oplus\psi\\ \hline 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1\\ 1 & 1 & 1 & 0 \end{array}\]
Negation, conjunction, and disjunction
