MCS 1.1

UNIT 1

CHAPTER 3: The Logic of Compound Statements

1. Statements or Propositions

• Definition: A statement or proposition is a sentence that holds a definite truth value — either true or false, but not both simultaneously.

• Examples:

  • “Mumbai is in India.” → True

  • “1 + 1 = 3.” → False

  • “Where are you going?” → Neither true nor false (not a statement)

2. Compound Statements

• Definition: Compound statements are statements formed by combining one or more statements using logical connectives.

• Example: “Roses are red and violets are blue.”

• Components: Comprised of sub-statements linked by logical connectives.

3. Basic Logical Operations

Logical Operations Defined

• Conjunction

  • Notation: $p \land q$

  • Read As: “p and q”

• Disjunction

  • Notation: $p \lor q$

  • Read As: “p or q”

• Negation

  • Notation: ${\sim}p$

  • Read As: “not p”

4. Example Problems

Example 1: Symbolic Form

Given statements:

• h: “Raj is healthy”

• w: “Raj is wealthy”

• s: “Raj is wise”

  Convert into Symbolic Form:

• a. Raj is healthy and wealthy but not wise.

  • Symbolic form: $(h \land w) \land {\sim} s$

• b. Raj is not wealthy, but he is healthy and wise.

  • Symbolic form: ${\sim} w \land (h \land s)$

• c. Raj is neither healthy, wealthy, nor wise.

  • Symbolic form: ${\sim}h \land {\sim}w \land {\sim}s$

• d. Raj is neither wealthy nor wise, but he is healthy.

  • Symbolic form: $({\sim}w \land {\sim}s) \land h$

• e. Raj is wealthy, but he is not both healthy and wise.

  • Symbolic form: $w \land {\sim}(h \land s)$

Example 2: Symbolic Form

Given Statements:

• n: “This polynomial has degree 2”

• k: “This polynomial has degree 3”

  Convert into Symbolic Form:

• Either this polynomial has degree 2 or it has degree 3 but not both.

  • Symbolic form: $(n \lor k) \land {\sim}(n \land k)$

5. Truth Values

• The truth values associated with logical operations are represented in a truth table.

Truth Table of Logical Operations

6. Conditional Statements

• Definition: For statement variables p and q, the conditional statement denoted as $p \rightarrow q$ translates to “If p then q” or “p implies q”.

• Logic: This statement holds false when p is true and q is false; it is true in all other cases.

• Components:

  • p is referred to as the hypothesis.

  • q is referred to as the conclusion.

7. Contrapositive of Conditional Statements

• Definition: The contrapositive of a conditional statement “If p then q” is expressed as “If {\sim}q then {\sim}p,” denoted as ${\sim}q \rightarrow {\sim}p$.

• Logical Equivalence: A conditional statement is logically equivalent to its contrapositive:

  • Notation: $p \rightarrow q \equiv {\sim}q \rightarrow {\sim}p$

• Examples:

  • a) If p = “Anuj can swim across the lake” and q = “Anuj can swim to the island.”

    • Contrapositive: “If Anuj cannot swim to the island, then Anuj cannot swim across the lake.”

  • b) If p = “Today is Holi” and q = “Tomorrow is Monday.”

    • Contrapositive: “If tomorrow is not Monday, then today is not Holi.”

8. Converse and Inverse of a Conditional Statement

• A conditional statement of the form “If p then q” consists of the following:

  1. Converse: “If q then p”

     • Notation: $q \rightarrow p$

     • Example: If Anuj can swim to the island, then Anuj can swim across the lake.

  2. Inverse: “If {\sim}p then {\sim}q”

     • Notation: ${\sim}p \rightarrow {\sim}q$

     • Example: If Anuj cannot swim across the lake, then Anuj cannot swim to the island.

• Note on Logical Equivalence:

  1. A conditional statement and its converse are not logically equivalent.

  2. A conditional statement and its inverse are not logically equivalent.

  3. The converse and the inverse of a conditional statement are logically equivalent to each other:

     • Notation: $q \rightarrow p \equiv {\sim}p \rightarrow {\sim}q$

Example 1: Converse & Inverse

• a) p: Anuj can swim across the lake

• q: Anuj can swim to the island

  • Converse: If Anuj can swim to the island, then Anuj can swim across the lake.

  • Inverse: If Anuj cannot swim across the lake, then Anuj cannot swim to the island.

• b) p: Today is Holi

• q: Tomorrow is Monday

  • Converse: If tomorrow is Monday, then today is Holi.

  • Inverse: If today is not Holi, then tomorrow is not Monday.

9. Negation of a Conditional Statement

• Definition: The negation of the statement “If p then q” is logically equivalent to “p and not q.”

• Notation: $\sim (p \rightarrow q) \equiv p \land \sim q$

Example: Negation Tasks

