CvSU Mission

CvSU Vision Republic of the Philippines Cavite State University shall provide
The premier university in excellent, equitable and relevant educational
historic Cavite recognized for CAVITE STATE UNIVERSITY opportunities in the arts, science and technology
through quality instruction and relevant research and
excellence in the development
of globally competitive and
Cavite City Campus development activities.

morally upright individuals. Brgy. 8, Pulo II, Dalahican, Cavite City morally
It shall produce professional, skilled and
upright individuals for global
competitiveness.

CHAPTER 1
FUNDAMENTALS OF LOGIC
Objectives:
After the completion of the chapter, students should be able to:

 Identify propositional statements

 Apply logical operators on propositional statements
 Construct truth tables
 Construct the inverse, converse and contrapositive of a propositional statement
 Prove biconditional statements using rules of replacement

It is not easy to summarize in a few paragraphs the subject matter known as logic. For lawyers and
judges, it is the science of correct reasoning. They often use logic to communicate more effectively,
construct valid arguments, analyze legal contracts, and make decisions.
Many other professions make extensive use of logic. For instance, programmers use logic to design
computer software, electrical engineers use logic to design circuits for smartphones, and mathematicians
use logic to solve problems and construct mathematical proofs.
Logic is the discipline that studies the distinction of correct reasoning from incorrect reasoning by
determining the conditions under which the truth of certain beliefs leads naturally to the truth of some other
belief, and by drawing attention to the ways in which we may be led to believe something without respect
for its truth. In other words, logic is the study of language and reasoning. It shows relationships among
statements enforcing critical thinking. The purpose of logic is to enable the logician to construct valid
arguments which satisfies the basic principles.
Why do mathematicians require proofs? How are you supposed to read and understand a proof? If
you have to prove something yourself, how do you know where to start? How do you know when you’re
finished? Perhaps most importantly, what is a proof?

Historical Notes
George Boole was born in 1815 in Lincoln, England. He was raised in poverty but he was very industrious and had
learned Latin and Greek by the age of 12. Later he mastered German, French, and Italian. His first profession, at the
young age of 16, was that of an assistant school teacher. At the age of 20, he started his own school.
In 1849, Boole was appointed the chairperson of mathematics at Queens College in Cork, Ireland.
Many of Boole’s mathematical ideas, such as Boolean Algebra, have applications in the areas of computer
programming and the design of electric circuits.

Gottfried Wilhelm Leibniz (1646 – 1716) tried to advance the study of logic from a merely philosophical subject to a
formal mathematical subject. Leibniz never really completed this goal; however several mathematicians, such as
Augustus de Morgan (1806-1871) and George Boole (1815-1864), contributed to the advancement of symbolic logic
as mathematical discipline.

1.1 PROPOSITIONS AND LOGICAL OPERATORS

A statement is also called a proposition. It is defined as a declarative sentence that is either true or false, but
can’t be both simultaneously.

Examples:
1. Corazon Aquino is the first female president of the Republic of the Philippines.
2. For every positive integer n, there is a prime number larger than n.

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

The truth value of a proposition is true (T) if the sentence is true and false (F) if the sentence is false.

Let’s consider several sentences.

• Two plus two equals four. This sentence is true, hence a proposition.
• Seven minus three equals twelve. This sentence is false, hence a proposition.
• It will snow in Grand Forks on March 17, 2525. This sentence is either true or false, even if nobody
currently alive will ever know which. It is a proposition, we just don’t happen to know the truth value.
• Go clean your room. This sentence is a command, not a proposition.
• Is it raining outside? Again, this is not a proposition. It is a question.
• This sentence is false. This sentence is not a proposition because it cannot be either true or false. If it is
true, then it’s claim is false. If it’s false, then it’s claim must be true. We will not allow sentences that
refer to themselves except as examples of what might go wrong if we are not careful.
• x + 3 = 12. This sentence cannot be said to be true or false without more information about the
variable x. If x = 0, then it is false. If x = 9, then it is true. Statements like this are not propositions, but
are extremely important.

We will use uppercase letters, frequently P or Q, to stand for variable propositions in much the same way
that you might use x or y to represent variable numbers in algebra.

