CHAPTER 1

LOGIC AND PROOF

1. Propositional Logic

Proposition is a declarative sentence, or a sentence that declares a fact, that is either true or false
but not both.

Examples of propositions:

a. The town of Isabel is found in Leyte.

b. Engr. Roy Roger B. Jaime is teaching IT 102.
c. The students attending this class are education major.
d. The current mayor of this town is Hon. Richard Gomez.

It can be observed that examples A and B are true, while examples C and D are false.

Examples of non-propositions:

a. When is your birthday?

b. Jump.
c. X+1=2
d. X+Y=Z

Examples A and B are not proposition because they are not declarative sentences. Examples C and
D are not proposition because they are neither true nor false. If a value is assigned to the variables
of examples C and D then they can be turned into propositions.

It is common to denote a propositional variables or statement variables with letters except T and F.
T is used to denote a “TRUE” truth value of a proposition, while F is used to denote a “FALSE” truth
value of a proposition.

The area of logic that deals with propositions is called the propositional calculus or propositional
logic. It was first developed systematically by the Greek philosopher Aristotle more than 2300 years
ago.

Many mathematical statements are constructed by combining one or more propositions. New
propositions, called compound propositions, are formed from existing propositions using logical
operations.

Definition 1: Let p be a proposition. The negation of p, which can be denoted by –p or p’, is

the statement

“It is not the case that p.”

The proposition –p or p’ is read “not p”. The truth value of the negation of p is the opposite of the
truth value of p.

The truth table of negation

P -p
F T
T F

Example: Find the negation of the proposition “Today is Friday.” And express it in plain English.

Solution: The negation is “It is not the case that today is Friday” and this can be simply expressed
as “Today is not Friday” or “It is not Friday today.”
The negation operator constructs a new proposition from a single existing proposition.

Connectives are logical operators that are used to form new propositions from two or more existing
propositions.

Definition 2: Let p and q be propositions. The conjunction p and q, denoted by p Λ q, is the

proposition “p and q”. The conjunction p Λ q is true when both p and q are true
and is false otherwise.

The truth table for the conjunction of two propositions

p q pΛq
F F F
F T F
T F F
T T T

Example: Find the conjunction of the propositions p and q where p is the proposition “Today is
Friday” and q is the proposition “It is raining today”.

Solution: The conjunction of these propositions, p Λ q, is the proposition “Today is Friday and it is
raining today.” This proposition is true on rainy Fridays and is false on any day that is
not a Friday and on Fridays when it does not rain.

Note that the logic word “but” sometimes is used instead of “and” in a conjunction.

Definition 3: Let p and q be propositions. The disjunction of p and q, denoted by p V q, is the

proposition “p or q”. The disjunction p V q is false when both p and q are false
and is true if otherwise.

The truth table of the disjunction of two propositions

p q pVq
F F F
F T T
T F T
T T T

Example: What is the disjunction of the propositions p and q where p is the proposition “Today is
Friday” and q is the proposition “It is raining today”?

Solution: The disjunction of p and q, p V q, is the proposition “Today is Friday or it is raining

today.”

This proposition is true on any day that is either a Friday or a rainy day, including rainy Fridays. It is
only false on days that are not Fridays when it also does not rain. This is the inclusive way of using
the connective or in a disjunction, or “inclusive or”.

On the other hand, we are using the exclusive or when we say “Today is Friday or is raining, but not
both.” Here, we mean that today is Friday or is raining but not a rainy Friday.

Definition 4: Let p and q be propositions. The exclusive or of p and q, denoted by p q, is

the proposition that is true when exactly on of p and q is true and is false
otherwise.
The truth table for the exclusive or of two propositions

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

 Other ways in which a proposition is combined:

Definition 5: Let p and q be propositions. The conditional statement p  q is the proposition

“if p, then q”. The conditional statement p  q is false when p is true and q is
false, and true otherwise. In the conditional statement p  q, p is called the
hypothesis (or antecedent or premise) and q is called the conclusion (or
consequence).

The statement p  q is called a conditional statement because p  q asserts that q is true on

the condition that p holds. A conditional statement is also called an implication.

The truth table for the conditional statement p  q is shown below. Note that the statement p
 q is true when both p and q are true and when p is false (no matter what truth value q has).

p q pq
F F T
F T T
T F F
T T T

