Formula Trees and Propositional Logic

Question 1

Definition: A language L of propositional (or sentential) logic consists of …

Answer 1

1. a set PVar(L) of propositional variables: P0, P1, P2, …
2. a set of Conn1(L) of unary (one) logical connectives, containing ¬ (negation)
3. a set Conn2(L) of binary logical connectives, containing: ∧ (conjunction), ∨ (disjuction), ⊃ (implication)

L is the meta-variable for a formal language

Not need to distinguish between arity of connectives, speak of set Conn(L) of logical connectives, such that Conn(L) = Conn1(L) ⋃ Conn2(L)

Question 2

Recursive definition of a formula tree:

Answer 2

1. Base clause: Any propositional variable Pi is a formula tree (atomic trees)
2. Inductive Clauses: If A and B are formula trees: …
3. Final Clause: Only trees that are obtained from the above rules are formula trees

Question 3

What are the different definition for the parts of a formula tree?

Answer 3

#1: Formula tree not a single propositional variable, then the top connective of the formula tree is called the main connective (also: root or top node)

#2: If the main connective is unary we say that the tree is unary; if the main connective of the formula is binary, then the tree is binary

#3: For the unary tree in the above inductive clases, subtree. For the binary trees in the above inductive clauses, A is the left subtree and B is the right subtree

Question 4

Define interpretation:

Answer 4

mapping from the alphabet to the formula tree

Question 5

Define truth value assignment:

Answer 5

Mapping f: PVar(L) → {T, F}

(f maps each propositional variable Pi to one of the truth values T or F)

Mapping: relation between two sets

Question 6

Definition of a truth value of a formula tree:

State the cases

A would be considered a meta-variable

Answer 6

i. Case 1 (Atomic Formula Tree):
If A is a propositional variable, then the truth value of A if f(A)

ii. Case 2 (Unary Formula Tree):
If A is of the form …, then the trueth value of A is determined by the truth table, contingent on the value of B

*iii. Case 3 (Binary Formula Tree): *
If A is in the form …, then the truth valye of A is determined depending on the truth values of B and C by the respective truth tables.

Question 7

Exercise 01:

If the truth value assignments of f maps P1 to T, P2 to F, and P3 to T, then what are the truth values of the following three formula trees?

Answer 7

a) T
b) T
c) T

Question 8

Translating formula trees into other notation:

Prefix/ Preorder/ Polish Method:

Answer 8

1. Visit the root
2. Traverse the left subtree
3. Traverse the right subtree

Start from top

More economical - no parentheses are necessary

Question 9

Translating formula trees into other notation:

Infix/ Inorder/ Algebraic Method:

Answer 9

1. Traverse the left subtree
2. Visit the root
3. Traverse the right subtree

Easier to read

Question 10

Translating formula trees into other notation:

Postfix/ Postorder/ Endorder Method:

Answer 10

1. Traverse the left subtree
2. Traverse the right subtree
3. Visit the root

Question 11

Translating formula trees into other notation:

Frege’s Begriffsschrift notation:

Answer 11

Variant of the prefix representation is Frege’s two-dimentional notation

Isomorphic relationship with the formula trees from exercise 01

Question 12

Translating formula trees into other notation:

Dot notation by Peano/Whitehead and Russell:

Answer 12

Isomorphic to exercise 1

Question 13

What is propositional logic?

Answer 13

A formal language to express logical relations between propositions or statements. Can be true or false

Question 14

Alphabet of propositional logic:

Answer 14

1. Propositional Variables: P0, P1, P2, …
2. Logical Connectives: ∧ (conjunction), ∨ (disjuction), ⊃ (implication), and ~ (negation)
3. Parenthesis: (, ).

Since we do not want to consider all possible combinations of these symbols, we restrict ourselves to well-formed formulas (wff) are defined by the following recursive definition:
1. Base Clause: P1 is a wff for i E ℕ. These wffs are also called atomics wffs
2. Inductive clauses: IF A and B are wffs thhen so are the logic connectives between them
3. Final Clause: Only strings of symbols that are obtained by the above two rules are wffs.

Note: ‘A’ and ‘B’ are not wffs themselves, but only metalogical variables that stand for wffs

Question 15

How does parenthesis relate to formulas

Answer 15

Clutter
To avoid clutter, leave out parentheses when its clear how the formulas are intended to be read.

Question 16

Bivalence and propositional logic:

Answer 16

Only consider two truth values, true and false (T and F)
In classical logic every proposition is either true or false (principle of bivalence)

Question 17

How are connectives in classical logic truth-functional?

Answer 17

Given a interpretation of the components of wff into the set of truth values (truth assignment), we can determine the truth value of a more complicated wff:

Question 18

Truth value assignment of the connective “conjunction”

Answer 18

Question 19

Truth value assignment of the connective “disjunction”

Answer 19

Question 20

Truth value assignment of the connective “implication”

Answer 20

A implies B: not have a causational relationshp

Question 21

Define tautologies:

Answer 21

If a wff is always true

Question 22

What are logically equivalent formulas?

Answer 22

Conjuctions and disjuctions are be given explicit meanings in terms or implication and negation:

Question 23

What are the minimum set of connectives?

Answer 23

{~, ⊃}, {~, ∧}, and {~, ∨}

Any of these pairs is sufficient to define the other connectives