SIMPLE STATEMENTS AND COMPOUND STATEMENTS

A simple statement is a statement that conveys a single idea.
Example: Ms. Alyssa Bianca Aguilar is smart.
She is beautiful.

A compound statement is a statement that conveys two or more ideas.

Example:
1. Ms. Alyssa Bianca Aguilar is smart and beautiful.
(The connective here is “and” which conjuncts two ideas/statements: Ms. Alyssa Bianca Aguilar is
smart; and Ms. Alyssa Bianca Aguilar is beautiful.)
2. Shania is a good cook or an excellent singer.
(The connective here is “or” which disjuncts two ideas/statements: Shania is a good cook; or Shania
is an excellent singer.)

EXERCISE 1.1 DATE: ________________

A. Determine whether each sentence is a statement.
_______1. Harry Potter is the greatest movie of all time.
_______2. Our Mathematics instructor is stunning.
_______3. Have a fun trip.
_______4. Are you single?
_______5. 5 is an odd number.
_______6. 𝑥 2 = 25
_______7. 𝑥 = 𝑥 + 1
_______8. A triangle is an acute triangle if and only if it has three acute angles.
_______9. Please stop writing.
_______10. 1

B. In the following compound statements, determine the simple statements.

1. The dean visits the main campus on a Tuesday or Friday.
2. 5 is an odd number and 6 is an even number.
3. If today is Saturday, then yesterday was Friday.
4. You are a logician if and only if you have excellent reasoning ability.
5. I went to the post office and the bookstore.

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

1.2 CONNECTIVES AND TRUTH TABLES
Logic Connectives and Symbols
Statement Connective Symbolic Form Type of Statement
not 𝑝 not ~𝑝 negation
𝑝 and 𝑞 and 𝑝∧𝑞 conjunction
𝑝 or 𝑞 or 𝑝∨𝑞 disjunction
If 𝑝, then 𝑞 if…then 𝑝→𝑞 conditional
𝑝 if and only if 𝑞 if and only if 𝑝↔𝑞 biconditional

EXERCISE 1.2.1 DATE: ________________

Consider the following statements:
𝑝: Taylor Swift is a singer.
𝑞: Taylor Swift is not a songwriter.
𝑟: Taylor Swift is an actress.
𝑠: Taylor Swift plays the piano.
𝑡: Taylor Swift does not play the guitar.
Write each symbolic statement as an English sentence.
1. (𝑝 ∨ 𝑟) ∧ 𝑞

2. ~𝑠 ⇒ (𝑝 ∧ ~𝑞 )

3. 𝑡 ⇔ (~𝑟 ∧ ~𝑝)

Write each english sentence as a symbolic statement.

4. Taylor Swift does not play the guitar nor the piano, and she is an actress and not a singer.

5. Taylor swift is a singer or a songwriter, if and only if she plays the piano or the guitar.

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

 1.2.1 CONJUNCTION
The conjunction of the propositions p and q is the proposition p and q, denoted p ∧ q. The conjunction
p ∧ q is true when both p and q are true and false if either p or q (or both) are false.
TRUTH TABLE
P Q 𝑷∧𝑸
T T T
T F F
F T F
F F F

The table above indicates that when P and Q are both true, P ∧ Q is true; when P is true and Q is
false, P ∧ Q is false; etc. Note that in this case there are four rows in the table. For a proposition made up of
n elementary propositions, there will be 2 n rows in the truth table because there are two possible truth values
for each of the elementary propositions. This makes it cumbersome to construct truth tables for very
complicated propositions. Nevertheless, we will find them to be a convenient tool.

1.2.2 DISJUNCTION
We next consider propositions of the form P or Q. We have to be a bit more careful defining what we mean
in this case, because the word or can be ambiguous in English.

Let’s consider a couple of English sentences to see why:

• Either it’s Tuesday or it’s raining.
• Do you prefer coffee or tea?

In the first of these sentences we mean that at least one of the two conditions must be met, it’s Tuesday or
it’s raining. If it’s raining on a Tuesday, this proposition is still true. In this case or is inclusive in the sense that it
includes the possibility that both conditions are met.

