Propositional Logic

Question 1

A proposition is a

Answer 1

declaration of fact that is either true or false, but not both

Question 2

¬

Answer 2

Negation

not

Question 3

∧

Answer 3

Conjunction

and

Question 4

∨

Answer 4

Disjunction

(inclusive) or

Question 5

⨁

Answer 5

Exclusive Disjunction

exclusive or, xor

Question 6

→

Answer 6

Conditional

If .. then, ..implies..

Question 7

↔

Answer 7

Biconditional

if and only if, iff

Question 8

negation is defined by the following truth table:

Answer 8

Question 9

Objects cannot be negated, only statements

Answer 9

Incorrect negation:

¬JackistallerthanJoe ≡(¬Jackistallerthan¬Joe)

The correct negation is:

¬JackistallerthanJoe ≡JackisatmostastallasJoe.

Question 10

Negation Rules for Inequalities

Answer 10

the negation of a strict inequality is non-strict inequality and vice versa.

¬𝑥>𝑦 ≡(𝑥≤𝑦)

¬𝑥≥𝑦 ≡(𝑥<𝑦)

Question 11

You must exercise special care when negating a double inequality.

Answer 11

The correct negation of 1 ≤ 𝑥 ≤ 2 is

𝑥<1∨𝑥>2

Question 12

Conjunction

Answer 12

Question 13

Disjunction

Answer 13

Question 14

Exclusive Disjunction (aka Exclusive Or)

Answer 14

Question 15

Conditional

Answer 15

Question 16

Biconditional

Answer 16

𝑝 ↔ 𝑞 ≡ (𝑝 → 𝑞) ∧ (𝑞 → 𝑝)

Question 17

Observe that 𝑝 ↔ 𝑞 is the negation of

Answer 17

𝑝⨁𝑞.

Also observe that the biconditional is true exactly when p and q have the same truth value, whether that is true or false.

Question 18

It is not a very good idea to attempt to reduce the understanding of “necessary” and “sufficient” typestatements to the mindlessly symbolical level.

Answer 18

Question 19

Just like “sufficient” type phrases in English defy simplistic word order analysis, so do “necessary” type statements.

Answer 19

Question 20

It is helpful to change “necessary” to

Answer 20

“precondition”.For example, we rephrase

“A cloudless sky is necessary to see the stars” as
“A cloudless sky is a precondition for seeing the stars.”

The word precondition makes it clear that the cloudless sky does not guarantee that we can see the stars

Question 21

“p only if q” means

Answer 21

𝑝 → 𝑞

If you find this hard to remember, just translate the conditional as if the word only was not there, and then switch premise and conclusion.

Question 22

“p unless q” means

Answer 22

¬𝑞 → 𝑝

This rule shows that unless means if not. “You will get sick unless you take the medicine” means “You will get sick if you don’t take the medicine.”

Question 23

𝑞 → 𝑝 is called the converse of

Answer 23

𝑝 → 𝑞

Question 24

¬𝑝 → ¬𝑞 is called the inverse of

Answer 24

𝑝 → 𝑞

Question 25

¬𝑞 → ¬𝑝 is called the contrapositive of

Answer 25

𝑝 → 𝑞

Question 26

Order of Operations

Answer 26

1. negation
2. conjunction
3. disjunction
4. conditional
5. biconditional

Question 27

Logical Operators on Bitstrings

Answer 27

Question 28

tautology

Answer 28

A compound proposition that is always true, regardless of the truth values of the individual propositions involved

Question 29

contradiction

Answer 29

A compound proposition that is always false, regardless of the truth values of the individual propositions involved

Question 30

contingency

Answer 30

A compound statement that is neither a tautology nor a contradiction

Question 31

Logical equivalence

Answer 31

two compound statements 𝑝 and 𝑞 “equal” ifthey always share the same truth value

use the symbol ≡ to represent logical equivalence

Using the biconditional and the concept of a tautology that we just introduced, we can formally define logical equivalence as follows:

𝑝 ≡ 𝑞 means that 𝑝 ↔ 𝑞 is a tautology.

