Propositional Logic: Connectives & Examples

Propositional Logic

• Explores propositions and their relationships in logic.
• A proposition is a statement that is either true or false, but not both.

Examples of Propositions

• The sun is shining.
• 2 + 2 = 4
• All men are mortal.

Non-Propositions Examples

• What time is it?
• Be quiet!
• x + y = 5 (Equation)

Logical Connectives

• Symbols used to combine simple propositions into compound ones.

Common Logical Connectives

• Negation (¬): Reverses the truth value of a proposition; if p is true, ¬p is false, and vice versa.
• Conjunction (∧): True only if both propositions are true; if p and q are true, p ∧ q is true.
• Disjunction (∨): True if at least one of the propositions is true; if p or q is true, p ∨ q is true.
• Implication (→): False only if the first proposition is true and the second is false; if p is true and q is false, p → q is false.
• Double Implication (↔): True only if both propositions have the same truth value; if p and q are both true or both false, p ↔ q is true.

Truth Tables

• Displays all possible truth values of a compound proposition for all possible combinations of truth values of its simple propositions.

Truth Table - Negation (¬)

• p = V, ¬p = F
• p = F, ¬p = V

Truth Table - Conjunction (∧)

• p = V, q = V, p ∧ q = V
• p = V, q = F, p ∧ q = F
• p = F, q = V, p ∧ q = F
• p = F, q = F, p ∧ q = F

Truth Table - Disjunction (∨)

• p = V, q = V, p ∨ q = V
• p = V, q = F, p ∨ q = V
• p = F, q = V, p ∨ q = V
• p = F, q = F, p ∨ q = F

Truth Table - Implication (→)

• p = V, q = V, p → q = V
• p = V, q = F, p → q = F
• p = F, q = V, p → q = V
• p = F, q = F, p → q = V

Truth Table - Double Implication (↔)

• p = V, q = V, p ↔ q = V
• p = V, q = F, p ↔ q = F
• p = F, q = V, p ↔ q = F
• p = F, q = F, p ↔ q = V

Tautologies, Contradictions, Contingencies

• Tautology: A compound proposition that is always true.
• Contradiction: A compound proposition that is always false.
• Contingency: A compound proposition that can be true or false, depending on its simple propositions.

Laws of Propositional Logic

• Rules used to simplify or transform compound propositions.

Common Laws of Propositional Logic

• Double Negation: ¬¬p ≡ p
• De Morgan's Laws:
  • ¬(p ∧ q) ≡ ¬p ∨ ¬q
  • ¬(p ∨ q) ≡ ¬p ∧ ¬q
• Commutativity:
  • p ∧ q ≡ q ∧ p
  • p ∨ q ≡ q ∨ p
• Associativity:
  • (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
  • (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
• Distributivity:
  • p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
  • p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

Applications

• Applications are found in computer science, philosophy, and mathematics.
• Used in the design of digital circuits, program verification, artificial intelligence, philosophical argument analysis, and as a basis for set and model theory.

Algorithms and Data Structures

Sorting

Problem

• Given a sequence of n elements $a = (a_1, a_2,..., a_n)$.
• Search a permutation of a $(a'_1, a'_2,..., a'_n)$, such that $a'_1 \leq a'_2 \leq... \leq a'_n$.

Sorting Algorithms

• Selection Sort
  • Find the smallest element in a and swap with the first element.
  • Find the smallest element in $a_2... a_n$ and swap it with $a_2$.
  • Continue until a is sorted.
• Insertion Sort
  • Elements of a are considered one at a time.
  • Each element is inserted into the correct spot in the already sorted sequence $a_1... a_{i-1}$.
• Bubblesort
  • Compares consecutive elements and swaps them if they are in the wrong order.
  • This is repeated until no more swaps are required.
• Mergesort
  • Split a into two halves.
  • Sort each hafl recursively.
  • Merge the two sorted halves.
• Quicksort
  • Select a pivot element from a.
  • Divide a into two parts. Elements that are less than the pivot element and parts that are greater than the pivot element.
  • Sort the two parts recursively.

Properties

• In-place: Only requires a constant quantity of additional memory.
• Stable: Maintains the relative order of elements with equal value.

Sorting Algorithms - Overview

• Selection Sort
  • In-place: Yes
  • Stable: No
  • Time complexity (average): $O(n^2)$
  • Time complexity (worst case): $O(n^2)$
• Insertion Sort
  • In-place: Yes
  • Stable: Yes
  • Time complexity (average): $O(n^2)$
  • Time complexity (worst case): $O(n^2)$
• Bubblesort
  • In-place: Yes
  • Stable: Yes
  • Time complexity (average): $O(n^2)$
  • Time complexity (worst case): $O(n^2)$
• Mergesort
  • In-place: No
  • Stable: Yes
  • Time complexity (average): $O(n log n)$
  • Time complexity (worst case): $O(n log n)$
• Quicksort
  • In-place: Yes
  • Stable: No
  • Time complexity (average): $O(n log n)$
  • Time complexity (worst case): $O(n^2)$

Search Algorithms

Problem

• Given a sequence of n elements $a = (a_1, a_2,..., a_n)$ and an element x.
• Searched. The index i of the element in a, such that $a_i = x$, or -I, if x does not occur in a.

Search Algorithms

• Lineare Suche
  • Every element is checked in every a until the x is found.
• Binäre Suche
  • Works only on sorted sequences.
  • x is coompared with the average element in a.
  • Search in the right half or a if x is bigger than the middle element.
  • Repeat this until x is found or the sequence is empty.

Summary