text:
Logic for Computer Science/Propositional Logic

Propositional Logic
Propositional logic is a good vehicle to introduce basic properties of logic. It does not provide means to determine the validity (truth or false) of atomic statements. Instead, it allows you to evaluate the validity of compound statements given the validity of its atomic components.

For example, consider the following:
 * I like Pat or I like Joe.
 * If I like Pat then I like Joe.
 * Do I like Joe?

Accept as facts the first two statements, noting that the use of "or" here is not exclusive and thus could really be thought of as saying "I like Pat, or I like Joe, or I like them both". Do these statements imply that "I like Joe" is true? Try to convince yourself that "I like Joe" is true, and consider another line of reasoning:
 * Pigs can fly or fish can sing.
 * If pigs can fly then fish can sing.
 * Can fish sing?

We can see that the answer is yes in both cases. The above two sets of statements can be both abstracted as follows:
 * $$\begin{align}&P\lor Q\\&P\to Q\\&Q\end{align}$$?

Here, we are concerned about the logical reasoning itself, and not the statements. Thus, instead of working with pigs or Pats, we simply write $$Q$$s or $$P$$s. We begin our study first with the syntax of propositional logic: that is, we describe the elements in our language of logic and how they are written. We then describe the semantics of these symbols: that is, what the symbols mean.

Syntax
The syntax of propositional logic is composed of propositional symbols, logical connectives, and parenthesis. Rules govern how these elements can be written together. First, we treat propositional symbols merely as a set of some symbols, for our purposes we'll use letters of the Roman and Greek alphabets, and refer to the set of all symbols as $$\text{Prop}$$:
 * Propositional symbols: A set $$\text{Prop}$$ of some symbols. For example $$p,q,r,\ldots$$

Second, we have the logical connectives:
 * Logical connectives: $$\land,\lor,\neg,\to$$

Note that these are not the minimal required set; they can be equivalently represented only using the single connective NOR (not-or) or NAND (not-and) as is used at the lowest level in computer hardware. Finally, we use parenthesis to denote expressions (later on we make parenthesis optional):
 * Parentheses: $$$$

An expression is a string of propositional symbols, parenthesis, and logical connectives.

The expressions we consider are called formulas. The set $$\textrm{Form}$$ of formulas is the smallest set of expressions such that:
 * 1) $$\text{Prop}\sube\text{Form}$$
 * 2) If $$\phi,\psi\in\text{Form}$$ then
 * 3) $$(\phi\land\psi)\in\text{Form}$$ ,
 * 4) $$(\phi\lor\psi)\in\text{Form}$$ ,
 * 5) $$(\phi\to\psi)\in\text{Form}$$, and
 * 6) $$(\neg\phi)\in\text{Form}$$.

Another way to define formulas is as the language defined by the following context-free grammar (with start symbol $$\text{Form}$$):
 * $$\text{Form}\Rarr\text{Prop}$$, where $$\text{Prop}$$ stands for any propositional symbol
 * $$\begin{align}\text{Form}\Rarr(\text{Form}\land\text{Form})\\\text{Form}\Rarr(\text{Form}\lor\text{Form})\\\text{Form}\Rarr(\text{Form}\to \text{Form})\\\text{Form}\Rarr(\neg\text{Form})\end{align}$$

Fact 1 (Unique Readability): The above context free grammar is unambiguous.

Semantics
The function of a formula is to create meanings of statements given meanings of atomic statements. The semantics of a formula $$\phi$$ with propositional symbols $$p_1,\ldots,p_n$$ is a mapping associating to each truth assignment $$V$$ to $$p_1,\ldots,p_n$$ a truth value (0 or 1) for $$\phi$$. (The truth values true and false can be used instead of 1 or 0, respectively, as well as the abbreviations T and F.)

The semantics are well defined due to Fact 1 (seen just above).

One way to specify semantics of a logical connective is via a truth table:
 * {| border=1 style=text-align:center

! $$p$$ !! $$q$$ !! $$p\land q$$ (p and q)
 * 0 || 0 || 0
 * 0 || 1 || 0
 * 1 || 0 || 0
 * 1 || 1 || 1
 * }
 * 1 || 0 || 0
 * 1 || 1 || 1
 * }
 * }

Can one always find a formula that implements any given semantics? Yes, any truth table is realized by a formula. The formula can be found as follows. "Represent" the rows where $$\phi=1$$ with conjunctions of the true proposition symbols and negations of the false ones. Finally write the disjunction of the results.

For example,
 * {| border=1 style=text-align:center

! $$p$$ !! $$q$$ !! $$\phi$$ !! Conjunctions (true values only)
 * 0 || 0 || 1 || $$\neg p\land\neg q$$
 * 0 || 1 || 0 ||
 * 1 || 0 || 1 || $$p\land\neg q$$
 * 1 || 1 || 0 ||
 * }
 * 1 || 0 || 1 || $$p\land\neg q$$
 * 1 || 1 || 0 ||
 * }
 * }

$$\phi:(p\land\neg q)\lor(\neg p\land\neg q)$$

Corollary: Every formula is equivalent to a disjunction of conjunctions of propositional symbols or negation of propositional symbols (DNF).

Dual of DNF is CNF.

To get $$\phi$$ in CNF:
 * 1) Describe cases when $$\phi$$ is false.
 * 2) Note that $$\phi$$ is true when $$\neg \psi$$ is false. Hence, negate $$\psi$$ using DeMorgan's laws.

There are cases when DNF (resp. CNF) is exponentially larger than the original formula. For example, for $$(x_1\lor y_1)\land\cdots\land(x_n\lor y_n)$$ the equivalent DNF is exponential in size.

Does each truth table have a polynomial size formula implementing it? More precisely, does there exist $$k$$ such that every truth table with $$n$$ propositional symbols has a form $$\phi$$ of size $$\le n^k$$ ? Answer: no.

Proof: Assume there exists such $$k$$. The number of truth tables for $$n$$ propositional symbols is $$2^{2^n}$$. The number of formulas of size $$\le n^k$$ is $$(n+6)^{n^k}$$ ($$n$$ propositional symbols, 4 connectives and parentheses.) Clearly, $$(n+6)^{n^k}<2^{2^n}$$, for sufficiently large $$n$$.

[TODO: exposition to explain what these definitions are and provide their context]

 * Satisfaction: Satisfaction of a formula $$\phi$$ by a truth assignment $$\tau$$ . Notation: $$\tau\models\phi$$ ($$\phi$$ is true for $$\tau$$).
 * Implication: A set of formulas $$\Sigma$$ implies $$\phi$$ . Notation: $$\Sigma\models\phi$$ . $$\Sigma$$ implies $$\phi$$ if and only if every truth assignment that satisfies $$\Sigma$$ also satisfies $$\phi$$.

Formula Classes of Special Interest

 * $$\text{VALID}$$ – the set of formulas that are always true (also known as tautologies). For example, $$(p\lor\neg p),(p\to p),([(p\lor q)\land(p\to q)]\to q)$$ are valid formulas.
 * $$\text{UNSAT}$$ – the set of formulas that are never true (unsatisfiable).
 * In between: $$\text{SAT}$$ - the set of formulas for which there exists a satisfying assignment (not unsatisfiable).

Note. $$\phi\in\text{VALID}\iff\neg\phi\in\text{UNSAT}$$.

Claim: $$\Sigma\models\phi\iff(\Sigma\cup\{\neg\phi\})\in\text{UNSAT}$$

Claim: $$\text{SAT}$$ is NP-complete.

Proof:
 * $$\text{SAT}\in\text{NP}$$ : guess a satisfying assignment, then verify that the formula is true (a satisfying assignment is a certificate).
 * Hardness. graph 3-coloring $$\in\text{NP}$$ (there also exists a direct proof). We reduce 3-coloring to $$\text{SAT}$$. Let $$G=(V,E)$$ be a graph with $$n$$ nodes $$\{1,\ldots,n\}$$ . We use propositional variables $$p_{i,g},p_{i,r},p_{i,b}$$ to indicate that vertex $$i$$ is colored with green, red, or blue. Construct $$\phi$$ as follows:
 * $$\begin{align}\phi=&\bigwedge_{i=1}^n\bigl((p_{i,g}\land\neg p_{i,r}\land\neg p_{i,b})\lor(p_{i,r}\land\neg p_{i,g}\land\neg p_{i,b})\lor(p_{i,b}\land\neg p_{i,r}\land\neg p_{i,g})\bigr)\\&\wedge\bigwedge_{(i,j\in E)}\neg(p_{i,g}\land p_{j,g})\land\neg (p_{i,r}\land p_{j,r})\land\neg(p_{i,b}\land p_{j,b})\end{align}$$

Claim: $$G\in\text{3-Coloring}\iff\phi\in\text{SAT}$$.

It is also possible to prove that $$\textrm{SAT}\in\text{NP}$$ directly

Claim: $$\text{VALID}\in\text{coNP}$$.

Horn Clauses
Special case for which SAT is in polynomial time. Example:
 * $$(p\lor\neg q\lor r)\land(\neg p\lor q\lor\neg r)$$

A Horn clause is a disjunction of literals of which at most one is positive. There are two kinds of possible Horn clauses:
 * 1) clause has 1 positive literal
 * 2) $$p$$, or
 * 3) $$p\lor\neg x_1\lor\cdots\lor\neg x_k:x_1\land\cdots\land x_k\to p$$
 * 4) no positive literal
 * 5) $$\neg x_1\lor\cdots\lor\neg x_k:\neg(x_1\land\cdots\land x_k)$$
 * 6) $$x_1\land\cdots\land x_k\to\text{false}$$

Claim: For every set $$\Sigma$$ of Horn formulas, checking whether $$\Sigma$$ is satisfiable is in $$\text{P}$$.

Proof Idea: Let $$\Sigma_1$$ be the subset of $$\Sigma$$ containing only clauses of type 1, and $$\Sigma_2$$ the subset of $$\Sigma$$ containing clauses of type 2. Note first that $$\Sigma_1$$ is satisfiable. To obtain a minimum satisfying assignment $$\sigma$$, start with literals from single-literal clauses and crank the rules. It now remains to check consistency of $$\sigma$$ with the clauses in $$\Sigma_2$$. To do this, it is enough to check that for each clause $$x_1\land\cdots\land x_k\to\text{false}$$ in $$\Sigma_2$$, $$\sigma$$ is not true for all of $$x_1,\ldots,x_k$$.

Example: Consider the set $$\Sigma$$ of Horn clauses:
 * $$\begin{align}&p\\&q\\&r\\&\neg p\lor\neg q\lor s\\&\neg s\lor\neg r\lor t\\&\neg t\end{align}$$

The set $$\Sigma_1$$ of clauses of type 1 consists of the first 5 clauses, and $$\Sigma_2$$ consists of the last clause. Note that $$\Sigma_1$$ can also be written as:
 * $$\begin{align}&p\\&q\\&r\\&p\land q\to s\\&s\land r\to t\end{align}$$

The minimum satisfying assignment for $$\Sigma_1$$ is obtained as follows: Thus, the minimum satisfying assignment makes $$\{p,q,r,s,t\}$$ true. This contradicts $$\Sigma_2$$, which states that $$t$$ must be false. Thus, $$\Sigma$$ is not satisfiable.
 * 1) start with $$\{p,q,r\}$$
 * 2) use the first implication to infer $$s$$
 * 3) use the second implication to infer $$t$$

Deductive Systems
A deductive system is a mechanism for proving new statements from given statements.

