Propositional Logic
Contents
1.1. Propositional Logic#
Propositional Logic is the logical system built around propositions. From such propositions one can build logical arguments and implications.
In this section we will explore the language of propositions, their applications, and deriving logical equivalences.
1.1.1. The Language of Propositions#
Propositions are all about truth. Is a statement true or false? Is a statement correct or incorrect?
Propositions#
Definition (Proposition)
A proposition is a declarative sentence or statement has a truth value. It is a statement which is either true or false. Each proposition has a “truth value”: either true or false.
To get acquainted with propositions, let us see some examples and counterexamples.
Examples of propositions
Socrates was a human.
Socrates was a pigeon.
It is raining today.
The logo of Starbucks is a green mermaid.
\(1 + 1 = 2\)
\(1 + 1 = 4\)
Notice that propositions need not be a true statement. Propositions only need to be declarative. Their truth value may be true or false. However, all propositions must have a particular truth value. The statement cannot be both true and false. The statement must be able to be interpreted as true or false.
From the previous definition and examples, propositions are therefore not questions, general statements, demands, or hypotheses. Propositions do not have any variables, quantifiers, or parameters (e.g. the words “some” or “any” typically do not appear). Consider now a few non-examples.
Examples of statements that are not propositions
Do you have a dog?
Let’s go!
Some coffee mug with a mermaid on it.
\(x + 2 = 3\)
\(y = x^2 - 1\)
Are each of these propositions?
I am a dolphin.
Supercalifragilisticexpialidocious.
Jupiter is the 5th planet from the sun.
On Thursdays, van Gogh painted landscapes.
\(\frac{11+56*3-8}{19} = 9\)
Are each of these propositions?
Yes. This is a statement which is false. The author and the reader are both humans, right?
No. A single adjective on its own can not be true or false.
Yes. This is a statement which is true.
Yes. While I do not personally know the truth value of this statement, it certainly has one.
Yes. A formula with no variables precisely stating an equality. The equality is true.
Constructing Propositions#
An entire proposition is often denoted by a single propositional variable. Propositional variables are typically among \(p, q, r, s, t, \ldots\).
Using propositional variables
\(p := \) “The sky is blue”
\(q := \) “The sun rises from the west”
We also denote truth values in particular ways. “True” may be denoted by \(T\). “False” may be denoted by \(F\). When a proposition (or proposition variable) is known to always be true, we can replace it by \(T\). When a proposition (or proposition variable) is known to always be false, we can replace it by \(F\).
Connectives#
We can combine propositions (and propositional variables) into compound propositions or propositional formulas. This is akin to compound sentences and other logical connectives in natural language.
In propositional logic, we have 5 main connectives. Each connective has a corresponding meaning in natural language as we will soon see.
Negation: \(\neg\)
Conjunction: \(\land\)
Disjunction: \(\lor\)
Implication: \(\rightarrow\)
Biconditional: \(\leftrightarrow\)
Logical connectives are like arithmetic operators (\(+, -, \times, \div\)).
Negation#
The negation of a proposition results in a proposition with the opposite truth value. It is akin to adding “not” into a sentence, or starting a sentence with “it is not that case that…”.
Given a proposition \(p\) its negation is \(\neg p\) and has the following truth values.
\(p\) |
\(\neg p\) |
|---|---|
F |
T |
T |
F |
Negation
Let \(p := \) “the sky is blue”.
\(\neg p\) is “the sky is not blue” or “it is not the case that the sky is blue”.
Let \(q := \) “\(2 + 2 = 5\)”.
\(\neg q\) is “\(2 + 2 \neq 5\).
Notice in these examples that negation does not necessarily make a proposition false. Rather, it makes the proposition have the opposite truth value.
Conjunction#
The conjunction of two propositions is the logical “and” of the two propositions. The conjunction of two proposition is only true if both the propositions are individually true, otherwise the conjunction is false.
Given proposition \(p\) and \(q\) their conjunction is denoted \(p \land q\) and has the following truth values.
\(p\) |
\(q\) |
\(p \land q\) |
|---|---|---|
F |
F |
F |
F |
T |
F |
T |
F |
F |
T |
T |
T |
Conjunction
Let \(p\) be “birds lay eggs” and \(q\) be “my eyes are blue”. \(p \land q\) is then “birds lay eggs and my eyes are blue”.
Disjunction#
The disjunction of two propositions is the “or” of the two propositions. The disjunction is true if at least one of the propositions is individually true, otherwise the disjunction is false.
Given proposition \(p\) and \(q\) their disjunction is denoted \(p \lor q\) and has the following truth values.
\(p\) |
\(q\) |
\(p \lor q\) |
|---|---|---|
F |
F |
F |
F |
T |
T |
T |
F |
T |
T |
T |
T |
Disjunction
Let \(p\) be “it is raining” and \(q\) be “I am wearing sunglasses”. \(p \lor q\) is then “it is raining or I am wearing sunglasses”.
Notice that in this previous example, it is may be true that it is both raining and that I am wearing sunglasses. While that may be silly, \(p \lor q\) is still true! In logic, we only require that at least one of the propositions in a disjunction is true. That means both are allowed to simultaneously be true.
Caution
In natural language, “or” is often interpreted as an exclusive or.
Language “or”
“You can have a cookie or a piece of cake.” Most people assume that this means you can have a cookie or a piece of cake, but not both.
In logic, “or” is not exclusive. You can have a cookie, a piece of cake, or both!
If you want logical exclusive or, we use the symbol \(\oplus\). However, we will not use that in this course.
What is the truth value of these compound propositions?
“The earth is round and the sky is blue.”
“Dogs or cats make great pets.”
“It is \(20^{\circ}\) Celsius outside and it is snowing.”
“Lemons are purple or grass is green”
What is the truth value of these compound propositions?
True. Both propositions are individually true.
True. You may not like dogs, or you may not like cats, but at least one of dogs or cats make a great pet.
False. Both “it is \(20^{\circ}\) Celsius outside” and “it is snowing” cannot simultaneously be true. Therefore, their conjunction is false.
True. Lemons may not be purple, but (healthy) grass is green.
Implication#
Implication is one of the most challenging connectives to understand. Yet it is arguably the most important for creating logical arguments (see Logical Equivalences).
An implication is a conditional statement. For two propositions \(p\) and \(q\), \(p \rightarrow q\) is an implication which is read “if \(p\), then \(q\)”. You can also say “\(p\) implies \(q\)”.
Implication
Let \(p\) be “it is raining” and \(q\) be “the ground is wet”. \(p \rightarrow q\) can be read “if it is raining, then the ground is wet”.
In an implication \(p \rightarrow q\), the first proposition \(p\) is known as the hypothesis, antecedent, or premise. The second proposition \(q\) is known as the conclusion or consequence.
Because an implication is a conditional, the truth value of the implication as a whole changes depending on the truth value of the premise. The following truth table summarizes the truth values of an implication.
\(p\) |
\(q\) |
\(p \rightarrow q\) |
|---|---|---|
F |
F |
T |
F |
T |
T |
T |
F |
F |
T |
T |
T |
An implication can be viewed as an obligation, a contract, or a commitment. The implication \(p \rightarrow q\) is false (the contract is broken; the obligation is unmet) only when \(p\) is true and \(q\) is false.
There are several important observations from this truth table about logical implication.
If \(q\) is true, then \(p \rightarrow q\) is always true.
If \(p\) is true and the implication correct (the obligation is upheld), then \(q\) can never be false.
“Falsity can imply anything.” If the hypothesis is false, then the implication is always true, regardless of the whether or not the conclusion is true.
Some of these observations may seem counter-intuitive at first. Let us clarify with some examples.
The truth value of implications
Let \(p\) be “that animal is a panda bear” and \(q\) be “that animal is black and white”. \(p \rightarrow q\) can be read as “if that animal is a panda bear, then that animal is black and white”.
If \(p\) is true, and that animal is indeed a panda bear (and the implication is correct),
then it is also black and white.
If \(q\) is true, and the animal is black and white, it might be a panda bear, but it might also be a cow.
From \(p \rightarrow q\), we can say that knowing the animal is a panda bear is sufficient to know that the animal is black and white.
Valid implications can be formed from completely unrelated propositions. Moreover, if you begin with a nonsensical hypothesis, then one can construct valid (but equally nonsensical) implications. Falsity implies anything.
Absurd but valid implications
“If pigs can fly, then I am the pope.”
“If \(2+2=5\), then lemons are purple.”
“If the sun is made of ice, then my father is Morgan Freeman”.
There are many equivalent ways to think about the implication \(p \rightarrow q\).
If \(p\), then \(q\)
\(p\) implies \(q\)
\(q\) when \(p\)
\(q\), if \(p\)
\(q\) whenever \(p\)
\(q\) follows from \(p\)
\(p\) is sufficient for \(q\)
\(q\) is necessary for \(p\)
Necessity and Sufficiency
An implication connects propositions by a necessary or sufficient condition. From \(p \rightarrow q\) we get two relations:
\(p\) is sufficient for \(q\)
\(q\) is necessary for \(p\)
That is, “if sufficient condition, then necessary condition”.
Necessary and Sufficient
“If all birds have feathers, then a chicken is a type of bird.”
Knowing birds have feathers is sufficient information to conclude that a chicken is a type of bird. If a chicken is a type of bird, then chickens necessarily have feathers.
Fig. 1.1 Being in the inner circle is sufficient for being in the outer circle. Being in the outer circle is necessary for being in the inner circle.#
Biconditional#
For two propositions \(p\) and \(q\), they can be connected by a biconditional as \(p \leftrightarrow q\).
A biconditional is an double implication. A biconditional is true if both propositions have the same truth value. \(p \leftrightarrow q\) can be read as “\(p\) if and only if \(q\)”. A biconditional has the following truth table.
\(p\) |
\(q\) |
\(p \leftrightarrow q\) |
|---|---|---|
F |
F |
T |
F |
T |
F |
T |
F |
F |
T |
T |
T |
The biconditional \(p \leftrightarrow q\) can be expressed in many ways:
“\(p\) if and only if \(q\)”
“if \(p\) then \(q\), and if \(q\) then \(p\)”
“\(p\) is necessary and sufficient for \(q\)”
“\(p\) iff \(q\)”
Biconditional
Let \(p\) be “\(2\) is an even number”. Let \(q\) be “\(4\) is an even number”. \(p \leftrightarrow q\) is a biconditional and its truth value is true, since both \(p\) and \(q\) are true.
Tip (thinking in memes)
“The venn diagram is a circle” exactly means that the two subjects form a biconditional.
What is the truth value of these compound propositions?
“The Earth is flat” \(\rightarrow\) “Pigeons are robots”
“Bats have wings” \(\rightarrow\) “Bats are birds”
“A square is a rectangle” \(\leftrightarrow\) “A square had four \(90^{\circ}\) interior angles”
“Spinach is green” \(\leftrightarrow\) “Penguins can fly”
What is the truth value of these compound propositions?
True. “The Earth is flat” is false, and false implies anything!
False. An implication is false if the hypothesis is true meanwhile the conclusion is false. Bats have wings but are not birds. Therefore, the implication is false.
True. Both sides of the biconditional are true.
False. The left-hand side is true meanwhile the right-hand side is false.
Propositional Formulas#
In the previous section we saw 5 different logical connectives: \(\neg\), \(\land\), \(\lor\), \(\rightarrow\), and \(\leftrightarrow\). Much like arithmetic formulas using addition, multiplication, division, etc., propositional formulas may use several connectives simultaneously.
Remember BEDMAS or PEDMAS? Now we have “PaNCo DIB” (“Panko Dib”)?
For logical connectives we have a similar order of precedence.
Parenthesis: always perform operations on expressions inside parentheses first.
Negation: apply negation to a proposition before binary connectives.
Conjunction: conjunction before disjunction
Disjunction: disjunction after conjunction, but before implication
Implication: \(\rightarrow\) after \(\land\), \(\lor\)
Biconditional: \(\leftrightarrow\) after \(\land, \lor, \rightarrow\).
Logical order of precendence
\(p \lor q \rightarrow \neg r\ \ \) is the same as \(\ \ (p \lor q) \rightarrow (\neg r)\)
\(p \lor \neg q \land r\ \ \) is the same as \(\ \ p \lor ( \ (\neg q)\ \land r)\)
Propositional variables need not be associated with a particular proposition or truth value. A propositional variable could be just that: a variable. Replacing the variables in a propositional formula with a truth value is called a truth assignment.
Definition (truth assignment)
A truth assignment is the assignment of a truth value (true or false) to a propositional variable. Equally, it is the replacement of a propositional variable with a truth value.
Much like logical connectives, propositional formulas will result in different truth values depending on the particular truth assignment on its consituent propositional variables. When at least one truth assignment exists so that a formula is true, that formula is said to be satisfiable.
Definition (satisfiable)
A propositional formula is satisfiable if its truth value can be true under some truth assignment. If every possible truth assignment makes the formula have false as its truth value, that formula is said to be unsatisfiable.
In order to determine the truth value of a propositional formula, and to determine if it is satisfiable, we can create a truth table.
Truth Tables#
Truth tables are tools for determining the truth values of propositional formulas.
The table is separated into two sets of columns:
The first set of columns represent each proposition (or propositional variable) in a formula.
The second set of columns represents the sub-formulas and formulas whose truth values are to be determined.
There must be one row in the table for every possible combination of truth values of the propositional variables. For example, in a formula with two variables, the possible combinations are: \((T,T), (T,F), (F,T), (F,F)\).
3-variable truth table
Let \(p, q, r\) be propositional variables. A truth table for the formula \((p \land q) \lor r\) is:
\(p\) |
\(q\) |
\(r\) |
\(p \land q\) |
\((p \land q) \lor r\) |
|---|---|---|---|---|
F |
F |
F |
F |
F |
F |
F |
T |
F |
T |
F |
T |
F |
F |
F |
F |
T |
T |
F |
T |
T |
F |
F |
F |
F |
T |
F |
T |
F |
T |
T |
T |
F |
T |
T |
T |
T |
T |
T |
T |
Notice that every possible combination of truth values for \(p\), \(q\), and \(r\) is contained in this table. Since at least one choice of truth value for \(p\), \(q\), and \(r\) results in the formula being true, then this formula is satisfiable.
In a truth table, you begin by filling out the columns corresponding to each propositional variable. These columns represent every possible combination of truth values on those variables. Then, you add columns for each sub-formula, one at a time, building up to the final formula.
Consider the formula \(p \land q \land r \ \lor\ \neg q \land r \rightarrow p\). By order of precendence, this is equal to \((\ (p \land q \land r) \ \lor\ ((\neg q) \land r)\ ) \rightarrow p\) This contains several sub-formulas which we can parse:
\(\neg q\)
\(\neg q \land r\)
\(p \land q\)
\((p \land q) \land r\)
\((p \land q \land r) \lor (\neg q \land r)\)
\((\ (p \land q \land r) \lor (\neg q \land r)\ ) \rightarrow p\)
To be as explicit as possible, we could create a truth table with 3 + 6 = 9 columns (3 variables, 6 sub-formulas). But this is excessive. For example, we could directly compute \((\neg q \land r)\) and \((p \land q \land r)\). This gives the following truth table.
A large truth table
A truth table for the propositional formula \(p \land q \land r \ \lor\ \neg q \land r \rightarrow p\).
\(p\) |
\(q\) |
\(r\) |
\(p \land q \land r\) |
\(\neg q \land r\) |
\((p \land q \land r) \lor (\neg q \land r)\) |
\((p \land q \land r) \lor (\neg q \land r) \rightarrow p\) |
|---|---|---|---|---|---|---|
F |
F |
F |
F |
F |
F |
T |
F |
F |
T |
F |
T |
T |
F |
F |
T |
F |
F |
F |
F |
T |
F |
T |
T |
F |
F |
F |
T |
T |
F |
F |
F |
F |
F |
T |
T |
F |
T |
F |
T |
T |
T |
T |
T |
F |
F |
F |
F |
T |
T |
T |
T |
T |
F |
T |
T |
Construct a truth table
Give a truth table for the propositional formula \(p \land r \rightarrow q \lor \neg r\)
Construct a truth table
\(p \land r \rightarrow q \lor \neg r\ \ \ \) is equal to \(\ \ \ (p \land r) \rightarrow (q \lor (\neg r)\ )\)
\(p\) |
\(q\) |
\(r\) |
\(p \land r\) |
\(q \lor \neg r\) |
\(p \land r \rightarrow q \lor \neg r\) |
|---|---|---|---|---|---|
F |
F |
F |
F |
T |
T |
F |
F |
T |
F |
F |
T |
F |
T |
F |
F |
T |
T |
F |
T |
T |
F |
T |
T |
T |
F |
F |
F |
T |
T |
T |
F |
T |
T |
F |
F |
T |
T |
F |
F |
T |
T |
T |
T |
T |
T |
T |
T |
Implication, Inverse, Converse, and Contrapositive#
Now that we have seen propositional formulas and truth tables, let’s revisit implications. This connective has many related conditionals.
Consider the propositional formula \(p \rightarrow q\). Then, we have:
Converse: \(q \rightarrow p\)
Inverse: \(\neg p \rightarrow \neg q\)
Contrapositive: \(\neg q \rightarrow \neg p\)
A conditional and its inverse
The proposition “if it is raining, then I wear a jacket” is a conditional statement. Its inverse is “if it is not raining I do not wear a jacket”.
Notice from this previous example than an implication and its inverse are not exactly the same. If the conditional “if it is raining, then I wear a jacket” is true, that is not the same as its inverse. Indeed, you might still wear a jacket even if its not raining. Maybe you’re just cold.
Important
An implication is not equivalent to its converse or inverse. However, it is equivalent to its contrapositive. See Logical Equivalences and Exercises.
1.1.2. Applications#
There are many many applications of propositional logic. You will explore many more of them in other courses on logic, computer architecture, theoretical computer science, and more.
In this section we review a small sampling of applications:
Translating English to logic.
Boolean searches.
Formal specifications of software and computer systems.
Solving logic puzzles.
Translating English to Propositional Logic#
To convert an English sentence to a propositional formula, there are two significant steps. First, find the atomic propositions, the smallest clauses of the sentence which do not contain connectives. Represent each such proposition as a unique variable. Second, determine the appropriate logical connectives for those propositions.
A first logical translation
“If it is raining and I am going outside, I bring an umbrella.”
Let \(p\) be “it is raining”
Let \(q\) be “I am going outside”
Let \(r\) be “I bring an umbrella”
Choosing the corrective connectives gives the logical translation of this sentence:
A second logical translation
“The dog is large and friendly or small and boisterous”
Let \(p\) be “the dog is large”
Let \(q\) be “the dog is friendly”
Let \(r\) be “the dog is small”
Let \(t\) be “the dog is boisterous”
Choosing the corrective connectives gives the logical translation of this sentence:
Note the ambiguity of the previous example. Did the English sentence assume an exlusive or? Probably. Then, a correct translation might be \((p \land q) \oplus (r \land t)\).
Boolean Searches#
Boolean, from mathematician George Boole, refers to a special kind of mathematics that deals with turth values: true and false. Boolean algebra is a set of rules for manipulating formulas containing variables and truth values. This is very similar to, but slightly distinct from propositional logic. We will not explore Boolean algebra in this course.
Boolean searches are about using logical connectives to help search through datasets and filter pieces of data. This includes databases and internet search engines.
Consider a search using two keywords “foo” and “bar”.
AND is used to find records which contain both “foo” and “bar”.
OR is used to find records which contain “foo” or “bar” or both.
NOT is used to exclude records which do contain a keyword.
Web Searches
Consider the key words “London”, “Beer”, “England”, and “Cider”
If we are looking for places to find beer in London, England we might search:
London AND England AND Beer
In most search engines, the AND is implicit, and we can simply search “London England Beer”.
If we are looking for places to find beer or cider in London, England we might search:
London England Beer | Cider
The ANDs are implicit: “London AND England AND (Beer OR Cider)”
If we are looking for places to find beer in London, Ontario we might try to exclude entries for London, England. Searching for:
(London AND Beer) NOT England
Search engines often use the minus sign to denote NOT: “London Beer -England”
Formal Specifications#
In software, computer, and electrical engineering, the requirements of a system, software, or defice must often meet very precise specifications.
These specifications are sometimes easy to express. For example, “the circuit carries 115-125 volts”. For softare in particular, its requirements are often expressed as (ambiguous) natural language requirements. Those requirements must be translated into precise logical statements.
Logical Specification
“Mute all notifications during buisness hours when the user’s status is not available.”
Let \(p\) be “it is during business hours”.
Let \(q\) be “the user’s status is set to available”.
Let \(r\) be “mute all notifications”.
A propositional formula for this specification is:
Propositional logic can also be used to determine if the collection of all requirements for a system is consistent.
Definition (consistent)
A set of propositional formulas is consistent if there exsists at least one truth assignment so that every proposition is simultaneously true.
Notice that consistency is not the same as every formula in a set being satisfiable. The formulas must be simultaneously satisfied by the same truth assignment.
One way to determine consistency is as follows. Given a collection of propositions \(p_1,p_2,\ldots,p_n\), the propositions are consistent if their conjunction is satisfiable. That is, the following formula has at least one truth assignment that makes it true:
To determine the consistency of a requirement set, we must first build propositional formulas for each requirement. Where the same “clause” exists in multiple requirements (recall Translating English to Propositional Logic), we should re-use that propositional variable. Second, we must assign true or false to each variable so that every formula is simultaneously true. If no such assignment exists, the set of requirements is said to be inconsistent.
Exercise
Let us consider an electronic messaging network which requires that all sent messages are certain to be received. This behaviour might be modelled as the following specifications:
Messages remain in the outbound message queue until they have been received by the recipient.
An unreceived message is either a draft or is in the outbound message queue.
Received messsages cannot be drafts.
Is this set of requirements consistent?
Solution
Let \(p\) be “message is in the outbound message queue”.
Let \(q\) be “message is received”.
Let \(r\) be “message is a draft”.
We have:
\(p \rightarrow \neg q\)
\(\neg q \rightarrow (p \lor r)\)
\(q \rightarrow \neg r\)
\(p\) |
\(q\) |
\(r\) |
\(p \rightarrow \neg q\) |
\(\neg q \rightarrow (p \lor r)\) |
\(q \land \neg r\) |
|---|---|---|---|---|---|
F |
F |
F |
T |
F |
F |
F |
F |
T |
T |
T |
F |
F |
T |
F |
T |
T |
T |
F |
T |
T |
T |
T |
F |
T |
F |
F |
T |
T |
F |
T |
F |
T |
T |
T |
F |
T |
T |
F |
F |
T |
T |
T |
T |
T |
F |
T |
F |
Since at least one truth assignment simultaneously satisfies all equations, namely \(p := F, q := T, r := F\), this set of requirements is consistent. In the language of this problem, that means the message is received and is not a draft and is not in the outbound queue.
Solving logic puzzles#
Many puzzles are based around logical arguments and reasoning. So solve such puzzles, propositional logic is a very useful tool. The idea is to model the elements of the puzzle as propositional formula(s), and use those formulas to determine if the formula(s) are satisfiable, consistent, etc., depending on the puzzle.
Let’s see an example.
Activity (Knights and Knaves)
Suppose you are on an island with two kinds of people:
knights, who always tell the truth; and
knaves, who always lie.
You meet two people, \(A\) and \(B\). \(A\) says “\(B\) is a knight.” \(B\) says “the two of us are different kinds of people”.
What kind of people are \(A\) and \(B\)?
Solution
\(A\) and \(B\) are both knaves.
Let \(p\) be “\(A\) is a knight”. Let \(q\) be “\(B\) is a knight”. The statement “the two of us are different kinds of people” can be represented as \((p \land \neg q) \lor (\neg p \land q)\).
Assume \(A\) is a knight and therefore \(p\) is true. Then, their statement “\(B\) is a knight” must be true and therefore \(q\) is true. If \(B\) is a knight, then the formula \((p \land \neg q) \lor (\neg p \land q)\) should be true. However, this formula is false if both \(p\) and \(q\) are true.
Assume \(A\) is a knave (i.e. \(\neg p\) is true). Then, their statement “\(B\) is a knight” must be false (i.e. \(\neg q\) is true). Therefore, \(B\) is a knave and their statement should be a lie. Both \(p\) and \(q\) being false makes \((p \land \neg q) \lor (\neg p \land q)\) false, which is consistent.
1.1.3. Logical Equivalences#
Propositional logic is the foundation of more complex logical systems and of formal mathematical proofs. One particular kind of proof, an “equivalence proof”, proves that one thing is equivalent to another through a sequence of equivalences.
What is an equivalence? Well, the first quesiton to ask is: what is a tautology?
Definition (tautology)
A propositional formula that is always true, for every possible truth assignment, is a tautology.
A proposition that is not a tautology is either a contradiction or a contingency.
Definition (contradiction)
A propositional formula that is always false, for every possible truth assignment, is a contradiction.
Definition (contingency)
A propositional formula that is neither a tautology nor a contradiction is a contingency.
Logically Equivalent#
Two propositional formulas, say \(p\) and \(q\), are logically equivalent if \(p \leftrightarrow q\) is a tautology. When this is the case, we may write \(p \iff q\) or \(p \equiv q\).
A simple and explicit way to determine if two expressions are logically equivalent is if their two columns in a truth table are identical.
Logically equivalent truth table
\(p\) |
\(q\) |
\(\neg p\) |
\(p \rightarrow q\) |
\(\neg p \lor q\) |
|---|---|---|---|---|
F |
F |
T |
T |
T |
F |
T |
T |
T |
T |
T |
F |
F |
F |
F |
T |
T |
F |
T |
T |
There are several logical equivalences which would be good to memorize. They are similar to many laws of arithmetic. For example, we know \(x \times 0 = 0\) regardless of the value of \(x\).
Identity Laws
Annihilation Laws
Idempotent Laws
Complementation Laws
Double negation
\(p \land T \equiv p\)
\(p \land F \equiv F\)
\(p \land p \equiv p\)
\(p \land \neg p \equiv F\)
\(\neg (\neg p) \equiv p\)
\(p \lor F \equiv p\)
\(p \lor T \equiv T\)
\(p \lor p \equiv p\)
\(p \lor \neg p \equiv T\)
There are also interesting properties of logical connectives between two or more propositional variables.
Commutativity
Associativity
Distributivity
Absorption
De Morgan’s Laws
\(p \land q \equiv q \land p\)
\(p \land (q \land r) \equiv (p \land q) \land r\)
\(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\)
\(p \land (p \lor q) \equiv p\)
\(\neg (p \land q) \equiv \neg p \lor \neg q\)
\(p \lor q \equiv q \lor p\)
\(p \lor (q \lor r) \equiv (p \lor q) \lor r\)
\(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)\)
\(p \lor (p \land q) \equiv p\)
\(\neg (p \lor q) \equiv \neg p \land \neg q\)
De Morgan’s Laws are very important. These laws explain how negation distributes over a conjunction and disjunction. In particular, it turns disjunctions into conjunctions, and vice versa.
Important
In these laws and properties, we can replace any propositional variable with an entire propositional formula, and the law is still correct.
Variable-expression replacement
Let \(p := (\neg a \land b) \lor c\).
These laws and properties can be used as building blocks to prove that certain expressions are logically equivalent. Before we see that process, let’s see some more interesting logical equivalences.
More logical equivalences
\((p \rightarrow q) \equiv \neg p \lor q\)
\((p \rightarrow q) \land (p \rightarrow r) \equiv p \rightarrow (q \land r)\)
\((p \rightarrow r) \land (q \rightarrow r) \equiv (p \lor q) \rightarrow r\)
\(p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)\)
\(p \leftrightarrow q \equiv \neg p \leftrightarrow \neg q\)
\(p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)\)
Tip
Draw the truth table for some of the above examples to prove to yourself that the two expressions are logically equivalent.
Equivalence proof#
We can show two expressions, say \(A\) and \(B\), are logically equivalent by constructing a sequence of logically equivalent statements \(E_i\), beginning with \(A\) and ending with \(B\).
A first equivalence proof
Prove that \(p \land (\neg p \lor q) \equiv p\land q\).
Whenever we use propositional logic, we will return to equivalence proofs and truth tables. It is important that you really understand the manipulation and equivalency of propositional truth tables.
Equivalence proof
Prove that \(p \lor (p \land q) \lor (\neg p \land r) \equiv (p\land q) \lor p \lor r\).
Equivalence proof
1.1.4. Exercises#
Basic Propositions#
Exercise 1.1
If a propositional formula has 5 variables, how many rows are needed in its truth table?
Solution to Exercise 1.1
\(\mathbf{32}\). Each variable has two choices: true of false. 5 variables means there are \(2 \times 2 \times 2 \times 2 \times 2 = 2^5 = 32\) possible combinations of truth values.
Exercise 1.2
Express the following English sentence as a propositional formula. “If it is snowing I wear a jacket and I wear mittens.”
Solution to Exercise 1.2
\(p\): It is snowing
\(q\): I wear a jacket
\(r\): I wear mitterns
Exercise 1.3
Express the following English sentence as a propositional formula. “When I am at the beach or I go swimming, I wear a swimsuit.”
Solution to Exercise 1.3
\(p\): I am at the beach
\(q\): I go swimming
\(r\): I wear a swimsuit
Exercise 1.4
Classify each of the following statements as true or false.
“\(4 = 2+2\) and \(7 < \sqrt{50}\)”
“\(4 = 2+2 \rightarrow 7 < \sqrt{50}\)”
“\(4 \neq 2 +2 \rightarrow 7 < \sqrt{50}\)”
“\(4 = 2 +2 \rightarrow 7 \geq \sqrt{50}\)”
Solution to Exercise 1.4
True. Both clauses are true.
True. Both premise and conclusion are true.
True. The hypothesis is false, therefore true.
False. The premise is true, but the conclusion is false.
Exercise 1.5
Give the negation of each of the following compound statements.
“Either \(a^2 > 0\) or \(a\) is not a real number.”
“\(x = \pm 1\)”
“\(x\) is a real number and \(x^2 + 1 = 0\)”
Solution to Exercise 1.5
“\(a^2 \leq 0\) and \(a\) is a real number”; also “\(a = 0\)”
“\(x \neq 1\) and \(x \neq -1\)”
“\(x\) is not a real number or \(x^2 + 1 \neq 0\)”
Exercise 1.6
Give the converse, inverse, and contrapositive of each of the following implications.
“If \(\frac{a}{b}\) and \(\frac{b}{c}\) are integers, then \(\frac{a}{c}\) is an integer.”
“Every Eulerian graph is connected”.
“\(ab = 0 \rightarrow a = 0\) or \(b = 0\)”.
Solution to Exercise 1.6
Converse: “If \(\frac{a}{c}\) is an integer then \(\frac{a}{b}\) and \(\frac{b}{c}\) are integers”
Inverse: “If \(\frac{a}{b}\) is not an integer or \(\frac{b}{c}\) is not an integer then \(\frac{a}{c}\) is not an integer.”
Contrapositive: “If \(\frac{a}{c}\) is not an integer then \(\frac{a}{b}\) is not an integer or \(\frac{b}{c}\) is not an integer”
Converse: “Every connected graph is Eulerian”
Inverse: “Every non-Eulerian graph is not connected.”
Contrapositive: “Every non-connected graph is not Eulerian.”
Converse: “\(a=0\) or \(b=0\) \(\rightarrow\) \(ab=0\)”
Inverse: “\(ab \neq 0 \rightarrow a \neq 0\) and \(b \neq 0\)”
Contrapositive: “\(a \neq 0\) and \(b \neq 0 \rightarrow ab \neq 0\)
Exercise 1.7
For each of the following propositional formulas, determine which are satisfiable. If they are satisfiable, give a truth assignment which satisfies the formula.
\(p \land (\neg q \lor \neg r) \land (q \lor \neg p)\)
\(p \land (q \lor \neg p) \land (\neg q \lor \neg p) \land r\)
\((p \land q \land \neg r) \lor (p \land \neg q \land \neg r)\)
Solution to Exercise 1.7
\((p, q, r) := (T, T, F)\)
Not satisfiable
\((p,q,r) := (T, T, F)\) or \((T, F, F)\)
Applications#
Exercise 1.8
Julie and Jamie are identical twins. One of then always lies and one of them always tells the truth. Suppose you meet one of them. What 3-word question (with a yes/no answer) can you ask to determine which twin is in front of you? You do not know which twin lies.
Solution to Exercise 1.8
“Does Julie lie?”
Suppose you meet Julie and Julie tells the turth. Julie will reply “no”.
Suppose you meet Julie and Julie lies. Julie will reply “no” (i.e. “no, Jamie lies”).
Suppose you meet Jamie and Jamie tells the truth. Jamie will reply “yes”.
Suppose you meet Jamie and Jamie lies. Jamie will reply “yes” (i.e. “yes, Julie lies”).
Exercise 1.9
Define the basic clauses of each of the following statements as propositional variables. Then, express each of the following compound statements as propositional formulas. Finally, is this set of propositions consistent? If so, give a truth assignment which shows they are consistent.
The campus server does not work if the internet is off.
Students can skype during the test when the prof is distracted.
If the classroom phone does not ring then the prof is not distracted.
Students cannot skype during the test unless the internet is on.
If the classroom phone rings then the campus server works.
Solution to Exercise 1.9
\(I :=\) “internet is on”
\(C :=\) “the campus server works”
\(D :=\) “the professor is distracted”
\(S :=\) “students can Zoom during the test”
\(R :=\) “the classroom phone rings”
\(\neg I \rightarrow \neg C\)
\(D \rightarrow S\)
\(\neg R \rightarrow \neg D\)
\(S \rightarrow I\); \(\neg I \rightarrow \neg S\); “A unless B” translates logically to “A if not B”
\(R \rightarrow C\)
To check consistency, we need to see if the following conjunction is satisfiable.
This is satisfiable with: \((I, S, R, D, C) := (T, T, T, T, T)\)
Logical Equivalences#
Exercise 1.10
Show that \(p \rightarrow q\) is logically equivalent to \(\neg q \rightarrow \neg p\).
Exercise 1.11
Prove De Morgan’s law \(\neg (p \land q) \equiv \neg p \lor \neg q\) by a truth table.
Solution to Exercise 1.11
\(p\) |
\(q\) |
\(\neg (p \land q)\) |
\(\neg p \lor \neg q\) |
|---|---|---|---|
F |
F |
T |
T |
F |
T |
T |
T |
T |
F |
T |
T |
T |
T |
F |
F |
Exercise 1.12
If \((p \land q) \lor ((\neg p) \land q \land r)\) is logically equivalent to \((p \land q \land r) \lor (p \land q)\), show their biconditional is a tautology. If not, give a truth assignment which results in different truth values for each formula.
Exercise 1.13
Show that the following expressions are logically equivalent. Do this by (a) truth tables, and (b) logical equivalences.
Exercise 1.14
Prove that \(p \lor (p \land q) \lor (\neg p \land r) \equiv p \lor r\).
Solution to Exercise 1.14
Exercise 1.15
Prove that \(\neg (p \lor (\neg p \land q)) \equiv \neg p \land \neg q\).
Solution to Exercise 1.15
Let \(A\) be \(\neg p \land q\).
Exercise 1.16
Prove that \(p \land r \land (\neg q \lor p) \equiv p\land r\).