3. Tautologies, Satisfiability and Consistency

Tautologies, Satisfiability and Consistency

Computing truth tables of compound formulas

Given the formula: $(p\to (q\wedge r))\to ((p\wedge q)\to \neg r)$

• It has $2^3=8$ rows as it contains $3$ variables.

$p$	$q$	$r$	$\neg r$	$p\wedge q$	$(p\wedge q)\to (\neg r)$	$q\wedge r$	$p\to (q\wedge r)$	$(p\to (q\wedge r))\to ((p\wedge q)\to (\neg r))$
F	F	F	T	F	T	F	T	T
F	F	T	F	F	T	F	T	T
F	T	F	T	F	T	F	T	T
F	T	T	F	F	T	T	T	T
T	F	F	T	F	T	F	F	T
T	F	T	F	F	T	F	F	T
T	T	F	T	T	T	F	F	T
T	T	T	F	T	F	T	T	F

Precedence of logical operators

We have to use parantheses to not create confusion, for example $p\wedge q\vee r$ can have two different truth tables depending on how you parse it. To reduce the number of brackets, we agree $\neg$ takes priority, for example $\neg p\wedge q$ means $(\neg p)\wedge q$.

Propositional satisfiability

Tautology

A tautology (otherwise known as valid) is a formula that is true under all [[Interpretation|interpretations]], every row in a truth table of a tautology makes it true.

We can denote a tautology by $\boxed{\models x}$, where $x$ is a formula which is a tautology.

$p$	$\neg p$	$p\vee \neg q$
T	F	T
F	T	T

Given the set of formulas, $\Delta = \{ A_1, A_2, A_3 \}$, provided $\Delta \models \varphi$:
 
$$
	\begin{aligned}
		\Delta &\models \varphi \\
		A_1, A_2, A_3 &\models \varphi \\
		A_1 \land A_2 \land A_3 &\models \varphi \\
		A_1 , A_2 &\models A_3 \rightarrow \varphi \\
		A_1 &\models A_2 \rightarrow (A_3 \rightarrow \varphi) \\
		\emptyset &\models A_1 \rightarrow (A_2 \rightarrow (A_3 \rightarrow \varphi)) \\
	\end{aligned}
$$

Link to original

Contradiction

A contradiction is a formula that is false under all [[Interpretation|interpretations]].

$p$	$\neg p$	$p\wedge \neg q$
T	F	F
F	T	F

Link to original

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

Consistency

Consistent

A collection of formulas is consistent if: ?

• Not only each and every formula in the collection is satisfiable.
• It is possible to find a truth table assignment with the propositional variables in them that make all of the formulas true at the same time.

Link to original

Given the following specifications:
- Message is stored in buffer or it is trasmitted. $p\vee q$
- Message is not stored in buffer. $\neg p$
- Message is stored in buffer then it is trasmitted. $p \rightarrow q$
 
|  $p$  |  $q$  | $p \vee q$ | $\neq p$ | $p\rightarrow q$ |
|:-----:|:-----:|:----------:|:--------:|:----------------:|
|   T   |   T   |     T      |    F     |        T         |
|   T   |   F   |     T      |    F     |        F         |
|  *F*  |  *T*  |   **T**    |  **T**   |      **T**       |
|   F   |   F   |     F      |    T     |        T         |