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 $\MM$ 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

$\MM \models \neg \neg \mathbf A$ if and only if $\MM \models \mathbf A$

This is the rule of Double Negation.


And

$\MM \models \paren {\mathbf A \land \mathbf B}$ if and only if both $\MM \models \mathbf A$ and $\MM \models \mathbf B$

This follows by definition of Conjunction.


Not And

$\MM \models \neg \paren {\mathbf A \land \mathbf B}$ if and only if either $\MM \models \neg \mathbf A$ or $\MM \models \neg \mathbf B$

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


Or

$\MM \models \paren {\mathbf A \lor \mathbf B}$ if and only if either $\MM \models \mathbf A$ or $\MM \models \mathbf B$

This follows by definition of Disjunction.


Not Or

$\MM \models \neg \paren {\mathbf A \lor \mathbf B}$ if and only if $\MM \models \neg \mathbf A$ and $\MM \models \neg \mathbf B$

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


Implies

$\MM \models \paren {\mathbf A \implies \mathbf B}$ if and only if either $\MM \models \neg \mathbf A$ or $\MM \models \mathbf B$

This follows from Disjunction and Implication.


Not Implies

$\MM \models \neg \paren {\mathbf A \implies \mathbf B}$ if and only if $\MM \models \mathbf A$ and $\MM \models \neg \mathbf B$

This follows from Conjunction and Implication.


Iff

$\MM \models \paren {\mathbf A \iff \mathbf B}$ if and only if either:
both $\MM \models \mathbf A$ and $\MM \models \mathbf B$

or:

both $\MM \models \neg \mathbf A$ and $\MM \models \neg \mathbf B$

This follows by definition of biconditional.


Exclusive Or

$\MM \models \mathbf A \oplus \mathbf B$ if and only if either:
both $\MM \models \mathbf A$ and $\MM \models \neg \mathbf B$

or:

both $\MM \models \neg \mathbf A$ and $\MM \models \mathbf B$

This follows by definition of exclusive or.


Sources