UoL CS Notes
Menu

Propositional Logic

COMP111 Lectures

for many purposes, rules are not expressive enough. for example:

  • You cannot express that something is not the case: $\text{not FrenchFootballClub(LiverpoolFC)}$
  • You cannot connect sentences using or:
    $\text{Today, I will do the AI exercise or}$ $\text{I will play football.}$

A proposition is a statement that can be true or false, but not both at the same time.

  • Logic is easy.
  • I eat toast.
  • $2+3=5$

Questions and statements are not propositions.

Reasoning About Propositions

The meeting takes place if all members have been informed in advance, and it is quorate. It is quorate provided that there are at least 15 people present. Member will have been informed in advance if there is not a postal strike.

Therefore:

If the meeting does not take place, we conclude that there were fewer than 15 members present, or there was a postal strike.

Understanding Compound Propositions

Compound statements are built from atomic propositions - the simplest statements that is possible to make about the world.

To simplify this for a computer then we can assign the atomic propositions variables to form a logical statement with:

  • $m:$ The meeting takes place.
  • $a:$ All members have been informed.
  • $p:$ There is a postal strike.
  • $q:$ The meeting is quorate.
  • $f:$ There are at least 15 members present.

From: \(\text{If }a\text{ and }q\text{ then }m\text{. If }f\text{ then }q\text{. If not }p\text{ then }a.\)

Conclude: \(\text{If not }m\text{ then not }f\text{ or }p\)

Connectives

Propositions may be combined with other propositions to form compound propositions. These in turn may be combined into further propositions.

The connectives that may be used are:

Connective English Equivalent Math Symbol Mathematical Equivalent
$\neg$ not $\sim$ Negation
$\wedge$ and $\&$ or $.$ Conjuction
$\vee$ or $\vert$ or $+$ Disjunction
$\iff$ or $\Leftrightarrow$ If and only if $\leftrightarrow$ Equivalence
$\Rightarrow$ If … then $\rightarrow$ Implication

Propositional Formulas

The set of propositional formulas is defines as follows:

  • Every atomic proposition is a propositional formula. We denote atomic propositions by $p, q,a, p_1, p_2,\ldots$
  • If $P$ and $Q$ are propositional formulas, then:
    • $(P\wedge Q)$
    • $(P\vee Q)$
    • $(P\Rightarrow Q)$
    • $(P\Leftrightarrow Q)$

    are propositional formulas.

  • If $P$ is a propositional formula, then $\neg P$ is a propositional formula.

Examples

The following are propositional formulas:

  • $p$
  • $\neg\neg p$
  • $(p\vee q)$
  • $(((p\Rightarrow q)\wedge\neg q)\Rightarrow\neg p)$

The following are not propositional formulas:

  • $p\wedge q$
  • $(p)$
  • $(p\wedge q)\neg q$

Example With Compund Proposition

By this syntax the proposition before would be:

From:

  • $((a\wedge q) \Rightarrow m)$
  • $(f \Rightarrow q)$
  • $(\neg p \Rightarrow a)$

Conclude:

  • $(\neg m \Rightarrow\neg (f\vee p))$