Mathematics and Problem Solving

Laws of Propositional Logic

In the assessment you will need to make use of these numbered laws of propositional logic expressed as axiom schemata.

Law 1.1: Complement Law of Negation

\[ ( \neg \top) \iff \bot \]

\[ ( \neg \bot) \iff \top \]

Law 1.2: Double Negation

\[ ( \neg \neg \phi) \iff \phi \]

Law 2.1: Idempotence of Conjunction

\[ (\phi \wedge \phi) \iff \phi \]

Law 2.2: Conjunction identity

\[ (\phi \wedge \top) \iff \phi \]

Law 2.3: Domination Law of Conjunction

\[ (\phi \wedge \bot) \iff \bot \]

Law 2.4: Complement law

\[ (\phi \wedge ( \neg \phi)) \iff \bot \]

Law 2.5: Commutativity of Conjunction

\[ (\phi \wedge \chi) \iff (\chi \wedge \phi) \]

Law 2.6: Associativity of Conjunction

\[ (\phi \wedge \chi) \wedge \psi \iff \phi \wedge (\chi \wedge \psi) \]

Law 3.1: de Morgan’s Laws

\[ \neg (\phi \wedge \chi) \iff (( \neg \phi) \vee ( \neg \chi)) \]

\[ \neg (\phi \vee \chi) \iff (( \neg \phi) \wedge ( \neg \chi)) \]

Law 3.2: Idempotence of Disjunction

\[ (\phi \vee \phi) \iff \phi \]

Law 3.3: Disjunction Identity

\[ (\phi \vee \bot) \iff \phi \]

Law 3.4: Domination Law of Disjunction

\[ (\phi \vee \top) \iff \top \]

Law 3.5: Associativity of Disjunction

\[ \phi \vee (\chi \vee \psi) \iff (\phi \vee \chi) \vee \psi \]

Law 3.6: Commutativity of Disjunction

\[ \phi \vee \chi \iff \chi \vee \phi \]

Law 3.7: Complement law

\[ (( \neg \phi) \vee \phi) \iff \top \]

Law 3.8: Disjunction distributes through conjunction

\[ \phi \vee (\chi \wedge \psi) \iff (\phi \vee \chi) \wedge (\phi \vee \psi) \]

Law 3.9: Conjunction distributes through disjunction

\[ \phi \wedge (\chi \vee \psi) \iff (\phi \wedge \chi) \vee (\phi \wedge \psi) \]

Law 4.1: Definition of Implication

\[ (\phi \implies \chi) \iff (( \neg \phi) \vee \chi) \]

Law 5.1: Associativity of Equivalence

\[ ((\phi \iff \chi) \iff \psi) \iff (\phi \iff (\chi \iff \psi)) \]

Law 5.2: Commutativity of Equivalence

\[ (\phi \iff \chi) \iff (\chi \iff \phi) \]

Law 5.3: Equivalence Identity

\[ (\phi \iff \phi) \iff \top \]

Law 5.4: Complement Law

\[ (\phi \iff ( \neg \phi)) \iff \bot \]

Law 5.5: Definition of Equivalence

\[ (\phi \iff \chi) \iff ((\phi \implies \chi) \wedge (\chi \implies \phi)) \]