Propositional Logic

Definition: A proposition or statement is a sentence which is either true or false.

Definition:If a proposition is true, then we say its truth value is true, and if a proposition
is false, we say its truth value is false.
Are these propositions?
1. The sun is shining.
2. The sum of two prime numbers is even.
3. 3+4=7
4. It rained in Austin, TX, on October 30, 1999.
5. x+y > 10
6. Is it raining?
7. Come to class!
8. n is a prime number.
9. The moon is made of green cheese.
Definition: A propositional variable represents an arbitrary proposition. We represent
propositional variables with uppercase letters.
1
What is an Argument?
Definition: An argument consists of a sequence of statements called premises and a
statement called a conclusion. An argument is valid if the conclusion is true whenever the
premises are all true.

Example: My program won’t compile or it produces a division by 0 error.

My program does not produce a division by 0 error.
Therefore my program will not compile.
Now: Rewrite this argument in its general form by defining appropriate propositional
variables.
This is one example of an argument form that is called disjunctive syllogism.
2
Example: Another disjunctive syllogism example
Ladybugs are purple or green.
Ladybugs are not green.
Therefore ladybugs are purple.

Let P be: Ladybugs are purple.

Let Q be: Ladybugs are green.
Rewritten argument: P or Q not Q
Therefore P
This argument is valid, but it isn’t very meaningful since P and Q are not true.
3
LOGICAL CONNECTIVES
• Use logical connectives to build complex propositions from simpler ones.
The First Three Logical Connectives
• ¬ denotes not. ¬P is the negation of P.
• ∨ denotes or. P ∨ Q is the disjunction of P and Q.
• ∧ denotes and. P ∧ Q is the conjunction of P and Q.
Order of Operations
• ¬ first
• ∧/∨ second
• implication and biconditionals last (more on these later)
• parentheses can be used to change the order
4
Translating English Into Logic
Note: The word “but” in English is often translated as ∧.
Example: Today is is hot but it is not sunny. Because the second part of the sentence is a
surprise, “but” is used instead of “and”.
Example: Write each sentence in symbols, assigning propositional variables to statements
as follows: P: It is hot. Q: It is sunny.
1. It is not hot but it is sunny.
2. It is neither hot nor sunny.
Answers: (in class)
5
Exercise (on your own) Try out google’s advanced search, which let’s you use logical
connectives to limit your hits. What options on the search page correspond to:
• AND’ing together several terms, e.g., search for pages that contain “induction” and
“mathematical”.
• OR’ing - search for pages that contain “Russell” or “Barber” plus also “paradox”.
• AND’ing and negation - search for pages that contain “wheat” but not “gluten”.
6
Truth Tables
Truth tables represent the relationship between the truth values of propositions and
compound propositions formed from those propositions.
Examples: Give truth tables for the logical connectives not, and, or.
Example: P: Today is Friday. What is ¬P?
Example: P: At least two inches of rain fell in Austin today. ¬P?
Example: P: Today it is raining. Q: Today is it snowing. P ∧ Q? P ∨ Q?
7
Inclusive vs. Exclusive Or
Note: The ∨ operation represents “inclusive” or. P ∨Q is true if either P and Q are true, or
if both P and Q are true.
“Or” has two meanings in English:
1. Inclusive Or: I will take cs 305j or cs 313k this fall. (Possibly I will take both).
2. Exclusive Or: I will order a steakor enchiladas fordinner tonight. (But hopefully not
both!).
Make sure you are interpreting “or” correctly when translating English statements into
logic!!
Exercise: Write a truth table for exclusive or operation, sometimes denoted ⊕ or ∨.
8
Conditional Statements or Implications, and Bi-conditionals
For propositions P and Q, the implication or conditional statement P → Q is false when P
is true and Q is false, and is true otherwise. P is called the premise or hypothesis, and Q
is called the conclusion.
Ways to read P → Q: If P then Q. P is sufficient for Q. P implies Q. Q follows from P.
9
Implication Example
Example: If you earn 90% of the possible points in cs 313k, then you will get an A.
Rewritten in logical notation: P → Q,
where P is: You earn 90% of the possible points in cs 313k.
Q is: You will get an A in cs 313k.

Interpretation of P → Q: Think of P → Q being true as long as I do what I promised: If P