An alternative definition is that 𝑝 ≡ 𝑞 means that 𝑝 and 𝑞 share the same truth table.

Question 32

“Equivalent” vs “Equal”

Answer 32

Do not use the words “equivalent” and “equal” interchangeably . Equivalenceapplies to statements. Two quantities that are the same are equal. If you fail to keep this distinction in mind when dealing with statements that are about quantities, you are in danger of making wholly nonsensical statements.

Question 33

An important logical equivalence

𝑝 → 𝑞 ≡ ¬𝑝 ∨ 𝑞

Answer 33

Unlike other important logical equivalences, 𝑝 → 𝑞 ≡ ¬𝑝 ∨ 𝑞 does not have a commonly agreed upon name. Technically, we could consider this law the definition of the conditional, so we will refer to it by that name

Question 34

The Laws of De Morgan

Answer 34

The negation of a conjunction must be the disjunction of the negations. There is also a symmetric law of De Morgan which is obtained by switching the roles of conjunction and disjunction.

Both laws can be formally proved by truth table.

¬(𝑝 ∧ 𝑞) ≡ ¬𝑝 ∨ ¬𝑞

¬(𝑝 ∨ 𝑞) ≡ ¬𝑝 ∧ ¬𝑞

Question 35

Negation of Conditionals

Answer 35

To negate a conditional, we must rewrite it using disjunction and negation, and then carefully apply De Morgan.

¬𝑝→𝑞 ≡¬¬𝑝∨𝑞 ≡ 𝑝∧¬𝑞

Question 36

De Morgan and Double Inequalities

Answer 36

The correct negation of 1 ≤ 𝑥 ≤ 2 is

𝑥<1∨𝑥>2

To understand this, consider that the original double inequality is a conjunction of two inequalities:

1 ≤ 𝑥 ≤ 2 ≡ 1 ≤ 𝑥 ∧ 𝑥 ≤ 2.

Thereby, by De Morgan, the negation is the disjunction of the individual inequalities, which leads to 𝑥 < 1 ∨ 𝑥 > 2.

Question 37

Commutative laws

Answer 37

𝑝∨𝑞≡𝑞∨𝑝

𝑝∧𝑞≡𝑞∧𝑝

Question 38

Associate laws

Answer 38

𝑝 ∨ (𝑞 ∨ 𝑟) ≡ (𝑝 ∨ 𝑞) ∨ 𝑟

𝑝 ∧ (𝑞 ∧ 𝑟) ≡ (𝑝 ∧ 𝑞) ∧ 𝑟

Question 39

Distributive Laws

Answer 39

𝑝 ∨ (𝑞 ∧ 𝑟) ≡ (𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟)

𝑝∧ (𝑞∨𝑟) ≡(𝑝∧𝑞)∨(𝑝∧𝑟)

Question 40

Identity Laws

Answer 40

𝑝∨𝐹≡𝑝

𝑝∧𝑇≡𝑝

Question 41

Domination Laws

Answer 41

𝑝∨𝑇≡𝑇

𝑝∧𝐹≡𝐹

Question 42

Idempotent Laws

Answer 42

𝑝∨𝑝≡𝑝

𝑝∧𝑝≡𝑝

Question 43

Double Negation Law

Answer 43

¬(¬𝑝) ≡ 𝑝

Question 44

Absorption Laws

Answer 44

𝑝∨ (𝑝∧𝑞) ≡𝑝

𝑝 ∧ (𝑝 ∨ 𝑞) ≡ 𝑝

Question 45

Logical Equivalence of Conditionals

Answer 45

It is an important fact that a conditional is logically equivalent to its contrapositive, but not to its inverse or converse.

𝑝 → 𝑞 ≡ ¬𝑞 → ¬𝑝

Since the inverse is the contrapositive of the converse, inverse and converse are logically equivalent to each other:

𝑞 → 𝑝 ≡ ¬𝑝 → ¬𝑞

Question 46

Logical Equivalence of Conditionals Diagram

Answer 46