• Example 1:

  • a) If my car is in the repair shop, then I cannot get to class.

    • “My car is in the repair shop and I can not get to class.”

  • b) If Anu lives in Mumbai, then she lives in Maharashtra.

    • “Anu lives in Mumbai and she does not live in Maharashtra.”

Additional Example:

• Negation Statements:

• a) If x is nonnegative, then x is positive or x is 0.

  • Negation: “x is nonnegative and x is not positive and x is not 0.”

• b) If n is divisible by 6, then n is divisible by 2 and n is divisible by 3.

  • Negation: “n is divisible by 6 and either n is not divisible by 2 or n is not divisible by 3.”

10. Bi-Conditional Statements

• Definition: A biconditional statement, expressed as “p if and only if q” is denoted as $p \leftrightarrow q$. It is true when both p and q possess the same truth values and false when they differ.

11. Truth Tables of Compound Propositions

Precedence of Logical Operators:

1. Negation is prioritized before all other operations.

2. Conjunction has priority over disjunction.

3. Conditional and biconditional operators have lower precedence than conjunction and disjunction.

12. Truth Table Examples

Example 1

• Construct the truth table: $(p \lor q) \land \sim (p \land q)$

Example 2

• Construct the truth table: $(p \land q) \lor \sim r$

13. Logic and Bit Operations

• Definition: A bit is a symbolic representation in binary with values of 0 (false) and 1 (true). The term “bit” comes from binary digit, which denotes these two values.

• Boolean Variable: This is a variable that can only take the values true or false, associated with bits.

14. Bit String Operations

• Examples:

• Find the bitwise OR, AND, and XOR of the bit strings:

  • Input:

  • 01 1011 0110

  • 11 0001 1101

  • Results:

  • Bitwise OR: 11 1011 1111

  • Bitwise AND: 01 0001 0100

  • Bitwise XOR: 10 1010 1011

• Definition: A bit string is a sequence consisting of zero or more bits, with the length representing the number of bits contained in the string.

15. Evaluate Expressions

Example Evaluations

• a) $1 1000 \land (0 1011 \lor 1 1011)$

• b) $(0 1111 \land 1 0101) \lor 0 1000$

• c) $(0 1010 \oplus 1 1011) \oplus 0 1000$

• d) $(1 1011 \lor 0 1010) \land (1 0001 \lor 1 1011)$

16. Tautologies and Contradictions

Definitions

• Tautology: A statement that is always true irrespective of the individual truth values of the statements it encompasses.

  • Example: $(P \lor \sim P)$ — “It is either raining or not raining.”

• Contradiction: A statement that is always false regardless of individual truth values.

  • Example: $(P \land \sim P)$ — “It is both raining and not raining.”

17. Logical Equivalence

• Definition: Two statements (or propositions) P and Q are logically equivalent if they exhibit identical truth tables.

• Notation: $P \equiv Q$

• Example: $p \land \sim ( \sim p)$ are logically equivalent.

Example: Verification of Logical Equivalences

• a) $p \rightarrow q \equiv \sim p \lor q$

• b) $\sim (p \rightarrow q) \equiv p \land \sim q$

18. Further Logical Laws

1. Commutative Laws:
   i) $p \land q \equiv q \land p$
   ii) $p \lor q \equiv q \lor p$

2. Associative Laws:
   i) $(p \land q) \land r \equiv p \land (q \land r)$
   ii) $(p \lor q) \lor r \equiv p \lor (q \lor r)$

3. Distributive Laws:
   i) $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$
   ii) $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$

4. Double Negative Law: $\sim (\sim p) \equiv p$

5. Idempotent Laws:
   i) $p \land p \equiv p$
   ii) $p \lor p \equiv p$

6. De Morgan’s Laws:
   i) $\sim (p \land q) \equiv \sim p \lor \sim q$
   ii) $\sim (p \lor q) \equiv \sim p \land \sim q$

7. Absorption Laws:
   $p \lor (p \land q) \equiv p$
   $p \land (p \lor q) \equiv p$

8. Identity Laws:
   i) $p \land t \equiv p$
   ii) $p \lor c \equiv p$

9. Negation Laws:
   i) $p \lor \sim p \equiv t$
   ii) $p \land \sim p \equiv c$

10. Universal Bound Laws:
    i) $p \lor t \equiv t$
    ii) $p \land c \equiv c$

11. Negations of t and c:
    i) $\sim t \equiv c$
    ii) $\sim c \equiv t$

19. Example Applications using De Morgan’s Laws

• Negation Examples:

1. “Raj is an orange belt and Suraj is a red belt.”

   • Negation: “Raj is not an orange belt or Suraj is not a red belt.”

2. “The connector is loose or the machine is unplugged.”

   • Negation: “The connector is not loose and the machine is not unplugged.”

20. Example Problem Solving with Negations

• Problems:

1. Negation of 1 < x ≤ 4:

   • Equivalent to: 1 < x and x ≤ 4.

   • Negation: “x ≤ 1 or x > 4.”