Reasoning in everyday life

Propositional Logic: Introduction

Reasoning in everyday life

Logic is widely used in daily life.

Restaurant example Suppose you are in a restaurant with a friend and he ordered fish and you ordered poultry. The waiter comes with two plates. What is happening?

The following scenario will not seem strange: The waiter asks who ordered fish and puts the plate in the right place at the table. Without further questioning, the waiter will also put the plate with poultry in the right place. The answer to the question was enough for the waiter to decide where the poultry plate should go. The argument scheme used by the waiter, with the special notation of \(f\) for "fish" and \(p\) for "poultry", can be written as: \[f\text{ or } p, \text{not }f\text{. So: }p\text.\] This notation of the inference, written even more formally in logic language as \(\bigl((f \lor p)\land \neg\, f\bigl)\rightarrow p\), not only describes the waiter's pattern of reasoning, but applies to many more situations because it does not matter much what the letters \(f\) and \(p\) symbolise. An example of a similar logical reasoning: a computer screen fails down if the connection cable is not working properly or the screen is broken. If the connection cable functions properly, then the screen must be broken.

But there is more going on in this restaurant example: the waiter asks a question in order to reach a conclusion based on the answer. The inference is a form of computing on information states. Initially there are two possible ways in which the two dishes can be divided between two people, indicated by ( \(fp\) and \(pf\) ). The answer to the waiter's question reduces this to only one possibility and the waiter knows what to do.

Sudoku Many people try to solve a sudoku puzzle every day. The easiest is a \(3\times 3\) sudoku. In this puzzle you have a block of three times three squares. Each square box should contain a number from 1 to 3. You must complete a given block in such a way that the digits 1 to 3 appear once in each row and each column. Logical reasoning leads to the unique solution.

How can such a puzzle be constructed? Logic helps with this too! Start with a correctly completed block. Now choose any box and delete the number in it. The remaining numbers still determine which number in the open box must necessarily be filled in; we say "that is logical!", but in fact filling in the missing number follows from logically valid reasoning. Now go on: choose a random square box, empty it and check whether the remaining numbers can lead to only one answer by logical reasoning. Repeat this until you cannot empty any more boxes. You have now found a minimal puzzle and since you obviously do not tell how you came up with this block, it has indeed become a logical puzzle for someone else.

An example of a sudoku Solve the following sudoku via logical reasoning: \[\begin{array} {|c|c|c|} \hline 1 & \phantom{4} & \\ \hline & & 3\\ \hline & & \\ \hline \end{array}\]
Possible solution

The box in the first row and third column cannot contain \(1\) or \(3\) because then the rules of the game are violated. So there must be a \(2\) there. We apply the following argument scheme: "\(A\text{ or } B \text{ or } C, \text{ not }A,\text{ not }B\text{: So } C\)." We now have \[\begin{array} {|c|c|c|} \hline 1 & \phantom{4} & 2\\ \hline & & 3\\ \hline & & \\ \hline \end{array}\]
The box in the second row and first column cannot contain \(1\) or \(3\) either, because then the rules of the game are violated. So there must be a \(2\) there. We again apply the " \(A\text{ or } B \text{ or } C,\text{ not }A,\text{ not }B\text{: So C}\) " reasoning scheme. We now have \[\begin{array} {|c|c|c|} \hline 1 & \phantom{4} & 2\\ \hline 2 & & 3\\ \hline & & \\ \hline \end{array}\]
With the rules of the game you can only fill in the remaining empty boxes in one way by completing a row or column each time. The final result is: \[\begin{array} {|c|c|c|} \hline 1 & 3 & 2\\ \hline 2 & 1 & 3\\ \hline 3 & 2 & 1\\ \hline \end{array}\]

The given puzzle is also minimal. Suppose you omit the \(3\). Then several answers are possible, for example also \[\begin{array} {|c|c|c|} \hline 1 & 2 & 3\\ \hline 2 & 3 & 1\\ \hline 3 & 1 & 2\\ \hline \end{array}\] The puzzle has in this case no unique solution and that spoils the fun.

Patterns in logical reasoning Inferences have a typical global form: there are one or more assumptions, usually called hypotheses and premises, followed by a conclusion. In the restaurant example, the text "Thus:" indicates that a conclusion is being drawn. A second example: \[\begin{array}{ll} \text{premise:} & \text{When your bicycle has been stolen, you raise your voice.}\\ \text{Premise:} & \text{You do not raise your voice.}\\ \text{Conclusion:} & \text{So: your bicycle has not been stolen.} \end{array}\] The pattern of reasoning is symbolised by \(\bigl((p\rightarrow q) \land \neg\, q\bigr)\vDash\neg\, p\), where "your bicycle has been stolen" and "you raise your voice" are replaced by the letters \(p\) and \(q\). The symbol \(\vDash\) indicates that the formula to the right of this follows logically from the formula to the left; \(\neg\,\) denotes a negation of a statement ("not" in a natural language); the symbols \(\lor\) and \(\land\) represent "or" and "and" in natural languages, respectively, and allow compound statements to be made. In this way the inference has been reduced to a clearer abstract form.

