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:

  1. is greater than .
  2. There exists a number that is between and .
  3. 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:

  1. Close the door.
  2. 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:

  1. and
  2. if ( or ), then
  3. (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?

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:

  1. Exhaustively list all combinations of truth assignments
  2. 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:

Try creating the truth table for the formula:

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:

  1. Since , we have .
  2. Since and (from line 1), we have .
  3. Since (from line 2) and , we have .
  4. Since (from line 3), we have .
  5. Since and , we have .
  6. Since (from line 4) and (from line 5), we have , as desired.

Try it yourself!

  1. , with .
  2. , with
  3. , with

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.

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.

Compare the two statements, what is the difference?

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?

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?

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.

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 ?

Example 2.2: Another example: Parsing Nested Quantifiers

Let’s try one more, but a little more mathematical this time. Is this statement true?

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?

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?