Let $$\Sigma$$ be a set of known valid statements (propositional formulas). In a deductive system, there are two components: inference rules and proofs.

 * Inference rules
 * An inference rule indicates that if certain set of statements (formulas) $$\varphi_1,\ldots,\varphi_k$$ is true, then a given statement $$\varphi$$ must be true. An inference rule $$H$$ is denoted as $$H:\frac{\varphi_1,\ldots,\varphi_k}{\varphi}$$.
 * Example (modus ponens): $$\frac{p,p\to q}{q}$$

A proof of $$\varphi$$ from $$\Sigma$$ is sequence of formulas $$\varphi_1,\ldots,\varphi_n$$ such that $$\varphi_n=\varphi$$ and for all $$i\le n$$
 * Proofs
 * Each formula $$\varphi_i\in\Sigma$$, or
 * There are a subset of formulas $$\varphi_{i_1},\ldots,\varphi_{i_k}:i_1,\ldots,i_k<i$$, such that $$\frac{\varphi_{i_1},\ldots,\varphi_{i_k}}{\varphi_i}$$ is an inference rule.

If $$\varphi$$ has a proof from $$\Sigma$$ using inference rule $$H$$ we write $$\Sigma\vdash_H\varphi$$.

Properties:
 * Soundness: If $$\Sigma\vdash_H\varphi$$ then $$\Sigma\models\varphi$$ (i.e., all provable sentences are true). This property is fundamental for the correctness of the deductive system.
 * Completeness: If $$\Sigma\models\varphi$$ then $$\Sigma\vdash_H\varphi$$ (i.e., all true sentences are provable). This is a desirable property in deductive systems.

Natural Deduction
Natural deduction is a collection of inference rules. Let $$\perp$$ denote contradiction, falsity. The following are the inference rules of natural deduction:
 * 1) $$\left\{\frac{\varphi,\psi}{\varphi\land\psi}\right.$$
 * 2) $$\left\{\frac{\varphi\land\psi}{\varphi}\right.$$
 * 3) $$\left\{\frac{\varphi\land\psi}{\psi}\right.$$
 * 4) $$\left\{\frac{\varphi,\varphi\to\psi}{\psi}\right.$$
 * 5) $$\left\{\frac{\varphi,\neg\varphi}{\perp}\right.$$
 * 6) $$\left\{\frac{\neg(\neg\varphi)}{\varphi}\right.$$
 * 7) $$\left\{\frac{\perp}{\varphi}\right.$$
 * 8) $$\left\{\frac{\varphi\to\psi,\psi\to\varphi}{\varphi\lrarr\psi}\right.$$
 * 9) $$\left\{\frac{\varphi\lrarr\psi}{\varphi\to\psi}\right.$$
 * 10) $$\left\{\frac{\varphi\lrarr\psi}{\psi\to\varphi}\right.$$
 * 11) $$\left\{\frac{\varphi}{\varphi\lor\psi}\right.$$
 * 12) $$\left\{\frac{\psi}{\varphi\lor\psi}\right.$$
 * 13) $$\begin{cases}\dfrac{\begin{matrix}\varphi\\\vdots\\\psi\end{matrix}}{\varphi\to\psi}\end{cases}$$
 * 14) $$\begin{cases}\dfrac{\begin{matrix}\varphi\\\vdots\\\perp\end{matrix}}{\neg\varphi}\end{cases}$$
 * 15) $$\begin{cases}\dfrac{\begin{matrix}\neg\varphi\\\vdots\\\perp\end{matrix}}{\varphi}\end{cases}$$
 * 16) $$\begin{cases}\dfrac{\begin{matrix}\varphi\lor\psi&\varphi&\psi\\&\vdots&\vdots\\&\rho&\rho\end{matrix}}{\rho}\end{cases}$$

Rule (13) allows us to prove valid statements of the form "If $$\varphi$$ then $$\psi$$" even if we don't know the truth value of the $$\varphi$$ statement (i.e., $$\varphi$$ is not in the set $$\Sigma$$ of known valid statements). Indeed, for this rule, we start assuming $$\varphi$$ is valid. If we can conclude $$\psi$$ is valid in a world where $$\Sigma\cup\varphi$$ are valid, then we conclude that the relation $$\varphi\to\psi$$ is true, and we "release" the assumption $$\varphi$$ is valid.

We now show how to apply the above inference rules.

Example: De Morgan's Law for negated or-expressions says:
 * $$\neg(\varphi\lor\psi)\lrarr(\neg\varphi\land\neg\psi)$$

Proof: By rule $$(8)$$ if we can prove $$\neg(\varphi\lor\psi)\to(\neg\varphi\land\neg\psi)$$ and $$(\neg\varphi\land\neg\psi)\to\neg(\varphi\lor\psi)$$ we can infer the desired result.

To prove the first direction, we use rule 13 and assume the hypothesis $$\neg (\varphi \vee \psi)$$. Then
 * $$\neg(\varphi\lor\psi)$$ (assumed)
 * $$\varphi$$ (assumed)
 * $$\varphi\lor\psi$$ (by rule 11)
 * $$\perp$$ (by rule 5)
 * $$\neg\varphi$$ (by rule 14)
 * $$\psi$$ (assumed)
 * $$\varphi\lor\psi$$ (by rule 11)
 * $$\perp$$ (by rule 5)
 * $$\neg\psi$$ (by rule 14)
 * $$\neg\varphi\land\neg\psi$$ (by rule 1)
 * $$\neg(\varphi\lor\psi)\to(\neg\varphi\land\neg\psi)$$ (by rule 13)

We now prove the second direction.
 * $$\neg\varphi\land\neg\psi$$ (assumed)
 * $$\neg\varphi$$ (by rule 2)
 * $$\neg\psi$$ (by rule 3)
 * $$\varphi\lor\psi$$ (assumed)
 * $$\varphi\psi$$ (assumed)
 * $$\perp\perp$$ (by rule 5)
 * $$\perp$$(by rule 16)
 * $$\neg(\varphi\lor\psi)$$ (by rule 14)
 * $$(\neg\varphi\land\neg\psi)\to\neg(\varphi\lor\psi)$$ (by rule 13)

Proof of Pierce's Law:
 * $$[(A\to B)\to A]\to A$$
 * $$(A\to B)\to A$$ (assumed) (1*)
 * $$\neg A$$ (assumed)
 * $$A$$ (assumed)
 * $$\perp$$ (by rule 5)
 * $$B$$ (by rule 7)
 * $$A\to B$$ (by rule 13)
 * $$A$$ (by assumption (1*) and rule 4)
 * $$\perp$$ (by rule 5)
 * $$A$$ (by rule 14)
 * $$[(A\to B)\to A]\to A$$ (by rule 13)

Fact 2: Natural deduction is sound.

To show that natural deduction is also complete we need to introduce propositional resolution.

Propositional Resolution
Resolution is another procedure for checking validity of statements. It involves clauses, formulas and a single resolution rule.

Some terminology:
 * Clause
 * A clause is a propositional formula composed by disjunction of literals. For example $$p\lor q\lor\neg r$$ . It is usually denoted as the set of literals, e.g. $$\{p,q,\neg r\}$$.
 * The empty clause, denoted as an open box "$$\Box$$", is the disjunction of no literals. It is always false.

 * Formula
 * A set of clauses, each of them satisfiable. For example, $$\bigl\{\{p,\neg q\},\{r\},\{\neg r, s\}\bigr\}$$ represents the CNF formula $$(p\lor\neg q)\land(r)\land(\neg r\lor s)$$.
 * The empty formula, denoted as $$\varnothing$$, is the set that contains no clauses. It is always true.

 * Resolution Rule
 * It is a rule that, given two clauses $$C$$ (containing some literal $$y$$) and $$C'$$ (containing some literal $$\neg y$$), allows to infer a new clause, called the resolvent of $$C$$ and $$C'$$ (with respect to $$y$$).

A proof system for resolution contains a single resolution rule, where the resolvent is defined as follows. Assume $$C$$ and $$C'$$ are clauses such that $$y\in C$$ and $$\neg y\in C'$$, then
 * $$\text{Res}_y(C,C')=(C-\{y\})\cup(C'-\{\neg y\})$$

The smallest set of clauses containing $$\varphi$$ and closed under resolution is denoted $$\text{Res}(\varphi)$$.

Example: If $$C=\{p,y\}$$ and $$C'=\{q,\neg y\}$$, then $$\text{Res}_y(C,C')=\{p,q\}$$.

It is possible to show that the resolution rule, as defined, computes a clause that can be inferred using natural deduction.

Claim: Let $$C$$ and $$C'$$ be any two clauses such that $$y\in C$$ and $$\neg y\in C'$$. Then $$C\land C'\implies\text{Res}_y(C,C')$$.

In order to prove the validity of a statement $$\psi$$, we will prove the negated statement $$\neg\psi$$ is unsatisfiable. To prove unsatisfiability of a formula $$\varphi$$, we need to define the resolution refutation of the formula $$\varphi$$ :

The resolution refutation tree of the formula $$\varphi$$ is a tree rooted at the empty clause, where every leaf is a clause in $$\varphi$$ and each internal node is computed as the resolvent of the two corresponding children.

Notice that clauses of $$\varphi$$ can appear repeated as leaves. From above claim we can conclude that:

Claim: If there exists a resolution refutation tree for formula $$\varphi$$, then $$\varphi\implies\Box$$ , that is, $$\varphi$$ is unsatisfiable.

Example: The formula
 * $$\varphi=(p\lor q)\land(\neg q\lor r)\land(\neg r)\land(\neg p\lor\neg s)\land(s\lor\neg t)\land(t)$$

has the following resolution refutation tree:

The order in which clauses are selected to compute the resolvent matters when computing the resolution refutation tree, as the following example shows: Consider the formula
 * $$\psi=(p\lor q)\land(\neg q\lor r)\land(\neg p)\land(\neg q)$$

Even though a resolution refutation tree may exist for $$\psi$$, order is important when trying to build the tree. Below are two different resolution refutation trees, but only one is successful:

Properties of Propositional Resolution
Soundness: Propositional resolution is sound, that is, if there exists a resolution refutation tree for a given formula $$\varphi$$, then $$\varphi$$ must be unsatisfiable.

Theorem: For any formula $$\varphi$$, if $$\Box \in Res(\varphi)$$, then $$\varphi \implies \Box$$.

Completeness: Propositional resolution is complete, that is, if a given formula $$\varphi$$ is unsatisfiable, then $$\varphi$$ has a resolution refutation tree.

Theorem: For any formula $$\varphi$$, if $$\varphi \implies \Box$$, then $$\Box \in Res(\varphi)$$.

Proof: By induction on the number of variables in $$\varphi$$.

Basis: We have one variable, say $$p$$. All possible clauses of $$\varphi$$ are $$\{p\}$$ and $$\{\lnot p\}$$. If $$\varphi$$ is unsatisfiable then both clauses occur, and therefore $$\Box \in Res(\varphi)$$.

Induction step: Suppose the hypothesis is true for formulas with less than $$n$$ variables. Let $$\varphi$$ be a formula with $$n$$ variables. Suppose $$\Box \notin Res(\varphi)$$; we will show $$\varphi$$ is satisfiable. Let $$p$$ be a variable of $$\varphi$$. Then either $$\{p\}\notin Res(\varphi)$$ or $$\{\lnot p\}\notin Res(\varphi)$$ (if both hold then $$\Box\in Res(\varphi)$$ immediately).

Assume $$\{\lnot p\}\notin Res(\varphi)$$. We define the formula $$\varphi^p$$ as containing all clauses that do not contain $$\{p\}$$ and where the literal $$\lnot p$$ has been removed from each clause (in other words, $$\varphi^p$$ is equivalent to the formula resulting from setting $$p$$ true).

Formally,
 * $$\varphi^p = \{C-\{\lnot p\} : C\in \varphi,\,p\notin C\}$$.

First, notice that
 * $$Res(\varphi^p) = \{C-\{\lnot p\} : C\in Res(\varphi),\,p\notin C\}$$