Because conditional statements play such an essential role in mathematical reasoning, a variety
of terminology is used to express p  q. We will encounter most if not all of the following ways
to express this conditional statements:

“if p, then q” “if p, q” “p is sufficient for q”

“q if p” “q when p” “a necessary condition for p is
q”
“q unless –p” “p implies q” “p only if q”
“q whenever p” “q is necessary for p” “a sufficient condition for q is
p”
“q follows from p”

Example: Let p be the statement “Maria learns discrete mathematics” and q the
statement “Maria will find a good job”. Express the statement p  q as a
statement in English.

Solution: From the definition of conditional statement, p  q represensts the statement

“If Maria learns discrete mathematics, then she will find a good job.”

There are many other ways to express this conditional statement in English.

A useful way to understand the truth value of a conditional statement is to think of an obligation
or a contract.

We can form some new conditional statements starting with a conditional statement p  q. In
particular, there are three related conditional statements that occur so often that they have
special names.
a. The proposition q  p is called the converse of p  q.
b. The proposition –q  -p is called the contrapositive of p  q.
c. The proposition –p  -q is called the inverse of p  q.

It can be shown that the contrapositive of a conditional statement always has the same truth
value as to the original conditional statement. It can also be shown that neither the converse
nor the inverse of a conditional statement has the same truth value of the original conditional
statement.

When two compound propositions always have the same truth value we call them equivalent,
so that a conditional statement and it contrapositive are equivalent. The converse and inverse
of a conditional statement are also equivalent but not equivalent to the original conditional
statement.

Example: What are the contrapositive, the converse, and the inverse of the conditional
statement “The home team wins whenever it is raining”?

Solution: Because “q whenever p” is one of the ways to express the conditional statement
p  q, the original statement can be rewritten as “If it rains, then the home
team wins.”

Consequently, the contrapositive of this conditional statement is “If the home

team does not win, then it is not raining.”

The converse is “If the home team wins, then it is raining.”

The inverse is “If it is not raining, then the home team wins.”

Definition 6: Let p and q be propositions. The biconditional statement p ↔ q is the

proposition “p if and only if q”. The biconditional statement p ↔ q is true when
p and q have the same truth values, and is false otherwise. Biconditional
statements are also called bi-implications.

The truth table of biconditional statement is shown below:

p Q p↔q
F F T
F T F
T F F
T T T

Note that the statement p ↔ q is true when both the conditional statements p  q and q  p
are true and is false otherwise. That is why we use the words “if and only if” to express this
logical connective and why it is symbolically written by combining the symbols  and . There
other ways to express p ↔ q:

“p is necessary and sufficient for q”

“if p then q, and conversely”
“p iff q”

The last way of expressing biconditional statements p ↔ q uses the abbreviation “iff” for “if and
only if”. Note that p ↔ q has exactly the same truth value as (p  q) Λ (q  p).

Example: Let p be the statement “You can take the flight” and let q be the statement “You
buy a ticket.” Then p ↔ q is the statement “You can take the flight if and only if
you buy a ticket.”
 This statement is true if p and q are either both true or both false, that is, if you buy a ticket and
can take the flight or if you do not buy a ticket and you cannot take the flight. It is false when p
and q have opposite truth values, that is, when you do not buy a ticket, but you can take the
flight (such as when you get a free trip) and when you buy a ticket and cannot take a flight (such
as when the airline bumps you).
Exercise:

I. Fill in the blank.

a. _________________________ is a declarative sentence that has either a True truth value or

False truth value.
b. ________________________________ is the area of logic that deals with propositions. It was
first developed systematically by ________________________.
c. ___________________________________ are new propositions formed from existing
propositions using logical operations.
d. _________________________ are logical operators used to form new propositions from two or
more existing propositions.

II. Identification.

Identify the statements which are considered as proposition. If the statement is a proposition, write
Yes then followed by the truth value of the statement on the space provided, otherwise write No.

__________ 1. X+Y=Z
__________ 2. Am I the instructor of ITec 112?
__________ 3. You are a student of VSU Isabel.
__________ 4. Engr. Albert S. Pasana is our chancellor.
__________ 5. X + 3 = 5 if x is equal to -4.

Use the given assumptions to provide what is being asked in Test III and Test IV.

Assumptions:

P = I am a BSIT student of VSU – Isabel.

Q = I am a computer lover.
R = I am not a computer programmer.

III. Creating English propositions.

