# Connexions

You are here: Home » Content » Intro to Logic » propositions

• #### First-Order Logic

• ##### Reasoning with inference rules
• Exercises for First-Order Logic

### Lenses

What is a lens?

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

#### Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
• Rice Digital Scholarship

This collection is included in aLens by: Digital Scholarship at Rice University

Click the "Rice Digital Scholarship" link to see all content affiliated with them.

### Recently Viewed

This feature requires Javascript to be enabled.

Inside Collection (Course):

# propositions

Summary: (Blank Abstract)

Recall examples of where we'd like proofs:

• WaterWorld (Is a certain location guaranteed safe?)
• type checking (Does a program call functions in the proper way?)
• circuit verification (Does a circuit always work as advertised?)
After seeing the reasons why proofs are important, we ended with a call for first needing a precise language for writing down statements without the ambiguity of English.

## Aside:

Might a programming language be a good way to specify formal concepts without ambiguity? Programming languages are usually motivated by specifying how to do something (implementation), rather than formally specifying what is being done (interface). While there is a deep relation between these two, logic is more appropriate for specifying the “what”.

## A formal vocabulary

Imagine an offer where, for a mere \$6.99, you can get: EEEE, (FFFF or CFCF or OBOB or HBHB) or CCCC and PHPH and BRBR and GRGR or WBWB and PJPJ. Some fine print clarifies for us that BRBR includes TT (WhiWhi, WheWhe, RaRa, or HbHb), FTFT, HMHM (BbBb, BaBa, or CaCa), EMEM, BB with CrChCrCh, BBBB (GRGR from 6-11am). Unfortunately, it's not clear at all how the “and” and “or”s relate. Fundamentally, is “xx and yy or zz” meant to be interpreted as “(xx and yy) or zz”, or as “xx and (yy or zz)”? With some context, we might be able to divine what the author intended: the above offer is the direct translation from the menu of a local diner: 2 eggs, potatoes (french fries, cottage fries, O'Brien or hashed brown) or cottage cheese and peach half (grits before 11am) and choice of bread with gravy or whipped butter and premium jam. Bread choices include toast (white, wheat ,raisin or herb), hot flour tortillas, homemade muffin (blueberry, banana or carrot), English muffin, bagel with cream cheese, homemade buttermilk biscuits. Grits available from 6:00am to 11:00am. (In a brazen display of understatement, this meal was called “Eggs Alone”.) Even given context, this offer still isn't necessarily clear to everybody: can I get both french fries and a peach half? Happily, coffee is available before having to decipher the menu. In this example, parentheses would have clarified how we should interpret “and”, “or”. But before we discuss how to connect statements, we will consider the statements themselves.

Definition 1: proposition
A statement which can be either true or false.

### Example

Definition 2: propositional variable
A variable that can either be true or false, representing whether a certain proposition is true or not.

### Example

HBHB

We will often refer to “propositional variables” as just plain ol' “propositions”, since our purpose in studying logic is to abstract away from individual statements and encapsulate them in a single variable, thereon only studying how to work with the variable.

For a proposition or propositional variable XX, rather than write “XX is true”, it is more succinct to simply write “XX”. Likewise, “XX is false” is indicated as “¬XX”.

### Aside:

Compare this with Boolean variables in a programming language. Rather than (x == true) or (x == false), it's idiomatic to instead write x or !x.

Observe that not all English sentences are propositions, since they aren't true/false issues. Which of the following do you think might qualify as propositions? If not, how might you phrase similar statements that are propositions?

• “Crocodiles are smaller than Alligators.”
• “What time is it?”
• “Hopefully, the Rice Owls will win tomorrow's game.”
• “Mr. Burns is filthy rich.”
• “Fresca® is the bee's knees.”

### A particular vocabulary for WaterWorld

When playing WaterWorld, what particular propositions are involved? To consider this, we think of a generic board, and wonder what the underlying statements are. They are statements like “location AA contains a pirate” (“A-unsafeA-unsafe”), “location GG has 2 adjacent pirates” (“G-has-2G-has-2”) and so on. Each of these statements may be true or false, depending on the particular board in question.

Here are all the WaterWorld propositions that we'll use.

Remember that B-unsafeB-unsafe doesn't mean “I'm not sure whether or not BB is safe”; rather it means “BB is unsafe” — it contains a pirate. You may not be sure whether (the truth of) this proposition follows what you see, but in any given board the variable has one of two values, true or false.

Every WaterWorld board has the same set of propositions to describe it: A-unsafeA-unsafe, B-has-2B-has-2, etc. However, different boards will have different underlying values of those propositions.

### Connectives

