2. Quine's method and satisfiability

Quine’s method

For any formula $W$ and propositional variable $P$:

• $W$ is a tautology if and only if $W(P/0)$ and $W(P/1)$ are tautologies.
• $W$ is a contradicition if and only if $W(P/0)$ and $W(P/1)$ are contradictions.

Quine’s Tree

Quine’s method can be described graphically using a binary tree.

1. Start with $W$ as the root of the tree.
2. Take the first level in the tree with a propositional symbol, say $P$, in any of the level’s nodes $n$. If none are left, then finish.
3. Let the left child of $n$ be $n(P/1)$ and let its right child be $n(P/0)$.
4. Repeat from $2$.

When no propositional symbols remain:

• $W$ is a tautology if all fo the leaves in the tree are true.
• $W$ is a contradiction if all leaves in the tree are false.
• Otherwise, $W$ is a contingency.

title: Example 1
![](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201%20%26%202/4CCS1ELA%20Elementary%20Logic%20with%20Applications/Week%205.%20Important%20Semantical%20Notions/Pasted%20image%2020211022121610.png)

title: Example 2
![](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%201%20%26%202/4CCS1ELA%20Elementary%20Logic%20with%20Applications/Week%205.%20Important%20Semantical%20Notions/Pasted%20image%2020211022121954.png)

Satisfiability

Satisfiable

A formula $F$ is satisfiable if there is an interpretation $v$ that makes the formula $F$ true. We say $v$ satisfies $F$.

$p$	$\neg p$
T	F
F	T

A set $S=\{A_1,...,A_n\}$ of propositional formulae is satisfiable if there is an interpretation $v$ satisfying every formula in $S$.

Link to original

Model

A model is an interpretation that makes a formula (or set of formulae) true.

We can denote that $v$ is a model of $A$ by $\boxed{v \models A}$.

Set of all models

The set of all models of a formula $A$ is denoted by $\boxed{\bmod(A)}$.

For example, it is written as $\mathrm{mod}(\mathcal{S})=\{v_0,v_7\}$. If $\mathcal{S}$ is not satisfiable, then $\mathrm{mod}(\mathcal{S})=\varnothing$.

Link to original

Link to original