Unit 2 of 4 · BCA Sem 1

Unit 2: Logic

Mathematics notes · PTU syllabus (UGCC2501)

3 min read5 topics15 exam questions
On this page
  1. Unit summary
  2. Logic statements
  3. Connectives and basic logic operations
  4. Truth tables
  5. Logical equivalence
  6. Tautologies and contradictions
  7. Key terms
  8. Quick revision
  9. Important questions

Unit summary

Logic is the science of correct reasoning and the basis of programming conditions, digital circuits and mathematical proof. This unit covers logical statements, the connectives and basic logical operations (negation, conjunction, disjunction, conditional and biconditional), truth tables, logical equivalence of statements, and tautologies and contradictions.

After this unit you can

  • Identify statements and form compound statements with connectives
  • Construct truth tables for compound statements
  • Prove logical equivalence using truth tables and standard laws
  • Identify tautologies, contradictions and contingencies

PTU syllabus topics

  • Logic statements
  • connectives
  • basic logic operations (conjunction, disjunction, negation)
  • logical equivalence/equivalent statements
  • tautologies and contradictions
1

Topic 1

Logic statements

A statement (proposition) is a declarative sentence that is either true or false, but not both.

ComparisonStatements vs non-statements
Statement
Not a statement

Examples

"5 is a prime number" (true); "Delhi is in Punjab" (false)

"What is your name?" (question); "Close the door" (order); "x + 2 = 5" (depends on x)

Reason

Has a definite truth value

Has no truth value

Key termsTerminology
Truth value
T (true) or F (false)
Simple statement
Cannot be broken into simpler statements
Compound statement
Made by joining simple statements with connectives
Propositional variable
Letters p, q, r that stand for statements
Paradox
Self-contradictory sentence such as "This sentence is false" — not a statement

Example

p: "The sun rises in the east" (T); q: "2 + 3 = 6" (F). The sentence "Is it raining?" is not a statement.

2

Topic 2

Connectives and basic logic operations

ComparisonLogical connectives
Symbol and name
Read as

Negation

¬p or ~p

"not p"

Conjunction

p ∧ q

"p and q"

Disjunction

p ∨ q

"p or q" (inclusive)

Conditional (implication)

p → q

"if p then q"

Biconditional

p ↔ q

"p if and only if q"

Exclusive or

p ⊕ q

"p or q but not both"

Basic operations: negation, conjunction, disjunction

pq¬pp ∧ qp ∨ q
TTFTT
TFFFT
FTTFT
FFTFF
Key termsRules to remember
Negation
Reverses the truth value
Conjunction (AND)
True only when both statements are true
Disjunction (OR)
False only when both statements are false
Link with circuits
AND gate = conjunction, OR gate = disjunction, NOT gate = negation
Number of rows
A truth table with n variables has 2ⁿ rows

Conditional and biconditional

pqp → qp ↔ q
TTTT
TFFF
FTTF
FFTT
  • p → q is false only when p is true and q is false. A promise "if you pass, I will give a gift" is broken only when you pass and get no gift.
ComparisonConverse, inverse and contrapositive of p → q
Form
Equivalent to the original?

Converse

q → p

No

Inverse

¬p → ¬q

No

Contrapositive

¬q → ¬p

Yes — always equivalent

Biconditional

(p → q) ∧ (q → p)

Equal to p ↔ q

Example

"If it rains, the match is cancelled": converse — "If the match is cancelled, it rained"; inverse — "If it does not rain, the match is not cancelled"; contrapositive — "If the match is not cancelled, it did not rain" (equivalent to the original).

Negation of compound statements

Key formulasNegation rules
  • Negation of conjunction

    ¬(p ∧ q) ≡ ¬p ∨ ¬q

  • Negation of disjunction

    ¬(p ∨ q) ≡ ¬p ∧ ¬q

  • Negation of conditional

    ¬(p → q) ≡ p ∧ ¬q

  • Negation of biconditional

    ¬(p ↔ q) ≡ (p ∧ ¬q) ∨ (¬p ∧ q)

  • Double negation

    ¬(¬p) ≡ p

3

Topic 3

Truth tables

ProcessBuilding a truth table
  1. 1List the variables and write 2ⁿ rows covering every combination of T and F
  2. 2Add a column for every sub-expression
  3. 3Fill the columns from the innermost bracket outward
  4. 4The last column gives the truth value of the whole statement
  5. 5Read the pattern: all T, all F or mixed

Example

Truth table for (p ∨ q) ∧ ¬(p ∧ q) — this is the exclusive-or p ⊕ q.

pqp ∨ qp ∧ q¬(p ∧ q)(p ∨ q) ∧ ¬(p ∧ q)
TTTTFF
TFTFTT
FTTFTT
FFFFTF

Example

Three variables need 8 rows: the pattern TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF lists every case exactly once.

4

Topic 4

Logical equivalence

Two statements are logically equivalent (≡) if they have the same truth value for every assignment of truth values — their truth table columns are identical.

