Notes - Logic MT24, Propositional logic

[[Course - Logic MT24]]^U
- See also: [[Notes - Logic and Proof MT24, Basic definitions for propositional logic]]^U
- This introduction to propositional logic is much more rigorous and is focused on more than just formulas in CNF.

Flashcards

@Define a proposition.

Something which can be true or false.

@Define a formula of $\mathcal L _ \text{prop}$.

A string from the alphabet $\{\lnot, \to, \wedge, \vee, \leftrightarrow, (, ), p _ 0, p _ 1, \ldots\}$ in one of the following forms:

$p _ i$ where $i \in \mathbb N$
$\lnot \phi$, where $\phi$ is a formula
The combination of two formulas $\phi$ and $\psi$:
- $(\phi \to \psi)$, “implication”
- $(\phi \land \psi)$, “conjunction”
- $(\phi \lor \psi)$, “disjunction”
- $(\phi \leftrightarrow \psi)$, “equivalence”

Why is $p _ 0 \land (p _ 1 \to \lnot p _ 2)$ not a formula of $\mathcal L _ \text{prop}$?

Because it would need to be enclosed in parentheses, but it is not.

@State the unique readability theorem.

Suppose $\phi$ is a formula of $\mathcal L _ \text{prop}$. Then exactly one of the following holds:

$\phi$ is $p _ i$ for some $i \in \mathbb N$
$\phi$ is $\lnot \psi$ for a unique formula $\psi$
$\phi$ is $(\psi \star \chi)$ for a unique pair of formulas $\psi$ and $\chi$.

@Prove the unique readability theorem, i.e. that if $\phi$ is a formula of $\mathcal L _ \text{prop}$. Then exactly one of the following holds:

$\phi$ is $p _ i$ for some $i \in \mathbb N$
$\phi$ is $\lnot \psi$ for a unique formula $\psi$
$\phi$ is $(\psi \star \chi)$ for a unique pair of formulas $\psi$ and $\chi$.

@todo, in problem sheet 1.

Define $\text{Form}(\mathcal L _ \text{prop})$.

The set of all formulas of $\mathcal L _ \text{prop}$.

@Define a valuation $v$, and explain its extension $\tilde v$.

A function

\[v : \\{p_0, \ldots, \\} \to \\{T, F\\}\]

(i.e. an assignment of true or value to the propositional variables).

$v$ can be extended to a function $\tilde v$:

\[\tilde v : \text{Form}(\mathcal L_\text{prop}) \to \\{T, F\\}\]

by “evaluating the formula” given those truth values (what this means can be made rigorous with the unique readability theorem).

@Define what it means for a valuation $v$ to satisfy a formula $\phi$.

\[\tilde v(\phi) = T\]

@Define what it means for a formula $\phi$ to be satisfiable

It is satisfied by some valuation.

@Define what it means for a formula $\phi$ to be logically valid/a propositional tautology.

$\phi$ is satisfied by every valuation.

@State a relationship between satisfiability of a formula $\phi$ and logical validity?

$\phi$ is satisfiable iff $\lnot \phi$ is not logically valid.

@Define what it means for a valuation to satisfy $\Gamma$, where $\Gamma$ is a set of formulas.

$v$ satisfies $\Gamma$ if it satisfies every element of $\Gamma$.

@Define what it means for a formula $\phi$ to be a logical consequence of $\Gamma$, i.e. $\Gamma \models \phi$?

Every valuation that satisfies $\Gamma$ satisfies $\phi$: for all valuations $v$, if $\tilde v (\psi) = T$ for all $\psi \in \Gamma$, then $\tilde v(\phi) = T$.

@State a lemma that connects the entailment of two formulas with one formula entailing an implication, and then state a useful special case.

Suppose:

$\Gamma$ is a set of formulas
$\psi$, $\phi$ are formulas (not necessarily in $\Gamma$)

Then:

\[\Gamma \cup \\{\psi\\} \models \phi \text{ iff } \Gamma \models (\psi \to \phi)\]

and, in particular when $\Gamma$ is empty:

\[\psi \models \phi \text { iff } \models \psi \to \phi\]

(i.e. $\psi \models \phi$ iff $\psi \to \phi$ is valid).

@Prove that if:

$\Gamma$ is a set of formulas
$\psi$, $\phi$ are formulas (not necessarily in $\Gamma$)

then:

\[\Gamma \cup \\{\psi\\} \models \phi \text{ iff } \Gamma \models (\psi \to \phi)\]

Suppose that $\Gamma \cup \{\psi\} \models \phi$. Let $v$ be a valuation satisfying $\Gamma$, we aim to show that this valuation also satisfies $(\psi \to \phi)$.

