CHAPTER-1-PART-1-PROPOSITIONAL-LOGIC

Chapter One: Propositional Logic

Introduction to Propositional Logic

  • Course: IT 104 | Discrete Mathematics

PART 1: Introduction and Preliminaries

  • Session 1 Overview

Chapter Objectives

  • Write compound propositions in both statement and symbolic form.

  • Construct truth tables to establish the validity and falsity of arguments, determining logical equivalence.

  • State the converse, inverse, and contrapositive of conditional statements.

Topics Covered

Key Topics

  • Propositions

  • Logical Connectives and Truth Tables

  • Conditional and Biconditional Propositions

  • Tautologies and Contradictions

  • Logical Equivalence

  • Arguments

  • Applications of Logic in Circuits

Understanding Logic

  • Definition: Logic is a discipline dealing with reasoning methods, assessing the correctness of reasoning.

  • Determines the validity of an argument mainly based on logical form rather than the specific meanings of terms.

Logical Methods

  • Utilized across various fields:

    • Mathematics: For proving theorems.

    • Computer Science: For verifying program correctness.

    • Natural and Physical Sciences: To draw conclusions from experiments.

    • Social Sciences and Daily Life: To solve various problems.

Propositions

  • Definition: A proposition (or statement) is a declarative sentence that expresses information and assigns a truth value (true or false).

  • Characteristics:

    • Always ends in a period.

    • May be categorized as:

      • Atomic Proposition: Simple statements that cannot be decomposed.

      • Compound Proposition: Formed through logical connectives from atomic propositions.

Examples of Propositions

Valid Propositions

  • The only positive integers that divide 5 are 1 and 5 itself.

  • The sun will come out tomorrow.

  • a + b = b + c if a = c.

  • 10 - 1 = 9.

Invalid Propositions

  • 5-a = b.

  • What time is it?

  • Help!

  • Malolos is the best city in Bulacan.

  • This sentence is false.

Logical Connectives

  • Devices that link propositions include:

    • Negation ("not")

    • Conjunction ("and")

    • Disjunction ("or")

    • Inclusive Disjunction

    • Exclusive Disjunction

Truth Values vs. Truth Tables

Truth Values

  • Assigned values to propositions are True (1) or False (0).

Truth Table

  • A truth table summarizes the truth values of propositions, showing all combinations of truth values.

  • There are 2^n possible truth value combinations for n propositional variables.

Constructing a Truth Table

  1. Step 1: Prepare all possible truth value combinations for the propositional variables.

  2. Step 2: Compute the truth values for each connective and organize them into a new column.

Negation

  • For a proposition p, its negation is denoted as ¬p or ~p, which indicates "not p".

  • Examples:

    • p: "Today is Friday."

      • ~p: "Today is not Friday."

    • p: "The sun is not shining."

      • ~p: "The sun is shining."

Negation: Truth Table

p

~p

1

0

0

1

Compound Propositions

  • Combination of propositions formed using logical connectives.

  • Propositional Connectives: Operations that combine two propositions yielding a new one, dependent on the truth values of the originals.

Conjunction

  • Denoted as p ∧ q, true when both p and q are true.

  • Truth Table: | p | q | p ∧ q | |---|---|-------| | 1 | 1 | 1 | | 1 | 0 | 0 | | 0 | 1 | 0 | | 0 | 0 | 0 |

Examples

  • p: "Today is Friday"

  • q: "It is raining today"

  • p ∧ q: "Today is Friday and it is raining."

Disjunction

  • Denoted as p ∨ q (inclusive) or p ⊕ q (exclusive).

  • Truth Table for Inclusive Disjunction: | p | q | p ∨ q | |---|---|-------| | 1 | 1 | 1 | | 1 | 0 | 1 | | 0 | 1 | 1 | | 0 | 0 | 0 |

Conditional Propositions

  • Written as p → q, indicating "if p, then q."

  • Truth Table: | p | q | p → q | |---|---|-------| | 1 | 1 | 1 | | 1 | 0 | 0 | | 0 | 1 | 1 | | 0 | 0 | 1 |

Examples

  • p: "I am late"

  • q: "I cannot take the seatwork"

  • p → q: "If I am late, then I cannot take the seatwork."

Types of Conditional Proposition

  • Converse: q → p

  • Contrapositive: ~q → ~p

  • Inverse: ~p → ~q

Biconditional Propositions

  • Denoted as p ↔ q, meaning "p if and only if q."

  • Truth Table: | p | q | p ↔ q | |---|---|-------| | 1 | 1 | 1 | | 1 | 0 | 0 | | 0 | 1 | 0 | | 0 | 0 | 1 |

Examples

  • p: "David is the son of Ricky."

  • q: "Ricky is the father of David."

  • p ↔ q: "David is the son of Ricky if and only if Ricky is the father of David."

Tautologies and Contradictions

  • Tautology: True for all values.

  • Contradiction: Always false.

  • Contingency: Can be true or false depending on values.

Examples

  1. p ∧ ~p (Contradiction).

  2. (p → q) ∧ (p ∨ q) (Contingency).

End of Chapter 1: Part 1

  • Any questions?