Logic and

Computer
Addition
Definition of Logic
• Logic is the study of evaluating arguments and
reasoning.
• It helps differentiate correct reasoning from
poor reasoning.
• Used in mathematics to prove theorems and in
computer science to verify program
correctness.
Mathematical Logic (Symbolic Logic)
• A branch of mathematics closely related to computer
science.
• Includes both the mathematical study of logic and the
applications of formal logic to other areas of mathematics
Propositions
 A proposition is a declarative sentence that is either true
or false.
 Truth value indicates the truth or falsity of a proposition.

Example: Which of the following are

propositions?
1. Manila is the capital of the Philippines.
2. What day is it?
Answer:
1. “Manila is the capital of the Philippines” is
true, therefore it is a proposition.

2. “What day is it?” It is a question; it cannot

be considered either true or false and thus is
not a proposition.
Propositional Variables
 Represent propositions using variables like p, q, and r.
 Logical connectives combine simple propositions into compound
propositions.

A compound proposition is a proposition composed of two or more

simple propositions connected by logical connectives “and,” “ or,” ” if
then,” ” not,” ” if and only if,” and “exclusive-or.” A proposition which
is not compound is said to be simple (also called atomic).
Logical Connectives
a. Conjunction.
The conjunction of the proposition p and q is the compound proposition “p and q.”
Symbolically, 𝑝 ∧ 𝑞, where ∧ is the symbol for "and.”

Property 1: If p is true and q is true, then, 𝑝 ∧ 𝑞 is true; otherwise, 𝑝 ∧ 𝑞 is false.

Meaning, the conjunction of two propositions is true only if each proposition is true.
Example: Determine the truth value of each of the following conjunction.
1.2 + 6 = 9 and man is a mammal.

Answer: 1. Since “2 + 6 = 9” is a false proposition (note that 2 + 6 = 9) and the proposition

"man is a mammal” is true, the conjunction of the compound proposition is false.

b. Disjunction.
The disjunction of the proposition p, q is the compound proposition “p or q.”
Symbolically, 𝑝 ∨ 𝑞, where ∨ is the symbol for” or.”
both p and q are true, then 𝑝 ∨ 𝑞 is true;
Property 2: If p is true or q is true or if

otherwise 𝑝 ∨ 𝑞 is false. Meaning, the

disjunction of two propositions is false
only if each proposition is false.
Example: Determine the truth value of each of the following disjunction.
1. Philippine Senate is composed of 24 senators or Gloria Macapagal Arroyo is the first
female Philippine President.
Answer: Since proposition “Philippine Senate is composed of 24 senators” is true and the
proposition "Gloria Macapagal Arroyo is the first female Philippine President” is false,
therefore the disjunction of the compound proposition is true.
c. Negation.
The negation of the proposition p is denoted by ~𝑝, where ~ is the symbol for “not.”
Property 3: If p is true, ~p is false. Meaning, the truth value of the negation of a proposition
is always the reverse of the truth value of the original proposition.

Example: The following are propositions for p, find the corresponding ~𝑝.
1. 3 + 6 = 9.
2. Fholeen is a girl.
3. Andrew is not here.
Answer:
1. 3 + 6 ≠ 9.
2. Fholeen is not a girl. Or Fholeen is a boy.
3. Andrew is here.
d. Conditional.

then q.” Symbolically, 𝑝 → 𝑞, where → is the symbol for “if then.” p is called hypothesis (or
The conditional (or implication) of the proposition p and q is the compound proposition “if p

antecedent or premise) and q is called conclusion (or consequent or consequence).

Property 4: The conditional proposition 𝑝 → 𝑞 is false only when p is true and q is false;
otherwise 𝑝 → 𝑞 is true. Meaning 𝑝 → 𝑞 states that a true proposition cannot imply a false
proposition.
Example: Obtain the truth value of each of the following conditional propositions.
1. If vinegar is sweet, then sugar is sour.

Answer:
2. Since the propositions “vinegar is sweet” and the “sugar is sour” are both false, therefore
the conditional of the compound proposition is true.
e. Biconditional.

Symbolically, 𝑝 ⟷ 𝑞, where ⟷ is the symbol for “if and only if.”

The biconditional of the proposition p and q is the compound proposition “p if and only if q.”

Property 5: If p and q are true or both false,

then 𝑝 ⟷ 𝑞 is true; if p and q have opposite
truth values, then 𝑝 ⟷ 𝑞 is false.