and thus,
 * $$\{\lnot p\}\notin Res(\varphi^p)$$.

Also, since $$\Box\notin Res(\varphi)$$ we have that $$\Box\notin Res(\varphi^p)$$. By the induction hypothesis, $$\varphi^p$$ is satisfiable. Then $$\varphi$$ is satisfiable by an extension of the satisfying assignment of $$\varphi^p$$ with $$p$$ equal true. The case $$\{p\}\in Res(\varphi)$$ is analogous.

Completeness of Natural Deduction
Theorem: Let $$H$$ be the set of inference rules of Natural Deduction. If $$\Sigma \models \varphi$$ then $$\Sigma \vdash_H \varphi$$.

The idea behind the proof of completeness of natural deduction is as follows. Suppose $$\varphi$$ is valid (then $$\lnot \varphi$$ is unsatisfiable). We then show there exists a resolution refutation for $$\varphi$$ and then by applying the contradiction rule (rule 15):
 * $$\frac{\begin{matrix}\neg \varphi\\\vdots\\\perp\end{matrix}}{\varphi}$$

we conclude $$\varphi$$ can be inferred.

Proof: (Sketch) Given a formula $$\varphi$$ valid under $$\Sigma$$, we perform the following steps: Step (1) can be easily done by repeated application of De Morgan's laws. Step (2) can be proven using natural deduction. Finally, step (3) can be proven by induction on the number of steps to obtain $$Res(\psi)$$. Clearly, each step can be simulated using natural deduction. It is very likely that any algorithm for propositional resolution will take very long on the worst case (recall that checking validity of a formula $$\varphi$$ is co-NP complete).
 * 1) Prove that $$\lnot \varphi$$ is equivalent to some $$\psi$$, where $$\psi$$ is in CNF.
 * 2) Prove that $$\psi \implies Res(\psi)$$, for all $$\psi$$.
 * 3) By completeness of resolution, if $$\psi$$ is unsatisfiable then $$\Box \in Res(\psi)$$. Therefore, $$\{p\}$$ and $$\{\lnot p\} \in Res(\psi)$$ for some literal $$p$$. This implies $$Res(\psi)\implies \bot$$.
 * 4) Conclude that $$\lnot \varphi \implies \bot$$ and therefore $$\varphi$$ is valid.

Linear Resolution and PROLOG
Linear resolution is a particular resolution strategy that always resolves the most recent resolvent with a clause. The resolution refutation tree so obtained is therefore linear. It is possible to prove that, if the set of clauses are Horn clauses, there exists a linear resolution strategy for any formula. That is, linear resolution is complete for the set of Horn clauses.

The language PROLOG uses resolution on a set of Horn clauses. Each clause is called a program clause. Moreover, clauses composed by a single literal are called facts. A clause with a single negated literal is called a query. The table below shows a comparison of the different notations. In PROLOG, to query a statement $$t$$, the idea is to negate the statement ($$\lnot t$$) and to perform resolution with the set of known true statements. If a resolution refutation tree is found, the statement $$t$$ is implied by the program.

Example: An example of linear resolution for the formula
 * $$\phi = (p)\land (q)\land (r)\land (t\lor \lnot s \lor \lnot r)\land (s \lor \lnot p \lor \lnot q)\land (\lnot t)$$

is shown here:


text:
Wikipedia:Articles for deletion/Roy Geronemus

The result was keep. Tone 08:20, 25 August 2020 (UTC)

Roy Geronemus

 * – ( View AfD View log  Stats )

WP:PROMO for a run-of-the-mill dermatologist. Doctors are very often affiliated with hospitals, and very often publish in scientific journals. AleatoryPonderings (talk) 04:46, 18 August 2020 (UTC)
 * Struck "run-of-the-mill" as misleading per the below. Misreading of the evidence on my part. AleatoryPonderings (talk) 19:07, 19 August 2020 (UTC)
 * Note: This discussion has been included in the list of Academics and educators-related deletion discussions. AleatoryPonderings (talk) 04:46, 18 August 2020 (UTC)
 * Note: This discussion has been included in the list of Medicine-related deletion discussions. AleatoryPonderings (talk) 04:46, 18 August 2020 (UTC)
 * Note: This discussion has been included in the list of New York-related deletion discussions. AleatoryPonderings (talk) 04:48, 18 August 2020 (UTC)

 * Keep. It's always harder to judge with doctors, particularly with anything to do with dermatology, laser surgery, etc. But this doctor certainly does not appear to be "run-of-the-mill". GoogleScholar gives him the h-index of 76, which is astonomically high, for any discipline. Although in medicine many "best doctor in ..." type listings are not worth much as honors, he has a number of individual society awards (I added a couple to the article) of the type that WP:PROF has in mind. Also he was president of two scolarly/medical societies which could perhaps count as passing WP:PROF. In any case, one can't fake an h-index of 76. So I'll say that passes WP:PROF. Nsk92 (talk) 12:04, 18 August 2020 (UTC)
 * Keep per WP:PROF and maybe #C6 as above. —David Eppstein (talk) 18:57, 19 August 2020 (UTC)

source: wikimedia

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
User:Lior Zamir

Hello,

My name is Lior Zamir and I'm a senior web developer at CET (The Center for Educational Technology). You can see more information about me through my LinkedIn profile - https://www.linkedin.com/in/lzamir

Best regards, Lior

title: User:Lior Zamir


text:
Talk:Don Fontana

External links modified
Hello fellow Wikipedians,

I have just modified one external link on Don Fontana. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
 * Added archive https://web.archive.org/web/20110716211339/http://www.tenniscanada.com/tennis_canada/Pub/HallOfFame.aspx to http://www.tenniscanada.com/tennis_canada/Pub/HallOfFame.aspx

Cheers.— InternetArchiveBot  (Report bug) 12:52, 12 September 2017 (UTC)

Citation needed
Is it necessary to provide a citation when the reference is given in the body of the text? Tennisedu (talk) 05:05, 10 February 2023 (UTC)

title: Talk:Don Fontana


text:
Josephine Macalister Brew

Josephine Macalister Brew CBE (18 February 1904 –30 May 1957) was a British educationist and youth worker. A 'pioneer of social group work as a vehicle for social education,' her 1946 work Informal Education was the 'first text to deliberately employ the term' and the first solo-authored work on the subject.

Life and work
Josephine Macalister Brew was born Mary Winifred Brew in Llanelli, Wales, the daughter of Frederick Charles Brew, a boot and shoe dealer. She studied history at the University of Wales, Aberystwyth, and graduated in 1925, after which she became a history teacher at Shaftesbury High School for Girls, Dorset. In 1932, Brew moved to Cardiff to study for her Doctor of Law.

In Cardiff, Brew began her lifelong involvement in youth and community work, working with the Butetown Women and Girls' Club, and South Wales educational settlements. She later became a youth officer in Lincoln, where she acted as secretary of the Lincoln Federation of Girls Clubs. Subsequently, Brew served on the executive committee of the National Association of Girls' Clubs (later the National Association of Girls' Clubs and Mixed Clubs) for whom, following a comparatively short period as youth officer for Oldham, she was appointed Education Secretary in 1942. Among her colleagues there were Eileen Younghusband and Pearl Jephcott. The National Association of Girls Clubs and Mixed Clubs boasted, in 1944, 108,000 affiliated clubs, described as 'a training-ground for citizenship, giving a foretaste of the responsibilities and joys of an adult life, as well as an experience of community life.' Brew herself was a vocal advocate of mixed clubs, arguing for their benefits to young people and the society in which they lived.

Brew also played a key role in creating the pilot Girls' Award (launched in 1958), part of the Duke of Edinburgh's Award scheme, initiated two years earlier in 1956.

As well as active youth work, Brew was a sought after speaker, and contributor to numerous publications. These included pieces for the Times Educational Supplement, as well as national newspapers. Brew's writing has been described as having 'a characteristic flowing style that moves between erudition and the plain talking of a sensible aunt.'

Philosophy
Brew believed that society had a responsibility to prepare its young people for their role as future citizens in a rapidly changing world. In 'Why Clubs at All?' (1943), she argued that:

They are the citizens of tomorrow, and to them the community has a double responsibility. Firstly, to provide each one of them with the possibilities of full and harmonious development, and secondly, to try to ensure that they are fitted to be members of the community of the future.

In her preface to Informal Education, published in 1946, Brew wrote: "Perhaps nothing will matter more in the next fifty years than the ability of the common man to adapt himself to the changing world - a world in which material prosperity may be just around the corner, but where there are still vast acreages of barren land in the intellectual, emotional and spiritual field."For Brew, the function of youth work was educating 'individual personalities with powers of judgment who will indulge in group living in the service of a social ideal'. She believed that involvement in youth clubs, and opportunities for association with others, would best equip young people for the requirements of active citizenship; that 'it is in the interplay of social relationships that real and full individuality is attained'. This preparation would act as a counterbalance to a society in which, Brew wrote, 'we educate our children for the first fourteen years of their life as though there were no such thing as industry, and then surrender them to industry as though education had never been.'

Brew also believed that, in light of 'much social injustice and many intolerable circumstances', the aim of club leaders should be social reform. In Clubs and Club Making, she argued that:"If young people are to become fully alive to their own powers and capable of being responsible members of society, social conditions must not exist which make that almost impossible. Thus the club leader must constantly seek to persuade the wider community to fit itself to be the kind of society in which these young people can grow up to enter into full citizenship."

Death and legacy
Josephine Macalister Brew died on 30 May 1957 at Woodford Green, Essex. A funeral service was held at the City of London Crematorium on 3 June.

In an obituary in Nature, John Wolfenden wrote that 'there can be few people who have lived so fully, so usefully, or so serviceably' as Brew. 'She would', he concluded, 'prefer to be remembered as one who never lost her astringent affection for hundreds of 'crazy mixed-up kids'.' Dame Isobel Cripps described Brew as a 'constructive force', whose 'great gift to us all is that she has built into the fibre of our nation something which will live on in the generations to come.'

On 13 June 1957, as part of the Queen's Birthday Honours, Brew was appointed CBE.

Publications

 * Clubs and Club Making (1943)
 * In the Service of Youth, a practical manual of work among adolescents (1944)
 * Informal Education; Adventures and Reflections (1946)
 * The Young Idea (1956)
 * Youth and Youth Groups (1957)
 * 'Group Work with Adolescents' in Social Group Work in Great Britain, ed. Peter Kuenstler (1954)

title: Josephine Macalister Brew


text:
Talk:Dennis Corrigan

External links modified
Hello fellow Wikipedians,

I have just modified one external link on Dennis Corrigan. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
 * Added archive https://web.archive.org/web/20051025121628/http://www.galleryriver.com/website/exhibit.html to http://www.galleryriver.com/website/exhibit.html

Cheers.— InternetArchiveBot  (Report bug) 11:03, 8 January 2018 (UTC)

title: Talk:Dennis Corrigan


text:
Wikipedia:WikiProject Spam/LinkReports/blog.citrusstudios.com

Links

 * blog.citrusstudios.com resolves to [//<IP_ADDRESS> <IP_ADDRESS>]
 * blog.citrusstudios.com is hosted on citruswebdesign.wordpress.com
 * citruswebdesign.wordpress.com resolves to [//<IP_ADDRESS> <IP_ADDRESS>]
 * Link is not on the blacklist.
 * Link is not on the domainredlist.
 * Link is not on the Monitorlist.
 * None of the mentioned users is on the blacklist.
 * Link is not on the whitelist.
 * Link is not on the monitor list.
 * Link is not on the Monitorlist.
 * None of the mentioned users is on the blacklist.
 * Link is not on the whitelist.
 * Link is not on the monitor list.

Additions

 * Displayed all 1 additions.


text:
User:Lenneth

Hi my name is Lenneth. I just signed up and hope ot make good use of this site in future. I hope to have something to contribute too! cheerio!

uni3

title: User:Lenneth


text:
Talk:Komsomolsky, Pavlovsky District, Altai Krai

Russia
Dose this located in Europ or Asia side? <IP_ADDRESS> (talk) 11:11, 14 July 2023 (UTC)


text:
Dietmar Haaf

Dietmar Haaf (born 6 March 1967 in Bad Cannstatt) is a former (West) German long jumper.

Career
He won the gold medal at the 1990 European Championships in Split in a personal best jump of 8.25 metres. The following year he won the gold medal at the World Indoor Championships in Seville. He finished fourth at the 1991 World Championships in Athletics in Tokyo.

His personal best jump of 8.25 metres ranks him seventh among German long jumpers, behind Lutz Dombrowski, Frank Paschek, Josef Schwarz, Henry Lauterbach, Marco Delonge and Konstantin Krause.

Haaf retired in 1997.

International competitions
Note: Results with a Q, indicate overall position in qualifying round.

title: Dietmar Haaf


text:
Talk:Tehama Inc.

Re crunchbase
Thanks, User:JSFarman, for the information re the accepability of crunchbase as a reliable source. I'm working to find alternate sources to substitute for those.

I'm curious about why WP views cruchbase so. WP's page on it reports: "Crunchbase sources its data in four ways: the venture program, machine learning, an in-house data team, and the Crunchbase community. Members of the public can submit information to the Crunchbase database. These submissions are subject to registration, social validation, and are often reviewed by a moderator before being accepted for publication." Can you elucidate?

 * There isn't uniform editorial oversight. Machine learning and the in-house data team are only as reliable as the data, and community contributors aren't professional journalists. "Members of the public can submit information to the Crunchbase database" that is"often reviewed" means that not all of the content is reviewed. JSFarman (talk) 01:37, 22 December 2020 (UTC)

Notability
Evidence in cited sources:, , , ~Kvng (talk) 00:47, 29 December 2020 (UTC)

title: Talk:Tehama Inc.


text:
Bene Merito honorary badge

The Bene Merito honorary distinction (Odznaka Honorowa „Bene Merito”; Latin for "well-merited" or "worthy") is a departmental (ministerial) decoration of Poland. The Minister of Foreign Affairs of Poland awards the citizens of Poland and foreign nationals with this decoration "in recognition of their merits in promoting Poland abroad."

It was established in 2009 by the then Minister of Foreign Affairs Radosław Sikorski.

title: Bene Merito honorary badge


text:
Talk:Charles A. Watson

External links modified
Hello fellow Wikipedians,

I have just modified one external link on Charles A. Watson. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:
 * Added archive https://web.archive.org/web/20111017095520/http://www.aucegypt.edu/about/History/Pages/default.aspx to http://www.aucegypt.edu/about/History/Pages/default.aspx

Cheers.— InternetArchiveBot  (Report bug) 02:05, 3 August 2017 (UTC)

title: Talk:Charles A. Watson


text:
poten

Etymology 1
From, from , from.

Verb

 * 1) to set, plant, place a young plant or large seed individually in soil or other substrate where it can grow; sow
 * 2) to release young fish or - eggs to regulate the population for fishers' benefit

Etymology
From, from.

Verb

 * 1) to plant, to put (into the ground, usually of plants)

