Applying logic to solve puzzles
Now that we have the basics of logic, let’s see an example of how we can use it to describe real-world scenarios. Precisely describing a scenario in logic is referred to as modelling. Consider the following scenario:
If Eve is coming to the party then Christine and Darius are coming to the party. And, if Christine is coming to the party, then Anne is also coming to the party.
Hopefully, as you carefully read through the scenario, you will recognise some of the logical operators (conjunction, disjunction, negation and implication) that we introduced previously. The information that is represented in the text can be split up into simple propositions which can then be combined into a compound proposition.
Let us break up the scenario into simple propositions.
- Let (A) represent the proposition “Anne is coming to the party”
- Let (E) represent the proposition “Eve is coming to the party”
- Let (C) represent the proposition “Christine is coming to the party”
- Let (D) represent the proposition “Darius is coming to the party”
If proposition (A) is assigned the truth value true, then this indicates that Anne will be coming to the party. If proposition (A) is assigned the truth value false, then this indicates that Anne will not be coming to the party. The same is true for each of the other proposition (E), (C) and (D).
Step 1
Let us consider the first sentence of the example.
If Eve is coming to the party then Christine and Darius are coming to the party.
- This statement is a compound proposition which connects two simpler propositions using an implication operator, that is the statement has the structure “if ……., then ……..”.
- The antecedent, or condition, of the statement is “Eve is coming to the party” and the consequent of the statement is “Christine and Darius are coming to the party”. We can observe that the antecedent is in fact one of the propositions that we defined – it is the same as proposition (E).
- We can see that the consequent is itself a compound proposition as it is the conjunction of two other simpler statements, that is, the statement “Christine and Darius are coming to the party” is the conjunction of the propositions “Christine is coming to the party” and “Darius is coming to the party”. (Notice that there are some minor changes in the words of these sentences; this is just to make the sentences grammatically correct but does not change the meaning.)
- From this we can model the consequent as (Cland D). Recall from the previous item that this conjunction has the truth value of true when both Christine is coming to the party and Darius is coming to the party, and is false under all other combinations of them attending the party. This can be described in the truth table below.
|
(D) | (Cland D) |
|---|---|---|
| (F) | (F) | (F) |
| (F) | (T) | (F) |
| (T) | (F) | (F) |
| (T) | (T) | (T) |
Using brackets
Including this in the larger implication statement we can model this part of the scenario as (E rightarrow (C land D)). Notice here that we have introduced brackets into the compound proposition to ensure we know how to interpret the compound proposition. Brackets in logic have the same purpose as brackets do in algebra. They tell us which parts of the expression to work out first.
| (E) | (D) | (C) | (C land D) | (E rightarrow (C land D)) |
|---|---|---|---|---|
| (F) | (F) | (F) | (F) | (T) |
| (F) | (F) | (T) | (F) | (T) |
| (F) | (T) | (F) | (F) | (T) |
| (F) | (T) | (T) | (T) | (T) |
| (T) | (F) | (F) | (F) | (F) |
| (T) | (F) | (T) | (F) | (F) |
| (T) | (T) | (F) | (F) | (F) |
| (T) | (T) | (T) | (T) | (T) |
Step 2
We can now turn our attention the second sentence.
And, if Christine is coming to the party, then Anne is also coming to the party.
For the time being, let’s ignore the “And,” at the start of this sentence. We will return to it later, but let’s focus on modelling the following expression.
If Christine is coming to the party, then Anne is also coming to the party.
Again, the statement is a compound proposition which connects two simpler propositions using an implication operator. The antecedent, or condition, of the statement is “Christine is coming to the party” and the consequent of the statement is “Anne is coming to the party”.
We can observe that the antecedent is in fact one of the propositions that we defined – it is the same as proposition (C). We can also observe that the consequent is in fact one of the propositions that we defined – it is the same as proposition (A). The compound proposition can be represented as (C rightarrow A).
| (C) | (A) | (C rightarrow A) |
|---|---|---|
| (F) | (F) | (T) |
| (F) | (T) | (T) |
| (T) | (F) | (F) |
| (T) | (T) | (T) |
Step 3
Connecting these two sentences together results in the proposition ((E rightarrow (C land D)) land (C rightarrow A)). This is described in the table below.
| (E) | (D) | (C) | (A) | (C land D) | (E rightarrow (C land D)) | (C rightarrow A) | ((E rightarrow (C land D)) land (C rightarrow A)) |
|---|---|---|---|---|---|---|---|
| F | F | F | F | F | T | T | T |
| F | F | F | T | F | T | T | T |
| F | F | T | F | F | T | F | F |
| F | F | T | T | F | T | F | F |
| F | T | F | F | F | T | T | T |
| F | T | F | T | F | T | T | T |
| F | T | T | F | T | T | F | F |
| F | T | T | T | T | T | T | T |
| T | F | F | F | F | F | T | F |
| T | F | F | T | F | F | T | F |
| T | F | T | F | F | F | F | F |
| T | F | T | T | F | F | T | F |
| T | T | F | F | F | F | T | F |
| T | T | F | T | F | F | T | F |
| T | T | T | F | T | T | F | F |
| T | T | T | T | T | T | T | T |
How many people are coming to the party?
The final column of the table is true where the formula is satisfied. This can be interpreted as where all of the conditions are satisfied. Any row with a (T) in the final column is a feasible solution to who might attend the party. We can then ask ourselves questions such as:
- What is the maximum number of people that might attend the party?
- What is the minimum number of people that might attend the party?
- Is there ever a situation when 3 people will attend the party?
These are important questions if you are the party planner. To answer question (1) The maximum number of people that might attend the party is four. This is evidenced by the last row of the table where (E), (D), (C) and (A) are all set to true which indicates that they will be attending.
The minimum number of people that might attend the party is zero. This is evidenced by the first row of the table where (E), (D), (C) and (A) are all set to false which indicates that they will not be attending.
There is no way exactly 3 people will attend the party as no row with true in the final column has exactly three variables which have the value true.
An Introduction to Logic for Computer Science
An Introduction to Logic for Computer Science
Reach your personal and professional goals
Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.
Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.