A variant of this example is: \[\begin{array}{ll} \text{Premise:} & \text{When your bicycle has been stolen, you aren't speaking at normal volume.}\\ \text{Premise:} & \text{You are speaking at normal volume.}\\ \text{Conclusion:} & \text{So: your bicycle has not been stolen.} \end{array}\] The reasoning scheme is now \(\bigl((p\rightarrow \neg\, q) \land q\bigr)\vDash \neg\, p\), where \(p\) and \(q\) are in this case letters that symbolise "your bicycle has been stolen" and "you are speaking at normal volume", respectively.

In the examples so far, we have been very precise about the nature of the assumptions and the conclusion: for each statement, it can be determined objectively whether it is true or false ; we exclude a third possibility (say perhaps true or false, partially true or unknown ). In the restaurant example, there has been an order, so it should be clear who gets the fish or poultry. In the last example, raising your voice is observable (at least if the observer knows you well) and you either do it or not. However, a natural language allows for statements that cannot easily be said to be true or false. It is not possible for a third party to objectively determine whether the statement "you are angry" is true or false; you may be feigning anger or, vice versa, you are angry, but do not express this in any way.

Proposition and Truth

We speak of a proposition when it is a statement or assertion, expressed in a meaningful sentence that conveys a fact, which can be objectively determined to be true or false .

Often, this implicitly refers to a context.

Examples and counterexamples

The door is open (a true proposition)
\(x+1=0\) (not a proposition: it depends on the value of \(x\) whether it is true or false)
\(a^2+b^2=c^2\) (not a proposition: truth depends on \(a\), \(b\) and \(c\), or on the context.
\(4\) is a prime number (a false proposition)
Is Jan a boy's name? (not a proposition because not a statement, but a question)

\(\phantom{x}\)

More counterexamples More counterexamples of statements that are not propositions:

Ann is a nice girl.
It just depends who you ask; it's an opinion. The statement "Jan thinks Anne is a nice girl" is a proposition"
This sentence is false.
Suppose this is a proposition. Then the statement must be true or false, but not both. Suppose "This sentence is false" is true, then the reading must also be false, but it cannot be both. So "This sentence is false" must be false. But when we read the sentence, it now says that if the sentence is false, then the statement is also true. This is also not possible. We conclude that it is not a proposition because we cannot assign a unique truth value to it. However, it is sometimes considered as a special proposition, namely a paradox.

true and false propositions

Examples of statements that are always true:

Amsterdam is the capital of Amsterdam.
Pascal is a programming language.

Examples of statements that are generally true:

Vermeer's painting The Girl with a Pearl Earring hangs in the Mauritshuis.
It does indeed belong to the collection of the Mauritshuis, but it is sometimes loaned out for an exhibition
one plus one equals two.
This is correct, but not anymore if you calculate modulo \(2\).

Example of a mathematical statement that is generally false:

An even number is a prime number.
This is false except for the number \(2\).

Examples of statements that are always false:

Water is an alcoholic drink.
The object has a temperature of \(-10\,{}^{\circ}\! K\).
In nature, \(0\,{}^{\circ}K\) is the absolute zero temperature; no object has a lower temperature.

Examples of statements that we don't know whether they are true or false:

The universe is finite
(Goldbach's conjecture, 1690-1764) Every even number greater than two is the sum of two primes.

Context

The statement "The square root of a negative number does not exist." is true if you work within the context of real numbers, but false if you allow complex numbers. The truth value of the statement therefore depends on the context in which it is placed.

The equality \(a^2+b^2=c^2\) is a true proposition in the geometric context of a right triangle with \(c\) the length of the hypotenuse, and \(a\) and \(b\) the lengths of the other sides of the triangle. This is nothing more and nothing less than the Pythagoras theorem.

Complexity The sample sentences give the impression that propositions are simple statements. But with negation \(\neg\,\), implication \(\rightarrow\) and compounds such as "and" ( \(\land\) ) and "or" ( \(\lor\) ) more complicated propositions can be made. Proposition logic deals with how complicated propositions can be simplified.

Validity of an argument Propositional logic is concerned, among other things, with checking whether an argument is logically valid (on short: valid), meaning that in every situation where all premises are assumed to be true, the conclusion must necessarily be assumed to be true as well. An alternative but equivalent definition is: an argument is correct if there are no counterexamples, i.e. situations in which all premises are true, but the conclusion is still false..

Please note: validity is about the logical correctness of the reasoning, not about the truth of the premises or the conclusion. Two examples: \[\begin{array}{ll} \text{Premise:} & \text{A human being is immortal.}\\ \text{Premise:} & \text{Madonna is a human being}\\ \text{Conclusion:} & \text{Madonna is immortal}\end{array}\] This argument is logically valid, but the first premise is false. \[\begin{array}{ll} \text{Premise:} & \text{The calculated exam result is 5.5 or more.}\\ \text{Premise:} & \text{If your calculated exam result is 5.5 or more, then you pass the course.}\\ \text{Conclusion:} & \text{You pass the course.}\end{array}\] If you have received a pass mark, you know that your calculated result is at least 5.5. If you do not have a calculated result greater than or equal to 5.5, then you basically do not know whether or not you have received a pass mark; there may be all sorts of reasons why the teacher gave a pass mark after all. If your calculated exam result is at least 5.5, but you still didn't get a pass mark, then you feel cheated and you start complaining.

In the case of a valid reasoning \(p\vDash q\), which holds in the situation described last, you can therefore only say the following:

\(p, p\rightarrow q\vDash q\): If \(p\) is true, then the conclusion \(q\) is also true.
\(\neg\,q, p\rightarrow q\vDash \neg\,p\): If the conclusion is false, then \(p\) is also false.

\(\phantom{x}\)

A logically valid inference with 2 premises Imagine the following valid inference: \(p\text { and }q\vDash r\). Of all 8 true/false combinations of the three statements \(p\), \(q\), \(r\), one is excluded, namely \((p,q,r)=(\textit{true}, \textit{true}, \textit{false})\). In this case you can only say with certainty:

If all the premises are true, then the conclusion is also true.
If the conclusion \(q\) is false, then at least one premise is false.

A logically invalid inference with 2 premises

Consider the following reasoning: \[\begin{array}{ll} \text{Premise:} & \text{If it rains, I do not bike.}\\ \text{Premise:} & \text{I do not bike.}\\ \text{Conclusion:} & \text{It rains.}\end{array}\] In this example, we immediately see that the reasoning is not logically valid. There could be many reasons other than rainfall why I don't bike. It is an example of an invalid inference of the form \(\bigr((p\rightarrow q)\land q\bigr)\vDash p\), where \(p\) and \(q\) symbolise the statements "it's raining" and "I' do not bike" respectively.

Another example of the same kind of logically invalid reasoning: \[\begin{array}{ll} \text{Premise:} & \text{If the dike has broken, then the land is flooded.}\\ \text{Premise:} & \text{The land is flooded.}\\ \text{Conclusion:} & \text{The dike has broken.}\end{array}\] The land might as well be flooded by heavy rainfall.

An example of an invalid inference of the form \(\bigl((p\rightarrow q)\land \neg\, p\bigr)\vDash \neg\, q\) : \[\begin{array}{ll} \text{Premise:} & \text{If it's raining, then I don't bike.}\\ \text{Premise:} & \text{It's not raining.}\\ \text{Conclusion:} & \text{I bike.}\end{array}\] Even if it is not raining, we cannot conclude from this that I am cycling. Maybe I travel by public transportation. In propositional notation it can be written as follows: \(\bigl((p\rightarrow q)\land \neg\, p\bigr)\nvDash \neg\, q\). The symbol \(\nvDash\) means that the formula on the right-hand side of this symbol is not a a valid logical consequence of the formula on the left-hand side.

Reasoning in natural language Finding precise wording to accurately convey a thought or reasoning is often far form simple. Moreover, everyone has their own sense of language, which can result in the speaker of a sentence interpreting it differently from the listener.

Suppose a father says to his child, "If you are good, you will get a candy." Does he mean "If you're not good, you won't get a candy"? How well-behaved does the child need to be in order to receive something? What if the child is just slightly misbehaving?

It becomes even more unclear when the father says to the child: "If you are good, you will get an ice cream or a soft drink." If the child is good, can the child have both an ice cream and a soft drink? Can the child choose between an ice cream or a soft drink? Can the child also get something if it is not well behaving, or is that out of the question?

We aim to avoid such ambiguities by extracting statements and forms of reasoning from natural languages and formalising them into symbolic or formal logic.

Finally, in logical reasoning, many believe that you keep adding statements the given premises until you can justify the conclusion. But just as important as application is the refutation of an argument. This involves demonstrating that a false statement follows from the reasoning and undermines the inference. A false conclusion does not mean that all premises are false, just that at least one of the premises is false. Determining which premise is false can still require a significant amount of work.

Exercise Suppose that each individual inference below, with lowercase letters representing propositions, is valid. \[\begin{array}{l} &a\land b\land c\rightarrow d\\ &a\rightarrow d\\ &e\rightarrow f\\ & a\rightarrow b\\ & e\land f\land b\rightarrow g\end{array}\] From a reliable source, you know that proposition \(a\) is true and proposition \(g\) is false. Which statement can you determine to be true or false?

Solution

It follows from \(a\rightarrow b\) that the proposition \(b\) is true. Suppose proposition \(c\) is true, then it follows from \(a\land b\land c\rightarrow d\) that proposition \(d\) is true. Then it follows from \(a\land d\rightarrow e\) that proposition \(e\) is true. But if \(e\) is true, then according to \(e\rightarrow f\) the conclusion\(f\) is also true. Since \(e\), \(f\) and \(b\) are true statements, it follows from \(e\land f\land b\rightarrow g\) that proposition \(g\) is true. But we already knew from a reliable source that \(g\) is false. This cannot be both. So: either the reliable source is not so reliable after all, or proposition \(c\) must be false. But then proposition \(d\) is false too and consequently proposition \(e\) is false. The sub-conclusion \(f\) is then true or false; that's all we know. For the rest we know that \(a\) and \(b\) are true propositions and that propositions \(d\), \(d\), \(e\), and \(g\) are false.