title: poten


text:
A-level Mathematics/OCR/C1/Coordinate Geometry and Graphs

Co-ordinates are a way of describing position. In two dimensions, positions are given in two perpendicular directions, x and y.

Straight lines
A straight line has a fixed gradient. The gradient of a line and its y intercept are the two pieces of information that distinguish one line from another line.

Equations of a straight line
The most common form of a straight line is y = mx + c. m is the gradient of the line, and c is the point at which the line intercepts the y-axis. When c is 0, the line passes through the origin (0,0). Other forms of the equation are x = a, used for vertical lines of an infinite gradient and y = b is used for horizontal lines with a zero gradient. Also some equations are commonly written as: px + qy + c = 0. You can also use the equation y-y1=m(x-x1)

Gradient of a line
The steepness of a line can be measured by its gradient, which is the change in the y direction divided by the change in the x direction. The letter m is used to denote the gradient. The formula to find a gradient is: $$m = \frac{y_2-y_1}{x_2-x_1}$$ As a side note $$\tan\theta = m\,$$.

Point-Gradient Form
The equation of a line having the co-ordinate $$\left(x_1,y_1\right)$$ and having a gradient of m is: $$y-y_1=m\left(x - x_1\right)$$. Then you simply rearrange the equation into the form y = mx + c.

Parallel lines
A pair of lines are parallel (the symbol is $$\|$$ ). If their gradients are equal, $$m_1 = m_2\,$$. So in order to find the equation of a parallel line you need the slope of the original line and one set of co-ordinates on the parallel line. Then you use the Point-Gradient formula to find the equation of the parallel line.

Perpendicular lines
A pair of lines are perpendicular (the symbol is $$\perp$$) if the product of their gradients is $$m_1 \times m_2=-1$$,. So if you need the equation of a line perpendicular to another line, all you need to do is replace the gradient m with the negative reciprocal of m.

So for example if line 1 is y = 2x +3 and you need to find the line perpendicular to this that goes through the point (0,1), then the gradient m = -1/2 (because 2 x -1/2 = -1). This gives y = -x/2 +c.

Putting the known point (0,1) into this equation gives :

1= -0/2 +c which gives c = 1

so the equation is y = 1- x/2.

Distance between two points
Using the co-ordinates of two points, it is possible to calculate the distance between them using Pythagoras' theorem. The distance d between any two points $$A(x_1,y_1)$$ and $$B(x_2,y_2)$$ is given by: $$d = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$$

Mid-point of a line
When the co-ordinate of two points are known, the mid-point is the point halfway between those two points. For any two points A$$({x_1},{y_1})$$ and B$$({x_2},{y_2})$$, the co-ordinates of the mid-point of AB can be found by $$\left(\frac {{x_1} + {x_2}}{2}, \frac {{y_1} + {y_2}}{2}\right)$$.

Intersection of lines
Any two straight lines will meet at a point, as long as they are not parallel. You can find the point of intersection simply by solving the two equations simultaneously. This is also true for curves, although non linear curves may intersect at multiple points or not at all and usually require different methods to solve.

Curves
To sketch a graph of a curve, all you need to know is the general shape of the curve and other important pieces of information such as the x and y intercepts and the points of any maxima and minima.

Curves in the form $$y=x^n$$
Note: That all the odd powers of $$x$$ share the same general shape, moving from bottom-left to top-right, and that all the even powers of $$x$$ share the same "bucket" shaped curve.

Curves in the form $$y=\frac {1} {x^n}$$
Just like earlier, curves with an even powers of $$x$$ all have the same general shape, and those with odd powers of $$x$$ share another general shape.

All curves in this form do not have a value for $$x=0$$, because $$\frac {1} {0}$$ is undefined. There are asymptotes on the $$y$$ axis, where the curve moves towards the y axis increasingly slowly but will never actually touch.

Curves in the form $$y=\sqrt x$$

All curves in this form will not have values for x < 0. They will all have the same general shape.

Intersection of lines and curves
When a line intersects with a curve, it is possible to find the points of intersection by substituting the equation of the line into the equation of the curve. If the line is in the form $$y = mx + c$$, then you can replace any instances of $$y$$ with $$mx + c$$, and then expand the equation out and then factorise the resulting quadratic.

Need information on describing the geometrical relationship between a curve and a straight line

Intersection of curves
The same method can be used as for a line and a curve. However, it will only work in simple cases. When an algebraic method fails, you will need to resort to a graphical or Numerical Method. In the exam, you will only be required to use algebraic methods.

Graphical Rules
In many cases it is easy to obtain a graph from a preexisting graph using these rules.

Reflection

 * 1) $$y = -f \left (x \right )\,$$ is a reflection of $$y = f \left (x \right )\,$$ through the x axis.
 * 2) $$y = f \left (-x \right )\,$$ is a reflection of $$y = f \left (x \right )\,$$ through the y axis.

Stretching

 * 1) $$y = f \left (bx \right )\,$$ is stretched away from the y-axis if $$0 < b < 1\,$$ and stretched towards the y-axis if $$b > 1\,$$. In both cases the change is by b units.
 * 2) $$y = af \left (x \right )\,$$ is stretched towards the x-axis if $$0 < a < 1\,$$ and stretched away from the x-axis if $$a > 1\,$$. In both cases the change is by a units.

Translations

 * 1) $$y = f \left (x - h \right )\,$$ is a translation of f(x) by h units to the right.
 * 2) $$y = f \left (x + h \right )\,$$ is a translation of f(x) by h units to the left.
 * 3) $$y = f \left (x \right ) + k\,$$ is a translation of f(x) by k units upwards.
 * 4) $$y = f \left (x \right ) - k\,$$ is a translation of f(x) by k units downwards.

The Circle
A circle is a set of all points in a plane that are a fixed distance r away from a given point called the center. The distance r is the radius of a circle.

The two basic laws of circles are:

$$Area = \pi r^2 \,$$

$$Circumference = 2 \pi r\,$$

Properties of a circle
A radius always bisects a chord if they are perpendicular to each other.

If any point on the circumference of the circle is connected to the diameter, it forms a right angled triangle.

If a radius is drawn and then a tangent is drawn from that point. Then the radius and tangent line will be perpendicular to each other.

Equation of a Circle
The standard equation of a circle is:

$$x^2 + y^2 = r^2\,$$

This will always give us a circle centered around the origin (0,0). If we want a circle with a center at (h,k) we use the following formula.

$$\left (x - h \right )^2 + \left (y - k \right )^2 = r^2$$

However you can not graph either of these equations with a calculator. You will need to split it into two equations, but the graph will not be perfect, because x is undefined when x = 0 and when $$(x -h)^2 = r^2$$: $$y =+ \sqrt{r^2 - \left ( x - h \right )^2} + k$$ and $$y =- \sqrt{r^2 - \left ( x - h \right )^2} + k$$.

Here is how $$\left (x - 5 \right )^2 + \left (y - 8 \right )^2 = 2^2$$ would look graphed:


text:
Voter's Guide/Australia/Issue Guide/Medicare and Bulk-Billing

Medicare, Australia's universal health insurance system, became an issue in 2004, particularly when combined with the increasing scarceness of bulk-billing.


text:
Cookbook:MPT (Mozzarella Pasta with Tomato and Basil)

This is a delicious and quick recipe for a sunny day, or to bring back a little memory of summer. It's served warm so may not suit a winter evening! The combination of flavours (milky mozzarella, eggy pasta, sweet tomato and spicy basil) is just wonderful. The secret here is to prepare all the ingredients except the pasta ahead of time and let them soak together. You can also stand the prepared bowl of ingredients in a sink full of hot water, so that the mozzarella starts to soften and the juices start to run.

Ingredients

 * 2 mozzarella balls (cow or buffalo)
 * About 10–15 small tomatoes or 4–5 larger tomatoes (you need about the same amount as the mozzarella)
 * A good handful of basil leaves (about 15–20 leaves)
 * Olive oil
 * Salt
 * Black pepper
 * 250 g fresh egg pasta

Procedure

 * 1) Roughly chop the mozzarella and the tomatoes and put them in a big salad-type bowl.
 * 2) Tear up the basil and sprinkle it over the mozzarella and tomatoes.
 * 3) Drizzle on lots of extra virgin olive oil (at least 3 tablespoons).
 * 4) Add a good amount of salt and just a little black pepper. The salt will start to leach moisture out from the other ingredients and create a sauce.
 * 5) Let rest for at least 30 minutes.
 * 6) Boil the egg pasta until al dente, then drain.
 * 7) Add the hot pasta to the bowl of other ingredients. Toss well until the pasta is well-coated. Serve.


