Week 1 – Logic: Propositions & Logical Equivalence

Propositions

• Definition: A proposition (statement) is a declarative sentence that is either TRUE (T) or FALSE (F)—never both.

  • A declarative sentence makes a statement, as opposed to asking a question, giving a command, or expressing an exclamation.

  • The key characteristic is that its truth value must be objectively determinable.

• Truth value: the value (T or F) assigned to the proposition.

• Variable notation: $p, q, r, s, t, \ldots$ used as propositional variables, representing atomic propositions.

Examples (True / False)

• $p$ : “Two plus four equals six.” → T. (Mathematically verifiable as true).

• $q$ : “8 < 5.” → F. (Mathematically verifiable as false).

• $r$ : “2 + 3 = 4.” → F. (Mathematically verifiable as false).

Non-Examples (Not Propositions)

• “It is a prime number.” (The pronoun “It” is unspecified; the truth value cannot be determined without knowing what "It" refers to. It's an open sentence.)

• “He is a USP student.” (The specific individual referred to by “He” is undefined, rendering the truth value indeterminate.)

• Open sentences containing variables: y < 6,\; p - 10 = 13. These become propositions only when specific values are assigned to the variables.

• Commands / questions: “Run !!”, “What is your name?”. These are not declarative sentences and thus do not have truth values.

Compound Propositions & Logical Operators

• New statements formed by combining existing propositions using logical operators.

• Operator precedence (high → low):

  1. Parentheses (): Operations within parentheses are evaluated first.

  2. Negation $\lnot$: Applies to the single proposition immediately following it.

  3. Conjunction $\wedge$ (AND): Evaluated before disjunction.

  4. Disjunction $\vee$ (OR): Evaluated after conjunction.

  • Operators at the same level of precedence are typically evaluated from left to right.

Negation ($\lnot p$)

• Meaning: “not $p$” / “it is not the case that $p$”. It reverses the truth value of a proposition.

• Truth table:

• Example: $p$ : “Today is Monday.” → $\lnot p$ : “Today is not Monday.” If $p$ is true, then $\lnot p$ is false; if $p$ is false, then $\lnot p$ is true.

Conjunction ($p \wedge q$)

• Read “$p$ AND $q$”. It is true only when both $p$ and $q$ are individually true. Otherwise, it is false.

• Truth table:

• Example: $r$ : “2 is prime”, $s$ : “2 is even” → $r \wedge s$ : “2 is prime and even.” (True, since both $r$ and $s$ are true.)

Disjunction ($p \vee q$)

• Read “$p$ OR $q$” (inclusive OR). This means the disjunction is true if $p$ is true, or if $q$ is true, or if both are true.

• False only when both $p$ and $q$ are false.

• Truth table:

• Example: “Either 2 is prime or 2 is even.” (True, because both sub-statements "2 is prime" and "2 is even" are true.)

Conditional / Implication ($p \to q$)

• Read “IF $p$ THEN $q$”. This expresses a cause-and-effect or a logical consequence relationship.

• $p$ = hypothesis/antecedent (the condition); $q$ = conclusion/consequent (the result).

• Truth definition: An implication is FALSE only when the hypothesis ($p$) is true and the conclusion ($q$) is false. In all other cases, it is TRUE. This is often called the "broken promise" scenario: if you promise $p \to q$, you only break the promise if $p$ happens but $q$ doesn't.

• Truth table:

• Equivalent phrasing:

  • “$p$ implies $q$.”

  • “$p$ only if $q$.” (This means if $q$ doesn't happen, $p$ can't happen. Equivalently, if $p$ happens, $q$ must happen.)

  • “$p$ is sufficient for $q$.” (For $q$ to occur, $p$ is enough.)

  • “$q$ is necessary for $p$.” (For $p$ to occur, $q$ absolutely must occur.)

  • “$q$ whenever $p$.”

  • “$q$ even if $p$.”

  • “$q$ follows from $p$.”

  • “A sufficient condition for $q$ is $p$.”

  • “A necessary condition for $p$ is $q$.”

• Re-writing practice:

  1. “I go to the beach whenever it is a sunny day.” → If it is a sunny day ($p$), then I go to the beach ($q$). ($p \to q$)

  2. “You can access the website only if you have paid the subscription fee.” → If you can access the website ($p$), then you have paid the subscription fee ($q$). ($p \to q$) This means paying is necessary for access.

Converse / Inverse / Contrapositive / Negation

• For a given conditional statement $p \to q$:

  • Original Statement: $p \to q$

  • Converse: $q \to p$. Swaps the hypothesis and conclusion.

  • Inverse: $\lnot p \to \lnot q$. Negates both the hypothesis and conclusion.

  • Contrapositive: $\lnot q \to \lnot p$. Swaps and negates both the hypothesis and conclusion. This statement is logically equivalent to the original conditional statement.

  • Negation: $p \wedge \lnot q$. This means the original implication is false (i.e., $p$ occurs but $q$ does not).

• Example: “If it is raining, then the home team wins.” ($p$: "It is raining", $q$: "The home team wins")

  • Converse: “If the home team wins, then it is raining.” (Not necessarily true, even if the original is true.)

  • Inverse: “If it is not raining, then the home team does not win.” (Also not necessarily true.)

  • Contrapositive: “If the home team does not win, then it is not raining.” (Logically equivalent to the original statement, meaning they always have the same truth value.)

  • Negation: “It is raining AND the home team does not win.” (This scenario is when the original implication is false.)

Biconditional ($p \leftrightarrow q$)

• Read “$p$ IFF $q$” / “$p$ if and only if $q$”. This operator asserts that $p$ and $q$ have the exact same truth value.

• True when $p$ and $q$ share the same truth value (both true or both false); false otherwise.

• Truth table: