Module 1

Logic: Propositions, Connectives, Truth Tables,

Logical Equivalences, Logic Gates

Math006 – Discrete Mathematics

Intended Learning Outcomes (ILOs)
•Construct logic circuits
•Apply Bit String Operation in finding compound proposition
•Transform conditional statements to symbols
•Convert conditional statements to converse, contrapositive, inverse,
biconditonal proposition

Contents
•Logic Gates
• Bit String Operation
•Conditional Proposition
• Converse
• Contrapositive
• Inverse
• Biconditional
1.1 Logic, Propositions and Predicates

Logic and mathematical reasoning has numerous applications in

computer science. Rules in logic are used in the design of computer
circuits, the development of computer programs, the verification of
the correctness of programs and many other ways.

Logic is the basis of all mathematical reasoning, and it has

a practical applications to the design of computing
machines, to artificial intelligence, to computer
programming, to programming languages and to other areas
of computer science.
1.1 Logic, Propositions and Predicates

Propositional calculus is the study of the logical

relationships between statements called propositions, which
are usually interpretable as meaningful assertions in real-life
contexts.

Propositions are declarative sentences that are either true

or false but not both. (Theory, hypothesis, thesis,
argument, premise, principle, theorem, concept, idea,
statement.)
1.1 Logic, Propositions and Predicates

Examples of propositions:

1. 2 + 5 = 9 (F)
2. 5 is a prime number. (T)
3. 7 is a prime number, but 6 is not. (T)
4. Every natural number can be written as the sum of the
squares of three natural numbers. (F)
5. He is over 5 ft. tall. (TorF depends on who are you referring to.)
1.1 Logic, Propositions and Predicates

The following sentences are not propositions

Examples:

Your property or mine?

Oh my gosh! You are so handsome!
Go directly to him.
Certainly, why not?
4–x=5
a–b=b–a
1.1 Logic, Propositions and Predicates

The area of logic that deals with propositions is called propositional

logic. The bases for propositional logic are the three laws of
Aristotelian logic.

Law of Identity. “A thing is itself.”

Law of Excluded Middle. “A statement is either true or false
but not both.”
Law of Non-Contradiction. “No statement is both true or
false.”
1.1 Logic, Propositions and Predicates

Statements that include variables and that become propositions

upon substitution of values for those variables are called predicates
or propositional functions.

A predicate is also defined as sentence that contains a finite number

of variables and becomes a statement when specific values are
substituted for the variables.

The domain of a predicate variable is the set of all values that may
be substituted in place of the variable.
1.1 Logic, Propositions and Predicates

Predicates may involve more than one variable such as in the

following:

1. x+y > 2

2. x+y = 1

3. x^2+y^2 = z^2
1.1 Logic, Propositions and Predicates

The truth set of a predicate is the set of values of its variable or

variables for which the proposition is true.

Examples

1. f( x ) = x 2 ≤ x , for some integer x(TRUE)

2. f ( x ) = 3 x < 82 , x is a positive integer N.(FALSE)

3. f ( x ) = 2 x < 65 , x is any whole number W.(FALSE)

1.2: Logical Connectives and Truth Table
The logical operators that are used to form new propositions from
two or more existing propositions are called connectives.

In mathematics, the letters x, y, z, p, q, r often denote variables that

can be replaced by the real numbers, and these variables can be
combine with the familiar operations .

In logic, the letters x, y, z, p, q, r denote propositional variables that

is, that can be replaced by statements.

Compound statements – statements or propositional variables

combined by logical connectives.
1.2: Logical Connectives and Truth Table
The truth values of a proposition built up from other propositions by
using required connectives which are respectively determined by the
truth values of the original propositions and the way the proposition
is built up from them.

The decision of accepting or rejecting a statement depends on the

truth values of a proposition. An acceptable statement is given a
decision value or truth value “TRUE” and an unacceptable
statement is given a decision value “FALSE”.

Most logicians symbolize truth values as T or F (for true or false),

