SCC121 Fundamentals of Computer Science Notes

SCC121 Fundamentals of Computer Science

Prof Corina Sas
School of Computing and Communications

Week 5 Quiz

  • Topics covered:

    • Sets

    • Relations

    • Functions

    • Propositional Logic

Overview of Propositional Logic

Key Areas of Focus

  • Propositions

  • Truth tables

  • Fundamental connectives

  • Logical properties of propositions

Objectives of the Lesson

  • Understanding basic ideas about propositional logic, propositions, and their logical properties.

  • Facility in the construction of Truth tables and the use of fundamental connectives.

Introduction to Logic

  • Logic: The study of reasoning and rational methods of drawing conclusions.

Propositions

Definition

  • Proposition: A claim about how things are.

    • Characteristics:

    • A statement that is either true or false, but not both.

    • If a proposition is true, its truth value is "true" (T).

    • If a proposition is false, its truth value is "false" (F).

    • Notation:

    • Letters are used to represent propositions (e.g., A = "It is raining").

    • Truth values can be indicated as:

      • True (T, or 1)

      • False (F, or 0)

Examples of Propositions

Propositions with Truth Value True (T)

  • "Grass is green"

  • "Snow is white"

  • "2 + 2 = 4"

Propositions with Truth Value False (F)

  • "2 + 8 = 11"

  • "1 = 0"

Non-propositions

Characteristics

  • Non-propositions are not claims about how things are; thus, they cannot be said to be true or false.

Examples

  • "Is the water warm?"

  • "Where are we?"

  • "Go for it!"

  • "Put the phone down!"

  • "Ouch!"

  • "Aha!"

Atomic and Compound Propositions

Definitions

Atomic Proposition

  • A proposition whose truth or falsity does not depend on other propositions.

Compound Proposition

  • Propositions constructed from atomic propositions by combining them with fundamental connectives.

Truth Tables

Definition

  • A truth table is a tabulation of the value of a compound proposition for all possible truth values of its atomic propositions.

  • Each atomic proposition has its own column in the truth table.

Example for Two Atomic Propositions

P

Q

Compound

F

F

F

F

T

T

T

F

T

T

T

T

Fundamental Connectives

Types of Connectives

  • AND (∧)

  • OR (∨)

  • XOR (⊕) or (∨)

  • NOT (~ or ⊖)

  • Conditional (→ or ⇒)

  • Biconditional (↔, ⇔, or ≡)

AND (∧)

  • Definition: The AND connective takes two propositions P and Q to form a third proposition called the conjunction.

  • Truth Conditions:

    • The conjunction is true when both P and Q are true.

  • Written as: P ∧ Q

Truth Table for AND

P

Q

P ∧ Q

F

F

F

F

T

F

T

F

F

T

T

T

Examples

  • Let X = "Java is a programming language"; Y = "C is a programming language"; then:

    • X ∧ Y = "Java and C are programming languages"

Multiple Propositions for AND

  • R = A ∧ B ∧ C ∧ D …

  • Rule: All propositions must be true for R to be true. If any proposition is false, R is false.

OR (∨)

  • Definition: The OR connective takes two propositions P and Q to form a third proposition called the disjunction.

  • Truth Conditions:

    • The disjunction is true when P is true, Q is true, or both.

  • Written as: P ∨ Q

Truth Table for OR

P

Q

P ∨ Q

F

F

F

F

T

T

T

F

T

T

T

T

Examples

  • Let C = "I am going to the Lake District"; D = "I am going to London"; then:

    • C ∨ D = "I am going to the Lake District or I am going to London"

Multiple Propositions for OR

  • R = A ∨ B ∨ C ∨ D …

  • Rule: All propositions must be false for R to be false. If any proposition is true, R is true.

Exclusive OR (XOR) (⊕ or ∨)

  • Definition: The XOR connective creates a third proposition that is true when P is true and Q is true, but not both.

  • Written as: P ⊕ Q

