Back

# Notes on Propositional Logic

A proposition is a statement that can be true or false. Propositional logic uses true statements to form or prove other true statements.

There are two parts to propositional logic:

Representation (syntax): How to represent a proposition.
Reasoning (algorithm): How to create or prove new propositions.

## Representation:

A proposition is defined as:
1. A propositional symbol: p (propositions will always be lowercase)
2. The negation of a proposition: !p (traditionally a '¬' symbol)
3. The disjunction of two propositions: p+q (traditionally a 'v' symbol)
4. The conjunction of two propositions: p*q (traditionally a '^' symbol)
5. An implication: p=>q
6. A logical equivalence: p<=>q
7. An ordering operation: (p)
8. T (true)
9. F (false)

The order of operations is !, *, +, =>, <=>

This definition can be decribed by the following unambiguous BNF grammar:

Sentence -> EquivalenceSentence
EquivalenceSentence -> ImplicationSentence <=> EquivalenceSentence | ImplicationSentence
ImplicationSentence -> ConjunctiveSentence => ImplicationSentence | ConjunctiveSentence
ConjunctiveSentence -> DisjunctiveSentence + ConjunctiveSentence | DisjunctiveSentence
DisjunctiveSentence -> NegateSentence * DisjunctiveSentence | NegateSentence
NegateSentence -> !NegateSentence | GroupingSentence
GroupingSentence -> (Sentence) | AtomicSentence
AtomicSentence -> T | F | p | q | r | ...

The value of a proposition can be found by making a truth table from its components.

Example: (p*q)+r

```
p	q	r	p*q	(p*q)+r
0	0	0	0	0
0	0	1	0	1
0	1	0	0	0
0	1	1	0	1
1	0	0	0	0
1	0	1	0	1
1	1	0	1	1
1	1	1	1	1
```

### Properties of Propositional Operators:

```	+ and * are communitive:
p+q <==> p+p
p*q <==> q*p
+ and * are associative:
(p+q)+r <==> p+(q+r)
(p*q)*r <==> p*(q*r)
+ is distributable over *:
p+(q*r) <==> (p+q)*(p+r)
* is distributable over +:
p*(q+r) <==> (p*q)+(p*r)
DeMorgan's Theorem:
!(p+q) <==> !p * !q
!(p*q) <==> !p + !q
Complementation:
!(!p) <==> p
```

### Symantics and Definitions:

Interpretation
An interpretation can be described as one line of the truth table.
An interpretation can also be described as a mapping named 'G' that
takes a set of propositions named 'P' and returns T or F.
Example: (p*q)+r is true for interpretation G(pqr)=011

Valid
A proposition is valid if it is true for any interpretation G.
Example: p+!p is Valid (p or not p)

Satisfiable
A proposition is satisfiable it is true for at least one interpretation G.
Example: p is satisfiable since p is true for G(p)=1

Unsatisfiable
A proposition is unsatisfiable if is false for all interpretations.
Example: p*!p is false for G(p)=0 and G(p)=1.

Literal
A propositional symbol or its negation. Expressed as L
Examples: p, !p

Clause
A disjunction of literals. Expressed as C
Example: p + !p + q, L1 + L2 + L3

Conjunctive Normal Form (CNF)
A conjunction of clauses. This is the basis of a rule set or knowledge base.
Example: (p+q+r)*(!p+q+r), C1*C2*C3

### Mathematical Notation

```    G:P => {T,F}
Interpretation G takes a set of propositions P and returns an element T or F.
G |= P
P is true for interpretation G.
'|=' is a single symbol known as a double turnstyle.
G != P
P is not true for interpretation G.
```

## Reasoning:

### Theorem:

p is valid iff !p is unsatisfiable.
If there exists no interpretation for which !p is true, the p must be true for all interpretations.

This theorem is the basis of reasoning in propositional logic.

### Rules of Inference:

A way to derived new propositions or simplify existing ones.

Modus Ponens

```	If p=>q is true and p is true, then q must be true.

p=>q		!p+q
p			 p
---			---
q			 q

If a drunk person swerves while driving and the person is drunk, then the car is swerving.
```
Modus Tolens
```	If p=>q is true and q is false, then p must be false.

p=>q		!p+q
!q			!q
---			---
!p			!p

If a drunk person swerves while driving and the car is not swerving, then the person is not drunk.
```
And-Elimination
```	If p*q is true, the p is true and q is true

p*q
---
p
```
Or-Introduction
```	If p is true, then p+q is true.

p
---
p+q
```
Double-Negation Elimination
```	The negative of a negative is a positive.

!!p
---
p
```
Resolution
```	Because b and !b cannot both be true, one of the other literals in
a disjunction must be true.

a+b * !b+c		!a=>b * b=>c
----------		-------------
a+c			     a=>c

Resolution is the most powerful of the rules of inference since it allows
us to create new clauses from what we know.
```

This is all we have to reason. Other forms are considered bad logic:

If p=>q is true and q is true, it does not necessarily mean that p is true.
((p=>q)*q) => p is not a Valid statement (although it is satisfiable)

If a drunk person swerves while driving and the car is swerving, then the person may or may not be drunk.

### More on Resolution

The process of deriving new valid clauses from a CNF is called resolution.

Any two clauses in a valid CNF with one set of complementing literals can be disjoined together to create a new clause.

Within the new clause duplicate literals can combined to simplify it.

Example: C1*C2 <==> T

```			C1: !a+b+c+d
C2: a+b+c+e
--------------------
C3: b+b+c+c+d+e (by resolution)
C3: b+c+d+e

Thus C1*C2*C3 <==> T
```
Note that resolving two clauses with more than one set of complementing literels is not useful.

Example: C1*C2 <==> T,

```			C1: a+b
C2: !a+!b
-------------------
C3: a+!a
C4: b+!b
```
Since (a+!a) is T regardless of the state of a, the CNF becomes C1*C2*T*T. Conjunction of T with a true statement does not add anything to the statement.

### Proving Propositions using Resolution:

Recall that if a statement is unsatisfiable, then its negation must be valid.

If the clauses in a CNF can be resolved to an empty set {}, then the CNF is unsatisfiable.

Example: K:C1*C2

```				C1: b
C2: !b
----------------
C3: {}
```

An empty set is implicitly defined as false. Any statement P, made up of the disjunctions p1+p2+...+pn, can also be represented as P+F. The disjunction of F does not change the truth of P. If we resolve P+F and !P+F, we get F. Conjuncting F with the original statement C1*C2*F, shows that the statement is always false. This means that the negation of that statement is always true.

If a clause (C) is conjoined with a valid CNF (K) and the resulting CNF (K*C) is unsatisfiable, then C must be unsatisfiable and thus its inverse (!C) must be valid.

Proof: Given that K*!C is unsatisfiable.

```				!(K*!C)		valid by definition
!K+!!C		by DeMorgan
!K+C		by double negation
K=>C		If K is true then C is true.
```

Given any rule base K, and a negated conclusion !C we can prove that K implies C if and only if K and !C implies an empty statement {}. R=>C iff R*!C=>{}

Example: K:C1*C2*C3 C:r

```				C1: p
C2: p=>q
C3: q=>r
C4: !r
----------------
C5: !p+q    (C2)
C6: !q+r    (C3)
C7: !p+r    (C5,C6)
C8: r       (C1,C7)
C9: F,{}    (C4,C8)
```
Since !C results in a contradiction, C must always be true.
Back