Propositional Logic: 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?)
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:
- Definition 1: proposition
- A statement which can be either true or false.
Example
“Your meal will include hashbrowns.”
- Definition 2: propositional variable
- A variable that can either be true or false, representing whether a certain proposition is true or not.
Example
HB
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
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 statements 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?”
- “Pass the salt, please.”
- “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
Here are all the WaterWorld propositions that we'll use.
Remember that
Every WaterWorld board has the same set of
propositions to describe it:
Connectives
Some statements in the above proof were simple,
e.g., the single proposition “
- 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
Exercise 1
What do you think the truth table for
“
Solution 1
Exercise 2
The above proof
also used subexpressions of the form “not
Solution 2
Exercise 3
What is the truth table for the expression
“(not
Solution 3
- Definition 4: connective
- 1. The syntactic operator combining one or more logical expressions into a larger expression.
Example
Two operators are
- 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
Example
“nand” (mnemonic: “not and”) takes in two Boolean values
a b 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.
| Connective | Pronunciation | Meaning | Alternative pronunciations / notations |
|---|---|---|---|
| |
not | |
not( |
| |
and | |
and( |
| |
or | |
or( |
| |
implies | |
if |
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
Exercise 4
Another connective is “exactly-one-of”,
which is more traditionally
called exclusive-or or xor
(since it excludes both
Solution 4
Exactly one is true if either (
The two halves of that formula also correspond to the two true rows of xor's truth table:
Note that the conventional
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?
- “Whether you are tired or lazy, caffeine is just the drug for you!”
- “Whether you win a dollar or lose a dollar, the difference in your net worth will be noticed.”
- “If you own a house or a car, then you have to pay property tax.”
- “Give me your lunch money, or you'll never see your precious hoppy taw again!”
Solution 5
- Inclusive.
- Exclusive.
- Inclusive.
- Exclusive (hopefully).
Comments, questions, feedback, criticisms?
Send feedback
- E-mail the authors of the module, Propositional Logic: propositions
Footer
More about this content: Metadata | Version History
This work is licensed by Ian Barland, John Greiner, Phokion Kolaitis, Moshe Vardi, and Matthias Felleisen under a Creative Commons Attribution License (CC-BY 1.0).
Last edited by John Greiner on Feb 6, 2008 8:59 pm US/Central.