text:
turbolenza

Etymology
Probably a borrowing or semi-learned adaptation of. .

Noun

 * 1)  turbulence
 * 2) boisterousness
 * 3) upheaval
 * 4)  wake (the turbulent air left behind a flying aircraft)

title: turbolenza


text:
Talk:National Security Archive/Archive 1

Dispute
I would disagree that the NSA is a 'left-leaning' organization. I would say it is 'indepedent'. NSA doesn't state a position on this on their home page - they only say they are a 'non-governmental, non-profit institution'. I searched for 'left-leaning National Security Archive', 'right-leaning National Security Archive', and a few other combos and permutations and found nothing. I did find plenty of links from all sorts of newspapers/websites/publication to 'independent National Security Archive'. Anecdotally, from looking at their site, and seeing a live presentation, I know they work like crazy to declassify documents in every U.S. Administration, regardless of Dem/Repub.

I would disagree that the NSA has any position on 'the Bush administration's Middle East policy'. The NSA strives for government openness, so they'll always be the scourge of current and former presidents, and will always be a powerful tool for democracy. I've seen nothing on ther website, and nothing written in articles/etc., to suggest they have any position on any government policy, ever - except for the classification of materials and things related. They've strongly advocated for government openness, but that's it, that I know of.

I didn't make changes b/c I'm scared after wrecking something last time I tried, and orig author seems to feel pretty strongly that NSA is a lefty org.

Thanks.

Shmooth 10:10, 24 Nov 2004 (UTC)

 * NSA has been described as "leftist" by Media Research at and other similar pages on that site.  They are also cited at  in a very liberal oriented light.  I searched for 'liberal bias "National Security Archive"' on google and got a few hits. As to the Middle East comment, the most often cited work is  (go down to the Middle East section and read the work on Saddam), but I've certainly seen worse.  I would disagree that they have an institutional position on Bush's Mid East policy, but would probably agree that it is a left leaning organization.  btw, I changed your title to a section header.  Hope you don't mind. -Vina 01:32, 3 Dec 2004 (UTC)

"veiled in Secrecy"
If NSA typically relies on FOIA requests to get information, the term veiled in secrecy does not apply, and really the original wording, which was "otherwise be known" is more accurate. Does NSA affect the declassification of documents? If they do, the new wording is more appropriate. My research so far seems to reflect that the original writing is more accurate. -Vina 10:55, 5 Dec 2004 (UTC)

tbeatty edits
Fund For Peace: historical ties and the chairman of hte board is a trustee.

Independant is a POV term like "liberal" or "conservative." Their are a 501(c)(3) non-profit organization and that is a fact. But independance from who? That is POV.

Scholarly is likewise a POV term that depends on your interpretaion of the advisory board. I would like to see how the board is chosen as that is factual information. If that it included "scholarship" than that is a hard fact. But saying the adivce is "scholarly" is a POV.

And lastly, it is not plagiarism to take a small amount of sentences from the "About" page and cite them in the article. In fact, the citation is optional but I do include it. This is considered fair use. --Tbeatty 02:45, 3 April 2006 (UTC)

Yes, Fund for Peace has been associated with the Archive in the past but so have many other organizations; it would be superflous to link them all.

Scholarly is hardly a POV term. Someone who has a PhD is a scholar. They may not be notable and their work may be controversial but they are a scholar because they are an expert in their field otherwise, according to your way of thinking, no one could be considered scholarly because the term is too subjective. The Archive does what is considered scholarly work, they get the direction for this work THUS, their "scholarly direction" from that body. Further, independent is not referred to in a political manner as you are referring to it as. Non-profit organizations are either indepedent (ie an org which does not fall under the guidance/control of an umbrella organization) or dependent (ie one which does). According to the website of NSArchive, the organization IS independent. The Archive's discussion of its own organization considers itself independent. For a quote since you seem to rely on them so heavily rather than contributing your own work: "The National Security Archive is an independent non-governmental research institute and library located at The George Washington University in Washington, D.C." --Strothra 21:47, 3 April 2006 (UTC)

 * "Fund for Peace" was it's fiscal sponsor for most of it's life. The Chairman is on the Fund for Peace board of trustees.  There is an obvious association that is much larger than it's affiliation with any other group.  Since the organization noted it on their about page I don't see why it is controversial to have it hear.

 * "Scholarly advice" is a POV term. I don't argue that the people who are on the board are scholars.  I think that if scholarship is part of the requirements for selection, it should be noted.  Please cite it.  But claiming "Scholarly advice" attempts to characterize what advice this board is giving them.  It is inherently POV.  It would be better to list how the advisory board is selected based on the scholarship, contributions, etc.  There are lots of "scholars" throughout industry, government and academia and I daresay it wouldn't do justice to descrube all hteir advice as "scholarly".  The oil industry, for example, has plenty of PhD's advising against global warming.  It would be POV to say "the Oil Industries' scholarly advisors say there is no evidence of man-made global warming."    Instead, it would be better to say the advisors give advice and then list the qualification of the adviors rather than creating a poin-of-view that their advice is scholarly.  The same is true hear.  --Tbeatty 22:09, 3 April 2006 (UTC)

 * Please note that I stated "The Archive does what is considered scholarly work, they get the direction for this work THUS, their "scholarly direction" from that body." Also, among your many other spelling mistakes, you should have typed "here" and not "hear."  --Strothra 22:14, 3 April 2006 (UTC)

 * Unfortunately I type as if I am speaking and learned phonetically. I catch most of that on edit.  I'm glad you were able to interpret.

 * Who considers it "scholarly work"? This is an opinion.  The opinion can be cited but establishing opinion as fact is not encyclopedic.   Encyclopedias deal with facts.

 * As for "independant", there are a number of "independant" organizations that have political view points. A lot of organizations that claim independance really have view points that are not "indpendant" at all and the term is inherently POV. You could easily change it to "The NSA describes itself as: ..." But to state it as fact is POV.--Tbeatty 22:20, 3 April 2006 (UTC)

 * I type as if I am speaking as well but hardly make the spelling and grammar errors that you do but I can still understand you so it's not a problem. I was just letting you know that you may wish to work on that.  Okay, for now I will concede your point concerning the word "scholarly".  Your arguement concerning the word "independent" first of hall suggests that you believe that the archive has a political orientation.  Second of all, the term "independent" is not even being used in the manner in which you are implying.  You seem to believe that it means that it is independent in its political orientation.  This is not true.  Independent, as it is clearly used in the article and on the Archive's website, means that the organization is independent as an institutional body which it is.   The archive does not answer to any organization.  I think that you are showing your own political colors by implying that others are trying to make a political arguement.  I think that you are one trying to push their POV on the article.  --Strothra 02:14, 4 April 2006 (UTC)

 * Not at all. The fact that you can construe POV from the removal of adjectives tells me that the adjectives have a meaning to you.  That is by definition POV.  "Independant" can mean a lot of things but it is still POV.  Whether it's political, economic, academic, etc.  If you think it is important to reflect that the Institute considers itself "independant", put it in that voice.  I think those things are important.  It's own view as well as the view of outside organizations are important.  What is also important is that it's not reflected as Wikipedia's view.

 * And just an observation, if you think you can construe my 'political colors' by my support or opposal to an 'indepandant' organization, I would again question it's independance on it's face.  Why would opposition/support of an independant organization be colored by ones political views?

 * My suggestion is to rewrite it so that it is clear the organization's view is that it is independant. For example: "According to NSA's website they are an 'indpendant institure'" and cite the website location.  That makes it a fact and is perfectly acceptable to me.

 * As for scholarly, I would rewrite that so that the selection aspect of the board uses a scholarly criteria. Cite the selection aspect and it becomes a fact and not POV.  --Tbeatty 03:15, 4 April 2006 (UTC)

 * I'll agree with you on the scholarly part. But I stil feel that you are talking around my arguments concerning the word "independent."  I am saying that it is not meant in a political manner at all whether in this article or on the NSArchive's website.  I am saying that it means simply that no organization controls or directs NSArchive and it is an entity unto itself.  It is factual information which if you disagree with you must prove it wrong. The burden of prove lies on you. --Strothra 03:49, 4 April 2006 (UTC)

 * Independant is a POV term whether is polital or financial or parental or any way which you want to present it. It is certainly not common factual information as I could easily say it gets it's money from various organizations that have their own agendas and POV's.  There is certainly a method of how it chooses it's board.  There is certainly a method as to how it chooses it advisors.  It certainly has a process in determining it's priorities.  Absolute "independance" is easily challenged at any of these levels.  As you pointed out, indpendant can have many connotations including political.  If nothing else, it is beholden to it's own institutional biases.  Which version do you believe Wikipedia should vouch for and why?  It seems much more encyclopedic to have the organization vouch for it's own independance in the form of an attribution.  If it is indeed fact, it needs a reference.  I don't dispute it, it just needs attribution as to who believes it is independant.  --Tbeatty 06:05, 4 April 2006 (UTC)

 * This is absurd and childish. It is an indepdenent organization and that is undeniable fact. No one is discussing how it chooses it's advisors because it's not information worthy of Wikipedia because it is very considerably non-encyclopedic material which distracts from the purposes and aims of the organization.  Once again, by bringing this up you are doing nothing but talking around the arguement.  Not all facts need references.  Many facts stand alone by themselves such as that one which is proven by pure reason.  Further, the NSArchive's website is linked in the external links section and the phrase that it is an indepdenent org is on the main page. Institutional biases have no place in Wikipedia but Wikipedia is also not the place to sort out those biases.  The term indedepdent as used in this article does not even suggest having to do anything with any biases, political orientation, or institutional leanings of any sort.--Strothra 12:13, 4 April 2006 (UTC)

 * Unfortunately, this is the way wikipedia hsa chosen to present in NPOV. They may indeed be independant.  The may may be left-wing or right-wing.  They may dependant on the Carnegie Foundation or the Mellon Foundation.  How do you claim they are independant?  What source is there that they are independant?  I say name it and put it in the article.  I am not against saying they are independant.  I just want to know who is saying they are independant.  They should be the ones making the claim, not Wikipedia.  And it is not 'undeniable fact'.  The archive shows an immediate discussion about whether they were left0wing or not.  --Tbeatty 16:30, 4 April 2006 (UTC)

 * Once again you cloud the arguement by talking around it. Independent is not referring to its political orientation.  The arguements made my Mytwocents, however, are valid and I will support them.  There is reason to believe that an organization will follow the direction of its funders and thus their "independence" is understandably grey or one could even argue that their funders fund them because they already do work in line with their own objectives.  This understanding would make its indepdendence impossible to prove or disprove.  Please note for future reference that you could cite every claim on wikipedia and the citations would take up most of wikipedia's server space.  I will concede to the removal of the term in question due to the arguments put forth by Mytwocents.  --Strothra 18:12, 4 April 2006 (UTC)

 * Excellent. Can you remove the neutrality tag?  Thanks! --Tbeatty 18:16, 4 April 2006 (UTC)

 * No problem, done. --Strothra 18:18, 4 April 2006 (UTC)

A tutorial for plagiarism and copyright
First, Copyright: Works can be copyrighted. Copyrighted works can be cited under fair use. Quoting it or citing it is not a defense to copyright or else people would be able to copy books simply by saying "Joe Author said: ..." It is not a copyright violation to take less than 300 words from an article and cite it.

