Propositional Logic

Propositions
In general a proposition intends to express a statement of fact about our objects of study. In logic each proposition being considered is given a symbol, and the structure of the resulting symbolic representations itself is the object of study.

Thus we can treat a proposition as a formal symbol. It is customary to use p, q, r, or p_i, where i can be selected from any collection of symbols i. This is the origin of the expression “minding our p’s and q’s.”

Our interpretation of what truth means does not come into play until we introduce the concept of negation. Propositional logic without negation is known as positive propositional logic, or minimal logic.

Connectives
Given two or more propositions it is possible to form a new proposition expressing various relations between them.

Implication
The most basic logical operation requires us to conclude q from p. This is called implication, and can be phrased as p implies q. p→q

A symbol alone does not define what we mean by implication. If we know that p is true, then that knowledge is independent of the truth of q. Implication is transitive, in that if p implies q, and q implies r, then p implies r. These can be expressed using implication alone.

  • IMP-1: p→(q→p)
  • IMP-2: (p→(q→r))→((p→q)→(p→r))

IMP-2 will be revisited later, where it will be shown to be equivalent to simpler expressions using more intuitive representations of the statement if p implies q, and q implies r, then p implies r.

Conjunction
It is often useful to express the idea that both of the given propositions must hold at the same time. This is accomplished by the logical conjunction, p∧q, often read p and q.

A conjunction implies either of its base propositions. Conjunction is reflexive, p∧q is the same as q∧p. Finally, if we know p, then knowing q implies p∧q.

  • AND-1a: (p∧q)→p
  • AND-1b: (p∧q)→q
  • AND-2: (p∧q)→(q∧p)
  • AND-3: p→(q→(p∧q))

Disjunction
Likewise, one might need to express the idea that at least one of the given propositions is valid. This is accomplished by the logical disjunction, p∨q, often read p or q.

Either proposition implies a disjunction between them. Disjunction is also reflexive.

  • OR-1a: p→(p∨q)
  • OR-1b: q→(p∨q)
  • OR-2: (p∨q)→(q∨p)
  • OR-3: (p→r)→((q→r)→((p∨q)→r))

Like IMP-2, OR-3 will be revisited later, and shown to be equivalent to p implies r, and q implies r, then p or q implies r.

Biconditional
It is very useful to express that two statements are equivalent. This is accomplished by the biconditional, p↔q, often read “p if and only if q”, or informally “p ifphf q.”

The biconditional implies that p implies q. It is reflexive.

  • IFF-1a: (p↔q)→(p→q)
  • IFF-1b: (p↔q)→(q→p)
  • IFF-2: (p↔q)→(q↔p)
  • IFF-3: (p→q)→((q→p)→(p↔q))

IFF-3 should be added to the list of defining expressions to be revisited.

Universal substitution
The letters above were defined to represent a general predicate. The connections were defined to produce compound predicates from know predicates. This generates a recursive definition of compound predicates.

INDEX:

  • any representation of a specific member of some collection
  • any representation of a member of some collection in general

UNIT:

  • p
  • q
  • r
  • p_{INDEX}

PREDICATE:

  • UNIT
  • (PREDICATE→PREDICATE)
  • (PREDICATE∧PREDICATE)
  • (PREDICATE∨PREDICATE)
  • (PREDICATE↔PREDICATE)

In particular, p could have been p_1\rightarrow(p_2\wedge p_3). Thus case (p_1\rightarrow(p_2\wedge p_3)) could be used in place of p in any of the axioms above. The same goes for q and r. In fact, the same goes for all p_i in the new formulas. Thus these definitional axioms are often called axiom schemata.

Rule of inference
A rule of inference takes statements from a list of known propositions and generates a new statement that is then known. Often the required statements are given in a comma separated list, followed by the conclusion.

The most basic rule of inference is modus ponens.

  • MP: p, p→q ∴ q

Without this as an axiom one can generate an infinite regress argument against it.

This looks a lot like (p∧(p→q))→q. Indeed, I believe there is a platonic logic where this is the case. In classical logic, however, allowing statements about proofs to be treated as ordinary predicates can be used to create self referential predicates, which the liar’s paradox shows classical logic can not handle.

Further, in proof theory it is possible to show that a given axiom is independent of a collection of axioms. Thus the statement that given theorem can be proved by a collection of axioms invalidates the law of excluded middle. Thus our standard proof semantics do not fully embody classical logic.

In many logic systems most common rules of inference can be generated from this one. For example, disjunction addition can be derived as follows:

p, OR-1a ∴ p∨q

Since OR-1a is part of our definitions, it need not be listed. This then becomes:
p ∴ p∨q

In general,
(p→q) ∴ (p∴q)

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: