Overview:
In this page, we will provide more examples for each notable topic. There will also be a few examples for you to try out yourself, with solutions provided in case you wish to verify them yourself.
Do post on Canvas if something is unclear or you wish for more explanations.
Propositional Logic
Example: Propositions
Here are some more examples of propositions:
- is greater than .
- There exists a number that is between and .
- is equal to .
Recall that propositions are statements that are either true or false. For example, examples 1 and 2 are true. But example 3 is false.
Here are some non-examples of propositions:
- Close the door.
- I hope it rains today.
These statements don’t have a clear “must be either true or false” property to them.
Example: Logical Connectives
Here are some more examples on how to use logical connectives to connect propositions:
- and
- if ( or ), then
- (not ) or ()
In example 1, , and are propositions.
And and is used to connect the two propositions.
Try it yourself! What about the other 2 lines? What are the propositions? What are the connectives?
Answer
In example 2, the propositions are: , , . The connectives used are: or, if/then.
In example 3, the propositions are: , . The connectives used are: or, not.
Example: Truth tables
Truth tables are a handy way to help us determine if two formulae are logically equivalent. To construct a truth table, we need to:
- Exhaustively list all combinations of truth assignments
- Evaluate the intermediate propositions until the final formula has been attained
For instance, let’s draw the truth table for the formula .
Step 1: List out all 8 combinations of , and .
Step 2: Evaluate the intermediate propositions. In this case, we need the intermediate steps , then , and finally, .
We construct the column by taking all the corresponding values of and negating them.
(goal) | |||||
---|---|---|---|---|---|
Then, we construct the column by taking the corresponding values of and and performing an implication.
(goal) | |||||
---|---|---|---|---|---|
Lastly, we construct the column by taking the corresponding values of and and performing another implication.
(goal) | |||||
---|---|---|---|---|---|
And there we have our desired column!
Try it yourself! Try creating the truth table for the formula:
Answer
Try creating the truth table for the formula:
Answer
Example 2: Evaluating Formulae
Given a propositional formula such as , and given the truth values of the starting propositions, we can evaluate the truth value of the original formula. This is done by evaluating the “inner” formulae, then gradually working outwards to reach the final statement.
Suppose we had the following truth assignments for the propositions , and :
Then, we can begin evaluating by looking at the innermost formulae and working outwards:
- Since , we have .
- Since and (from line 1), we have .
- Since (from line 2) and , we have .
- Since (from line 3), we have .
- Since and , we have .
- Since (from line 4) and (from line 5), we have , as desired.
Try it yourself!
- , with .
- , with
- , with
Answers
For the first one, when , then is , and is . is . There is a slightly faster way to evaluate it. Notice that since is , and we are about to use , we don’t actually care what’s on the other side: since , and . In both cases, it is .
For the second one, when , then is , and the entire formula is . Again there is a slightly faster way to evaluate it. We already know that is and used with anything is also .
For the third and last one, is . On the other hand is also . Since both sides of the are , the entire formula is .
First-Order Logic
Example 1: Parsing Single Quantifiers
When we encounter a universal quantifier, say , we might decode it as “No matter which I choose from set “. Correspondingly, when we encounter an existential quantifier, say , we might decode it as “I can find a single in set “.
For example, let’s say we’re at a company dinner, and what to say every person is attending. We want to have a set that contains every person in the company. Something like:
(I guess this company only has people.)
Let’s also make a predicate that represents the fact that a person is attending: .
Then for example if:
is , then we know is attending the dinner.
On the other hand, if
is , we know is not attending.
So to say:
“Every person in the company is attending”
We would write:
If we wanted to say:
“Someone in the company is attending”
We would write:
If we wanted to say:
“No one is attending the company dinner”.
We could write:
There actually is a different way:
You could also think of this as saying “There is not a single person that is attending.”
Okay, let’s add one more predicate. means person is free. What happens if says “if I am free, I will attend the dinner?” We can write:
Try it yourself! Based on the above example, what if we wanted to say:
Anyone who is free at the company will attend the dinner.
Write your answer as a statement in first-order logic.
Answer
What if we wanted to say:
If everyone is free, then everyone will attend the dinner.
Write your answer as a statement in first-order logic.
Answer
Compare the two statements, what is the difference?
Answer
For example, in the first statement, it could be the case that and are free, but and are not. This means and will attend.
But in the second statement, since and are not free. We don’t know if everyone will attend the dinner or not. It could be possible that no one goes. (It could actually still be possible that some people go. Why is that? Hint: How does the logical connective work?)
What if we wanted to say:
All natural numbers are greater than .
Recall that the set of natural numbers is . The statement is clearly false, but how should we write it in first-order logic?
Answer
What about:
All integers are greater than or equal to when squared.
Recall that the set of natural numbers is . How should we write it in first-order logic?
Answer
Example 2.1: Parsing Nested Quantifiers
Nested quantifiers can be difficult to understand at first glance because of the different quantifiers regarding each variable, and the relationships between the variables. Let’s look at a few more examples:
Let’s re-visit the same English sentence we had in the notes:
Statement 1: “There exists a planet that every person lives on.”
Also compare it with the following statement:
Statement 2: “Every person is such that, there exists a planet that person lives on.”
Again, let’s make two sets, (is the set of people), and (is the set of planets). And another predicate like . This time, the predicate takes two values as input, and it means ” lives on “.
So for example if is true, it would mean lives on .
It also actually means if we said is true, then we would be saying lives on , as non-sensical as that sounds.
Try it yourself! Try to write statement 1, and statement 2 using the sets, and the predicate provided.
Answer
Statement 1:
Statement 2:
What is the difference between the two statements? Are they the same? Can we think of a (potentially fictitious) scenario where statement 1 is . but statement 2 is ?
Answer
Let’s say is a person (i.e. ). And is (in other words, actually lives on . On the other hand, every other person who is not lives on .
Then can we say there is a planet that every person lives on? No. Because we will need to fix a single planet. For that one planet, every person has to live on it. So Statement 1 is false.
On the other hand, statement is true, because everyone lives on a planet. In our example, it’s either or .
Example 2.2: Another example: Parsing Nested Quantifiers
Let’s try one more, but a little more mathematical this time. Is this statement true?
Solution Part 1
Translation: “I can find (fixed) integers and , such that no matter which rational number I choose, the following claim applies: ‘If is between and , then will still be between and ’.” (For convenience’s sake, let’s call this secondary statement Claim 0.)
Discussion: Fortunately/Unfortunately, many of the quantified statements that you will come across in computer science or mathematics involve significant nesting of quantifiers, such as this one. Let’s analyse this statement step by step.
Our task is to find the two integers and , not the rational number(s) ! For a start, let’s pick and to get a feel of what the statement is trying to say. Now, we pick any rational number , say , and try to evaluate the statement in square brackets: if , we find that it does not even fulfil the antecedent ! Therefore, the implication is true by default, but it’s a rather meaningless test.
Instead, let’s pick a rational number such that the antecedent is true, say . Then, , and here we run into a problem: now, the consequent is false! Hence, we have found an where Claim 0 (see above) is false, and so the and that we chose earlier (namely and ) are not the correct and .
Hopefully, after the “trial” above, you would’ve had a taste of what the statement is trying to say. Keep playing around with the values and to see if you can find the correct ones that prove the original statement is true. See Solution 4.2 below for the answers.
Solution Part 2
Choosing and will make the original statement true. By basic algebra, for any rational number , if , then as well.
Remember, since it’s , we only need to find one value for , one value for .
Example 3: Negating Quantifiers
Here’s another example, let’s go back to the dinner. Let’s say there are 4 people at the dinner. And let’s think about the following statement:
There is a dish that everyone likes
If we used the sets , , and the predicate to mean ” likes “. And also let’s say one of the dishes was .
We can write “Every person likes ” as:
What if we wrote:
This means
It is not true that everyone likes .
Why was that? It’s because at least one person does not like .
That means we can also write it as:
Similarly, if we instead want to say “no one likes ” instead, there are two possible ways:
The first statement is basically saying “Everyone does not like “. The second statement is saying “It is not the case that there exists a person that likes .” Like we mentioned in the notes, to move a symbol through a quantifier, we simply flip what the quantifier is.
Try it yourself! What is the negation of the following?
Answer
The negation of the statement is
which is also:
What if we wanted to say, “There exists a dish that everyone does not like”?
What if we wanted to say the negation of that statement? What does the negation mean?
Answer
The first statement is written as
To negate it, we can do the following:
Which we can simplify to:
which is also just:
The negation of the first statement means “Every dish is liked by at least one person.”