Propositional Atoms

Definition

A propositional atom is statement that is either true or false, and that contains no logical connectives (like and, or, not, if/then).

Examples of propositional atoms

For example, the following are propositional atoms:

• My shirt is red.
• It is sunny.
• Pigs can fly.
• I studied for the test.

Examples of what are NOT propositional atoms

Propositional atoms should not contain any logical connectives. If they did, this would mean we could have further subdivided the statement into multiple propositional atoms that could be joined with logical operators. For example, the following are NOT propositional atoms:

• It is not summer. (contains a not)
• Bob has brown hair and brown eyes. (contains an and)
• I walk to school unless it rains. (contains the word unless, which has if…then information)

Propositional atoms also must be either true or false – they cannot be questions, commands, or sentence fragments. For example, the following are NOT propositional atoms:

• What time is it? (contains a question - not a true/false statement)
• Go to the front of the line. (contains a command - not a true/false statement)
• Fluffy cats (contains a sentence fragment - not a true/false statement)

Identifying propositional atoms

If we are given several sentences, we identify its propositional atoms by finding the key statements that can be either true or false. We further ensure that these statements do not contain any logical connectives (and, or, not, if/then information) - if they do, we break the statement down further. We then assign letters to each proposition.

For example, if we have the sentences:

My jacket is red and green. I only wear my jacket when it is snowing. It did not snow today.

Then we identify the following propositional atoms:

p: My jacket is red
q: My jacket is green
r: I wear my jacket
s: It is snowing
t: It snowed today

Notice that the first sentence, “My jacket is red and green”, contained the logical connective “and”. Thus, we broke that idea into its components, and got propositions p and q. The second sentence, “I only wear my jacket when it is snowing”, contained if/then information about when I would wear my jacket. We broke that sentence into two parts as well, and got propositions r and s. Finally, the last sentence, “It did not snow today”, contained the logical connective “not” – so we removed it and kept the remaining information for proposition t.

Each propositional atom is a true/false statement, just as is required.

In the next section, we will see how to complete our translation from English to propositional logic by connecting our propositional atoms with logical operators.

NOT, AND, OR Translations

Now that we have seen how to identify propositional atoms in English sentences, we will learn how to connect these propositions with logical operators in order to complete the process of translating from English to propositional logic.

NOT translations

When you see the word “not” and the prefixes “un-” and “ir-”, those should be replaced with a NOT operator.

Example 1

For example, if we have the sentence:

I am not going to work today.

Then we would first identify the propositional atom:

p: I am going to work today

and would then use a NOT operator to express the negation. Our full translation to propositional logic would be: ¬p

Example 2

As another example, suppose we have the sentence:

My sweater is irreplaceable.

We would identify the propositional atom:

p: My sweater is replaceable.

And again, our complete translation would be: ¬p

AND translations

When you see the words “and”, “but”, “however”, “moreover”, “nevertheless”, etc., then the English sentence is expressing a conjunction of ideas. When translating to propositional logic, all of these words should be replaced with a logical AND operator.

It might seem strange that the sentences “It is cold and it is sunny” and “It is cold but it is sunny” should be translated the same way – but really, both sentences are expressing two facts:

1. It is cold
2. It is sunny

Using “but” instead of “and” in English adds a subtle comparison of the first fact to the second fact, but such nuances are beyond the capabilities of propositional logic (and are somewhat ambiguous anyway).

Example 1

Suppose we want to translate the following sentence to propositional logic:

I like cake but I don't like cupcakes.

We would first identify two propositional atoms:

p: I like cake
q: I like cupcakes

We would then translate the clause “I don’t like cupcakes” to ¬q, and then would translate the connective “but” to a logical AND operator. We would finish with the following translation:

p ∧  ¬q

Example 2

Suppose we want to translate the following sentence to propositional logic:

The school doesn't have both a pool and a track.

We would first identify two propositional atoms:

p: The school has a pool
q: The school has a track

We would then see that we are really taking the sentence, “The school has a pool and a track” and negating it, which leaves us with the following translation:

 ¬(p ∧ q)

OR translations

When you see the word “or” in a sentence, or some other clear disjunction of statements, then you will translate it to a logical OR operator. Because the word “or” in English can be ambiguous, We first need to determine whether the “or” is inclusive (in which case we would replace it with a regular OR operator) or exclusive (in which case we need to add a clause to explicitly express that both statements cannot be true).

As we saw in section 1.1, the word “or” in an English sentence is usually meant to be exclusive. However, because the logical OR is INclusive, and since the purpose of this class is not to have you wrestle with subtleties of the English language, then you can assume that an “or” in a sentence is inclusive unless clearly stated otherwise.