Second: plagiarism. Plagiarism is the tehft of an idea or an expression. IT is not illegal but also not scholarly. Repeating facts is not plagiarism. For example: if someone writes in ther About page: "The XYZ institute is funded by ABC Fund" it is not plagiarism to say "The XYZ institute is funded by ABC fund."[citation for fact]. You cannot plagiarize facts. See Plagiarism.

For factual material it is adequate to simply cite the cource for the fact. --Tbeatty 05:42, 3 April 2006 (UTC)

 * No one is taking issue with your use of facts. It is your use of entire sentences word for word that is the problem. Gamaliel 06:15, 3 April 2006 (UTC)

 * It is not a problem if it is a) a fact and b) sourced to the origin of the fact. Facts do not need to be quoted.  E=mc^2 is a fact and needs attribution to Albert Einstein but it does not not need to be quoted.  Footnoted sources are adequate for factual references.  You need to refresh your copyright and plagiarism training.--Tbeatty 18:45, 3 April 2006 (UTC)

You just aren't listening. The issue is not with your use of facts. It is with you copying word for word exactly the sentence which conveys these facts.

Your contribution: "The National Security Archive was founded in 1985 by a group of journalists and scholars who had obtained documentation from the U.S. government under the Freedom of Information Act and sought a centralized repository for these materials."

The NSA homepage: "The National Security Archive was founded in 1985 by a group of journalists and scholars who had obtained documentation from the U.S. government under the Freedom of Information Act and sought a centralized repository for these materials."

You could have easily conveyed these same facts in your own words. To not do so and to not identify these words as non-original is plagiarism. Gamaliel 19:28, 3 April 2006 (UTC)

 * Oooh, now you have come up with a form of "self-plagiarism" since you have copied your own works to two pages (yes, self-plagiarism is real and this is a textbook example as you didn't cite that you used this work on a different page).

 * But as I said on your talk page. You are simply mistaken.  Word-for-word, attributed excerpts of fact are not plagiarism.  Word-for-word is more closely tied to copyright, but we have already shown how htis is fair use and not a copyright (citation is irrelevant to copyright).  Please review what plagiarism is before making an accusation.  To be plagiarism it must satisfy two requirements 1) it must be thought or expression and 2) it must be passed off as orginal thought.  Since this was 1) fact and 2) cited it cannot possibly be considered plagiarism.  Rewording of an expression (which is what you appear to advocate) is a form of plagiarism as it is trying to express the idea of someone else without it appearing as their expression.  In that case, a word for word, attributed source is a more intellectually honest form.  --Tbeatty 20:05, 3 April 2006 (UTC)

 * If you prefer to use an exact quote instead of rewording material, then just identify it as such by using quote marks. This is more intellectually honest than inadvertantly passing it off as original material. Gamaliel 20:28, 3 April 2006 (UTC)

 * Okay a little simpler. Plagiarism is about ideas, not words.  It is not for factual content.  There is nothing "original" to quote.  There is no "quote". It is incorrect to use quotes for factual content as it implies an original idea or concept.  Citations are adequate for that.  Again, I point you to your album play lists.  The titles and order are facts and need no quote marks.  Citations are adequate.

 * Now if I had quoted pieces about their beliefs or goals, that is an expression and would need a quote to prevent plagiarism. Even rewording does not change the obligation since plagiarism is stealing ideas and viewpoints, not words.   You are confusing the copyright concept of word-for-word with the plagiarism concept of stealing ideas.  And you are simply incorrectly applying both standards.--Tbeatty 22:00, 3 April 2006 (UTC)
 * Tbeatty, this is not the forum to debate this. Wikipedia policy is Wikipedia policy.  If you wish to debate this then please debate this in the discussion section of that policy.  If you continue, I will request administrator arbitration in this matter. --Strothra 22:06, 3 April 2006 (UTC)
 * I did not violate Wikipedia policy so there is no debate. --Tbeatty 22:48, 3 April 2006 (UTC)

 * Please note that I have already done that with the limited amount of encyclopedic material which was included in tbeatty's edit. Also Tbeatty, you are seriously close to violating Wikipedia policies on WP:NPA and WP:CIVIL. --Strothra 21:48, 3 April 2006 (UTC)

 * I am? I am not aware of any personal attacks nor am I being uncivil. I believe you and Gamaliel are mistaken about interpretations of plagiarism (which is a serious accusation, but not Wikipedia policy) and copyright violation (which is a Wikipedia policy).  I have not attacked anyone.  I have tried to clarify, for your edification, what is a copyright violation and what is plagiarism so you don't mistakenly make the accusation again. --Tbeatty 22:48, 3 April 2006 (UTC)

Where I think Strothra's edits can go - copy of neutral version from Mytwocents
The National Security Archive was founded in 1985. It is a 501(c)(3) non-profit research and archival institution located within The George Washington University in Washington, D.C. ''' From NSA's website it is an "indpendant " [cite here]. ''' It archives and publishes declassified U.S. government files concerning selected topics of American foreign policy. The Archive collects and analyzes the documents of many various government institutions obtained via the Freedom of Information Act. The Archive then selects documents to be published in the form of manuscripts and microfiche as well as made available through their website.

The Archive operates under an advisory board which is overseen by a board of directors. ''' The board of directors are chosen according to [cite here]. ''' The Archive's research was awarded in late 2005 by winning an Emmy Award for its work on the documentary, "Declassified: Nixon in China." More recently, the Archive uncovered a secret reclassification program operating since 1999. This program was underway to reclassify documents related to American foreign policy during the 1940's and 1950's, at the National Archives and Records Administration. The materials in question had all been unclassified during the Clinton administration.

From 1985 until 1998, the Fund for Peace, Inc. was the archive's fiscal sponsor. Among the Archive's more prominent institutional supporters today, are the Carnegie Corporation of New York, the Ford Foundation, the Freedom Forum, the John D. and Catherine T. MacArthur Foundation, Congressional Quarterly, and Cox Enterprises. The Archive recieves funding from these, and other, organizations via their donations to the National Security Archive Fund, established in order to administer the Archive's finances.

Strothra mentioned that he works with the organization so if he can find sources to make the claims about how the board is chosen, that would be great but they should be in Wikipedia's voice.--Tbeatty 03:28, 4 April 2006 (UTC)

 * I do not work with the organization or for it. I mentioned in another user's talk page that I have been involved with it and that is how I gained knowledge concerning it. I am not currently, however, and I do not always agree with it.  Please do not talk around me and do not stalk the comments I make on other users' talk pages.--Strothra 03:43, 4 April 2006 (UTC)

 * I wasn't talking around you. It is clearer to write in third person so that other readers know who I am talking about.  Especially in a new section that isn't a reply.  As for your 'stalking' comment, you inserted your information in the middle of a discussion I was a part of.  My point in this is that with your knowledge you could find sources that might be able to corroborate the scholarly nature of the board.  Please WP:AGF.

 * This little note was left for me on my talk page:
 * Please stop removing content from Wikipedia; it is considered vandalism. If you want to experiment, please use the sandbox. Thank you. The topic is currently being discussed and was in the process of being discussed when you removed the information. Your process of sidestepping discussion and going ahead with the delete is vandalism.
 * Retrieved from "http://en.wikipedia.org/wiki/User_talk:Mytwocents"

 * Sandbox....vandalism.... you cannot be serious.
 * Here is the change I made earlier:   http://en.wikipedia.org/w/index.php?title=National_Security_Archive&diff=46820991&oldid=46819406

 * With this note; cleaned up text, removed some POV language.
 * If a few words might be POV and the article stands without them, then remove them. No big production number, no histrionics, no need for arbitration, just do it.  End of story.

 * This is a good article, but the facts are laid out now, on the page. I think we can put it to bed, and move on to other articles.

 * Mytwocents 03:48, 4 April 2006 (UTC)

 * Yes I was serious because you ignored legitimate discussion over information which I have proven as factual. If you have counter proof which you seem not to have then you are in error.  You sidestepped legitimate discussion on the article and thus I warned you for vandalism--Strothra 03:55, 4 April 2006 (UTC)

 * Strothra, you assume bad faith, the issue is not proof, it's NPOV. We determine that by consensus. We can also be bold and make edits without fear. Accusing me of vandalism is just plain wrong. Any editor, can make an NPOV at any time. That's what I did.
 * Mytwocents 04:05, 4 April 2006 (UTC)

 * I do ask that you discuss edits which are being hotly debated as the fact that the discussion is integral to the entire Wiki project. Rather than engaging in the democratic process of Wikipedia and joining in the attempt to build a concensus you chose to ignore the debate and go about your own way.  Not only is this rude, it is contrary to Wikipedia.  I will, however, assume good faith in your edits and strike the warning.  Do not lecture me in consensus when you refuse to engage in the dicussion which leads to it.  That just doesn't make sense. Further, I am highly suspicious of whether or not you and Tbeatty are sockpuppets.  --Strothra 04:15, 4 April 2006 (UTC)

 * Well, my point is, if a couple of adjectives are a bone of contention, and the article can survive without them, then take them out, for the sake of NPOV. I think that will be the end result on this page. I will stay on the sidelines for awhile, and let this play itself out.
 * Cheers to all.
 * PPS, Nope, I'm me!
 * Just Mytwocents 04:20, 4 April 2006 (UTC)

 * Please do not alter the archive box when you make edits to the discussion page.--Strothra 04:00, 4 April 2006 (UTC)

 * We are not sock puppets. I have given you a template that would satisfy me and remove the POV terms as fact.  I have engaged in discussion more so that anyone else.  Please WP:AGF.  Nothing I have said disparages this organzation in any way.  I just want it presented neutrally and factually.  I understand your desire to include "independant" and "scholarly" but it is not encyclopedic for Wikipedia to stipulate this as fact.  I don't think it disparages the board in any way to remove scholarly.  It is not saying they are unscholarly.  Just as removing independant doesn't mean they are not independant.  It just means these are POV determinations that can reasonably disputed.  --Tbeatty 05:57, 4 April 2006 (UTC)

 * I am, of course, aware of that and agreed to the removal of the term scholarly. After the previous comments of Mytwocents I am more satisfied that you are not sock puppets.  Your timing in joining the article was suspicious as was the fact that you would argue a point and he would just make the edit.  I have never accused you of disparaging the organization.  I feel that you, however, see POV when POV does not exist and are trying to delete a word ("indepdenent") which describes the structure of the organization and is important to describing its inter-organizational operation and that disputing the POV nature of the term is unreasonable.  --Strothra 12:19, 4 April 2006 (UTC)

 * The very first page described them as left-wing. This was changed later, by another editor, to no adjective at all, for NPOV. This group is a liberal orginisation, funded by a who's who of left-wing supporters. It's not independant of the money supply.  The Archive is not going to bite the hand that feeds it, by digging up a lot of dirt on the Johnson, Carter and Clinton administrations. The bulk of it's focus is on  the Nixon-Reagan-Bush-Bush eras.

 * So, no adjective at all is the best NPOV solution. It doesn't slant the page left or right. It just leaves a simple description of the Archives history, what they do, and who funds them. This leaves the reader to decide the political bent.
 * Mytwocents

 * I wouldn't go so far as to call it out-right liberal although it is left-leaning in its approach to the interpretation of certain documents it's general push for openness is a noble cause and in line with the system of checks and balances which sometimes does not exist in foreign policy making.  I think that the focus of the article from this point on should be less about the structure of the organization, its supporters, etc. and on its mission of seeking government openess.  For this reason I will agree to the no adjective arguement.--Strothra 18:06, 4 April 2006 (UTC)


text:
Algorithms/Backtracking

Backtracking is a general algorithmic technique that considers searching every possible combination in order to solve an optimization problem. Backtracking is also known as depth-first search or branch and bound. By inserting more knowledge of the problem, the search tree can be pruned to avoid considering cases that don't look promising. While backtracking is useful for hard problems to which we do not know more efficient solutions, it is a poor solution for the everyday problems that other techniques are much better at solving.