In the second sentence, we presume that only one of the two options is possible. This use of the word or is
exclusive since it excludes the possibility of both conditions being true at the same time. In normal discourse
this kind of ambiguity doesn’t usually cause any difficulty because we can determine the meaning from the
context. We do not want to allow this kind of ambiguity in logical propositions, so we always use the word or
in the inclusive sense.

In other words, P ∨ Q is true if at least one of P or Q is true.

The disjunction of P and Q is the proposition P or Q, denoted P ∨ Q, which is true whenever at least one of P
or Q is true. Here is a truth table for the proposition P ∨ Q

P Q 𝑷∨𝑸
T T T
T F T
F T T
F F F

1.2.3 IMPLICATION
Most mathematical propositions have the form If P, then Q. Of course, either of P or Q might be propositions
made of several other propositions.

Let’s consider an example: If the student is on the basketball team, then she won’t be in class on Friday.

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

Consider two students in my Friday class, Jill and Pat. We will assume that Jill is on the basketball team and
that Pat is not. Most of us would agree that Jill will not be in class Friday if the statement is true, so if Jill is in
class then the statement must be false. What does the statement tell us about Pat? If she shows up for class
Friday there’s certainly nothing false about the statement, but what if she doesn’t show up for class? Does
that make the statement false? No! The statement makes no claim about Pat, so her attendence or
absence doesn’t impact the truth of the statement.

The proposition If P, then Q is called an implication and is denoted P ⇒ Q. The proposition P is the hypothesis
of the implication and Q is the conclusion. The implication is false only when P is true and Q is false. Here is a
truth table for P ⇒ Q.
P Q 𝑷⇒𝑸
T T T
T F F
F T T
F F T
As a student of mathematics, it is absolutely essential that you understand what an implication means and
what it doesn’t mean. To say that P ⇒ Q is true does not mean that P is true or that Q is true, it does mean
that there is a relationship between the truth values of these two propositions. The implication P ⇒ Q is false
when P is true and Q is false; it is true when either P is false or Q is true. There are several related implications
related to the implication P ⇒ Q that we will occasionally find these useful. Be aware that these are not all
equivalent.

For the implication P ⇒ Q: (variations of the conditional)

• The converse is Q ⇒ P.
• The contrapositive is ¬Q ⇒ ¬P.
• The inverse of is ¬P ⇒ ¬Q

1.2.4 LOGICAL EQUIVALENCE

Two propositions P and Q are said to be logically equivalent if they always have the same truth value. We
use the connective iff, read “if and only if,” and use the symbol ⇔. The proposition P ⇔ Q is true when P and
Q have the same truth value.

P Q 𝑷⇔𝑸
T T T
T F F
F T F
F F T

1.2.5 NEGATION
The negation of P, denoted ¬P and sometimes read “not P,” is the proposition whose truth value is always
opposite that of P.
Note that negation is not actually a connective since it applies to a single proposition rather than
connecting two propositions.

P ¬P
T F
F T

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

FINDING THE TRUTH VALUES
1. Construct a table for ~(~𝑝 ∨ 𝑞) ∨ 𝑞.
Solution:

Step 1: Negate p.
p q ~𝒑
T T F
T F F
F T T
F F T
Step 2: Perform ~𝒑 ∨ 𝒒 by comparing the highlighted columns.

p q ~𝒑 ~𝒑 ∨ 𝒒
T T F T
T F F F
F T T T
F F T T
Step 3: Negate (~𝒑 ∨ 𝒒).

p q ~𝒑 ~𝒑 ∨ 𝒒 ~(~𝒑 ∨ 𝒒)
T T F T F
T F F F T
F T T T F
F F T T F

Step 4: Compare the highlighted columns. (disjunction)

p q ~𝒑 ~𝒑 ∨ 𝒒 ~(~𝒑 ∨ 𝒒) ~(~𝒑 ∨ 𝒒) ∨ 𝒒
T T F T F T
T F F F T T
F T T T F T
F F T T F F

Alternative Procedure