Some statements in the above proof were simple, e.g., the single proposition “A-has-2A-has-2”. Some statements had several parts, though, e.g., “(F-unsafeF-unsafe and G-unsafeG-unsafe)”. We build these more complicated statements out of propositions. If you know both F-unsafeF-unsafe is false, and G-unsafeG-unsafe is false, what can you deduce about the truth of the statement “(F-unsafeF-unsafe and G-unsafeG-unsafe)”? Clearly, it is also false. What about when F-unsafeF-unsafe is false, but G-unsafeG-unsafe is true? What about when both propositions are true? In fact, we can fill in the following table:

Table 1: Truth table for ∧ (AND)
aabb(ab)(ab)
falsefalsefalse
falsetruefalse
truefalsefalse
truetruetrue
Definition 3: truth table
A truth table for an expression has a column for each of its propositional variables. It has a row for each different true/false combination of its propositional variables. It has one more column for the expression itself, showing the truth of the entire expression for that row.

#### Exercise 1

What do you think the truth table for “aa or bb” looks like? Hint: To fill out one row of the table, say, for a=truea and b=falseb , ask yourself “For this row, is it true that (aa is true, or bb is true)?”

##### Solution
Table 2: Truth table for ∨ (OR)
aabb(ab)(ab)
falsefalsefalse
falsetruetrue
truefalsetrue
truetruetrue

#### Exercise 2

The above proof also used subexpressions of the form “not bb-unsafe”. What is the truth table for “not aa”?

##### Solution
Table 3: Truth table for ¬ (NOT)
aa¬a¬a
falsetrue
truefalse

#### Exercise 3

What is the truth table for the expression “(not aa) or bb”?

##### Solution
Table 4: Truth table for ⇒ (IMPLIES)
aabb(ab)(ab)
falsefalsetrue
falsetruetrue
truefalsefalse
truetruetrue
Definition 4: connective
1. The syntactic operator combining one or more logical expressions into a larger expression.

#### Example

Two operators are and .

2. A function with one or more Boolean inputs and a Boolean result. I.e., the meaning of a syntactic operator.

#### Example

The meaning of and , e.g., as described by their truth tables.

#### Example

nand (mnemonic: “not and”), written , takes in two Boolean values aa and bb, and returns true exactly when aba b is not true — that is, ab¬(ab) a b a b .

The following are the connectives we will use most often. At least some of these should already be familiar from Boolean conditional expressions.

Table 5: Connectives
Connective Pronunciation Meaning Alternative pronunciations / notations
¬¬ not ¬aa: aa is false -aa; !aa
and ab aa ba and bb are both true aa*bb; abab; aa&&bb; aa&bb
or aba b: at least one of aba b is true aa+bb; aa||bb; aa|bb
implies aba b: equivalent to ¬abab aabb; aabb; if aa then bb; aa only if bb; bb if aa; bb is necessary for aa; aa is sufficient for bb

Many other connectives can also be defined. In fact, it turns out that any connective for propositional logic can be defined in terms of those above.

#### Example 1

Another connective is if-and-only-if or iff, written as ab a b , which is true when aa and bb have the same truth value. So, as its name implies, it can be defined as (ab)(ba) ab ba . It is also commonly known as “aa is equivalent to bb” and “aa is necessary and sufficient for bb”.

#### Exercise 4

Another connective is “exactly-one-of”, which is more traditionally called exclusive-or or xor (since it excludes both aa and bb holding, unlike the traditional “inclusive” or.) How would you define aa “xor” bb in terms of the above connectives?

##### Solution

Exactly one is true if either (aa is true, and bb is false) or (aa is false, and bb is true). So, one way to define it is aba¬b¬ab a b a b a b .

The two halves of that formula also correspond to the two true rows of xor's truth table:

Table 6: Truth table for xor
aabb(ab)(ab)
falsefalsefalse
falsetruetrue
truefalsetrue
truetruefalse

Note that the conventional abab is sometimes called inclusive-or, to stress that it includes the case where both aa and bb hold.

In English, the word “or” may sometimes mean inclusive-or, and other times mean exclusive-or, depending on context. Sometimes the term “and/or” is used to emphasize that the inclusive-or really is intended.

#### Exercise 5

For each of the following English sentences, does “or” mean inclusive-or or exclusive-or?

1. “Whether you are tired or lazy, caffeine is just the drug for you!”
2. “Whether you win a dollar or lose a dollar, the difference in your net worth will be noticed.”
3. “If you own a house or a car, then you have to pay property tax.”
4. “Give me your lunch money, or you'll never see your precious hoppy taw again!”
##### Solution
1. Inclusive.
2. Exclusive.
3. Inclusive.
4. Exclusive (hopefully).

## Content actions

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

PDF | EPUB (?)

### What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

#### Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

#### Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

#### Definition of a lens

##### Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

##### What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

##### Who can create a lens?

Any individual member, a community, or a respected organization.

##### What are tags?

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks