Propositional Logic Fundamentals

Fundamentals of Propositional Logic

• Definition of a Proposition:

  • A proposition is a declarative sentence that declares a fact.
  • A proposition must evaluate to either True ($T$) or False ($F$), but it cannot be both True and False simultaneously.

• Non-Propositions:

  • Sentences or mathematical expressions that do not express a complete, definite statement of fact with a fixed truth value are not propositions.
  • Examples of non-propositions include:
  • Problem numbers or question prompts (such as $07-423$)
  • Equations with free variables whose truth values depend on variable assignments, such as $-x + y = 3$
  • Commands or imperative requests

• Propositional Variables:

  • Variables are used to represent specific propositions or facts.
  • Standard lowercase letters are used as propositional variables, primarily $p$, $q$, $r$, and $s$
  • Capital letters are not used for simple propositional variables because they are strictly reserved for propositional functions.

Negation of a Proposition

• Definition and Symbolic Notation:

  • The negation of a proposition $p$ is denoted symbolically by $\neg p$ or $\sim p$.
  • Negation represents the logical NOT operation.
  • Verbally, $\neg p$ is stated as "It is not the case that $p$".

• Example 1 (Ronnie and Taco Bell):

  • Define the propositional variable: $r = \text{Ronnie likes Taco Bell}$
  • The negation $\neg r$ can be written in either of the following equivalent forms:
  • "It is not the case that Ronnie likes Taco Bell"
  • "Ronnie does not like Taco Bell" (or "Ronnie does not like TB")

• Example 2 (Thor's Hammer and Double Negation):

  • Statement: "Thor's hammer is not named Mjölain."
  • Define the positive baseline propositional variable: $m = \text{Thor's hammer is named M.}$
  • The given statement corresponds to the negation $\neg m$.
  • Evaluating the negation of this statement produces a double negation: $\neg(\neg m)$
  • Double Negation Cancellation Law: A double negation operator cancels out, returning the original proposition:     $\neg(\neg m) \equiv m$

Truth Values and Truth Tables

• Truth Values:

  • Every proposition evaluates to one of two valid truth values: True ($T$) or False ($F$).

• Truth Table for Negation:

  • A truth table outlines the truth values of a logical expression based on input proposition variables.
  • For a proposition $p$ and its negation $\neg p$:
  • When $p = T$, $\neg p = F$
  • When $p = F$, $\neg p = T$

Logical Connectives: Conjunction, Disjunction, and Exclusive OR

• Conjunction ($\land$):

  • Let $p$ and $q$ be propositions.
  • The conjunction of $p$ and $q$ is "p and q", denoted symbolically as $p \land q$.
  • Conjunction represents the logical AND operation.
  • The compound statement $p \land q$ is True ($T$) if and only if both $p$ and $q$ are True ($T$).
  • If either $p$ or $q$ (or both) is False ($F$), then $p \land q$ is False ($F$).

• Disjunction ($\lor$):

  • Let $p$ and $q$ be propositions.
  • The disjunction of $p$ and $q$ is "p or q", denoted symbolically as $p \lor q$.
  • Disjunction represents the logical OR operation.
  • The compound statement $p \lor q$ is True ($T$) when $p$ is True ($T$), $q$ is True ($T$), or both $p$ and $q$ are True ($T$).
  • Disjunction is inclusive.

• Exclusive OR ($\oplus$ / XOR):

  • For propositions $p$ and $q$, the Exclusive OR is abbreviated as XOR or denoted symbolically as $p \oplus q$
  • The statement $p \oplus q$ is True ($T$) only when exactly one of $p$ OR $q$ is True ($T$).
  • The statement $p \oplus q$ evaluates to False ($F$) in all other cases (when both $p$ and $q$ are True, or both $p$ and $q$ are False).
  • The logical expansion for Exclusive OR using standard connectives is:     $(p \lor q) \land \neg(p \land q)$