COMP 1805: Propositional Logic - Study Notes

COMP 1805: Propositional Logic - Study Notes

What is Logic?

• Definition: Logic is the foundation of all mathematical reasoning and automated reasoning.

• Purpose of Logic:

  • Provides precise meaning to mathematical statements, eliminating ambiguity.

  • Enables computers to reason effectively.

• Focus of Study:

  • Rules and techniques to differentiate correct reasoning from incorrect reasoning.

  • Involvement of claims or statements in reasoning:

  • Making Claims: Formulating assertions or propositions.

  • Backing Claims: Supporting propositions with reasons.

  • Drawing Consequences: Analyzing implications of claims.

Proposition

• Definition: The fundamental building block of logic, known as a truth-bearer.

• Characteristics:

  • A proposition is a declarative sentence that has a truth value (either true or false but not both).

  • Examples of Propositions:

  • “Alex loves Eve”

  • “Eve is loved by Alex”

  • Both expressions convey the same proposition despite different wording.

Examples of Propositions

• False Propositions:

  • Toronto is the capital of Canada.

  • All apples are bananas.

  • $1 + 1 = 3$

  • The Moon is made of cheese.

  • The sum of two prime numbers is even.

• True Propositions:

  • Carleton University is located in Ottawa.

  • COMP1805 is a prerequisite for COMP2804.

  • 12 < 15

  • $3$ is the smallest odd prime number.

Not Propositions

• Non-Decalrative Sentences:

  • Interrogative sentences (questions): “Are you happy today?”

  • Imperative sentences (commands): “Let’s go now.”

  • Other examples:

  • “Assume the function is increasing.”

  • Paradoxical Statements:

    • “This sentence is false” (Truth depends on other information).

    • “$x^2 + y <br>eq 1$” (truth can vary).

Propositional Variables

• Definition: Variables used to represent propositions, similar to numerical variables in mathematics.

• **Notation and Example: **

  • E.g., Let $Q$ represent the proposition “$2$ is a prime number.”

• Variable Denotation:

  • Use single letters like $a$, $b$, $c$,…, $p$, $q$, $r$,…, $x$, $y$, $z$,

  • Avoid using $T$ and $F$ for naming variables.

• Examples:

  • $a$ = “The Sun is a star”

  • $p$ = “$5 + 3 = 9$”

Truth Values

• Definition: Each proposition has a truth value.

• True and False Representation:

  • If a proposition is true, its truth value is noted as true, True, $T$, or $1$.

  • If a proposition is false, its truth value can be noted as false, False, $F$, or $0$.

  • Importance of Consistency:

  • Maintain consistency in notation throughout logical expressions.

Atomic Propositions

• Definition: An atomic proposition expresses a single fact and cannot be simplified into simpler propositions.

• Examples of Atomic Propositions:

  • $2 + 3 = 5$ [True]

  • $9$ is a prime number. [False]

  • Carbon is the 5th element of the periodic table. [False]

  • A hydrogen atom has one proton. [True]

Compound Propositions

• Definition: Compounded propositions formed from atomic propositions by logical connectives.

• Examples:

  • “A student can have soup with dinner” & “A student can have salad with dinner” form a compound proposition.

• Connectives: Logical operators used to create compound propositions.

Logical Operators (Connectives)

• Definition: Logical operators enable the formation of compound propositions from atomic propositions.

• Types of Operators:

  • Unary Operators: Act on a single input, e.g., negation (−).

  • Binary Operators: Act on two inputs, e.g., addition (+). Examples include:

  • Negation: $<br>eg p$

  • Binary operations like conjunction and disjunction.

Negation

• Read as: “not $p$”

• Examples:

  • Let $p$ = “$2$ is a prime number”

  • $<br>eg p$ = “It is not the case that $2$ is a prime number”

• Truth Table for Negation:
  | $p$ | $<br>eg p$ |
  | ------- | ---------------- |
  | T | F |
  | F | T |

Conjunction (AND)

• 
  

• Definition: A conjunction $p ∧ q$ means both propositions $p$ and $q$ must be true.

• 
  

• Examples:

  • “The algorithm is correct and efficient.”

• 
  

• Truth Table for Conjunction:
  

  $p$	$q$	$p ∧ q$
  T	T	T
  T	F	F
  F	T	F
  F	F	F
  Disjunction (OR)

  • 
    

  • Definition: A disjunction $p ∨ q$ means at least one of the propositions is true (inclusive).

  • 
    

  • Example:

    • “I answer emails using my laptop or my phone.”

  • 
    

  • Truth Table for Disjunction:
    

    $p$	$q$	$p ∨ q$
    T	T	T
    T	F	T
    F	T	T
    F	F	F
    Exclusive OR (XOR)

    • 
      

    • Definition: Denoted as $p⨁q$, means either $p$ or $q$ is true but not both.

    • 
      

    • Truth Table for Exclusive OR:
      

      $p$	$q$	$p⨁q$
      T	T	F
      T	F	T
      F	T	T
      F	F	F
      Conditional Statement/Implication

      • 
        

      • Definition: An implication $p ⟶ q$ states that if $p$ is true, then $q$ must also be true.

      • 
        

      • Truth Table for Implication:
        

        $p$	$q$	$p ⟶ q$
        T	T	T
        T	F	F
        F	T	T
        F	F	T
        Biconditional (iff)

        • 
          

        • Definition: The biconditional $p ⟷ q$ is read as “$p$ if and only if $q$.”

        • 
          

        • It means: Both $p$ and $q$ have the same truth value.

        • 
          

        • Truth Table for Biconditional:
          

          $p$	$q$	$p ⟷ q$
          T	T	T
          T	F	F
          F	T	F
          F	F	T
          Precedence of Operators

          • Order of Evaluation:

          1. Parentheses

          2. Negation

          3. Conjunction

          4. Disjunction

          5. Implication

          6. Biconditional

          • Example evaluations:

            • $x ∨ (y ∧ z)$

            • $(<br>eg p) ⟶ ((q ∧ r) ∨ s)$

            • $(p ⟶ q ⟶ r)$

            • $(a ∧ b) ∧ c$

          Building Truth Tables

          • Truth table: A systematic arrangement to show truth values based on combinations of atomic propositions.

          • Columns in Truth Table:

            • Atomic propositions $p1, p2, …, p_n$

            • One last column for final proposition $P$

            • May include columns for intermediate propositions.

          • Example of Steps to Build a Truth Table:

          1. Start with all atomic propositions

          2. Fill truth values systematically based on the number of variables (2^n rows).

          Programming Logic Operators

          • Using logical operators in programming languages like Python and Java:

            • Negation:

            • Python: not x

            • Java: !x

            • Conjunction:

            • Python: x and y

            • Java: x && y

            • Disjunction:

            • Python: x or y

            • Java: x || y

            • Exclusive OR:

            • Python: (x and not y) or (not x and y)

            • Java: (x && !y) || (!x && y)