Notes - Logic and Proof MT24, Basic definitions for propositional logic

Created: October 14, 2024
Updated: January 01, 2025

Flashcards

Suppose:

  • $p _ 1, p _ 2, \ldots$ are an infinite set of propositional variables.

Can you inductively define the set of all formulas of propositional logic?
  1. $\mathbf{true}$ and $\mathbf{false}$ are formulas
  2. All propositional variables are formulas
  3. For every formula $F$, $\lnot F$ is a formula
  4. For all formulas $F$ and $G$, $(F \land G)$ and $(F \lor G)$ are formulas.

Can you define

\[F \to G\]

in terms of the connectives $\land, \lor$ and $\lnot$?
\[\lnot F \lor G\]

Can you define

\[F \to G\]

in terms of the connectives $\land, \lor$ and $\lnot$?
\[\lnot F \lor G\]

Can you define

\[F \oplus G\]

in terms of the connectives $\land, \lor$ and $\lnot$?
\[(F \land \lnot G) \lor (\lnot F \land G)\]

What is the formal definition of a valuation/assignment $\mathsf v$?
\[v : \\{ p_i \mid i \in \mathbb N \\} \to \\{0, 1\\}\]

A function from the set of propositional variables to the set of truth values.

Suppose we have a valuation/assignment $\mathsf v$ defined as a function from the set of propositional variables to the set of truth values:

\[v : \\{ p_i \mid i \in \mathbb N \\} \to \\{0, 1\\}\]

Can you inductively extend the valuation to the set of all formulas?
  • Base cases: $v(\mathbf{true}) = 1$, $v(\mathbf{false}) = 0$.
  • Inductive step: if $F$ and $G$ are formulas, then
    • $v(F \land G) = \min(v(F), v(G))$
    • $v(F \lor G) = \max(v(F), v(G))$
    • $v(\lnot F) = 1 - v(F)$

What natural partial order is there on the set of valuations?

Pointwise, $v \le v’$ if $v(p _ i) \le v’[p _ i]$ for $i = 1, \ldots, n$.

What does the notation

\[v \models F\]

mean?
\[v(F) = 1\]

i.e. $v$ satisfies/models $F$.

What does it mean for a formula $F$ to be a tautology/valid?

All valuations/assignments satisfy/model $F$.

Can you give a connection between unsatisfiability and validity?
\[F \text{ unsatisfiable} \iff \lnot F \text{ valid}\]

If $\mathbf S$ is a set of formulas, what does the notation

\[\mathbf S \models G\]

mean?

Every assignment that satisfies each formula in $\mathbf S$ also satisfies $G$.

What does

\[\models G\]

mean?

$G$ is a valid (because this is shorthand for $\emptyset \models G$).

What does it mean for formulas $F$ and $G$ to be logically equivalent, and what is the notation for this?
\[v(F) = v(G)\]

for every assignment $v$. The notation is

\[F \equiv G\]

What is a literal?

A propositional variable or its negation.

What’s the general expression for a formula $F$ in CNF?
\[F = \bigwedge^n _ {i = 1} \bigvee^{m _ i} _ {j = 1} L _ {i,j}\]

What’s the general expression for a formula $F$ in DNF?
\[F = \bigvee^n _ {i = 1} \bigwedge^{m _ i} _ {j = 1} L_{i, j}\]

What CNF formula is $\mathbf{true}$ equivalent to?

A CNF formula with no clauses.

What CNF formula is $\mathbf{false}$ equivalent to?

A CNF formula with one empty clause.

What’s the notation for a formula $G$ with $F$ substituted for all occurrences of $p$?
\[G[F/p]\]

What does the notation $G[F/p]$ mean?

The formula $G$ where all occurrences of $p$ are substituted by $F$.

If $v$ is an assignment and $b \in \{0, 1\}$ is a truth value, what does $v _ {[p \mapsto b]}$ mean and what is the name of this operation?
\[v_{[p \mapsto b]} (q) = \begin{cases} b &\text{if } q = p \\\\ v(q) &\text{if } q \ne p \end{cases}\]

This is called the “update operation”.

Can you @state a lemma which relates the substitution operation on formulas and the update operation on assignments?

Substitution Lemma. Suppose:

  • $F, G$ are formulas
  • $p$ is a propositional variable
  • $v$ is an assignment

Then:

\[v(G[F/p]) = v_{[p \mapsto v(F)]} (G)\]

@Prove the substitution lemma, that if:

  • $F, G$ are formulas
  • $p$ is a propositional variable
  • $v$ is an assignment

then:

\[v(G[F/p]) = v_{[p \mapsto v(F)]} (G)\]

Proof by induction on $G$.

Base cases: Suppose $G = p$. Then $v(p[F/p]) = v(F) = v _ {[p \mapsto v(F)]}(p)$. Now suppose $G = q$, $q \ne p$: Then $v(q[F/p]) = v(q) = v _ {[p \mapsto v(F)]}(q)$.

Inductive cases: Given only for conjunction, disjunctive and negation are similar.

\[\begin{aligned} v \models (G_1 \land G_2) [F/p] &\text{ iff } v \models G_1[F/p] \land G_2[F/p] \\\\ &\text{ iff } v \models G_1[F/p] \text{ and } v \models G_2[F/p] \\\\ &\text{ iff } v_{[p \mapsto v(F)]} \models G_1 \text{ and } v_{[p \mapsto v(F)]} \models G_2 &&(\star) \\\\ &\text{ iff } v_{[p \mapsto v(F)]} \models G_1 \land G_2 \end{aligned}\]

where $(\star)$ is justified by the inductive hypothesis.

Suppose $L$ is a literal. What is $\overline L$, and how is this different from what you might think it is?
\[\overline L = \begin{cases} \lnot p &\text{if } L = p \\\\ p &\text{if }L = \lnot p \end{cases}\]

This is different from $\lnot P$, since $p$ and $\lnot \lnot p$ are different formulas (although they are logically equivalent).

What does it mean for $F$ and $G$ to be equisatisfiable?

$G$ is satisfiable iff $F$ is satisfiable.

How can you regard a CNF formula as a set, and what is

\[(p_3 \land (p_1 \lor p_2 \lor \lnot p_2) \land p_3)\]

in this interpretation?
\[\\{\\{p_3\\}, \\{p_1, p_2, \lnot p_2\\}\\}\]

In the set representation of CNF formulas, what is the empty clause $\square$ equivalent to?
\[\mathbf{false}\]

In the set representation of CNF formulas, what is the empty set $\emptyset$ equivalent to?
\[\mathbf{true}\]

What are complementary literals in a propositional formula?

A variable and its negation.



Related posts