However, dynamic programming and greedy algorithms can be thought of as optimizations to backtracking, so the general technique behind backtracking is useful for understanding these more advanced concepts. Learning and understanding backtracking techniques first provides a good stepping stone to these more advanced techniques because you won't have to learn several new concepts all at once.

This methodology is generic enough that it can be applied to most problems. However, even when taking care to improve a backtracking algorithm, it will probably still take exponential time rather than polynomial time. Additionally, exact time analysis of backtracking algorithms can be extremely difficult: instead, simpler upperbounds that may not be tight are given.

Longest Common Subsequence (exhaustive version)
The LCS problem is similar to what the Unix "diff" program does. The diff command in Unix takes two text files, A and B, as input and outputs the differences line-by-line from A and B. For example, diff can show you that lines missing from A have been added to B, and lines present in A have been removed from B. The goal is to get a list of additions and removals that could be used to transform A to B. An overly conservative solution to the problem would say that all lines from A were removed, and that all lines from B were added. While this would solve the problem in a crude sense, we are concerned with the minimal number of additions and removals to achieve a correct transformation. Consider how you may implement a solution to this problem yourself.

The LCS problem, instead of dealing with lines in text files, is concerned with finding common items between two different arrays. For example,

let a := array {"The", "great", "square", "has", "no", "corners"} let b := array {"The", "great", "image", "has", "no", "form"}

We want to find the longest subsequence possible of items that are found in both a and b in the same order. The LCS of a and b is

 * "The", "great", "has", "no"

Now consider two more sequences:

let c := array {1, 2, 4, 8, 16, 32} let d := array {1, 2, 3, 32, 8}

Here, there are two longest common subsequences of c and d:

 * 1, 2, 32; and
 * 1, 2, 8

Note that

 * 1, 2, 32, 8

is not a common subsequence, because it is only a valid subsequence of d and not c (because c has 8 before the 32). Thus, we can conclude that for some cases, solutions to the LCS problem are not unique. If we had more information about the sequences available we might prefer one subsequence to another: for example, if the sequences were lines of text in computer programs, we might choose the subsequences that would keep function definitions or paired comment delimiters intact (instead of choosing delimiters that were not paired in the syntax).

On the top level, our problem is to implement the following function

// lcs -- returns the longest common subsequence of a and b function lcs(array a, array b): array

which takes in two arrays as input and outputs the subsequence array.

How do you solve this problem? You could start by noticing that if the two sequences start with the same word, then the longest common subsequence always contains that word. You can automatically put that word on your list, and you would have just reduced the problem to finding the longest common subset of the rest of the two lists. Thus, the problem was made smaller, which is good because it shows progress was made.

But if the two lists do not begin with the same word, then one, or both, of the first element in a or the first element in b do not belong in the longest common subsequence. But yet, one of them might be. How do you determine which one, if any, to add?

The solution can be thought in terms of the back tracking methodology: Try it both ways and see! Either way, the two sub-problems are manipulating smaller lists, so you know that the recursion will eventually terminate. Whichever trial results in the longer common subsequence is the winner.

Instead of "throwing it away" by deleting the item from the array we use array slices. For example, the slice

 * a[1,..,5]

represents the elements

 * {a[1], a[2], a[3], a[4], a[5]}

of the array as an array itself. If your language doesn't support slices you'll have to pass beginning and/or ending indices along with the full array. Here, the slices are only of the form

 * a[1,..]

which, when using 0 as the index to the first element in the array, results in an array slice that doesn't have the 0th element. (Thus, a non-sliced version of this algorithm would only need to pass the beginning valid index around instead, and that value would have to be subtracted from the complete array's length to get the pseudo-slice's length.)

// lcs -- returns the longest common subsequence of a and b function lcs(array a, array b): array if a.length == 0 OR b.length == 0: // if we're at the end of either list, then the lcs is empty return new array {} else-if a[0] == b[0]: // if the start element is the same in both, then it is on the lcs, // so we just recurse on the remainder of both lists. return append(new array {a[0]}, lcs(a[1,..], b[1,..])) else ''// we don't know which list we should discard from. Try both ways,'' // pick whichever is better. let discard_a := lcs(a[1,..], b) let discard_b := lcs(a, b[1,..]) if discard_a.length > discard_b.length: let result := discard_a else let result := discard_b fi    return result fi end

Shortest Path Problem (exhaustive version)
To be improved as Dijkstra's algorithm in a later section.

Bounding Searches
If you've already found something "better" and you're on a branch that will never be as good as the one you already saw, you can terminate that branch early. (Example to use: sum of numbers beginning with 1 2, and then each number following is a sum of any of the numbers plus the last number. Show performance improvements.)

Constrained 3-Coloring
This problem doesn't have immediate self-similarity, so the problem first needs to be generalized. Methodology: If there's no self-similarity, try to generalize the problem until it has it.

Traveling Salesperson Problem
Here, backtracking is one of the best solutions known.

title: Algorithms/Backtracking


text:
List of Isle of Man Twenty20 International cricketers

This is a list of Manx Twenty20 International cricketers.

In April 2018, the ICC decided to grant full Twenty20 International (T20I) status to all its members. Therefore, all Twenty20 matches played between Isle of Man and other ICC members after 1 January 2019 will be eligible for T20I status.

This list comprises all members of the Isle of Man cricket team who have played at least one T20I match. It is initially arranged in the order in which each player won his first Twenty20 cap. Where more than one player won his first Twenty20 cap in the same match, those players are listed alphabetically by surname.

Isle of Man played their first match with T20I status on 21 August 2020 against Guernsey during a tour of Guernsey.

List of players

 * Statistics are correct as of 16 June 2024.


text:
Dickinson Post Office

The Dickinson Post Office in Dickinson, North Dakota, is a post office building that was built in 1916. It was expanded to the east in 1965–66. It was listed on the National Register of Historic Places in 1989 as U.S. Post Office-Dickinson.

It is built to be fireproof, with hollow tile walls which are faced in gray pressed Hebron brick, laid in American bond. Ohio sandstone is used for trim, and polished granite is used for the front steps and the grade course.

title: Dickinson Post Office


text:
Miss Earth BiH

The Miss Earth BiH (Bosne i Hercegovine) pageant is a national beauty pageant in Bosnia and Herzegovina and has been held since 2010. It is responsible for selecting the country's representative to Miss Earth, which is an annual international beauty pageant promoting environmental awareness.

2002-2009: Miss Bosne i Hercegovine
Bosnia and Herzegovina debuted in Miss Earth in 2002. It was acquired by a 1994 born franchise, Miss Bosne i Hercegovine. Miss Bosne i Hercegovine is also responsible in sending winners to Miss World pageant. The first ever titleholder of Miss Earth BiH is Dzejla Glavovic who subsequently won the Miss Earth crown in 2002. However, Džejla was the first Miss Earth pageant winner to be dethroned on May 28, 2003. Carousel Productions, the pageant organizer, cited her failure to fulfill her duties as the main reason for her unseating. First runner-up from Kenya, Winfred Omwakwe, took over the position of Miss Earth 2002.

2010-present: Miss Earth BiH
Metropola Media, a company based in Slovenia, acquired the franchise of Miss Earth in 2010. The franchise is headed by its current national director, Drago Gavranovic. Miss Earth BiH is responsible for sending a delegate in Miss Earth since 2010.

Titleholders
Declared as Winner
 * Color key

Ended as runner-up

Ended as one of the finalists or semifinalists

Ended as special awards winner

title: Miss Earth BiH


text:
Talk:Merburg

Bad translation
Someone tried to translate this article from the German version with google translate and it was an unreadable mess. I simplified and added links. Someone who actually knows German needs to do it. Editfromwithout (talk) 07:08, 11 July 2012 (UTC)

 * Rephrased and added a few details. GermanJoe (talk) 22:49, 28 November 2015 (UTC)

title: Talk:Merburg


text:
Hackås IF

Hackås IF is a sports club in Hackås, Sweden, established in 1935. The women's bandy team has played two seasons in the Swedish top division. The women's soccer team played four seasons in the Swedish top division between 1978 and 1981.

title: Hackås IF


text:
Lipoprotein-X

Lipoprotein-X (Lp-X) is an abnormal low density lipoprotein found in cholestasis.

Structure
Lipoprotein-X is a lamellar particle of 30 to 70 nm in diameter as revealed by electron microscopy. It is characterized by its high content of phospholipids (66% by weight) and unesterified cholesterol (22%), and its low content of protein (6%), cholesterol esters (3%), and triglycerides (3%). The protein component is dominated by albumin, located in the core, and by apolipoprotein C, located on the surface of the particle. Using zonal ultracentrifugation, lipoprotein-X can be divided into three distinct populations: Lp-X1, Lp-X2, and Lp-X3, differing in density and apolipoprotein composition.

Pathogenesis
The pathogenesis of lipoprotein-X in cholestasis is not totally resolved. Normally, the liver excretes lipoprotein complexes into the bile showing phospholipid and unesterified cholesterol concentrations similar to Lipoprotein-X. The in vitro incubation of these bile lipoproteins with serum or albumin leads to the appearance of Lp-X–like particles. These findings suggest that the reflux of bile into the plasma compartment causes the formation of lipoprotein-X in cholestasis as a result of a physicochemical, nonmetabolic process. On the other hand, lipoprotein-X particles found in familial LCAT deficiency are identical to those in cholestasis regarding ultrastructure and biochemical composition. It has been supposed that reduced LCAT activities, common in patients with hepatocellular disease, cause, alone or in combination with other factors, the formation of Lipoprotein-X in cholestasis. Lipoprotein-X is mainly removed by the reticuloendothelial system of the liver and the spleen, as shown by studies using radioactively labeled lipoprotein-X in rats. Other organs, such as the kidney, also actively clear Lipoprotein-X from the plasma.

title: Lipoprotein-X


text:
Quadric geometric algebra

Quadric geometric algebra (QGA) is a geometrical application of the $$\mathcal{G}_{6, 3}$$ geometric algebra. This algebra is also known as the $$\mathcal{C} \ell_{6, 3}$$ Clifford algebra. QGA is a super-algebra over $$\mathcal{G}_{4, 1}$$ conformal geometric algebra (CGA) and $$\mathcal{G}_{1, 3}$$ spacetime algebra (STA), which can each be defined within sub-algebras of QGA.

CGA provides representations of spherical entities (points, spheres, planes, and lines) and a complete set of operations (translation, rotation, dilation, and intersection) that apply to them. QGA extends CGA to also include representations of some non-spherical entities: principal axes-aligned quadric surfaces and many of their degenerate forms such as planes, lines, and points.

General quadric surfaces are characterized by the implicit polynomial equation of degree 2

A x^2 + B y^2 + C z^2 + D x y + E y z + F z x + G x + H y + I z + J = 0. $$

which can characterize quadric surfaces located at any center point and aligned along arbitrary axes. However, QGA includes vector entities that can represent only the principal axes-aligned quadric surfaces characterized by

A x^2 + B y^2 + C z^2 + G x + H y + I z + J = 0. $$

This is still a very significant advancement over CGA.

A possible performance issue with using QGA is the increased computation required to use a 9D vector space, as compared to the smaller 5D vector space of CGA. A 5D CGA subspace can be used when only CGA entities are involved in computations.