is false, you should not expect an A (though I could give you an A), so I have honored the
commitment (P → Q is true). If P is true, P → Q is true only if Q is also true, ie if I give
you an A.
Example: Give the truth table for implication P → Q.
10
More on the Meaning of Implications
Note: In English, a sentence of the form “if A then B” can have different meanings. 1.
Typically there is a causal relationship between A and B, which is not required in logic. 2.
We are often implying more than simply that if A holds, then B holds as well.
Example: If I finish my work early, then I will pick you up before lunch. The common-
sense interpretation of this sentence is that the inverse statement is also true: If I do not
finish my work early, then I will not pick you up before lunch. But this is not implied by
the logical implication P → Q, where P is “I finish my work early” and Q is “I will pick
you up before lunch”. English is not as precise as logic.
Example: If 2 is prime, then grape juice will pour from the sky today. Logical implication
P → Q can be formed using propositions P and Q that are not related in any way. We
would never say this in English.
11
Examples: Are these implications true or false?
1. If it rains today, then 2 is a prime number.
2. If 2+2=5, then all dogs are black.
3. If 4*4 = 16, then (-1)*(-1) = 1.
4. If there are 100 students in class today, then we will order pizza.
12
Biconditionals
The biconditional of statements P and Q, denoted P ↔ Q, is read “P if and only if Q” (or
“P is necessary and sufficient for Q”), and is true if P and Q have the same truth values,
and false otherwise.
Example: Write down the truth table of P ↔ Q.
Example: True or false? 2+2 = 5 if and only if 2 is prime.
Example: true or false? 2+2 = 5 if and only if 10 is prime.
Note: If P ↔ Q is true, then P → Q and Q → P are true. Conversely if both P → Q and Q
→ P are true, then P ↔ Q is true. Prove this claim using a truth table.
13
Translating English into Logic
Example: You can use the microlab only if you are a cs major or not a freshman.
P: You can use the microlab.
Q: You are a cs major.
R: You are a freshman. Rewrite the statement using logical connectives.
Example: If it snows or rains today, I will not go for a walk.
Rewrite this proposition using logical connectives and propositional variables.
14
Rearrangements of an Implication
Definition: For conditional statement P → Q, the converse statement is Q → P, the
contrapositive statement is ¬Q → ¬P, and the inverse statement is ¬P → ¬Q.
Note: As we saw in a previous example, we can use a truth table to determine if two
compound propositions are logically equivalent, ie if they always have the same truth
values. If two propositions R and S are logically equivalent, we write R ≡ S.
Example: Use a truth table to determine whether or not the converse, contrapositive and
inverse statements are logically equivalent to P → Q.
Definition: If a compound proposition is always true, it is a tautology. Note that if R ↔ S
is a tautology, then R ≡ S.
Note: ≡ is not a logical connective and R ≡ S is not a compound proposition. R ≡ S just
means that R → S is a tautology. Alternate notation: R ⇔ S.
15
Using Truth Tables to Prove Identities
Example: Are ¬(P ∨Q) and ¬P ∧¬Q logically equivalent? Prove your answer with a truth
table.
Exercise: Show that P → Q and ¬P ∨ Q are logically equivalent. This is called an
implication law.
Exercise: Show P ∨ (Q ∧ R) and (P ∨ Q) ∧ (P ∨ R) are logically equivalent. This is one
of the distributive laws.
16
LOGICAL IDENTITIES
P ≡ P ∧ P idempotence of ∧
P ≡ P ∨ P idempotence of ∨
P ∨ Q ≡ Q ∨ P commutativity of ∨
P ∧ Q ≡ Q ∧ P commutativity of ∧
(P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R) associativity of ∨
(P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R) associativity of ∧
¬(P ∨ Q) ≡ ¬P ∧ ¬Q DeMorgan’s Laws
¬(P ∧ Q) ≡ ¬P ∨ ¬Q P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R) distributivity of ∧ over ∨
P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R) distributivity of ∨ over ∧
P ∨ T ≡ T domination laws
P ∧ F ≡ F P ∧ T ≡ P identity laws
P ∨ F ≡ P P ∨ ¬P ≡ T negation laws
P ∧ ¬P ≡ F ¬(¬P) ≡ P double negation law
P ∨ (P ∧ Q) ≡ P absorption laws
P ∧ (P ∨ Q) ≡ P P → Q ≡ ¬P ∨ Q implication
P → Q ≡ ¬Q → ¬P contrapositive
P ↔ Q ≡ [(P → Q) ∧ (Q → P)] equivalence
[(P ∧ Q) → R] ≡ [P → (Q → R)] exportation
17
Examples with Identities
1. P ≡ P ∧ P - idempotence of ∧
“Anna is wretched” is equivalent to “Anna is wretched and Anna is wretched”.
2. P ≡ P ∨ P - idempotence of ∨
“Anna is wretched” is equivalent to “Anna is wretched or wretched”.
3. P ∨ Q ≡ Q ∨ P - commutativity
“Sam is rich or happy” is equivalent to “Sam is happy or rich”.
3′.P∧Q≡Q∧P
“Sam is rich and Sam is happy” is equivalent to “Sam is happy and Sam is rich”.
4. ¬(P ∨ Q) ≡ ¬P ∧ ¬Q - DeMorgan’s law
“It is not the case that Sam is rich or happy” is equivalent to “Sam is not rich and he is
not happy”.
4 ′ . ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
“It is not true that Abby is quick and strong” is equivalent to “Abby is not quick or Abby
is not strong”.
5. P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R) - distributivity “
Abby is strong, and Abby is happy or nervous” is equivalent to “Abby is strong and
happy, or Abby is strong and nervous”.
5 ′ . P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)
“Sam is tired, or Sam is happy and rested” is equivalent to “Sam is tired or happy, and
Sam is tired or rested”.
6. P ∨ ¬P ≡ T - negation law
7. “Ted is healthy or Ted is not healthy” is true.
6 ′ . P ∧ ¬P ≡ F “Kate won the lottery and Kate didn’t win the lottery” is false.
18
7. ¬(¬P) ≡ P - double negation
“It is not the case that Tom is not rich” is equivalent to “Tom is rich”.
8. P ∨ (P ∧ Q) ≡ P - absorption
“Kate is happy, or Kate is happy and healthy” is true if and only if “Kate is happy” is
true. 8 ′ . P ∧ (P ∨ Q) ≡ P
“Kate is sick, and Kate is sick or angry” is true if and only if “Kate is sick” is true.
9. P → Q ≡ ¬P ∨ Q - implication
“If I win tne lottery, then I will give you half the money” is true exactly when I either
don’t win the lottery, or I give you half the money.
10. P → Q ≡ ¬Q → ¬P - contrapositive
“If Anna is healthy, then she is happy” is equivalent to “If Anna is not happy, then she is
not healthy”.
11. P ↔ Q ≡ (P → Q) ∧ (Q → P) equivalence
“Anna is healthy if and only if she is happy” is equivalent to “If Anna is healthy, then she
is happy, and if Anna is happy, then she is healthy”.
12. (P ∧ Q) → R ≡ P → (Q → R) - exportation
“Anna is famous implies that if she is rich, then she is happy” is equivalent to “If Anna is
famous and rich, then she is happy”.
19
More on Propositional Equivalence
Recall: A compound proposition that is always true is a tautology. Example: P ∨ ¬P
Definition: A compound proposition that is always false is a contradiction. Example: P ∧
¬P.
Definition: A compound proposition that is not a tautology or a contradiction is a
contingency.
Homework: Look at the table of logical equivalences and become familiar with the laws
and their names.
Example: P: Ann will go to the movie.
Q: Scott will go to the movie.
Using DeMorgan’s law, ¬(P ∨Q) ≡ ¬P ∧¬Q, write down ¬(P ∨Q).
20
Equivalence Proofs using the Logical Identities
Example - our first step by step equivalence proof Show P ∧ ¬Q ≡ ¬(P → Q).
Hint: You will need to use the fact that P → Q ≡ ¬P ∨ Q (we just proved this).
Example: Show that (P ∧ Q) → P is a tautology.
Note: We can also use a truth table to prove a compound proposition is a tautology, but
this is only practical if the number of propositional variables is small.
Exercise: Show ¬P → (P → Q) is a tautology, first using a truth table and then with an
equivalence proof.