Propositional Logic

Question 1

For propositional logic, define the set of well formed formulas.

Answer 1

Let X be the set of WFF. Then X has several properties.

1) It is minimal.
2) All atomic propositions are in X.
3) If a formula P is in X, then its negation (~P) is in X.
4) If two formulas P, Q are in X, then their combination using any of the connectives is also in X.

Question 2

What is the conventional priority given to the connectives in propositional logic?

Answer 2

In descending order of priority, negation, and, or, and then implication

Question 3

What are semantics?

Answer 3

Semantics deals not with the syntax of formulae, which is entirely part of the definition of WFF, but with the the so-called truth values of the formulae, which are found via a so-called interpretation function.

Question 4

What is an interpretation in propositional logic?

Answer 4

An interpretation is a function from the set of WFF to {0,1}. It must satisfy certain intuitive properties.

Question 5

What are five intuitive properties of an interpretation in propositional logic?

Answer 5

(1) The interpretation function maps falsum to zero.
(2) If an interpretation function maps the negation of a WFF to 1 iff it maps the WFF to 0.
(3) The interpretation function maps P and Q to min of the interpretation function of P, Q individually.
(4) The interpretation function maps P or Q to the max of the interpretation of the individual composing formulae.
(5) The interpretation of an implication is mapped to 0 if and only if the antecedent maps to 1 and the consequent maps to 0.

Question 6

There are two terms we use to indicate when an interpretation maps a formula P to one. What are these terms? How do we phrase it?

Answer 6

(1) We say that the interpretation satisfies the formula P.
(2) We also say that the interpretation is a model of the formula P.

We also use the semantic consequence operator to indicate this situation. v |= P. where v is an interpretation and P is a formula.

Question 7

In terms of models, what does it mean that a WFF, P, is satisfiable?

Answer 7

It means that there exists at least one model such that P is satisfied.

Question 8

What does tautology mean for a WFF, P?

Answer 8

It means that every interpretation satisfies P.

Question 9

What is a synonym for tautology?

Answer 9

Valid is synonymous with tautology.

Question 10

How can we mathematically denote a tautology?

Answer 10

We use the semantic consequence operator |= P if P is a tautology.

Question 11

If gamma is a set of WFF and Q is a WFF. What does it mean to say that Q is a semantic consequence of gamma? gamma |= Q.

Answer 11

This means that there does not exist an interpretation which makes every formula of gamma true and Q false. In other words, for every interpretation v, such that all formulas in gamma are true, then is follows necessarily that Q is true. This is what it means for a formula to be a semantic consequence of another.

Question 12

What does it mean for two formulae P and Q to be equivalent?

Answer 12

This means that for any interpretation, under the interpretation, the value of P and the value of Q (in propositional logic, the truth values are {0,1}), are the same.

Question 13

How can we relate a tautology P to its satisfiability or lack thereof?

Answer 13

A formula P is a tautology (or valid) if and only if the negation of P is unsatisfiable.

Question 14

If Q is a semantic consequence of gamma, what can you say about the satisfiability of gamma union not Q?

Answer 14

These statements are equivalent. In fact, if Q is a semantic consequence of gamma, then it is not possible to satisfy gamma union not Q. Because there does not exist an interpretation that makes all the formula of gamma true and Q false. And by definition this means semantic consequence.

Question 15

In propositional logic, what is idempotency?

Answer 15

This means that ORing or ANDing a WFF results simply in the WFF. This is in contrast to linear logic where you can have so-called tokens.

P V P = P and P ^ P = P.

Question 16

In propositional logic, what is commutativity?

Answer 16

The order of the propositions in an AND or OR statement is irrelevant.

Question 17

In propositional logic, what is associativity?

Answer 17

In a big conjunct or disjunct, then the priority in which one considers some pair of conjuncts or disjuncts does not matter.

Question 18

In propositional logic, what is absorbtion?

Answer 18

This is essentially a simplification formula. If P V (P ^ Q) == P. Since in any case satisfying this OR results in in a truth table equivalent to P.

Similarly, P ^ (P V Q) == P. In either case, P’s truth value is equivalent to this.

Question 19

In propositional logic, what is distributivity?

Answer 19

This means that if we have a WFF ANDed or ORed to a conjunct or disjunct, we may duplicate this formula appropriately into the conjunct or disjunct.

P V (Q ^ R) == (PVQ)^(PVR)
P ^ (Q V R) == (P^Q)V(P^R)

Question 20

What are DeMorgan’s Laws?

Answer 20

~(P^Q) = ~P v ~Q

~(PVQ)=~P ^ ~Q

Question 21

What is a literal?

Answer 21

It is an atomic formula or its negation.

Question 22

What is CNF?

Answer 22

This is conjunction normal form. This is when you have a series of WFF, Pi and P1 ^ P2 ^ P3 … Pn such that each Pi is composed of a disjunction of literals.

Question 23

What is DNF?

Answer 23

This is disjunctive normal form. This is when you have a set of WFF, Pi, and P1 V P2 V… V Pn, and each of the Pi are a conjunction of literals.

Question 24

Is it true that any WFF P may be expressed by an equivalent WFF in CNF and DNF?

Answer 24

Yes, it is true.

Question 25

What are two methods to compute the CNF or DNF or a WFF P?

Answer 25

One can use either equivalences or truth tables.

Question 26

Explain how to use truth tables to find the CNF of a WFF P.

Answer 26

To construct the CNF, take all the rows in the truth table for which the WFF P is false. Take the positive or negative literal in correspondence to its truth value in the truth table. Combine them in a conjunct. Then take a big disjunct of all these conjuncts. Then take the negative of this expression. Via DeMorgan’s Laws and the negation laws, one will now have a CNF.

Question 27

Explain how to use truth tables to find the DNF of a WFF P.

Answer 27

Take the WFF P and write down its truth table from all its atomic subformulae. Select all the rows for which the WFF P is true. Take the positive or negative literal of the atom if its truth value is 1 or 0, respectively, do this for each atom and form them into a big disjunct, then conjunct this for all the rows where WFF P is true. Then you have found a CNF.

Question 28

Are connectives equivalent to functions?

Answer 28

Yes, in fact a n-ary connection corresponds to a function that maps f: {0,1}^n -> {0,1}.

Question 29

What does it mean to be functionally complete?

Answer 29

A set of connectives is said to be functionally complete if every possible connective can be derived from it.

Question 30

What does it mean for a connective to be derivable?

Answer 30

A new connective c is derivable from big C a set of connectives. If there exists a WFF P with only connectives from C, such that its corresponding function Fp equals the function of the new connective c, Fc.

Question 31

What does the compactness theorem in propositional logic state?

Answer 31

Let gamma be an infinite set of WFF in propositional logic. Then gamma is satisfiable if and only if every finite subset of gamma is satisfiable.

Question 32

What is an atom?

Answer 32

An atom is a formula with no deeper propositional structure. It contains no logical connectives, not even negation!