Inclusive OR statements

Suppose we want to translate the following sentence to propositional logic:

You watch a movie and/or eat a snack.

We would first identify two propositional atoms:

p: You watch a movie
q: You eat a snack

The “and/or” in our sentence makes it extremely clear that the intent is an inclusive or, since the sentence is true if you both watch a movie and eat a snack. This leaves us with the following translation:

p V q

Exclusive OR statements

In this class, if the meaning of “or” in a sentence is meant to be exclusive, then the sentence will clearly state that the two statements aren’t both true.

For example, suppose we want to translate the following sentence to propositional logic:

On Saturday, Jane goes for a run or plays basketball, but not both.

We would first identify two propositional atoms:

p: Jane goes for a run on Saturday
q: Jane plays basketball on Saturday

We then apply our equivalence for simulating an exclusive or operator, which we saw in section 2.4. This leaves us with the following translation:

(p V q) ∧  ¬(p ∧ q)

Implies Translations

In this section, we will learn when to use an implies (→) operator when translating from English to propositional logic. In general, you will want to use an implies operator any time a sentence is making a promise – if one thing happens, then we promise that another thing will happen. The trick is to figure out the direction of the promise – promising that if p happens, then q will happen is subtly different from promising that if q happens, then p will happen.

Look for the words “if”, “only if”, “unless”, “except”, and “provided” as clues that the propositional logic translation will use an implies operator.

IF p THEN q statements

An “IF p THEN q” statement is promising that if p is true, then we can infer that q is also true. (It is making NO claims about what we can infer if we know q is true.)

For example, consider the following sentence:

If it is hot today, then I'll get ice cream.

We first identify the following propositional atoms:

p: It is hot today
q: I'll get ice cream

To determine the order of the implication, we think about what is being promised – if it is hot, then we can infer that ice cream will happen. But if we get ice cream, then we have no idea what the weather is like. It might be hot, but it might also be cold and I just decided to get ice cream anyway. Thus we finish with the following translation:

p → q

Alternatively, if we don’t get ice cream, we can be certain that it wasn’t hot – since we are promsied that if it is hot, then we will get ice cream. So an equivalent translation is:

 ¬q →  ¬p

(This form is called the contrapositive, which we learned about it in section 2.4). We’ll study it and other equivalent translations more in the next section.)

p IF q statements

A “p IF q” statement is promising that if q is true, then we can infer that p is also true. (It is making NO claims about what we can infer if we know p is true.) Equivalent ways of expressing the same promise are “p PROVIDED q” and “p WHEN q”.

For example, consider the following sentence:

You can login to a CS lab computer if you have a CS account.

We first identify the following propositional atoms:

p: You can login to a CS lab computer
q: You have a CS account

To determine the order of the implication, we think about what conditions need to be met in order for me to be promised that I can login. We see that if we have a CS account, then we are promised to be able to login. Thus we finish with the following translation:

q → p

In this example, if we knew we could login to a CS lab computer, we wouldn’t be certain that we had a CS account. There might be other reasons we can login – maybe you can use your eID account instead, for example.

Alternatively, if we can’t login, we can be certain that we don’t have a CS account. After all, we are guaranteed to be able to login if we do have a CS account. So another valid translation is:

 ¬p →  ¬q

p ONLY IF q

A “p ONLY IF q” statement is promising that the only time p happens is when q also happens. So if p does happen, it must be the case that q did too (since p can’t happen without q happening too).

For example, consider the following sentence:

Wilma eats cookies only if Evelyn makes them.

We first identify the following propositional atoms:

p: Wilma eats cookies
q: Evelyn makes cookies

What conditions need to be met for Wilma to eat cookies? If Wilma is eating cookies, Evelyn must have made cookies – after all, we know that Wilma only eats Evelyn’s cookies. Thus we finish with the following translation:

p → q

Equivalently, we are certain that if Evelyn DOESN’T make cookies, then Wilma won’t eat them – since she only eats Evelyn’s cookies. We can also write:

 ¬q →  ¬p

However, if we know that Evelyn makes cookies, we can’t be sure that Wilma will eat them. We know she won’t eat any other kind of cookie, but maybe Wilma is full today and won’t even eat Evelyn’s cookies…we can’t be sure.

p UNLESS b, p EXCEPT IF q

The statements “p UNLESS q” and “p EXCEPT IF q” are equivalent…and both can sometimes be ambiguous. For example, consider the following sentence:

I will bike to work unless it is raining.

We first identify the following propositional atoms:

p: I will bike to work
q: It is raining