Express the given expressions to simple English statement. Write the proposition on the space
provided.

1. -P = ___________________________________________________________
2. -Q = ___________________________________________________________
3. -R = ___________________________________________________________
4. P Λ -Q = ___________________________________________________________
5. PVQΛR = _______________________________________________________

IV. Create the expression.

Construct the expression of the proposition given. Write the expression on the space provided.

1. I am not a BSIT student of VSU – Isabel but I am a computer lover.

2. I am a computer programmer for I am a BSIT student of VSU – Isabel.
3. I am either a BSIT student of VSU – Isabel or a computer lover.
4. I am neither a computer programmer or a computer lover.
5. I am not a BSIT student of VSU – Isabel but I am a computer lover and a computer programmer.
Truth table of compound proposition

We have been introduced to four important logical connectives – conjunction, disjunction,

conditional statements and biconditional statements – as well as negations. We can use these
connectives to build up complicated compound propositions involving any number of propositional
variables. We can use truth tables to determine the truth value of these compound propositions.
We use separate columns to find the truth value of each compound expression that occurs in the
compound proposition as it is built up.

Precedence of Logical Operators

1. We generally use parentheses to specify the order in which logical operators in a compound
proposition are to be applied.
2. Conjunction operator takes precedence over the disjunction operator.
3. The conditional and biconditional operators have lower precedence than the conjunction and
disjunction.

Table of precedence of logical operators is shown below:

Precedence Operator
1 Negation
2 Conjunction
3 Disjunction
4 Conditional
5 Biconditional

Logic and bits operations

Computers represent information using bits. A bit is a symbol with two possible values, 0 (zero) and
1 (one). The meaning of the word bit comes from binary logic, because zeros and ones are the digits
used in binary representation of numbers. The well-known statistician John Tukey introduced this
terminology in 1946. A bit can be used to represent a truth value, because there are two truth
values, namely, true and false. As customarily done, we will use a 1 bit to represent true and a 0 bit
to represent false. A variable is called a Boolean variable if its value is either true or false.
Consequently, a Boolean variable can be represented using a bit.

Information is often represented using bits strings, which are lists of zeros and ones. When this is
done, operations on the bit strings can be used to manipulate this information.

Definition: A bit string is a sequence of zero or more bits. The length of the string is the number of
bits in the string.

Example: 101010011 is a bit string of length nine.

We can extend bit operations to bit strings. We can define the bitwise AND, bitwise OR, and bitwise
XOR of two strings of the same length.

Example: Find the bitwise OR, bitwise AND, and bitwise XOR of the bit strings 01 1011 0110 and
11 0001 1101.

Solution: 01 1011 0110

11 0001 1101
------------------
11 1011 1111 bitwise OR
01 0001 0100 bitwise AND
10 1010 1011 bitwise XOR
2. Propositional Equivalence

An important type of steps used in a mathematical argument is the replacement of a statement with
another statement with the same truth value. Because of this, methods that produce propositions
with the same truth value as a given compound proposition are used extensively in the construction
of mathematical arguments.

Definition: A compound proposition that is always true, no matter what the truth values of the
proposition that occur in it, is called a tautology. A compound proposition that is always
false is called a contradiction. A compound proposition that is neither a tautology nor a
contradiction is called a contingency.

Example of Tautology and Contradiction

P P’ P V P’ P Λ P’
F T T F
T F T F

Logical equivalence

Compound proposition that have the same truth values in all possible cases are called logically
equivalent.

Definition: The proposition p and q are called logically equivalent if p ↔ q is a tautology. The
notation p ≡ q denotes that p and q are logically equivalent.

Remark: The symbol ≡ is not a logical connective and p ≡ q is not a compound proposition but
rather is the statement that p ↔ q is a tautology.

One way to determine whether two compound propositions are equivalent is to use a truth table.
In particular, the compound propositions p and q are equivalent if and only if the columns giving
their truth values agree. This logical equivalence is one of the two De Morgan laws, table shown
below, named after the English mathematician Augustus De Morgan, in mid-19th century.

De Morgan’s Laws
(p V q)’ ≡ p’ Λ q’
(p Λ q)’ ≡ p’ V q’

Example: Show that (p V q)’ and p’ V q’ are logically equivalent.

Solution:

P Q PVQ (P V Q)’ P’ Q’ P’ V Q’
F F F T T T T
F T T F T F F
T F T F F T F
T T T F F F F