Example

Prove p → q ≡ ¬p ∨ q.

pqp → q¬p¬p ∨ q
TTTFT
TFFFF
FTTTT
FFTTT

Standard logical equivalences

Equivalence
Commutativep ∧ q ≡ q ∧ p ; p ∨ q ≡ q ∨ p
Associative(p ∧ q) ∧ r ≡ p ∧ (q ∧ r) ; (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Distributivep ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) ; p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
De Morgan¬(p ∧ q) ≡ ¬p ∨ ¬q ; ¬(p ∨ q) ≡ ¬p ∧ ¬q
Implicationp → q ≡ ¬p ∨ q ≡ ¬q → ¬p
Biconditionalp ↔ q ≡ (p → q) ∧ (q → p)
Idempotentp ∧ p ≡ p ; p ∨ p ≡ p
Absorptionp ∨ (p ∧ q) ≡ p ; p ∧ (p ∨ q) ≡ p

Set theory vs logic vs Boolean algebra

Correspondence
Union ∪Disjunction ∨ and Boolean OR +
Intersection ∩Conjunction ∧ and Boolean AND ·
Complement ′Negation ¬ and Boolean NOT ′
Universal set UTrue (T, 1)
Empty set ∅False (F, 0)

Exam tip

The same laws appear in sets, logic and Boolean algebra — learn them once. De Morgan in sets is (A ∪ B)′ = A′ ∩ B′, in logic ¬(p ∨ q) ≡ ¬p ∧ ¬q.

5

Topic 5

Tautologies and contradictions

ComparisonTautology, contradiction and contingency
Meaning
Example

Tautology

Always true, whatever the truth values of the variables — last column all T

p ∨ ¬p

Contradiction

Always false — last column all F

p ∧ ¬p

Contingency

Sometimes true, sometimes false

p → q

p¬pp ∨ ¬p (tautology)p ∧ ¬p (contradiction)
TFTF
FTTF

Example

Show that [(p → q) ∧ p] → q (modus ponens) is a tautology.

pqp → q(p → q) ∧ p[(p → q) ∧ p] → q
TTTTT
TFFFT
FTTFT
FFTFT
Key termsImportant tautologies (rules of inference)
Excluded middle
p ∨ ¬p
Modus ponens
[(p → q) ∧ p] → q
Modus tollens
[(p → q) ∧ ¬q] → ¬p
Hypothetical syllogism
[(p → q) ∧ (q → r)] → (p → r)
Disjunctive syllogism
[(p ∨ q) ∧ ¬p] → q
Contrapositive
(p → q) ↔ (¬q → ¬p)
ProcessTesting a statement
  1. 1

    Write the truth table

  2. 2

    Look at the final column

  3. 3

    All T — tautology

  4. 4

    All F — contradiction

  5. 5

    Mixed — contingency

  6. 6

    Negation of a tautology is a contradiction and vice versa

Key terms

Statement
A sentence that is either true or false but not both
Compound statement
Statement formed from simpler ones using connectives
Conjunction
p ∧ q, true only when both are true
Disjunction
p ∨ q, false only when both are false
Conditional
p → q, false only when p is true and q is false
Contrapositive
¬q → ¬p, equivalent to p → q
Logical equivalence
Same truth table for two statements
Tautology
A statement that is always true
Contradiction
A statement that is always false

Quick revision

  • A statement is true or false, never both; questions and commands are not statements.
  • ∧ true only if both true; ∨ false only if both false; p → q false only for T, F.
  • p → q ≡ ¬p ∨ q ≡ ¬q → ¬p; the converse and inverse are not equivalent to it.
  • De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q.
  • Tautology — all T; contradiction — all F; otherwise contingency.
  • n variables give 2ⁿ rows.

Important exam questions

Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).

Short-answer questions

  1. Q1.Define a statement. Give one example and one non-example.
  2. Q2.Write the truth table of conjunction.
  3. Q3.When is a conditional statement false?
  4. Q4.Write the converse and contrapositive of "If x is even then x² is even".
  5. Q5.State De Morgan's laws for statements.
  6. Q6.What is a tautology? Give an example.
  7. Q7.What is a contradiction?
  8. Q8.Write the negation of "p ∧ q".
  9. Q9.How many rows are there in a truth table for 4 variables?
  10. Q10.What is logical equivalence?

Long-answer questions

  1. Q1.Explain the logical connectives with truth tables.
  2. Q2.Construct a truth table for (p → q) ∧ (q → p) and compare it with p ↔ q.
  3. Q3.Prove p → q ≡ ¬p ∨ q and ¬(p ∧ q) ≡ ¬p ∨ ¬q using truth tables.
  4. Q4.Show that [(p → q) ∧ p] → q is a tautology.
  5. Q5.Explain tautology, contradiction and contingency with examples.

Stuck on this unit?

Message SBS on WhatsApp for help with Mathematics, or to ask about studying BCA at Synetic.

WhatsApp us