Next, we consider what exactly is being promised:

• If it isn’t raining, will I bike to work?   YES ¬ I promise to bike to work whenever it isn’t raining.
• If I don’t bike to work, is it raining?   YES ¬ I always bike when it’s not raining, so if I don’t bike, it must be raining.
• If it’s raining, will I necessarily not bike to work?   Well, maybe? Some people might interpret the sentence as saying I’ll get to work in another way if it’s raining, and others might think no promise has been made if it is raining.
• If I bike to work, is it necessarily not raining?   Again, maybe? It’s not clear if I’m promising to only bike in non-rainy weather.

As we did with ambiguous OR statements, we will establish a rule in this class for intrepeting “unless” statements that will let us resolve ambiguity.

If you see the word unless when you are doing a translation, replace it with the words unless possibly if.

If we rephrase the sentence as:

I will bike to work *unless possibly if* it is raining.

We see that there is clearly NO promise about whether I will bike in the rain. I might, or I might not – but the only thing that I am promising is that I will bike if it is not raining, or that IF it’s not raining, THEN I will bike. With that in mind, we can complete our translation:

 ¬q → p

Equivalently, if we don’t bike, then we are certain that it must be raining – since we have promised to ride our bike every other time. We can also write:

 ¬p → q

Equivalent Translations

As we saw in section 2.4), two logical statements are said to be logically equivalent if and only if they have the same truth value for every truth assignment.

We can extend this idea to our propositional logic translations – two (English) statements are said to be equivalent iff they have the same underlying meaning, and iff their translations to propositional logic are logically equivalent.

Common equivalences, revisited

We previously identified the following common logical equivalences:

• Double negative: ¬ ¬ p and p
• Contrapositive: p → q and ¬ q → ¬ p
• Expressing an implies using an OR: p → q and ¬ p ∨ q
• One of DeMorgan’s laws: ¬ (p ∧ q) and ( ¬ p ∨ ¬ q)
• Another of DeMorgan’s laws: ¬ (p ∨ q) and ( ¬ p ∧ ¬ q)

Equivalence example 1

Suppose we have the following propositional atoms:

p: I get cold
q: It is summer

Consider the following three statements:

• I get cold except possibly if it is summer.
• If it’s not summer, then I get cold.
• I get cold or it is summer.

We translate each sentence to propositional logic:

• I get cold except possibly if it is summer.

  • p → ¬q
  • Meaning: I promise that if I get cold, then it must not be summer…because I am always cold when it’s not summer.

• If it’s not summer, then I get cold.

  • ¬q → p
  • Meaning: I promise that anytime it isn’t summer, then I will get cold.

• I get cold or it is summer.

  • p V q
  • Meaning: I’m either cold or it’s summer…because my being cold is true every time it isn’t summer.

As we can see, each of these statements is expressing the same idea.

Equivalence example 2

Suppose we have the following propositional atoms:

p: I eat chips
q: I eat fries

Consider the following two statements:

• I don’t eat both chips and fries.
• I don’t eat chips and/or I don’t eat fries.

We translate each sentence to propositional logic:

• I don’t eat both chips and fries.

  • ¬(p ∧ q)

• I don’t eat chips and/or I don’t eat fries.

  • ¬p V ¬q

These statements are clearly expressing the same idea – if it’s not the case that I eat both, then it’s also true that there is at least one of the foods that I don’t eat. This is an application of one of DeMorgan’s laws: that ¬ (p ∧ q) is equivalent to ( ¬ p ∨ ¬ q).

If we were to create truth tables for both ¬(p ∧ q) and ¬p V ¬q, we would see that they are logically equivalent (that the same truth assignments make each statement true).

Equivalence example 3

Using the same propositional atoms as example 2, we consider two more statements:

• I don’t eat chips or fries.
• I don’t eat chips and I don’t eat fries.

We translate each sentence to propositional logic:

• I don’t eat chips or fries.

  • ¬(p V q)

• I don’t eat chips and I don’t eat fries.

  • ¬p ∧ ¬q

These propositions are clearly expressing the same idea – I have two foods (chips and fries), and I don’t eat either one. This demonstrates another of DeMorgan’s laws: that ¬ (p ∨ q) is equivalent to ( ¬ p ∧ ¬ q). If we were to create truth tables for each proposition, we would see that they are logically equivalent as well.

Knights and Knaves, revisited

Recall the Knights and Knaves puzzles from section 1.2. In addition to solving these puzzle by hand, we can devise a strategy to first translate a Knights and Knaves puzzle to propositional logic, and then solve the puzzle using a truth table.

Identifying propositional atoms