STEPS 4 2 3 1 5 1
p q ~ (~𝒑 ∨ 𝒒) ∨ 𝒒
T T F F T T T T
T F T F F F T F
F T F T T T T T
F F F T T F F F

Step 1: Copy the truth values for q.

Step 2: Start with the simplest operation, negate p.
Step 3: Since ~𝒑 ∨ 𝒒 is grouped, perform the operation by comparing columns from step 1 and 2.
Step 4: Negate the answer from step 3.
Step 5: Compare the answers from step 4 and the truth values of q.

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

2. Use the truth table to determine the truth value of ~(~𝑝 ∨ 𝑞 ) ∨ 𝑞 given that p is true and q is false.
Solution: When p is true and q is false, the truth value of ~(~𝑝 ∨ 𝑞 ) ∨ 𝑞 is TRUE.
p q ~𝒑 ~𝒑 ∨ 𝒒 ~(~𝒑 ∨ 𝒒) ~(~𝒑 ∨ 𝒒) ∨ 𝒒
T T F T F T
T F F F T T
F T T T F T
F F T T F F

3. Construct a truth table for (𝑝 ∧ 𝑞 ) ∧ (~𝑟 ∨ 𝑞).

Solution:
Since there are three propositions (p, q, and r), the number of rows of the truth table is determined
by 23 = 8 rows.
p q 𝒓 𝒑 ∧ 𝒒 ~𝒓 ~𝒓 ∨ 𝒒 (𝒑 ∧ 𝒒) ∧ (~𝒓 ∨ 𝒒).
T T T T F T T
T T F T T T T
T F T F F F F
T F F F T T F
F T T F F T F
F T F F T T F
F F T F F F F
F F F F T T F

4. Use the truth table from number 3 to determine the truth value of (𝑝 ∧ 𝑞 ) ∧ (~𝑟 ∨ 𝑞 ), given that p is
true, q is true, and r is false.
p q 𝒓 𝒑 ∧ 𝒒 ~𝒓 ~𝒓 ∨ 𝒒 (𝒑 ∧ 𝒒) ∧ (~𝒓 ∨ 𝒒).
T T T T F T T
T T F T T T T
T F T F F F F
T F F F T T F
F T T F F T F
F T F F T T F
F F T F F F F
F F F F T T F

Alternative Solution:
Determine the truth value of (𝑝 ∧ 𝑞 ) ∧ (~𝑟 ∨ 𝑞 ), given that p is true, q is true, and r is false.
Given:
𝑝=𝑇 𝑞=𝑇 𝑟=𝐹

(𝑝 ∧ 𝑞 ) ∧ (~𝑟 ∨ 𝑞 ) = (𝑇 ∧ 𝑇) ∧ (~𝐹 ∨ 𝑇) substitute the truth values

(𝑝 ∧ 𝑞 ) ∧ (~𝑟 ∨ 𝑞 ) = (𝑇) ∧ (𝑇 ∨ 𝑇) simplify the operations inside the grouping
symbols
(𝑝 ∧ 𝑞 ) ∧ (~𝑟 ∨ 𝑞 ) = (𝑇) ∧ (𝑇) perform the operations until one truth value
remains
(𝒑 ∧ 𝒒) ∧ (~𝒓 ∨ 𝒒) = 𝑻 final answer

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

EXERCISE 1.2.2 DATE: ________________
A. Construct truth tables for the following:
1. (𝑝 ∧ 𝑞) ⇒ (~𝑝 ∨ 𝑞)

p q
T T
T F
F T
F F

2. 𝑝 ∨ [~(𝑝 ∨ 𝑞 )]

p q
T T
T F
F T
F F

3. (~𝑟 ∨ 𝑞) ∧ (~𝑝 ∧ ~𝑞)

p q 𝒓
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

 B. Determine the truth value of the following, given that 𝒑 = 𝑻, 𝒒 = 𝑭, 𝒓 = 𝑻, 𝒔 = 𝑭.

1. 𝑝 ⟸ ~(𝑞 ∨ 𝑟) 2. ~{𝑠 ∨ [(𝑝 ∨ 𝑞 ) ⇔ ~𝑟]}