Truth Table for XOR

P

Q

P ⊕ Q

F

F

F

F

T

T

T

F

T

T

T

F

Examples

  • Let A = "I will have the soup for starters" and B = "I will have the salad for starters"; then:

    • A ⊕ B = "I will have either the soup or salad for starters, but not both"

Multiple Propositions for XOR

  • R = A ⊕ B ⊕ C ⊕ D …

  • Rule: An odd number of propositions must be true for R to be true; an even number must be true for R to be false.

Negation (~)

  • Definition: The negation connective takes one proposition P to form a second proposition called negation.

  • Truth Conditions: The negation is true when P is false.

  • Written as: ~P

Truth Table for Negation

P

~P

T

F

F

T

Examples

  • Let A = "It is raining"; then:

    • ~A = "It is not raining"

Conditional or Implication (→ or ⇒)

  • Definition: The (if…then) connective combines two propositions P and Q into a third proposition called a conditional or implication.

  • Form: If the antecedent (after "if") is true and the consequent (after "then") is false, the implication is false; otherwise, it is true.

  • Written as: P → Q

Truth Table for Conditional

P

Q

P → Q

F

F

T

F

T

T

T

F

F

T

T

T

Example

  • "If the train is late, then we will miss our flight."

    • Antecedent (P): "The train is late"

    • Consequent (Q): "We will miss our flight"

Biconditional (if and only if) (↔, ⇔, or ≡)

  • Definition: The biconditional combines two propositions into a third that is true when both have the same truth value, and false when they have different truth values.

  • Written as: P ↔ Q

Truth Table for Biconditional

P

Q

P ↔ Q

F

F

T

F

T

F

T

F

F

T

T

T

Example

  • Equivalent statement: P ↔ Q

    • "It is raining if and only if I have an umbrella."

    • P = "It is raining"

    • Q = "I have an umbrella"

Logical Properties

Types

  • Tautologies

  • Contradictions

  • Contingencies

  • Logical equivalence

Tautologies


  • Definition: Propositions that are always true, regardless of the truth values of atomic propositions.


  • Example: Q ∨ ~Q

    • Where Q = "I passed the exam".


  • Truth Table:

    Q

    ~Q

    Q ∨ ~Q


    T

    F

    T


    F

    T

    T

    Contradictions


    • Definition: Propositions that are always false, regardless of the truth values of atomic propositions.


    • Example: Q ∧ ~Q

      • Where Q = "I passed the exam".


    • Truth Table:

      Q

      ~Q

      Q ∧ ~Q


      T

      F

      F


      F

      T

      F

      Contingencies


      • Definition: Propositions that are neither tautologies nor contradictions.


      • Example: P, ~P where P = "I passed the exam".


      • Truth Table:

        P

        ~P


        T

        F


        F

        T

        Logical Equivalence

        • Definition: Two propositions are logically equivalent if they have the same truth value under all circumstances.

        • Notation: P ≡ Q

        • If propositions are logically equivalent, they can be substituted for one another without changing the truth value.

        Summary

        Propositions

        • Definition: A claim that is either true or false, but not both.

        • Atomic Proposition: A proposition whose truth or falsity does not depend on other propositions.

        • Compound Proposition: Propositions constructed from atomic propositions using connectives.

        • Truth Table: A table that displays the value of a compound proposition for all possible values of its atomic propositions.

        Fundamental Connectives

        • AND (∧): True when both propositions are true.

        • OR (∨): True when at least one proposition is true.

        • XOR (⊕): True when one proposition is true, but not both.

        • Negation (~): True when the proposition is false.

        • Conditional (→): False when the antecedent is true and the consequent is false.

        • Biconditional (↔): True when both propositions have the same truth value.

        Logical Properties

        • Tautologies: Always true propositions.

        • Contradictions: Always false propositions.

        • Contingencies: Propositions that can be true or false.

        • Logically Equivalent: Propositions with the same truth values under all circumstances.