Computers and phones

"I have always wished that my computer would be as easy to use as my telephone.
My wish has come true.
I no longer know how to use my telephone."
Bjarne Stroustrup (C++ creator)

'Compatible' change

"Every change is an incompatible change. A risk/benefit analysis is always required."
Martin Buchholz (veteran JDK engineer)

Tree (graph theory)

http://en.wikipedia.org/wiki/Tree_(graph_theory)

Ranked, unranked, and labelled trees

Until recently, most logical formalisms for trees dealt with ranked trees. In such trees, all nodes have the same fixed number of children (or, a bit more generally, the number of children of a node is determined by the label of that node). Over the past several years, however, the focus has shifted towards unranked trees, in which there are no restrictions on the number of children a node can have.

XML data is typically modelled as labelled unranked trees.

First-order Logic

There are two key parts of first order logic: the syntax (determines which collections of symbols are legal expressions) and the semantics (determines the meanings behind these expressions).

[edit]Alphabet

There are two key types of legal expressions:

• terms, which intuitively represent objects, and 
• formulas, which intuitively express predicates that can be true or false. 

The terms and formulas of first-order logic are strings of symbols which together form the alphabet of the language. As with all formal languages, the nature of the symbols themselves is outside the scope of formal logic; they are often regarded simply as letters and punctuation symbols.

It is common to divide the symbols of the alphabet into:

• logical symbols, which always have the same meaning, and 
• non-logical symbols, whose meaning varies by interpretation. 

For example, the logical symbol  always represents "and"; it is never interpreted as "or". On the other hand, a non-logical predicate symbol such as Phil(x) could be interpreted to mean "x is a philosopher", "x is a cat", or any other unary predicate, depending on the interpretation at hand.

[edit]Logical symbols

There are several logical symbols in the alphabet, which vary by author but usually include:

• The quantifier symbols  and 
• The logical connectives:  for conjunction,  for disjunction,  for implication,  for biconditional,  for negation. Occasionally other logical connective symbols are included. Some authors use  and  instead of  and , especially in contexts where  is used for other purposes. Moreover, , tilde (~) and & may replace ,  and , especially if these symbols are not available for technical reasons.
• Parentheses, brackets, and other punctuation symbols. The choice of such symbols varies depending on context.
• An infinite set of variables, often denoted by lowercase letters at the end of the alphabet x, y, z, … . Subscripts are often used to distinguish variables: x₀, x₁, x₂, … .
• An equality symbol (sometimes, identity symbol) =; see the section on equality below.

It should be noted that not all of these symbols are required - only one of the quantifiers, negation and conjunction, variables, brackets and equality suffice. There are numerous minor variations that may define additional logical symbols:

• Sometimes the truth constants T or  for "true" and F or  for "false" are included. Without any such logical operators of valence 0, these two constants can only be expressed using quantifiers.
• Sometimes additional logical connectives, such as the Sheffer stroke (NAND) and exclusive or operators are included.

[edit]Non-logical symbols

The non-logical symbols represent predicates (relations), functions and constants on the domain of discourse. It used to be standard practice to use a fixed, infinite set of non-logical symbols for all purposes. A more recent practice is to use different non-logical symbols according to the application one has in mind. Therefore it has become necessary to name the set of all non-logical symbols used in a particular application. This choice is made via a signature.

The traditional approach is to have only one, infinite, set of non-logical symbols (one signature) for all applications. Consequently, under the traditional approach there is only one language of first-order logic. This approach is still common, especially in philosophically oriented books.

1. For every integer n ≥ 0 there is a collection of n-ary, or n-place, predicate symbols. Because they represent relations between n elements, they are also called relation symbols. For each arity n we have an infinite supply of them:
   

   Pⁿ₀, Pⁿ₁, Pⁿ₂, Pⁿ₃, …



2. For every integer n ≥ 0 there are infinitely many n-ary function symbols:
   

   f ⁿ₀, f ⁿ₁, f ⁿ₂, f ⁿ₃, …

In contemporary mathematical logic, the signature varies by application. Typical signatures in mathematics are {1, ×} or just {×} for groups, or {0, 1, +, ×, <} for ordered fields. There are no restrictions on the number of non-logical symbols. The signature can be empty, finite, or infinite, even uncountable. Uncountable signatures occur for example in modern proofs of the Löwenheim-Skolem theorem.

In this approach, every non-logical symbol is of one of the following types.

1. A predicate symbol (or relation symbol) with some valence (or arity, number of arguments) greater than or equal to 0. These which are often denoted by uppercase letters P, Q, R,... .
   • Relations of valence 0 can be identified with propositional variables. For example, P, which can stand for any statement.
   • For example, P(x) is a predicate variable of valence 1. One possible interpretation is "x is a man".
   • Q(x,y) is a predicate variable of valence 2. Possible interpretations include "x is greater than y" and "x is the father of y".
2. A function symbol, with some valence greater than or equal to 0. These are often denoted by lowercase letters f, g, h,... .
   • Examples: f(x) may be interpreted as for "the father of x". In arithmetic, it may stand for "-x". In set theory, it may stand for "the power set of x". In arithmetic, g(x,y) may stand for "x+y". In set theory, it may stand for "the union of x and y".
   • Function symbols of valence 0 are called constant symbols, and are often denoted by lowercase letters at the beginning of the alphabet a, b, c,... . The symbol a may stand for Socrates. In arithmetic, it may stand for 0. In set theory, such a constant may stand for the empty set.

The traditional approach can be recovered in the modern approach by simply specifying the "custom" signature to consist of the traditional sequences of non-logical symbols.

NP (complexity) and NP-complete

NP refers to "non-deterministic polynomial time".

NP is the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs of the fact that the answer is indeed "yes."
More precisely, these proofs have to be verifiable in polynomial time by a deterministic Turing machine.

Many natural computer science problems are covered by the class NP. In particular, the decision versions of many interesting search problems and optimization problems are contained in NP.

NP contains many important problems, the hardest of which are called NP-complete problems, for which no polynomial-time algorithms are known. Once a problem has been proven to be NP-complete this is widely regarded as a sign that a polynomial algorithm for this problem is unlikely to exist.

Polynomial Time

An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., T(n) = O(n^k) for some constant k.

Problems for which a polynomial time algorithm exists belong to the complexity class P, which is central in the field of computational complexity theory.

Cobham's thesis states that polynomial time is a synonym for "tractable", "feasible", "efficient", or "fast".

Examples:
- The quicksort sorting algorithm on n integers performs at most An^2 operations for some constant A. Thus it runs in time O(n^2) and is a polynomial time algorithm.
- All the basic arithmetic operations (addition, subtraction, multiplication, division, and comparison) can be done in polynomial time.
- Maximum matchings in graphs can be found in polynomial time.