3. 𝑝 ⇒ [(~𝑟 ∧ 𝑠) ∨ 𝑠] 4. ~{~[~𝑞 ∧ ~𝑝] ∨ 𝑠} ∨ (~𝑟 ⇔ 𝑠)

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

 1.2.6 TAUTOLOGY AND CONTRADICTION
A tautology is a proposition that is always true, regardless of the truth values of the elementary propositions
that make it up.
A contradiction is a proposition that is always false.
Examples:
1. The proposition P ∨ ¬P is an example of a tautology. One way to see this is to look at a truth table.
Notice that all truth values in the column for P ∨ ¬P are true.
We can also use this truth table to see that P ∧ ¬P is a contradiction because every truth value in
that column is false.
𝒑 ~𝒑 𝒑 ∧ ~𝒑 𝒑 ∨ ~𝒑
T F F T
F T F T
2. P ⇒ (P ∨ Q)
𝑷 𝑸 𝑷∨𝑸 𝑷 ⇒ (𝑷 ∨ 𝑸)
T T T T
T F T T
F T T T
F F F T

Therefore, 𝑃 ⇒ (𝑃 ∨ 𝑄) is a tautology.
3. (P ⇒ Q) ⇔ (¬Q ⇒ ¬P)
𝑷 𝑸 (𝑷 ⟹ 𝑸) ⟺ (~Q ⟹ ~P)
T T T T F T F
T F T F T F F
F T T T F T T
F F F F T T T
Therefore, (𝑃 ⇒ 𝑄) ⟺ (~𝑄 ⟹ ~𝑃) is NOT a tautology.

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

EXERCISE 1.2.3 DATE: ________________
Determine whether each of the following is a tautology, a contradiction, or neither one.
1. (𝑃 ⇒ 𝑄) ⇒ 𝑄

2. (𝑃 ∧ (𝑃 ⇒ 𝑄)) ⇒ 𝑄

3. (𝑃 ⇒ 𝑄) ⇔ (𝑄 ⇒ 𝑃)

4. ((𝑃 ⇒ 𝑄) ∧ (𝑄 ⇒ 𝑅)) ⇒ (𝑃 ⇒ 𝑅)

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

1.3 PREDICATES, INSTANTIATION, AND QUANTIFICATION
We return our attention now to statements that involve variables, like x + 3 = 12. Such a statement is called a
predicate and we will usually indicate it with P(x) rather than P. Before a predicate takes on a truth value,
we need to know something about the variable.
We noted before that if x = 0, then the statement is false; but if x = 9, then the statement is true. What if x
represents my desk? In that case, the statement is complete nonsense, but you probably feel like there’s
something a little bit unfair about that choice for x. We see an equation and usually think that the variable
must represent a number, right? The first thing you should know about any variable in a predicate is what it
can represent. This is called the universe or the domain of discourse. In mathematics, we will be very explicit
about what universe we are talking about.

1.3.1 INSTANTATION
Instantiation means choosing a particular value for the variable(s). Consider this example: Let x = 2, then x +
3 = 12. In this case the sentence is a proposition with truth value F.

1.3.2 UNIVERSAL QUANTIFICATION

A universal quantifier indicates that the predicate is true for all instances of the variable in the given
universe. It is typically indicated by using the phrase “for every” or “for all,” and can be denoted
symbolically by ∀ in symbolic statements.

The following sentences are universally quantified propositions. Only the second is true.
• For every real number x, x + 3 = 12.
• The square of x is nonnegative for all real x.
• The square of x is nonnegative for all complex x

1.3.3 EXISTENTIAL QUANTIFICATION

An existential quantifier indicates that the predicate is true for at least one instance of the variable in the
given universe. It is typically indicate by the phrase “for some” or “there exists,” and can be denoted by ∃ in
symbolic statements.

The following sentences are existentially quantified. All three of these are true.
• There is a real number x so that x + 3 = 12.
• The square of x is nonnegative for some real x.
• The square of x is nonnegative for some complex x.

1.3.4 SYLLOGISMS AND VENN DIAGRAMS