while others symbolize them as 1 or 0 (for true or false).
1.2: Logical Connectives and Truth Table
1.2: Logical Connectives and Truth Table
NEGATION
Definition: Let p be a proposition. The statement “It is not the case that
p” is another proposition called the negation of p, denoted by ~p . The
proposition ~p is read as “not p”.
The proposition ~p should not be true exactly when p is true and vice The Truth Matrix of the
versa. Negation of a Proposition
Examples: Write the negation of the following propositions:
p ¬p
1.5 is positive. T F
It is not the case that 5 is positive or 5 is not positive.
[Link] air in Metro Manila is polluted. F T
It is not the case that the air in Metro Manila is polluted or
The air in Metro Manila is not polluted.
3. 2 + 1 > 5
It is not the case that 2 + 1 > 5 or 2+1<5
1.2: Logical Connectives and Truth Table
NEGATION
Definition: Let p be a proposition. The statement “It is not the case that
p” is another proposition called the negation of p, denoted by ~p . The
proposition ~p is read as “not p”.
The proposition ~p should not be true exactly when p is true and vice The Truth Matrix of the
versa. Negation of a Proposition
Examples: Write the negation of the following propositions:
p ¬p
1.5 is positive. T F
It is not the case that 5 is positive or 5 is not positive.
[Link] air in Metro Manila is polluted. F T

3. 2 + 1 > 5
 1.2: Logical Connectives and Truth Table
CONJUNCTION

Definition: Let p and q be propositions. The proposition “ p and q”

denoted by p ∧ q, is the proposition that is true when both P and Q are true
and is false otherwise. The proposition p ∧ q is called the conjunction of P
The Truth Matrix for the
and Q. Conjunction of Two Propositions

p q p∧q
Other ordinary language conjoiners besides "and" include some uses of
"but," "although," "however "yet," and "nevertheless." T T T
T F F
Examples: Write the conjunctions of the following propositions. F T F
F F F
p: 2 is an even integer ; q: 3 is an odd integer.
“2 is an even integer and 3 is an odd integer.”
There is only one
condition p ∧ q to be
p: 3 divides 9; q: 3 divided 15 TRUE and this is when both
”3 divides 9 and 3 divides 15” or “3 divides both 9 and 15” statements are true.
1.2: Logical Connectives and Truth Table

DISJUNCTION

Definition: Let p and q be propositions. The proposition “ p or q” denoted by p ∨ q, is the

proposition that is false when both p and q are false and true otherwise. The proposition p ∨ q is
called the disjunction of p and q.

Examples: Write the disjunction of the following propositions.

p: Students who have taken algebra can take Discrete Mathematics.

q: Students who have taken computer science can take Discrete Mathematics.

Students who have taken algebra or computer science can take Discrete Mathematics.
1.2: Logical Connectives and Truth Table

DISJUNCTION

p: John is at the Library. q: John is studying.

John is at the library or John is studying. or John is at the library or he is

studying.

The Truth Matrix for the Disjunction of Two

Propositions
p q p∨q
This means that the disjunction
T T T of two statements is TRUE if at
T F T least one of the statements is
F T T true.
F F F
1.2: Logical Connectives and Truth Table

Let p and q be propositions

p: Cristina is a computer engineering major.

q: Leonardo is an Information Technology major.

Express each of these propositions as an English sentence:

a. ¬ q

b. b. ¬ p ∧ q
1.2: Logical Connectives and Truth Table

Let p and q be propositions

p: Keranki is a secret agent.

q: Light is a criminal.

Express each of these propositions as an English sentence:

a. ~q ^ p

b. b. ¬ p v ~q
1.3: Logic Gates
A logic gate is an elementary building block of a digital circuit. Most logic gates have two
inputs and one output. At any given moment, every terminal is in one of the two binary
conditions low (0) or high (1), represented by different voltage levels.

There are seven basic logic gates: AND, OR, XOR, NOT, NAND, NOR, and XNOR.

