Models for Propositional Logic

From ProofWiki
Jump to navigation Jump to search

Theorem

This page gathers together some useful results that can be used in the derivation of proofs by propositional tableau.


Let $\mathcal M$ be a model for propositional logic, and let $\mathbf A$ and $\mathbf B$ be WFFs of propositional logic.

Then the following results hold.

The symbol $\models$ is used throughout to denote semantic consequence.


Double Negation

$\mathcal M \models \neg \neg \mathbf A$ iff $\mathcal M \models \mathbf A$

This is the rule of Double Negation.


And

$\mathcal M \models \left({\mathbf A \land \mathbf B}\right)$ iff both $\mathcal M \models \mathbf A$ and $\mathcal M \models \mathbf B$

This follows by definition of Conjunction.


Not And

$\mathcal M \models \neg \left({\mathbf A \land \mathbf B}\right)$ iff either $\mathcal M \models \neg \mathbf A$ or $\mathcal M \models \neg \mathbf B$

This follows from De Morgan's Laws: Disjunction of Negations.


Or

$\mathcal M \models \left({\mathbf A \lor \mathbf B}\right)$ iff either $\mathcal M \models \mathbf A$ or $\mathcal M \models \mathbf B$

This follows by definition of Disjunction.


Not Or

$\mathcal M \models \neg \left({\mathbf A \lor \mathbf B}\right)$ iff $\mathcal M \models \neg \mathbf A$ and $\mathcal M \models \neg \mathbf B$

This follows from De Morgan's Laws: Conjunction of Negations.


Implies

$\mathcal M \models \left({\mathbf A \implies \mathbf B}\right)$ iff either $\mathcal M \models \neg \mathbf A$ or $\mathcal M \models \mathbf B$

This follows from Disjunction and Implication.


Not Implies

$\mathcal M \models \neg \left({\mathbf A \implies \mathbf B}\right)$ iff $\mathcal M \models \mathbf A$ and $\mathcal M \models \neg \mathbf B$

This follows from Conjunction and Implication.


Iff

$\mathcal M \models \left({\mathbf A \iff \mathbf B}\right)$ iff either:
both $\mathcal M \models \mathbf A$ and $\mathcal M \models \mathbf B$

or:

both $\mathcal M \models \neg \mathbf A$ and $\mathcal M \models \neg \mathbf B$

This follows by definition of biconditional.


Exclusive Or

$\mathcal M \models \mathbf A \oplus \mathbf B$ iff either:
both $\mathcal M \models \mathbf A$ and $\mathcal M \models \neg \mathbf B$

or:

both $\mathcal M \models \neg \mathbf A$ and $\mathcal M \models \mathbf B$

This follows by definition of exclusive or.


Sources