/

(p ’ q) & (q ∨ r) p∨r q∨s

\ /\ /\

/

p’q q∨r p r q s

/\ /\

p qq r

or, in an abbreviated style,

’

’ ¬

/\ |

∨ ∨

&

/\ /\ /\

’ ∨pr qs

/\ /\

pqqr

4

Remark 1.1.13. Note that, if we identify formulas with formation trees in the

abbreviated style, then there is no need for parentheses.

Remark 1.1.14. Another way to avoid parentheses is to use Polish notation.

In this case the set of L-formulas is generated as follows:

1. If p is an atomic L-formula, then p is an L-formula.

2. If A is an L-formula, then ¬ A is an L-formula.

3. If A and B are L-formulas and b is a binary connective, then bAB is an

L-formula.

For example, the formula of Example 1.1.4 in Polish notation becomes

’ ’ & ’ p q ∨ q r ∨ pr ¬ ∨ q s .

A formation sequence for this formula is

p, q, ’ pq, r, ∨ qr, & ’ pq ∨ qr, ∨ pr, ’ & ’ pq ∨ qr ∨ pr,

s, ∨ qs, ¬ ∨ qs, ’ ’ & ’ pq ∨ qr ∨ pr¬ ∨ qs .

Obviously Polish notation is di¬cult to read, but it has the advantages of being

linear and of not using parentheses.

Remark 1.1.15. In our study of formulas, we shall be indi¬erent to the ques-

tion of which system of notation is actually used. The only point of interest for

us is that each non-atomic formula is uniquely of the form ¬ A or AbB, where

A and B are formulas and b is a binary connective.

1.2 Assignments and Satis¬ability

De¬nition 1.2.1. There are two truth values, T and F, denoting truth and

falsity.

De¬nition 1.2.2. Let L be a propositional language. An L-assignment is a

mapping

M : {p : p is an atomic L-formula} ’ {T, F} .

Note that if L has exactly n atoms then there are exactly 2n di¬erent L-

assignments.

Lemma 1.2.3. Given an L-assignment M , there is a unique L-valuation

vM : {A : A is an L-formula} ’ {T, F}

given by the following clauses:

T if vM (A) = F ,

1. vM (¬ A) =

F if vM (A) = T .

5

T if vM (A) = vM (B) = T ,

2. vM (A & B) =

F if at least one of vM (A), vM (B) = F .

T if at least one of vM (A), vM (B) = T ,

3. vM (A ∨ B) =

F if vM (A) = vM (B) = F .

4. vM (A ’ B) = vM (¬ (A & ¬ B)) .

T if vM (A) = vM (B) ,

5. vM (A ” B) =

F if vM (A) = vM (B) .

Proof. The truth value vM (A) is de¬ned by recursion on L-formulas, i.e., by

induction on the degree of A where A is an arbitrary L-formula.

Remark 1.2.4. The above lemma implies that there is an obvious one-to-one

correspondence between L-assignments and L-valuations. If the language L is

understood from context, we may speak simply of assignments and valuations.

Remark 1.2.5. Lemma 1.2.3 may be visualized in terms of formation trees.

To de¬ne vM (A) for a formula A, one begins with an assignment of truth values

to the atoms, i.e., the end nodes of the formation tree for A, and then proceeds

upward to the root, assigning truth values to the nodes, each step being given

by the appropriate clause.

Example 1.2.6. Consider the formula (p ’ q) ’ (q ’ r) under an assignment

M with M (p) = T, M (q) = F, M (r) = T. In terms of the formation tree, this

looks like

(p ’ q) ’ (q ’ r)

\

/

p’q q’r

/\ /\

pq qr

TF FT

and by applying clause 4 three times we get

(p ’ q) ’ (q ’ r)

T

p’q q’r

F T

/\ /\

pq qr

TF FT

and from this we see that vM ((p ’ q) ’ (q ’ r)) = T.

6

Remark 1.2.7. The above formation tree with truth values can be compressed

and written linearly as

(p ’ q) ’ (q ’ r)

TFF T FTT.

Remark 1.2.8. Note that each clause of Lemma 1.2.3 corresponds to the fa-

miliar truth table for the corresponding propositional connective. Thus clause

3 corresponds to the truth table

A∨B

A B

T T T

T F T

F T T

F F F

for ∨ , and clause 4 corresponds to the truth table

A’B

A B

T T T

T F F

F T T

F F T

for ’ .

Fix a propositional language L.

De¬nition 1.2.9. Let M be an assignment. A formula A is said to be true

under M if vM (A) = T, and false under M if vM (A) = F.

De¬nition 1.2.10. A set of formulas S is said to be satis¬able if there exists

an assignment M which satis¬es S, i.e., vM (A) = T for all A ∈ S.

De¬nition 1.2.11. Let S be a set of formulas. A formula B is said to be a

logical consequence of S if it is true under all assignments which satisfy S.

De¬nition 1.2.12. A formula B is said to be logically valid (or a tautology) if

B is true under all assignments. Equivalently, B is a logical consequence of the

empty set.