Week 2 - Syntactical Transformations

Transformations using Logical Equivalences

Fundamental Equivalences

Like in Maths and Stats, due to similar properties of union/disjunction, intersection/conjunction and difference/negation, there are logical equivalences that are always true. You don’t need to learn them, but recognise what these words mean:

• Idempotency

• Commutativity

• Associativity

• Distributivity

• De Morgan’s Law

Idempotency is the property where applying an operation multiple times does not change the result beyond the first application.

Commutativity allows changing the order of operands without affecting the outcome.

Associativity concerns how operands are grouped in expressions. Grouping does not affect the result.

Distributivity allows one operation to be distributed over another.

De Morgan's Laws express the negation of conjunctions and disjunctions:

Other Logical Equivalences

• Excluded middle

  • P V ¬P = 1 : the disjunction of P and not P is a tautology i.e. one of them is always true therefore the entire formula will always be true.

• Contraposition

  • P → Q = ¬Q → ¬P

The Equivalence Replacement Rule

Any subformula can be replaced by an equivalent formula without changing the truth-value of its containing formula.

e.g. if G is logically equivalent to H, we can use either formula in a more complex formula i.e. A(…G…) = A(…H…)

This rule is commonly used to simplify formulas.

Disjunctive Normal Form (DNF)

There are standardised ways of rewriting formulas so that they are more amenable for computer use. Every formula can be rewritten in DNF (or CNF, covered later).

We can find the DNF of formulas through:

1. Transformation rules

2. Using truth tables

Literals

In normal form, a literal is a single propositional symbol (or its negation). Literals have one propositional symbol and at most one logical connective (negation).

e.g. P, Q, ¬P and ¬Q are literals wheres P V P, ¬¬Q and Q ^ ¬P are not.

What makes a formula fit DNF?

A formula is in DNF if:

1. The formula only contains disjunction, conjunction and/or negation

2. Negation only appears when as part of a literal

3. Disjunction is not in the scope of a conjunction i.e. if conjunction is part of the formula, they must not join disjunctive subformulas

Rewriting formulas

Using truth tables, you can find logical equivalences in DNF.

Finding DNF of P ←> Q using truth tables

1. Truth table for P ←> Q

The models of the formula P ←> Q are what we are concerned with (recall that models are interpretations of a formula that lead to the formula being true).

2. Interpret

So P ←> Q is only true if v(P) = 1 and v(Q) = 1 OR if v(P) = 0 and v(Q) = 0

i.e. P ←> Q = (P ^ Q) V (¬P ^ ¬Q)

This is in DNF therefore we have found an expression for P ←> Q in DNF.

Conjunctive Normal Form (CNF)

For a formula to be in CNF:

1. It can only include conjunction, disjunction and negation

2. Negation only appears with literals

3. A conjunction is not in the scope of disjunction

   • so P V (P ^ Q) is not in CNF

e.g. (P V ¬Q ^ R) ^ (¬P V Q) is not in CNF. We can check by looking at its syntax tree:

Rewrite rules

Obtaining CNF from truth tables

it’s not as easy as it is for DNF…

Let’s use the example P ←> Q:

1. Take the valuations of the propositional symbols that make the entire formula false.

   • So P ←> Q is false when v(P) = 1 and v(Q) = 0 OR when v(P) = 0 and v(Q) = 1.

   • This can be rewritten as (P ^ ¬Q) V (¬P ^ Q)

2. Negate and simplify the formula found in step 1. This will represent the truth values of the propositional symbols that make the entire formula true → a logical equivalence for the entire formula

   • ¬((P ^ ¬Q) V (¬P ^ Q)) = ¬(P ^ ¬Q) ^ ¬(¬P ^ Q) = (¬P V Q) ^ (P V ¬Q)

   • Negation flips disjunction ←> conjunction through de Morgan’s Law.