Because the truth values of the given compound propositions agree for all possible
combinations of the truth values of p and q, if follows that the compound propositions
are logically equivalent.
 Logical Equivalence
Equivalence Name
P Λ T ≡P
Identity law
PVF≡P
PVT≡T
Domination law
PΛF≡F
PVP≡P
Idempotent law
PΛP≡P
(P’)’ Double negation law
PVQ≡QVP
Commutative law
PΛQ≡QΛP
(P V Q) V R ≡ P V (Q V R)
Associative law
(P Λ Q) Λ R ≡ P Λ (Q Λ R)
P V (Q Λ R) ≡ (P V Q) Λ (P V R)
Distributive law
P Λ (Q V R) ≡ (P Λ Q) V (P Λ R)
(P V Q)’ ≡ P’ Λ Q’
De Morgan’s Law
(P Λ Q)’ ≡ P’ V Q’
P V (P Λ Q) ≡ P
Absorption law
P Λ (P V Q) ≡ P
P V P’ ≡ T
Negation law
P Λ P’ ≡ F

Logical Equivalence Involving Logical Equivalence Involving

Conditional Statements Biconditional Statements
P  Q ≡ P’ V Q P ↔ Q ≡ (P  Q) Λ (Q  P)
P  Q ≡ Q’  P’ P ↔ Q ≡ P’ ↔ Q’
P V Q ≡ P’  Q P ↔ Q ≡ (P Λ Q) V (P’ Λ Q’)
P Λ Q ≡ (P  Q’)’ (P ↔ Q)’ ≡ P ↔ Q’
(P  Q)’ ≡ P Λ Q’
(P  Q) Λ (P  R) ≡ P  (Q Λ R)
(P  R) Λ (Q  R) ≡ (P V Q)  R
(P  Q) V (P  R) ≡ P  (Q V R)
(P  R) V (Q  R) ≡ (P Λ Q)  R

Using De Morgan’s Law

Example: Use De Morgan’s Law to express the negation of “Miguel has a cellphone and he has a
laptop computer” and “Heather will go to the concert or Steve will go to the concert”.

Solution: Let p be “Miguel has a cellphone” and q be “Miguel has a laptop computer”. Then
“Miguel has a cellphone and he has a laptop computer” can be represented by p Λ q. By
the first of the De Morgan’s Laws, (p Λ q)’is equivalent to p’ V q’. Consequently, we can
express the negation of the original statement as “Miguel does not have a cellphone or
he does not have a laptop computer.”

Let r be “Heather will go to the concert” and s be “Steve will go to the concert”. Then
“Heather will go to the concert or Steve will go to the concert” can be represented by
p V q. By the second of the De Morgan’s laws, (p V q)’ is equivalent to p’ Λ q’.
Consequently, we can express the negation of the original statement as “Heather will
not go to the concert and Steve will go to the concert.”

Constructing New Logical Equivalence

Example: Show that (p  q)’ and p Λ q’ are logically equivalent.

Solution: (p  q)’ ≡ (p’ V q)’ logical equivalence involving conditional statement

 ≡ (p’)’ Λ q’ second De Morgan’s law
≡ p Λ q’ double negation law
Example: Show that (p V (p’ Λ q))’ and p’ Λ q’ are logically equivalent by developing a series of
logical sequence.

Solution: (p V (p’ Λ q))’ ≡ p’ Λ (p’ Λ q)’ second De Morgan’s law

≡ p’ Λ ((p’)’ V q’) first De Morgan’s law
≡ p’ Λ (p Λ q’) double negation law
≡ (p’ Λ p) V (p’ Λ q’) second distributive law
≡ F V (p’ Λ q’) (p’ Λ p) ≡ F
≡ (p’ Λ q’) V F commutative law of disjunction
(p V (p’ Λ q))’ ≡ p’ Λ q’ identity law for F

Consequently (p V (p’ Λ q))’ and p’ Λ q’ are logically equivalent.

Example: Show that (p Λ q)  (p V q) is a tautology.

Solution: (p Λ q)  (p V q) ≡ (p Λ q)’ V (p V q) logical equivalence of conditional

Statement
≡ (p’ V q’) V (p V q) first de Morgan’s law
≡ (p’ V p) V (q’ V q) associative and commutative law of
Disjunction
≡ TVT Truth table of disjunction
≡ T

3.