In general, the operation of rotation  does not work   correctly on non-spherical QGA quadric surface entities. Rotation also does not work correctly on the QGA point entities. Attempting to rotate a QGA quadric surface may result in a different type of quadric surface, or a quadric surface that is rotated and distorted in an unexpected way. Attempting to rotate a QGA point may produce a value that projects as the expected rotated vector, but the produced value is generally not a correct embedding of the rotated vector. The failure of QGA points to rotate correctly also leads to the inability to use outermorphisms to rotate dual Geometric Outer Product Null Space (GOPNS) entities. To rotate a QGA point, it must be projected to a vector or converted to a CGA point for rotation operations, then the rotated result can be re-embedded or converted back into a QGA point. A quadric surface rotated by an arbitrary angle cannot be represented by any known QGA entity. Representation of general quadric surfaces with useful operations will require an algebra (that appears to be unknown at this time) that extends QGA.

Although rotation is generally unavailable in QGA, the transposition operation is a special-case modification of rotation by $$\pi / 2$$ that works correctly on all QGA GIPNS entities. Transpositions allow QGA GIPNS entities to be reflected in the six diagonal planes $$y = \pm x$$, $$z = \pm x$$, and $$z = \pm y$$.

Entities for all principal axes-aligned quadric surfaces can be defined in QGA. These include ellipsoids, cylinders, cones, paraboloids, and hyperboloids in all of their various forms.

A powerful feature of QGA is the ability to compute the intersections of axes-aligned quadric surfaces. With few exceptions, the outer product of QGA GIPNS surface entities represents their surfaces intersection(s). This method of computing intersections works the same as it does in CGA, where only spherical entities are available.

title: Quadric geometric algebra


text:
Cala Iris Islet

Cala Iris Islet is a small island in Morocco, located in the Alboran Sea in the bay of the village, Al Hoceima Province. It is about 500 m off the Cala Iris beach. This island is a part of the Al Hoceima National Park. Cala Iris Islet is one of the few places where the ribbed Mediterranean limpet (Patella ferruginea) has survived, with a population of 110 specimens.

title: Cala Iris Islet


text:
User:Poker.Face.201212

Hello. I have no clue how this works so please forgive me for having absolutely nothing important about me or Wikipedia on here. To be honest I'm not even sure why I made an account here.........

title: User:Poker.Face.201212


text:
Ahmatjan Osman

Ahmatjan Osman (ئەخمەتجان ئوسمان; born 1964), also spelled Ekhmetjan, Exmetjan or Ahmetcan, is a Uyghur poet and Uyghur independence activist who writes in both Uyghur and Arabic. A leader of the Uyghur New Poetry (gungga) movement in the 1980s, he is considered one of the "foremost Uyghur poets of his generation". His use of free verse was influential in subsequent Uyghur poetics. His poetry has been described as trying to "capture the sacred and philosophical, the ineffable and the transient, in a wholly unique lyric voice".

Early life
He grew up in Ürümqi, the largest city in Xinjiang. His father Osman Bey, a coal mine manager, was imprisoned for six years during the Cultural Revolution for being "bourgeois capitalist". He spent years in and out of the hospital after his release and passed away from lung disease. His mother, Cemile Hanım, taught him Uyghur folk tales and took care of their family, which included Ahmatjan's two siblings. His father's death and his mother's singing folk poetry to him influenced his work. Ahmatjan started writing poetry when he was twelve or thirteen years old. His work was first "published" when three of his poems were read on air by a radio station in Ürümqi when he was thirteen. After going to a famous experimental high school in Ürümqi, he entered Xinjiang University's Faculty of Language and Literature in 1981. His first Uyghur-language poetry collection was published in 1982.

In 1982, he went to Syria to study Arabic literature at Damascus University. He completed bachelor's and master's degree in Arabic literature. He returned to Ürümqi in 1990. He also worked as a journalist and continued to write. He made a splash with his controversial essays on literary theory.

Exile
In 1994, he was arrested by the Chinese government for two months and then fled to Syria. While in Syria, he reoriented himself toward Arabic poetry and occasionally contributed to Radio Free Asia's Uyghur service. While in Syria, he married a Syrian Alawite woman.

In 2004, he was deported from Syria under pressure from the Chinese government. Upon learning of his expulsion, 270 figures from the world of Arab poetry (including renowned Syrian poet Adunis) signed a petition and staged a demonstration against the deportation order. The action was condemned by international Arabic newspapers in London and Lebanon. He left for Turkey, where he spent a few days, but again was deported due to Chinese government pressure. He finally received asylum in Canada, where he has been living since October 2004. There, he found work at a grocery store, a coffee factory, and as a forklift operator in a warehouse.

Activism
He served as the president of the East Turkistan Government-in-Exile from November 2015 to October 2018, when he was dismissed for violating the East Turkistan Government in Exile's Constitution.

Despite his involvement in the Uyghur independence movement, Ahmatjan doesn't write poems explicitly about politics; his poems don't claim a particular political ideology.

Influences
Early on while in Xinjiang, Ahmatjan was influenced by Uyghur folk poetry sung to him by his mother, Uyghur poets of the previous generation like Qurban Barat and Boghda Abddulla, classical Uyghur poets like the eighteenth-century Sufi poet Shah Meshrep, and what he could find in Uyghur-language translations: collections of Tang poetry and Lao Zi, the contemporary Misty Poets writing in Mandarin, early nineteenth-century English and Russian Romantic poetry, and the essays of Vissarion Belinsky, the critic who originated of Russian social realism in the 1840s. Later, he picked up modernists like Paul Celan, Stéphane Mallarmé, and Arthur Rimbaud.

Once in Damascus, he immersed himself in Arabic literature, reading influential poets like the Syrian Adunis. According to critic Andre Naffis-Sahely, Adunis seemed to have a significant effect on Ahmatjan's work: "many of Ahmatjan’s poems marry lyrical descriptions of the natural world with the human need to ask metaphysical questions" and he "seems to have adopted Adunis’s use of the qit’a (or fragment) as one of the primary vessels for his poetics, juxtaposing images to create a vortex of sights, sounds, and ideas that always circle back to raw emotion". In turn, Adunis was one of the earliest admirers of Ahmatjan's Arabic poetry.

The Uyghur New Poetry movement (gungga)
In the 1980s, Ahmatjan was one of the leaders of the Uyghur New Poetry movement, known as gungga (hazy, vague, or uncertain) in Uyghur. There were several strands of influences that affected this movement. Symbolism and surrealism had just arrived in Xinjiang, after a long period of isolation from the 1950s to the 1980s. The experience of political repression during that era also drove them to more indirect means of expression. The direct inspiration, however, came from the Misty Poets group of the late 1970s and early 1980s (gungga was a direct translation of menglong, "obscure", "misty", or "hazy" in Mandarin.) The movement absorbed "the vision and the aesthetic principles of that groundbreaking movement through the literary manifestations were necessarily different."

The gungga movement's works were in free verse, not the aruz or syllabic metrical forms then dominant in Uyghur poetry. They relied on metaphor, contrast, images and symbols, instead of more direct means of expression. Their titles didn't directly relate to the bodies of the poems. Ahmatjan's choice of subjects included home, nation, and longing.

He gained critical attention after his poem Hain Dağlar ("Treacherous Mountains") was published by the popular literary magazine Tangritagh, based in Ürümqi. After that, he published his poems regularly in the magazine, which became the center of the movement.

According to Ahmatjan and Ablikim Baqi, the editor of Tangritagh, gungga "demonstrated an opening out of traditional form and content, an art unfettered by any implicit message of 'social value', and offered a new vision of Uyghur poetry as attuned to the French symbolists Baudelaire and Mallarmé, the surrealists Breton and Aragon, as well as to Manichean scripture and the Sufi poets Shah Meshrep and Ali-Shir Nava'i." These views were a departure from Maoist ideas of art as "proletarian revolutionary utilitarianism", and closer to Western Modernism's focus on "psychologizing, subjective, sometimes surreal art."

The movement started a fierce debate around tradition and authenticity in Uyghur letters. Critics of the movement said gungga poets simply lacked the skill to compose classical Uyghur poetry, with its strict metrical forms. The school's adherents countered that experimentation was crucial to the vitality and relevance of Uyghur poetry.

The movement declined after Ahmatjan's immigration to Syria in 1994 and his subsequent reorientation toward Arabic poetry. However, it left a mark on contemporaries like Perhat Tursun and Tahir Hamut Izgil and the next generation of Uyghur poets, who continued to write in free verse.

Translations
He has translated the poems of Rumi, Octavio Paz, Paul Celan, Fernando Pessoa, and Adunis into Uyghur. His eight collections of poetry (six in Arabic and two in Uyghur) have been published in Syria and Xinjiang.

At times, Ahmatjan has composed Arabic and Uyghur versions of a poem simultaneously over a period of years.

Jeffrey Yang published a collection of translations of Ahmatjan's Arabic and Uyghur poetry in Uyghurland in 2015; it was the first collection of Uyghur poetry to be translated into English. The translation was long-listed for the PEN Award for Poetry in Translation. Ahmatjan's work has also been anthologized in The Heart of Strangers, a collection of exile literature edited by Andre Naffis-Sahely.

Poetry collections

 * Al-Suqût al-thânî (The Second Fall or The Second Stumble, Arabic), 1988
 * Lughz Al-a'araas (The Mystery of Weddings, Arabic), 1990
 * Uyghur Qizi Lerikisi (Ode to a Uyghur Girl or Uyghur Girl Lyric, Uyghur), 1992
 * Roh Pesli (Moroccan Soul or Moroccan Spirit), 1996
 * Al-wasiy Ala Al-thaat (Guardian of the Self ), 1997
 * Ka'an ( As Though ), 1998
 * Fiy Atlaar Somar Haythu Oqiym (In Ruins of Sumer Where I Reside, Arabic), 2003
 * Hissaty Min Al-layl (My Night Part or My Share of the Night, Arabic), 2007
 * Season of the Soul

Translations of Ahmatjan Osman's work

 * Uyghurland, the Farthest Exile, translated into English by Jeffrey Yang, 2015
 * ああ、ウイグルの大地 (Oh, Land of Uyghurs), translated into Japanese by Mukai Dice and Makoto Kawai, 2015

Anthologies including Ahmatjan Osman's poems

 * The Heart of Strangers, edited by Andre Naffis-Sahely, 2020

title: Ahmatjan Osman


text:
User:Lennyde

I`m a wikipedian since 2007 / celebrity photographer / Film maker - interested in music, film, history and art.

title: User:Lennyde


text:
Tangos & Tragédias

Tangos & Tragédias was a Brazilian comedy musical act created by the musicians and actors Hique Gomez and Nico Nicolaiewsky. The duo performed as characters, musicians from the fictional country of Sbórnia. Gomez played the role of Kraunus Sang (violin and vocal) and Nicolaiewsky played as Maestro Pletskaya (piano, accordion and vocal). They presented from 1984 until 2014, when Nicolaievsky died of acute leukemia.

History
Tangos & Tragédias was founded in 1984, in Porto Alegre. Since 1987, they presented at the Teatro São Pedro, during the summer season, in January.

The duo presented in several venues in Brazil, having also a Spanish language version off the show, presented in Buenos Aires (Argentina), Quito (Ecuador), Manizales (Colombia), Cádiz and Donostia-San Sebastián (Spain). They were chosen as the Audience's Choice in Portugal's 2003 International Theater Festival of Almada, and as Espetáculo de Honra, in 2004.

In December 2007 the duo released the DVD Tangos e Tragédias na Praça da Matriz, filmed in 2004, during an commemorative show of the act's 20th anniversary, gathering 20.000 people on Porto Alegre's Praça da Matriz (Matriz Square).

In January 2014, Tangos & Tragédias summer season at Teatro São Pedro was interrupted when Nicolaiewsky was diagnosed with acute leukemia. He was interned in a hospital on January 23, and died on 7 February 2014.

In other media
In 2013, Tangos e Tragédias starred an animated feature film, Até que a Sbórnia nos Separe, directed by Otto Guerra.

title: Tangos & Tragédias