Example: Determine the truth values of each of the following biconditional propositions.
1. Manila is the capital of the Philippines is equivalent to fish live in the moon.
Answer:
1. Note that “Manila is the capital of the Philippines”
is true proposition while “fish live in the moon”
is false, thus the conditional of the compound proposition is false.
exclusive-or q.” Symbolically, 𝑝⨁𝑞, where ⨁ is the symbol for “exclusive-or.”
f. Exclusive-or. The exclusive-or of the proposition p and q is the compound proposition “p

Property 6: If p and q are true or both false, then 𝑝⨁𝑞 is false; if p and q have opposite truth
values, then 𝑝⨁𝑞 is true.
It can be noted that the true values of 𝑝⨁𝑞 is the negation of the truth values
of p ↔ q.

Given the proposition “Sofia will take her lunch in Batangas or she will have it in
Singapore,” it can be noted from the statement that “Sofia cannot have her
lunch in Batangas and at the same time do it in Singapore,” thus it is considered
false. If Sofia will have her lunch in Batangas or in Singapore, meaning she can
only have it in one location given a single schedule (the truth value is true).
Lastly, if she ought to decide to have her lunch elsewhere (neither in Batangas
nor in Singapore), therefore the truth value is false.
• Logical Equivalence and Forms of Conditional Propositions
There are three important classes of compound statements namely tautology, contradiction,
and contingency which are briefly discussed below.

1. Tautology is a compound statement that is true for all possible combinations of the truth
values of the propositional variables also called logically true.

2. Contradiction is a compound statement that is false for all possible combinations of the
truth values of the propositional variables also called logically false or absurdity.

3. Contingency is a compound statement that can be either true or false, depending on the
truth values of the propositional variables are neither a tautology nor a contradiction.
Example: Write the truth table for each of the following compound statements and determine
whether the compound statement is tautology, contradiction or contingency.
1. (~𝑝 ∧ 𝑞) → 𝑞
2. (𝑝 → 𝑞) ∧ (𝑝 → ~𝑞)
3. (~𝑝 ∨ 𝑞) ⊕ (𝑝 → 𝑞).

Solution:
1. (~𝑝 ∧ 𝑞) → q
p q ~p ~p∧q (~p∧q) →q

T T F F T
T F F F T
F T T T T
F F T F T

Since all the truth values of the compound statement (~𝑝 ∧ 𝑞) → 𝑞 are true, thus it is a
tautology.
2. (𝑝 → 𝑞) ∧ (𝑝 → ~𝑞) p q 𝑝→𝑞 ~𝑞 𝑝 → ~𝑞 (𝑝 → 𝑞) ∧ (𝑝 → ~𝑞)
T T T F F F
T F F T T F
F T T F T T

Note that the truth values of the statement (𝑝 → 𝑞) ∧ (𝑝 → ~𝑞) are combinations of true
F F T T T T

and false, therefore the compound statement is contingency.

~𝑝 ∨ 𝑞 𝑝→𝑞 (~𝑝 ∨ 𝑞) ⊕ (𝑝 → 𝑞)
3. (~𝑝 ∨ 𝑞) ⊕ (𝑝 → 𝑞)
p q ~𝑝
T T F T T F
T F F F F F
F T T T T F
F F T T T F

Observe that all the truth values of the compound statement are false, thus it is a
contradiction.
every row of the truth table, that is if 𝑥 ↔ 𝑦 is a tautology. Symbolically, 𝑥 ≡ 𝑦.
Two propositions are said to be logically equivalent if they have the same truth value for

Example: Show that the following are equivalent.

1. 𝑝 ∧ (𝑞 ∨ 𝑟) and (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)
Solution:
1. 𝑝 ∧ (𝑞 ∨ 𝑟) and (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑞)

Observe that the truth values of compound statements 𝑝 ∧ (𝑞 ∨ 𝑟) and (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)

are the same, thus we can say that they are logically equivalent.
(𝑝 ∨ ~𝑞) ⟷(r∧s)
p q r s
HAMMING AND REPETITION CODES
WHAT IS HAMMING CODE?
Hamming code is a liner code that is useful for error detection up to two immediate bit
errors. It is capable of single-bit errors.
7 BITS
commonly used

HISTORY OF HAMMING CODE