If $\tilde v(\psi) = T$, then $\tilde v(\phi) = T$, since $\Gamma \cup \{\psi\} \models \phi$. Hence $\tilde v((\psi \to \phi)) = T$ by the truth table of “$\to$”.
If $\tilde v(\psi) = F$, then $\tilde v((\psi \to \phi)) = T$ by the truth table of “$\to$”.

Hence $\Gamma \models (\psi \to \phi)$.

Now suppose that $\Gamma \models (\psi \to \phi)$. Let $v$ be a valuation satisfying $\Gamma \cup \{\psi\}$. Then $\tilde v((\psi \to \phi)) = T = \tilde v(\psi)$, so $\tilde v(\phi) = T$ by the truth table of “$\to$”.

Hence $\Gamma \cup \{\psi\} \models \phi$.

@Define what it means for two formulas $\phi$ and $\psi$ to be logically equivalent and give the notation used for this?

$\phi \models \psi$ and $\psi \models \phi$, so $\tilde v(\phi) = \tilde v(\psi)$ for every valuation $v$. The notation is $\phi \equiv \psi$.

@Define an $n$-ary truth function?

\[J : V_n \to \\{T, F\\}\]

where $V _ n$ is the set of all valuations on the first $n$ propositional variables, i.e. functions $v : \{p _ 0, \ldots, p _ {n-1}\} \to \{T, F\}$.

@Define $\text{Form} _ n(\mathcal L _ \text{prop})$.

The set of all formulas which contain only variables from the set $\{p _ 0, \ldots, p _ {n-1}\}$.

Suppose $\phi \in \text{Form} _ n(\mathcal L _ \text{prop})$. @Define the $n$-ary truth function that $\phi$ represents.

An $n$-ary truth function is a function of the form

\[J : V_n \to \\{T, F\\}\]

where $V _ n$ is the set of all valuations on $n$ propositional variables. Then $\phi$ represents the $n$-ary truth function given by

\[\begin{aligned} &J_\phi^n : V_n \to \\{T, F\\} \\\ &v \mapsto \tilde v(\phi) \end{aligned}\]

What is true about the $n$-ary truth functions corresponding to logically equivalent formulas $\phi$ and $\psi$?

They are equal.

@Prove that for every $n \ge 1$, every $n$-ary truth function $J : V _ n \to \{T, F\}$ is represented by a formula in disjunctive normal form.

Let

\[U := \\{v \in V_n \mid J(v) = T\\}\]

i.e. the set of valuations where $J$ is true. If $U$ is empty, then take $\phi = (p _ 0 \land \lnot p _ 0)$. Then $\phi$ represents $J$ since both are identically false.

Otherwise, suppose $U = \{v _ 0, \ldots, v _ {k-1}\}$. Consider the formula

\[\phi := \bigvee^{k-1}_{i = 0} \bigwedge^{n-1}_{j = 0} \psi_{i,j}\]

where

\[\psi_{i,j} = \begin{cases} p_j &\text{if } v_i(p_j) = T \\\\ \lnot p_j &\text{if } v_i(p_j) = F \end{cases}\]

Now consider an arbitrary valuation $w \in V _ n$ and some $0 \le i \le k-1$. Then

\[\tilde w\left( \bigwedge^{n-1}_{j = 0} \psi_{i,j} \right) = T \iff w = v_i\]

since the construction of $\psi$ ensures that the valuations must match exactly. Hence

\[\begin{aligned} J^n_\phi (w) = T &\iff \tilde w(\phi) = T \\\\ &\iff (w = v_0 \text { or ... or } w = v_{k-1}) \\\\ &\iff w \in U \\\\ &\iff J(w) = T \end{aligned}\]

so then $J^n _ \phi = J$.

Suppose that $\ast _ 1, \ldots, \ast _ k$ are truth-functional connectives. @Define

\[\mathcal L_\text{prop} [\ast_1, \ldots, \ast_k]\]

and

\[\text{Form}(\mathcal L_\text{prop} [\ast_1, \ldots, \ast_k])\]

The language with those connectives and the corresponding formulas.

Suppose that $\ast _ 1, \ldots, \ast _ k$ are truth-functional connectives and that $\mathcal L _ \text{prop} [\ast _ 1, \ldots, \ast _ k]$ is the corresponding language. @Define what it means for $\mathcal L _ \text{prop} [\ast _ 1, \ldots, \ast _ k]$ to be adequate.

Every $n$-ary truth function is represented by some $\phi \in \text{Form} _ n(\mathcal L _ \text{prop}[\ast _ 1, \ldots, \ast _ k])$, i.e. every $n$-ary truth function can be made out of an expression in this language.

@Define $\mathcal L _ 0$.

\[\mathcal L_\text{prop}[\lnot, \to]\]

(i.e. propositional formulas using only negation and implication, this is adequate).

Flashcards

Related posts