AND GATE
The AND gate is so named because, if 0 is called Truth Table for AND Gate
"false" and 1 is called "true," the gate acts in the same
A B A∧B
way as the logical "and" operator.
T T T
T F F
F T F
(In the symbol, the input terminals are at left and the
F F F
output terminal is at right.) The output is "true" when
both inputs are "true." Otherwise, the output is "false."
1.3: Logic Gates

OR GATE

The OR gate gets its name from the fact that it

behaves after the fashion of the logical inclusive Truth Table for OR Gate
"or." The output is "true" if either or both of the
inputs are "true." If both inputs are "false," then A B A∧B
the output is "false." T T T
T F T
F T T
F F F
1.3: Logic Gates

NOT GATE

A logical inverter , sometimes called a NOT gate

to differentiate it from other types of electronic Truth Table for NOT Gate
inverter devices, has only one input. It reverses
the logic state. A ¬A

T F
F T
1.3: Logic Gates
Draw the logic gate representation and determine the truth table of the of the logic expression

X = (p v~q) ^ (~p)
1.3: Logic Gates
Draw the logic gate representation and determine the truth table of the of the logic expression

X = (p v ~q) ^ (q v r)
1.3: Logic Gates

XOR GATE

The XOR ( exclusive-OR ) gate acts in the same

way as the logical "either/or." The output is Truth Table for XOR Gate
"true" if either, but not both, of the inputs are
"true." The output is "false" if both inputs are A B
"false" or if both inputs are "true." Another T T F
way of looking at this circuit is to observe that the
T F T
output is true if the inputs are different, but false
if the inputs are the same. F T T
F F F
1.3: Logic Gates

NAND GATE

The NAND gate operates as an AND

gate followed by a NOT gate. It acts in Truth Table for XOR Gate
the manner of the logical operation "and" A B ~(A ∧ B)
followed by negation. The output is
T T F
"false" if both inputs are "true."
T F T
Otherwise, the output is "true."
F T T
F F T
1.3: Logic Gates

NOR GATE

The NOR gate is a combination OR gate

followed by an inverter. Its output is Truth Table for XOR Gate
"true" if both inputs are "false." A B ~(A V B)
Otherwise, the output is "false."
T T F
T F F
F T F
F F T
1.3: Logic Gates

XNOR GATE

The XNOR (exclusive-NOR) gate is a

combination XOR gate followed by an Truth Table for XOR Gate
inverter. Its output is "true" if the A B
inputs are the same, and "false" if the
T T T
inputs are different.
T F F
F T F
F F T
1.3: Logic Gates
Draw the logic gate representation and determine the truth table of the of the logic expression

𝐗 = ~[~ 𝒂 ∨ 𝒃 ⊕ ~(𝒃 ∧ ~𝒄)]

1.4: Bit String Operators
Bitwise AND operator &
The output of bitwise AND is 1 if the corresponding bits of two operands is 1. If either bit of an operand is 0,
the result of corresponding bit is evaluated to 0.

Example:
1.4: Bit String Operators
Convert decimal to binary (2^n)
1.4: Bit String Operators
Bitwise OR operator |
The output of bitwise OR is 1 if at least one corresponding bit of two operands is 1. In C Programming,
bitwise OR operator is denoted by |.
Example:
1.4: Bit String Operators
Bitwise XOR (exclusive-OR) operator ^
The result of bitwise XOR operator is 1 if the corresponding bits of two operands are opposite. It is denoted
by ^.

Example:
1.4: Bit String Operators
Bitwise complement operator ~
Bitwise compliment operator is an unary operator (works on only one operand). It changes 1 to 0 and 0 to
1. It is denoted by ~.

Example:
1.5: Major Connectives
When two or more connectives are present in a statement, one of them is the
dominant or major connective. The major connective is shown by using
parentheses.

Examples: Determine the major connectives of the following:

1. In the statement “x = 1 o r x = 2 , and y = 3”

The major connective is conjunction.

2. ( s ∧ t ) ⟶ r
The major connective is implication.

3. [ ( p ⟶ q ) ∧ ( q ⟶ r ) ] ∨ q
The major connective is disjunction.
1.6: Conditional Propositions
IMPLICATION

