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

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?