A syllogism is a form of logical argument that deduces a conclusion based on two premises. For example:

All men are mortal. Socrates is a man. Hence Socrates is mortal.

This is a valid syllogism. If we assume that the premises are true, then the conclusion must follow.

One tool we can use to help think about syllogisms is a Venn diagram, which in its simplest form is a
collection of circles that represent the various categories in the premises. In this case we will have one circle
representing mortals and another representing man. Since one of our premises is that all men are mortal,
the circle representing men is completely contained inside the circle representing mortals:

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

Since Socrates is a man, hence inside the circle representing men, he must of necessity also be inside the
circle representing mortals, hence the syllogism is valid.

Examples:
Determine whether each of the following syllogisms is valid.
1. Some students are freshmen. Pat is a student. Hence Pat is a freshman.

The circle for students should overlap the circle for freshmen, but
need not be contained within it since our assumption is that only
some students are freshmen.

Note that Pat may be in the student circle without being inside
the freshmen
circle, so the syllogism is not valid.

2. No cats are dogs. Jade is a cat. Hence Jade is not a dog.

In this case, the circle for cats should be completely outside the
circle for dogs since no cats are dogs.
Since Jade must be within the cats circle, Jade cannot be within
the dogs circle, so the syllogism is valid.

3. Some cats are psychopaths. Jawa is a cat. Hence Jawa is a psychopath.

Since Jawa must be in the cats circle, but may or may not be
within the psychopaths circle, this syllogism is not valid.

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

 4. Some Billywiggles are Bleepzigs. Some Bleepzigs are Jabberwoks. Hence some Billywiggles are
Joabberwoks

This requires a slightly more complicated Venn diagram, and we must be very careful about what is
absolutely necessary. This syllogism is not valid

1.3.5 QUANTIFICATION OF SEVERAL VARIABLES

A predicate can have two or more variables. In order to use the predicate in a proposition, a universe must
be declared for each variable and each variable must be instantiated or quantified. We will discuss the
various ways a two variable predicate might be quantified by considering an example.

We consider the predicate P(x, y) given by x + y = 0. Throughout, we will assume that the universe for both x
and y is the set of real numbers. Without redefining the universe every time, variables could be universally
quantified, both could be existentially quantified, or one could be universally quantified and the other
existentially quantified. We are particularly interested in determining when each proposition will be true and
whether the order of the quantifiers matters.

• ∀𝑥 ∀𝑦 𝑃(𝑥, 𝑦): This proposition can be read as for all (real) x and for all (real) y, x + y = 0, which says
the sum of any two real numbers is 0. Clearly this is false.
• ∀𝑦 ∀𝑥 𝑃(𝑥, 𝑦): Restating this as we did above, it is not difficult to see that this proposition is equivalent
to the first one.
• ∃𝑥 ∃𝑦 𝑃(𝑥, 𝑦): We can read this as there is an x so that there is a y so that x + y = 0, which says that
there are real numbers x and y such that x + y = 0. This is true. Once again, reversing the order of the
quantifiers doesn’t matter.
• ∀𝑥 ∃𝑦 𝑃(𝑥, 𝑦): This proposition says that for every x there is a y such that x + y = 0, in other words every
real number has an additive inverse, which is certainly true.
• ∃𝑦 ∀𝑥 𝑃(𝑥, 𝑦): The variables here are quantified the same, but the order is changed. Does that
matter? The proposition this time says there is a y so that for all x, x + y = 0. In other words, there is
some real number y so that adding any real number to y yields a sum of 0, which is certainly false!

The moral of the last example is that you must be careful to quantify variables in the correct order when
some variables are universally quantified and some are existentially quantified

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