Definition: Let p and q be propositions. The implication “p ⟶ q” is the proposition that is false
when p is true and q is false and true otherwise. In this implication

Statement p – antecedent, premise or hypothesis.

Statement q – consequent or conclusion.

The implication p ⟶ q can be expressed in the following:

“If p then q” “A necessary condition for p is q”

“p implies q” “q is necessary for p”
“p is sufficient for q” “q follows from p”
1.6: Conditional Propositions
IMPLICATION
Examples:

If all men are mortal then Mario is mortal. (Logical implication).

If this polygon is a quadrilateral then it has four sides. (Definitional implication.)

If today is Monday then tomorrow is Tuesday. (Sequential implication).

If sugar is placed in water, it will dissolved. (Causal implication)

If x = 0 → y = 10 , x ≠ 0 ⟶ y ≠ 10 (Material implication)
1.6: Conditional Propositions
IMPLICATION

Truth Matrix for Implication

p q p⟶q
T T T
T F F
F T T
F F T
This means if p is true, then q must be true. The only way that
this can fall (or be false) is when p is true while q is false.
1.6: Conditional Propositions
BI- CONDITIONAL
Definition: Let p and q be propositions. The bi-conditional “ p⟷ q ” is the
proposition that is true when p and q have the same truth values and false
otherwise.
The implication can be expressed in the following:
p iff q
q iff p
p implies q and q implies p
1.6: Conditional Propositions
BI- CONDITIONAL

Examples:
1. The curve is a circle if and only if the curve is equidistant to a point.
2. The polygon is a triangle if and only if it has three sides.
3. 68,295 is divisible by 15 if and only if 68,295 is divisible by 3 and 15.

Truth Matrix for Bi-conditional

p q p⟷q
T T T
T F F
F T F
F F T
 1.6: Conditional Propositions
Let s, t and u denote the following statement:
s: June goes out to see a movie;
t: The sun is out;
u: it is a good weather.
Translate the following English sentences into symbolic compound statements.

1. If the sun is out and it is not a good weather, then Jun goes out to see a movie.

2. If the sun is out, then if it is not a good weather, Jun goes out to see a movie.
1.6: Conditional Propositions
Let s, t and u denote the following statement:
s: June goes out to see a movie;
t: The sun is out; u: it is a good weather.
Translate the following English sentences into symbolic compound statements.

3. It is not the case that Jun goes out to see a movie if and only if it is good
weather or the sun is out.

4. Jun will see a movie if and only if the sun is out.

5. If it is good weather and the sun is out, then Jun will not go out to see a movie.
1.7: Converse, Inverse and Contrapositivie
CONDITIONAL
p⟶q

Determine the proposition p and q.

If it rains, then they cancel school.

p: It rains.
q: They cancel School.
1.7: Converse, Inverse and Contrapositivie
CONVERSE

To form the converse of the conditional statement, interchange the

hypothesis and the conclusion.

p ⟶ q to q ⟶ p
Example:
p: It rains.
q: They cancel School.
1.7: Converse, Inverse and Contrapositivie
INVERSE

To form the inverse of the conditional statement, take the negation of

both the hypothesis and the conclusion.
p ⟶ q to ~p ⟶ ~q
Example:
p: It rains.
q: They cancel School.
1.7: Converse, Inverse and Contrapositivie
CONTRAPOSITIVE

Switching the hypothesis and conclusion of a conditional statement

and negating both.

p ⟶ q to ~q ⟶ ~p
Example:
p: It rains.
q: They cancel school.
1.7: Converse, Inverse and Contrapositivie
Get the converse, inverse and contrapositive of the given proposition

p: It is raining.
q: The grass is wet
1.7: Converse, Inverse and Contrapositivie
Get the converse, inverse and contrapositive of the given proposition

p: Roxanne is a Frost-Mage player.

q: The player’s elemental skill is ice.
Please answer:

Discussion 1.3 and 1.4

Assignment 1.2 and 1.3

Long quiz 1.1 on Saturday.

The quiz is available on
Oct 10 from 7:30am-
10:30am