• Hamming code is a technique build by R.W. Hamming to detect errors.
• Hamming code should be applied to data units of any length and uses the relationship
between data and redundancy bits.
• He worked on the problem of the error-correction method and developed an increasingly
powerful array of algorithms called Hamming code.
• In 1950, he published the Hamming Code, which widely used today in application like ECC
Memory.
Application of Hamming Code
Here are some common applications of using Hamming code:
 Satellites
 Computer Memory
 Modems
 PlasmaCAM
 Open Connectors
 Shielding Wire
 Embedded Processor
Advantages of Hamming Code
 Hamming code methos is effective on networks where the data streams are given for the
single-bit errors.
 Hamming code not only provides the detection of a bit error but also helps you to indent
bit containing error so that it can be corrected.
 The ease of use of hamming code makes it best suitable for use in computer memory and
single-error correction.

Disadvantages of Hamming Code

 Single-bit error detection and correction code.
 Hamming code algorithm can solve only single bit issues.
Process of Encoding a message using Hamming Code
The process used by the sender to encode the message includes the following three steps:
 Calculation of total numbers of redundant bits.
 Checking the position of the redundant bits.
 Lastly, calculating the values of these redundant bits.

Step 1. Calculation of the total number of redundant bits.

Let assume that the message contains:
n- number of data bits
p- number of redundant bits which are added to it so that np can indicate at least (n+p+1)
different states.
Here, (n + p) depicts the location of an error in each of (n + p) bit positions and one extra
state indicates no error. As p bits can indicate 2p states, 2p has to at least equal to (n + p + 1).
Step 2. Placing the redundant nits in their correct position.
The p redundant bits should be placed at bit positions of powers of 2.

For example, 1, 2, 4, 8, 16, etc. They are referred to as p1 (at position 1), p2 (at position 2),p3
(at position 4), etc.

Step 3. Calculation of the values of the redundant bit.

The redundant bits should be parity bits makes the number of 1s either even or odd.
The two types of parity are:
 Total numbers of bits in the message is made even is called even parity.
 The total number of bits in the message is made odd is called odd parity.
Here, all the redundant bit, p1, is must calculated as parity.
It should cover all the bit position whose binary representation should include a 1 in the 1st
position excluding the position of p1.

P1 is the parity bit for every data bit in positions whose binary representation includes a 1
in the less important position not including 1 like (3, 5, 7, 9, …)
P2 is the parity bit for every data bit in positions whose binary representation include 1 in
the position 2 from right, not including 2 like (3, 6, 7, 10, 11, …)
P3 is the parity bit for every bit in positions whose binary representation a 1 in the position
3 from right not include 4 like (5-7, 12-15, …)
GIVEN DATA
1001

HAMMING CODE:

Parity Formula
7 bits
Commonly used 2^n (n={0,1,2,3,…..n})

D7 D6 D5 P4 D3 P2 P1 2^0 = 1
2^1 = 2
2^2 = 4
7 6 5 4 3 2 1

Composed of:
Data Bits = 4
Parity Bits = 3
Given Parity CHECKING
P1 = D3 D5 D7 R T
P2 = D3 D6 D7
P4 = D5 D6 D7 1001100 1001110

P1 = 0 101
P1 = 0 101
Something wrong
P2 = 0 101 P2 = 0 101
with the data
P4 = 1 001 P4 = 1 001

1 0 0 1 1 0 0
R T
1001100 1001100
HAMMING CODE
P1 = 0 101
P2 = 0 101
P4 = 1 001
PROCESS OF DECRYPTING A MESSAGE IN HAMMING CODE

Receiver gets incoming messages require to performs recalculations to find and

correct errors.
The recalculation process done in the following steps:
• Counting the number of redundant bits.
• Correctly positioning of all redundant bits.
• Parity Check
Step 1. Counting the number of redundant bits
You can use the formula for encoding, the number of redundant bits
2p > n + p + 1
Here, the number of data bits and p is the number of redundant bits.

Step 2. Correctly positioning all the redundant bits

Here, p is a redundant bit which is located at bit positions of powers of 2, For example, 1, 2, 4, 8, etc.

Step 3. Parity Check

Parity bits need to calculated based on data bits and the redundant bits.
p1= parity (1, 3, 5, 7, 9, 11…)
p2= parity (2-3, 6-7, 10-11…)
p4= parity (4-7, 12-15, 20-23…)
p8= parity (8-15,24-31…)
REPETITON CODES
 Is one of the most basic error-correcting codes
FORMULA:
2r + 1

Example:
Given: 001, r=3
Solution: 2(3) + 1 = 7 -> 001001001001001001001 (repeated seven times, without space).
THANK YOU FOR LISTENING!