EXERCISE 1.3 DATE: ________________
Determine whether or not each of the syllogisms is valid. Use venn diagrams to support your answer.
_______1. Some dogs are beagles. Snoopy is a dog. Hence Snoopy is a beagle.
_______2. All cats are independent. Some pets are cats. Hence some pets are independent.
_______3. No pigs fly. Porky is a pig. Hence Porky does not fly.
_______4. No orcs are ogres. All ogres are green. Hence no orcs are green
_______5. No squares are triangles. Some triangles are equilateral. Hence, no squares are equilateral.
_______6. Some students like History. Venn is a student. Thus, Venn likes History.
_______7. Cheaters fail the subject. I am not a cheater. Therefore, I will not fail.
_______8. All grass is green. That ground cover is not green. Thus, the ground cover is not grass.
_______9. All prime numbers are odd. 2 is a prime number. Thus, 2 is an odd number.
_______10. No even numbers are odd numbers. 5 is an odd number. Therefore 5 is even.
1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

1.4 NEGATIONS
As mentioned previously in [1.2.5], the negation of a proposition is the proposition with the opposite set of
truth values. In this section we are going to discuss the negations of compound propositions, which can be
an important step in some kinds of proofs. We begin with two theorems that tell how to find the negations of
propositions involving connectives.

Theorem 1.1. Given any propositions 𝑝 and 𝑞, ¬(𝑃 ⇒ 𝑄) ⇔ (𝑃 ∧ ¬𝑄).

To see that this theorem is true, we first make sure that we understand what it is saying. The variables in this
case are actually propositions P and Q, both of which are universally quantified. The theorem asserts that
the compound proposition ¬(𝑃 ⇒ 𝑄) ⇔ (𝑃 ∧ ¬𝑄) is always true, so we must demonstrate that no matter
what the truth values of P and Q are, the statement in the theorem is a tautology.

We proceed by constructing a truth table.

The truth of the next theorem can be established in a similar fashion, which we leave to the exercises.

Theorem 1.2. (DeMorgan’s Laws)

Given any propostions P and Q:
(i) ¬(𝑃 ∧ 𝑄) ⇔ (¬𝑃 ∨ ¬𝑄)
(ii) ¬(𝑃 ∨ 𝑄) ⇔ (¬𝑃 ∧ ¬𝑄)
We can use these results to understand the negations of more complicated propositions. Suppose we want
to know how to negate the proposition P ⇒(Q ∧ R). We apply what we know one step at a time, beginning
with the implication:
¬ 𝑃 ⇒ (𝑄 ∧ 𝑅) ⇔ 𝑃 ∧ ¬(𝑄 ∧ 𝑅) Theorem 1.1
⇔ 𝑃 ∧ (¬𝑄 ∨ ¬𝑅) Theorem 1.2 (i)

Example:
Find the negation of each of the following propositions.
1. 𝑃 ∧ (𝑄 ⇒ 𝑅)

We apply Theorems 1.1 and 1.2 where indicated.

¬ 𝑃 ∧ (𝑄 ⇒ 𝑅) ⇔ ¬𝑃 ∨ ¬(𝑄 ⇒ 𝑅) (Theorem 1.2(i))
⇔ ¬𝑃 ∨ (𝑄 ∧ ¬𝑅) (Theorem 1.1)

2. (𝑃 ∨ 𝑄) ∧ (𝑃 ∨ 𝑅)

We apply Theorem 1.2 where indicated.

¬ (𝑃 ∨ 𝑄) ∧ (𝑃 ∨ 𝑅) ⇔ ¬(𝑃 ∨ 𝑄) ∨ ¬(𝑃 ∨ 𝑅) (Theorem 1.2(i))
⇔ (¬𝑃 ∧ ¬𝑄) ∨ (¬𝑃 ∧ ¬𝑅) (Theorem 1.2(i,ii))

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r

EXERCISE 1.4 DATE: ________________
A. Negate each of the following:
1. Every cloud has a silver lining.

2. If it’s Tuesday, this must be Belgium.

3. There is a light at the end of every tunnel.

B. Negate the following propositions:

1. (𝑃 ∨ 𝑄) ⟹ (𝑃 ⟹ ~𝑅)

2. 𝑃 ⇒ (~𝑄 ⇒ ~(𝑃 ⋀ ~𝑅))

3. ~(𝑄 ∨ ~𝑅) ∧ (𝑃 ∧ 𝑅)

BSE M 2 5 : Log ic a nd Set T h eor y | A.B. Ag uila r