To translate a Knights and Knaves puzzle to propositional logic, we first create a propositional atom for each person that represented whether that person was a knight. For example, if our puzzle included the people “Adam”, “Bob”, and “Carly”, then we might create propositional atoms a, b, and c:

a: Adam is a knight
b: Bob is a knight
c: Carly is a knight

Translating statements

Once we have our propositional atoms, we can translate each statement in the puzzle to propositional logic. For each one, we want to capture that the statement is true IF AND ONLY IF the person speaking is a knight. (That way, the statement would be false whenever the person was not a knight – i.e., when they were a knave.) We recall that we can express if and only if using a conjunction of implications. So if we want to write p if and only if q, then we can say (p → q) ∧ (q → p).

As an example, suppose we have the following statement:

Adam says: Bob is a knight and Carly is a knave.

Adam’s statement should be true if and only if he is a knight, so we can translate it as follows:

(a → (b ∧  ¬c)) ∧ ((b ∧  ¬c) → a)

Which reads as:

If I am a knight, then Bob is a knight and Carly is a knave. Also, if Bob is a knight and Carly is a knave, then I am a knight.

We repeat this process for each statement in the puzzle. Finally, since we solve a Knights and Knaves puzzle by finding a truth assignment (i.e., assignment of who is a knight and who is a knave) that works for ALL statements, then we finish by AND-ing together our translations for each speaker. When we fill in the truth table for our final combined proposition, then a valid solution to the puzzle is any truth assignment that makes the overall proposition true. If it was a well-made puzzle, then there should only be one such truth assignment.

Full example

Suppose we meet two people on the Island of Knights and Knaves – Ava and Bob.

Ava says, "Bob and I are not the same".
Bob says, "Of Ava and I, exactly one is a knight."

We first create a propositional atom for each person:

a: Ava is a knight
b: Bob is a knight

Then, we translate each statement:

• Bob and I are not the same
  • Translation: (a → (a ∧ ¬b V ¬a ∧ b)) ∧ ((a ∧ ¬b V ¬a ∧ b) → a)
  • Meaning: If Ava is a knight, then either Ava is a knight and Bob is a knave, or Ava is a knave and Bob is a knight (so they aren’t the same type). Also, if Ava and Bob aren’t the same type, then Ava must be a knight (because her statement would be true).
• Bob says, “Of Ava and I, exactly one is a knight.
  • Bob is really saying the same thing as Ava…if exactly one is a knight, then either Ava is a knight and Bob is a knave, or Ava is a knave and Bob is a knight.
  • Translation: (b → (a ∧ ¬b V ¬a ∧ b)) ∧ ((a ∧ ¬b V ¬a ∧ b) → b)

We combine our translations for Ava and Bob and end up with the following propositional logic statement:

(a → (a ∧ ¬b V ¬a ∧ b)) ∧ ((a ∧ ¬b V ¬a ∧ b) → a) ∧ (b → (a ∧ ¬b V ¬a ∧ b)) ∧ ((a ∧ ¬b V ¬a ∧ b) → b)`

We then complete the truth table for that proposition:

                                                                                  *
---------------------------------------------------------------------------------------------------------------
a b | (a →: (a ∧ ¬b V ¬a ∧ b)) ∧ ((a ∧ ¬b V ¬a ∧ b) →: a) ∧ (b →:(a ∧ ¬b V ¬a ∧ b)) ∧ ((a ∧ ¬b V ¬a ∧ b) →: b)
---------------------------------------------------------------------------------------------------------------
T T |    F     F F  F F  F     F     F F  F F  F    T     F    F    F  F F F  F     F     F  F F  F  F   T
T F |    T     T T  T F  F     T     T T  T F  F    T     T    T    T  T T F  F     F     T  T T  F  F   F
F T |    T     F F  T T  T     F     F F  T T  T    F     F    T    F  F T T  T     F     F  F T  T  T   T
F F |    T     F T  F T  F     T     F T  F T  F    T     T    T    F  T F T  F     T     F  T F  T  F   T
---------------------------------------------------------------------------------------------------------------
Contingent
T: [F F]
F: [T T] [T F] [F T]

And we see that there is only one truth assignment that satisfies the proposition – [F F], which corresponds to Ava being a knave and Bob being a knave.

Conclusion

As you can see, solving a Knights and Knaves problem by translating each statement to propositional logic is a tedious process. We ended up with a very involved final formula that made filling in the truth table somewhat arduous. Such problems are usually much simpler to solve by hand – but this process demonstrates that we can apply a systematic approach to solve Knights and Knaves problems with translations and truth tables.