text:
Propositional formula

In propositional logic, a propositional formula is a type of syntactic formula which is well formed. If the values of all variables in a propositional formula are given, it determines a unique truth value. A propositional formula may also be called a propositional expression, a sentence, or a sentential formula.

A propositional formula is constructed from simple propositions, such as "five is greater than three" or propositional variables such as p and q, using connectives or logical operators such as NOT, AND, OR, or IMPLIES; for example:

 * (p AND NOT q) IMPLIES (p OR q).

In mathematics, a propositional formula is often more briefly referred to as a "proposition", but, more precisely, a propositional formula is not a proposition but a formal expression that denotes a proposition, a formal object under discussion, just like an expression such as "x + y" is not a value, but denotes a value. In some contexts, maintaining the distinction may be of importance.

Propositions
For the purposes of the propositional calculus, propositions (utterances, sentences, assertions) are considered to be either simple or compound. Compound propositions are considered to be linked by sentential connectives, some of the most common of which are "AND", "OR", "IF ... THEN ...", "NEITHER ... NOR ...", "... IS EQUIVALENT TO ..." . The linking semicolon ";", and connective "BUT" are considered to be expressions of "AND". A sequence of discrete sentences are considered to be linked by "AND"s, and formal analysis applies a recursive "parenthesis rule" with respect to sequences of simple propositions (see more below about well-formed formulas).
 * For example: The assertion: "This cow is blue. That horse is orange but this horse here is purple." is actually a compound proposition linked by "AND"s: ( ("This cow is blue" AND "that horse is orange") AND "this horse here is purple" ).

Simple propositions are declarative in nature, that is, they make assertions about the condition or nature of a particular object of sensation e.g. "This cow is blue", "There's a coyote!" ("That coyote IS there, behind the rocks."). Thus the simple "primitive" assertions must be about specific objects or specific states of mind. Each must have at least a subject (an immediate object of thought or observation), a verb (in the active voice and present tense preferred), and perhaps an adjective or adverb. "Dog!" probably implies "I see a dog" but should be rejected as too ambiguous.

 * Example: "That purple dog is running", "This cow is blue", "Switch M31 is closed", "This cap is off", "Tomorrow is Friday".

For the purposes of the propositional calculus a compound proposition can usually be reworded into a series of simple sentences, although the result will probably sound stilted.

Relationship between propositional and predicate formulas
The predicate calculus goes a step further than the propositional calculus to an "analysis of the inner structure of propositions" It breaks a simple sentence down into two parts (i) its subject (the object (singular or plural) of discourse) and (ii) a predicate (a verb or possibly verb-clause that asserts a quality or attribute of the object(s)). The predicate calculus then generalizes the "subject|predicate" form (where | symbolizes concatenation (stringing together) of symbols) into a form with the following blank-subject structure " ___|predicate", and the predicate in turn generalized to all things with that property.

 * Example: "This blue pig has wings" becomes two sentences in the propositional calculus: "This pig has wings" AND "This pig is blue", whose internal structure is not considered. In contrast, in the predicate calculus, the first sentence breaks into "this pig" as the subject, and "has wings" as the predicate. Thus it asserts that object "this pig" is a member of the class (set, collection) of "winged things". The second sentence asserts that object "this pig" has an attribute "blue" and thus is a member of the class of "blue things". One might choose to write the two sentences connected with AND as:
 * p|W AND p|B

The generalization of "this pig" to a (potential) member of two classes "winged things" and "blue things" means that it has a truth-relationship with both of these classes. In other words, given a domain of discourse "winged things", p is either found to be a member of this domain or not. Thus there is a relationship W (wingedness) between p (pig) and { T, F }, W(p) evaluates to { T, F } where { T, F } is the set of the boolean values "true" and "false". Likewise for B (blueness) and p (pig) and { T, F }: B(p) evaluates to { T, F }. So one now can analyze the connected assertions "B(p) AND W(p)" for its overall truth-value, i.e.:
 * ( B(p) AND W(p) ) evaluates to { T, F }

In particular, simple sentences that employ notions of "all", "some", "a few", "one of", etc. called logical quantifiers are treated by the predicate calculus. Along with the new function symbolism "F(x)" two new symbols are introduced: ∀ (For all), and ∃ (There exists ..., At least one of ... exists, etc.). The predicate calculus, but not the propositional calculus, can establish the formal validity of the following statement:
 * "All blue pigs have wings but some pigs have no wings, hence some pigs are not blue".

Identity
Tarski asserts that the notion of IDENTITY (as distinguished from LOGICAL EQUIVALENCE) lies outside the propositional calculus; however, he notes that if a logic is to be of use for mathematics and the sciences it must contain a "theory" of IDENTITY. Some authors refer to "predicate logic with identity" to emphasize this extension. See more about this below.

An algebra of propositions, the propositional calculus
An algebra (and there are many different ones), loosely defined, is a method by which a collection of symbols called variables together with some other symbols such as parentheses and some sub-set of symbols such as *, +, ~, &, ∨, =, ≡, ∧, ￢ are manipulated within a system of rules. These symbols, and well-formed strings of them, are said to represent objects, but in a specific algebraic system these objects do not have meanings. Thus work inside the algebra becomes an exercise in obeying certain laws (rules) of the algebra's syntax (symbol-formation) rather than in semantics (meaning) of the symbols. The meanings are to be found outside the algebra.

For a well-formed sequence of symbols in the algebra —a formula— to have some usefulness outside the algebra the symbols are assigned meanings and eventually the variables are assigned values; then by a series of rules the formula is evaluated.

When the values are restricted to just two and applied to the notion of simple sentences (e.g. spoken utterances or written assertions) linked by propositional connectives this whole algebraic system of symbols and rules and evaluation-methods is usually called the propositional calculus or the sentential calculus.

While some of the familiar rules of arithmetic algebra continue to hold in the algebra of propositions (e.g. the commutative and associative laws for AND and OR), some do not (e.g. the distributive laws for AND, OR and NOT).

Usefulness of propositional formulas
Analysis: In deductive reasoning, philosophers, rhetoricians and mathematicians reduce arguments to formulas and then study them (usually with truth tables) for correctness (soundness). For example: Is the following argument sound?
 * "Given that consciousness is sufficient for an artificial intelligence and only conscious entities can pass the Turing test, before we can conclude that a robot is an artificial intelligence the robot must pass the Turing test."

Engineers analyze the logic circuits they have designed using synthesis techniques and then apply various reduction and minimization techniques to simplify their designs.

Synthesis: Engineers in particular synthesize propositional formulas (that eventually end up as circuits of symbols) from truth tables. For example, one might write down a truth table for how binary addition should behave given the addition of variables "b" and "a" and "carry_in" "ci", and the results "carry_out" "co" and "sum" Σ:
 * Example: in row 5, ( (b+a) + ci ) = ( (1+0) + 1 ) = the number "2". written as a binary number this is 102, where "co"=1 and Σ=0 as shown in the right-most columns.

Propositional variables
The simplest type of propositional formula is a propositional variable. Propositions that are simple (atomic), symbolic expressions are often denoted by variables named p, q, or P, Q, etc. A propositional variable is intended to represent an atomic proposition (assertion), such as "It is Saturday" = p (here the symbol = means " ... is assigned the variable named ...") or "I only go to the movies on Monday" = q.

Truth-value assignments, formula evaluations
Evaluation of a propositional formula begins with assignment of a truth value to each variable. Because each variable represents a simple sentence, the truth values are being applied to the "truth" or "falsity" of these simple sentences.

Truth values in rhetoric, philosophy and mathematics

The truth values are only two: { TRUTH "T", FALSITY "F" }. An empiricist puts all propositions into two broad classes: analytic—true no matter what (e.g. tautology), and synthetic—derived from experience and thereby susceptible to confirmation by third parties (the verification theory of meaning). Empiricits hold that, in general, to arrive at the truth-value of a synthetic proposition, meanings (pattern-matching templates) must first be applied to the words, and then these meaning-templates must be matched against whatever it is that is being asserted. For example, my utterance "That cow is !" Is this statement a TRUTH? Truly I said it. And maybe I am seeing a blue cow—unless I am lying my statement is a TRUTH relative to the object of my (perhaps flawed) perception. But is the blue cow "really there"? What do you see when you look out the same window? In order to proceed with a verification, you will need a prior notion (a template) of both "cow" and "", and an ability to match the templates against the object of sensation (if indeed there is one).

Truth values in engineering

Engineers try to avoid notions of truth and falsity that bedevil philosophers, but in the final analysis engineers must trust their measuring instruments. In their quest for robustness, engineers prefer to pull known objects from a small library—objects that have well-defined, predictable behaviors even in large combinations, (hence their name for the propositional calculus: "combinatorial logic"). The fewest behaviors of a single object are two (e.g. { OFF, ON }, { open, shut }, { UP, DOWN } etc.), and these are put in correspondence with { 0, 1 }. Such elements are called digital; those with a continuous range of behaviors are called analog. Whenever decisions must be made in an analog system, quite often an engineer will convert an analog behavior (the door is 45.32146% UP) to digital (e.g. DOWN=0 ) by use of a comparator.

Thus an assignment of meaning of the variables and the two value-symbols { 0, 1 } comes from "outside" the formula that represents the behavior of the (usually) compound object. An example is a garage door with two "limit switches", one for UP labelled SW_U and one for DOWN labelled SW_D, and whatever else is in the door's circuitry. Inspection of the circuit (either the diagram or the actual objects themselves—door, switches, wires, circuit board, etc.) might reveal that, on the circuit board "node 22" goes to +0 volts when the contacts of switch "SW_D" are mechanically in contact ("closed") and the door is in the "down" position (95% down), and "node 29" goes to +0 volts when the door is 95% UP and the contacts of switch SW_U are in mechanical contact ("closed"). The engineer must define the meanings of these voltages and all possible combinations (all 4 of them), including the "bad" ones (e.g. both nodes 22 and 29 at 0 volts, meaning that the door is open and closed at the same time). The circuit mindlessly responds to whatever voltages it experiences without any awareness of TRUTH or FALSEHOOD, RIGHT or WRONG, SAFE or DANGEROUS.

Propositional connectives
Arbitrary propositional formulas are built from propositional variables and other propositional formulas using propositional connectives. Examples of connectives include:
 * The unary negation connective. If $$\alpha$$ is a formula, then $$\lnot \alpha$$ is a formula.
 * The classical binary connectives $$\land, \lor, \to, \leftrightarrow$$. Thus, for example, if $$\alpha$$ and $$\beta$$ are formulas, so is $$(\alpha \to \beta)$$.
 * Other binary connectives, such as NAND, NOR, and XOR
 * The ternary connective IF ... THEN ... ELSE ...
 * Constant 0-ary connectives ⊤ and ⊥ (alternately, constants { T, F }, { 1, 0 } etc. )
 * The "theory-extension" connective EQUALS (alternately, IDENTITY, or the sign " = " as distinguished from the "logical connective" $$\leftrightarrow$$)

Connectives of rhetoric, philosophy and mathematics
The following are the connectives common to rhetoric, philosophy and mathematics together with their truth tables. The symbols used will vary from author to author and between fields of endeavor. In general the abbreviations "T" and "F" stand for the evaluations TRUTH and FALSITY applied to the variables in the propositional formula (e.g. the assertion: "That cow is blue" will have the truth-value "T" for Truth or "F" for Falsity, as the case may be.).

The connectives go by a number of different word-usages, e.g. "a IMPLIES b" is also said "IF a THEN b". Some of these are shown in the table.

Engineering connectives

In general, the engineering connectives are just the same as the mathematics connectives excepting they tend to evaluate with "1" = "T" and "0" = "F". This is done for the purposes of analysis/minimization and synthesis of formulas by use of the notion of minterms and Karnaugh maps (see below). Engineers also use the words logical product from Boole's notion (a*a = a) and logical sum from Jevons' notion (a+a = a).

CASE connective: IF ... THEN ... ELSE ...
The IF ... THEN ... ELSE ... connective appears as the simplest form of CASE operator of recursion theory and computation theory and is the connective responsible for conditional goto's (jumps, branches). From this one connective all other connectives can be constructed (see more below). Although " IF c THEN b ELSE a " sounds like an implication it is, in its most reduced form, a switch that makes a decision and offers as outcome only one of two alternatives "a" or "b" (hence the name switch statement in the C programming language).

The following three propositions are equivalent (as indicated by the logical equivalence sign ≡ ):

 * 1) ( IF 'counter is zero' THEN 'go to instruction b ' ELSE 'go to instruction a ') ≡
 * 2) ( (c → b) & (~c → a) ) ≡  ( ( IF 'counter is zero' THEN 'go to instruction b ' ) AND ( IF 'It is NOT the case that counter is zero' THEN 'go to instruction a ) "  ≡
 * 3) ( (c & b) ∨ (~c & a) ) ≡  " ( 'Counter is zero' AND 'go to instruction b ) OR ( 'It is NOT the case that 'counter is zero' AND 'go to instruction a ) "

Thus IF ... THEN ... ELSE—unlike implication—does not evaluate to an ambiguous "TRUTH" when the first proposition is false i.e. c = F in (c → b). For example, most people would reject the following compound proposition as a nonsensical non sequitur because the second sentence is not connected in meaning to the first.
 * Example: The proposition " IF 'Winston Churchill was Chinese' THEN 'The sun rises in the east' " evaluates as a TRUTH given that 'Winston Churchill was Chinese' is a FALSEHOOD and 'The sun rises in the east' evaluates as a TRUTH.

In recognition of this problem, the sign → of formal implication in the propositional calculus is called material implication to distinguish it from the everyday, intuitive implication.

The use of the IF ... THEN ... ELSE construction avoids controversy because it offers a completely deterministic choice between two stated alternatives; it offers two "objects" (the two alternatives b and a), and it selects between them exhaustively and unambiguously. In the truth table below, d1 is the formula: ( (IF c THEN b) AND (IF NOT-c THEN a) ). Its fully reduced form d2 is the formula: ( (c AND b) OR (NOT-c AND a). The two formulas are equivalent as shown by the columns "=d1" and "=d2". Electrical engineers call the fully reduced formula the AND-OR-SELECT operator. The CASE (or SWITCH) operator is an extension of the same idea to n possible, but mutually exclusive outcomes. Electrical engineers call the CASE operator a multiplexer.

IDENTITY and evaluation
The first table of this section stars *** the entry logical equivalence to note the fact that "Logical equivalence" is not the same thing as "identity". For example, most would agree that the assertion "That cow is blue" is identical to the assertion "That cow is blue". On the other hand, logical equivalence sometimes appears in speech as in this example: " 'The sun is shining' means 'I'm biking' " Translated into a propositional formula the words become: "IF 'the sun is shining' THEN 'I'm biking', AND IF 'I'm biking' THEN 'the sun is shining'":
 * "IF 's' THEN 'b' AND IF 'b' THEN 's' " is written as ((s → b) & (b → s)) or in an abbreviated form as (s ↔ b). As the rightmost symbol string is a definition for a new symbol in terms of the symbols on the left, the use of the IDENTITY sign = is appropriate:
 * ((s → b) & (b → s)) = (s ↔ b)

Different authors use different signs for logical equivalence: ↔ (e.g. Suppes, Goodstein, Hamilton), ≡ (e.g. Robbin), ⇔ (e.g. Bender and Williamson). Typically identity is written as the equals sign =. One exception to this rule is found in Principia Mathematica. For more about the philosophy of the notion of IDENTITY see Leibniz's law.

As noted above, Tarski considers IDENTITY to lie outside the propositional calculus, but he asserts that without the notion, "logic" is insufficient for mathematics and the deductive sciences. In fact the sign comes into the propositional calculus when a formula is to be evaluated.

In some systems there are no truth tables, but rather just formal axioms (e.g. strings of symbols from a set { ~, →,, variables p1, p2, p3, ... } and formula-formation rules (rules about how to make more symbol strings from previous strings by use of e.g. substitution and modus ponens). the result of such a calculus will be another formula (i.e. a well-formed symbol string). Eventually, however, if one wants to use the calculus to study notions of validity and truth, one must add axioms that define the behavior of the symbols called "the truth values" {T, F} ( or {1, 0}, etc.) relative to the other symbols.

For example, Hamilton uses two symbols = and ≠ when he defines the notion of a valuation v of any well-formed formulas (wffs) A and B in his "formal statement calculus" L. A valuation v is a function from the wffs of his system L to the range (output) { T, F }, given that each variable p1, p2, p3 in a wff is assigned an arbitrary truth value { T, F }.

The two definitions ($$) and ($$) define the equivalent of the truth tables for the ~ (NOT) and → (IMPLICATION) connectives of his system. The first one derives F ≠ T and T ≠ F, in other words " v(A) does not mean v(~A)". Definition ($$) specifies the third row in the truth table, and the other three rows then come from an application of definition ($$). In particular ($$) assigns the value F (or a meaning of "F") to the entire expression. The definitions also serve as formation rules that allow substitution of a value previously derived into a formula:

Some formal systems specify these valuation axioms at the outset in the form of certain formulas such as the law of contradiction or laws of identity and nullity. The choice of which ones to use, together with laws such as commutation and distribution, is up to the system's designer as long as the set of axioms is complete (i.e. sufficient to form and to evaluate any well-formed formula created in the system).

More complex formulas
As shown above, the CASE (IF c THEN b ELSE a ) connective is constructed either from the 2-argument connectives IF ... THEN ... and AND or from OR and AND and the 1-argument NOT. Connectives such as the n-argument AND (a & b & c & ... & n), OR (a ∨ b ∨ c ∨ ... ∨ n) are constructed from strings of two-argument AND and OR and written in abbreviated form without the parentheses. These, and other connectives as well, can then be used as building blocks for yet further connectives. Rhetoricians, philosophers, and mathematicians use truth tables and the various theorems to analyze and simplify their formulas.

Electrical engineering uses drawn symbols and connect them with lines that stand for the mathematicals act of substitution and replacement. They then verify their drawings with truth tables and simplify the expressions as shown below by use of Karnaugh maps or the theorems. In this way engineers have created a host of "combinatorial logic" (i.e. connectives without feedback) such as "decoders", "encoders", "mutifunction gates", "majority logic", "binary adders", "arithmetic logic units", etc.

Definitions
A definition creates a new symbol and its behavior, often for the purposes of abbreviation. Once the definition is presented, either form of the equivalent symbol or formula can be used. The following symbolism =Df is following the convention of Reichenbach. Some examples of convenient definitions drawn from the symbol set { ~, &, } and variables. Each definition is producing a logically equivalent formula that can be used for substitution or replacement.
 * definition of a new variable: (c & d) =Df s
 * OR: ~(~a & ~b) =Df (a ∨ b)
 * IMPLICATION: (~a ∨ b) =Df (a → b)
 * XOR: (~a & b) ∨ (a & ~b) =Df (a ⊕ b)
 * LOGICAL EQUIVALENCE: ( (a → b) & (b → a) ) =Df ( a ≡ b )

Axiom and definition schemas
The definitions above for OR, IMPLICATION, XOR, and logical equivalence are actually schemas (or "schemata"), that is, they are models (demonstrations, examples) for a general formula format but shown (for illustrative purposes) with specific letters a, b, c for the variables, whereas any variable letters can go in their places as long as the letter substitutions follow the rule of substitution below.
 * Example: In the definition (~a ∨ b) =Df (a → b), other variable-symbols such as "SW2" and "CON1" might be used, i.e. formally:
 * a =Df SW2, b =Df CON1, so we would have as an instance of the definition schema (~SW2 ∨ CON1) =Df (SW2 → CON1)

Substitution versus replacement
Substitution: The variable or sub-formula to be substituted with another variable, constant, or sub-formula must be replaced in all instances throughout the overall formula.
 * Example: (c & d) ∨ (p & ~(c & ~d)), but (q1 & ~q2) ≡ d. Now wherever variable "d" occurs, substitute (q1 & ~q2):
 * (c & (q1 & ~q2)) ∨ (p & ~(c & ~(q1 & ~q2)))

Replacement: (i) the formula to be replaced must be within a tautology, i.e. logically equivalent ( connected by ≡ or ↔) to the formula that replaces it, and (ii) unlike substitution its permissible for the replacement to occur only in one place (i.e. for one formula).
 * Example: Use this set of formula schemas/equivalences:
 * ( (a ∨ 0) ≡ a ).
 * ( (a & ~a) ≡ 0 ).
 * ( (~a ∨ b) =Df (a → b) ).
 * ( ~(~a) ≡ a )
 * 1. start with "a": a

2. Use 1 to replace "a" with (a ∨ 0): (a ∨ 0)

3. Use the notion of "schema" to substitute b for a in 2: ( (a & ~a) ≡ 0 )

4. Use 2 to replace 0 with (b & ~b): ( a ∨ (b & ~b) )

5. (see below for how to distribute "a ∨" over (b & ~b), etc.)

Inductive definition
The classical presentation of propositional logic (see Enderton 2002) uses the connectives $$\lnot, \land, \lor, \to, \leftrightarrow$$. The set of formulas over a given set of propositional variables is inductively defined to be the smallest set of expressions such that: This inductive definition can be easily extended to cover additional connectives.
 * Each propositional variable in the set is a formula,
 * $$(\lnot \alpha)$$ is a formula whenever $$\alpha$$ is, and
 * $$ (\alpha\,\Box\,\beta)$$ is a formula whenever $$\alpha$$ and $$\beta$$ are formulas and $$\Box$$ is one of the binary connectives $$\land, \lor, \to, \leftrightarrow$$.

The inductive definition can also be rephrased in terms of a closure operation (Enderton 2002). Let V denote a set of propositional variables and let XV denote the set of all strings from an alphabet including symbols in V, left and right parentheses, and all the logical connectives under consideration. Each logical connective corresponds to a formula building operation, a function from XXV to XXV: The set of formulas over V is defined to be the smallest subset of XXV containing V and closed under all the formula building operations.
 * Given a string z, the operation $$\mathcal{E}_\lnot(z)$$ returns $$(\lnot z)$$.
 * Given strings y and z, the operation $$\mathcal{E}_\land(y,z)$$ returns $$(y\land z)$$. There are similar operations $$\mathcal{E}_\lor$$, $$\mathcal{E}_\to$$, and $$\mathcal{E}_\leftrightarrow$$ corresponding to the other binary connectives.

Parsing formulas
The following "laws" of the propositional calculus are used to "reduce" complex formulas. The "laws" can be verified easily with truth tables. For each law, the principal (outermost) connective is associated with logical equivalence ≡ or identity =. A complete analysis of all 2n combinations of truth-values for its n distinct variables will result in a column of 1's (T's) underneath this connective. This finding makes each law, by definition, a tautology. And, for a given law, because its formula on the left and right are equivalent (or identical) they can be substituted for one another.
 * Example: The following truth table is De Morgan's law for the behavior of NOT over OR: ~(a ∨ b) ≡ (~a & ~b). To the left of the principal connective ≡ (yellow column labelled "taut") the formula ~(b ∨ a) evaluates to (1, 0, 0, 0) under the label "P". On the right of "taut" the formula (~(b) ∨ ~(a)) also evaluates to (1, 0, 0, 0) under the label "Q". As the two columns have equivalent evaluations, the logical equivalence ≡ under "taut" evaluates to (1, 1, 1, 1), i.e. P ≡ Q. Thus either formula can be substituted for the other if it appears in a larger formula.

Enterprising readers might challenge themselves to invent an "axiomatic system" that uses the symbols { ∨, &, ~,, variables a, b, c }, the formation rules specified above, and as few as possible of the laws listed below, and then derive as theorems the others as well as the truth-table valuations for ∨, &, and ~. One set attributed to Huntington (1904) (Suppes:204) uses eight of the laws defined below.

If used in an axiomatic system, the symbols 1 and 0 (or T and F) are considered to be well-formed formulas and thus obey all the same rules as the variables. Thus the laws listed below are actually axiom schemas, that is, they stand in place of an infinite number of instances. Thus ( x ∨ y ) ≡ ( y ∨ x ) might be used in one instance, ( p ∨ 0 ) ≡ ( 0 ∨ p ) and in another instance ( 1 ∨ q ) ≡ ( q ∨ 1 ), etc.

Connective seniority (symbol rank)
In general, to avoid confusion during analysis and evaluation of propositional formulas, one can make liberal use of parentheses. However, quite often authors leave them out. To parse a complicated formula one first needs to know the seniority, or rank, that each of the connectives (excepting *) has over the other connectives. To "well-form" a formula, start with the connective with the highest rank and add parentheses around its components, then move down in rank (paying close attention to the connective's scope over which it is working). From most- to least-senior, with the predicate signs ∀x and ∃x, the IDENTITY = and arithmetic signs added for completeness:
 * ≡: (LOGICAL EQUIVALENCE)
 * →: (IMPLICATION)
 * &: (AND)
 * ∨: (OR)
 * ~: (NOT)
 * ∀x: (FOR ALL x)
 * ∃x: (THERE EXISTS AN x)
 * =: (IDENTITY)
 * +: (arithmetic sum)
 * * : (arithmetic multiply)
 * ' : (s, arithmetic successor).

Thus the formula can be parsed—but because NOT does not obey the distributive law, the parentheses around the inner formula (~c & ~d) is mandatory:
 * Example: " d & c ∨ w " rewritten is ( (d & c) ∨ w )
 * Example: " a & a → b ≡ a & ~a ∨ b " rewritten (rigorously) is
 * ≡ has seniority: ( ( a & a → b ) ≡ ( a & ~a ∨ b ) )
 * → has seniority: ( ( a & (a → b) ) ≡ ( a & ~a ∨ b ) )
 * & has seniority both sides: ( ( ( (a) & (a → b) ) ) ≡ ( ( (a) & (~a ∨ b) ) )
 * ~ has seniority: ( ( ( (a) & (a → b) ) ) ≡ ( ( (a) & (~(a) ∨ b) ) )
 * check 9 ( -parenthesis and 9 ) -parenthesis: ( ( ( (a) & (a → b) ) ) ≡ ( ( (a) & (~(a) ∨ b) ) )
 * Example:
 * d & c ∨ p & ~(c & ~d) ≡ c & d ∨ p & c ∨ p & ~d rewritten is ( ( (d & c) ∨ ( p & ~((c & ~(d)) ) ) ) ≡ ( (c & d) ∨ (p & c) ∨ (p & ~(d)) ) )

Commutative and associative laws
Both AND and OR obey the commutative law and associative law:
 * Commutative law for OR: ( a ∨ b ) ≡ ( b ∨ a )
 * Commutative law for AND: ( a & b ) ≡ ( b & a )
 * Associative law for OR: (( a ∨ b ) ∨ c ) ≡ ( a ∨ (b ∨ c) )
 * Associative law for AND: (( a & b ) & c ) ≡ ( a & (b & c) )

Omitting parentheses in strings of AND and OR: The connectives are considered to be unary (one-variable, e.g. NOT) and binary (i.e. two-variable AND, OR, IMPLIES). For example:
 * ( (c & d) ∨ (p & c) ∨ (p & ~d) ) above should be written ( ((c & d) ∨ (p & c)) ∨ (p & ~(d) ) ) or possibly ( (c & d) ∨ ( (p & c) ∨ (p & ~(d)) ) )

However, a truth-table demonstration shows that the form without the extra parentheses is perfectly adequate.

Omitting parentheses with regards to a single-variable NOT: While ~(a) where a is a single variable is perfectly clear, ~a is adequate and is the usual way this literal would appear. When the NOT is over a formula with more than one symbol, then the parentheses are mandatory, e.g. ~(a ∨ b).

Distributive laws
OR distributes over AND and AND distributes over OR. NOT does not distribute over AND or OR. See below about De Morgan's law:
 * Distributive law for OR: ( c ∨ ( a & b) ) ≡ ( (c ∨ a) & (c ∨ b) )
 * Distributive law for AND: ( c & ( a ∨ b) ) ≡ ( (c & a) ∨ (c & b) )

De Morgan's laws
NOT, when distributed over OR or AND, does something peculiar (again, these can be verified with a truth-table):
 * De Morgan's law for OR: ¬(a ∨ b) ≡ (¬a ^ ¬b)
 * De Morgan's law for AND: ¬(a ^ b) ≡ (¬a ∨ ¬b)

Laws of absorption
Absorption, in particular the first one, causes the "laws" of logic to differ from the "laws" of arithmetic:
 * Absorption (idempotency) for OR: (a ∨ a) ≡ a
 * Absorption (idempotency) for AND: (a & a) ≡ a

Laws of evaluation: Identity, nullity, and complement
The sign " = " (as distinguished from logical equivalence ≡, alternately ↔ or ⇔) symbolizes the assignment of value or meaning. Thus the string (a & ~(a)) symbolizes "0", i.e. it means the same thing as symbol "0" ". In some "systems" this will be an axiom (definition) perhaps shown as ( (a & ~(a)) =Df 0 ); in other systems, it may be derived in the truth table below:

 * Commutation of equality: (a = b) ≡ (b = a)
 * Identity for OR: (a ∨ 0) = a or (a ∨ F) = a
 * Identity for AND: (a & 1) = a or (a & T) = a
 * Nullity for OR: (a ∨ 1) = 1 or (a ∨ T) = T
 * Nullity for AND: (a & 0) = 0 or (a & F) = F
 * Complement for OR: (a ∨ ~a) = 1 or (a ∨ ~a) = T, law of excluded middle
 * Complement for AND: (a & ~a) = 0 or (a & ~a) = F, law of contradiction

Double negative (involution)

 * ¬(¬a) ≡ a

Well-formed formulas (wffs)
A key property of formulas is that they can be uniquely parsed to determine the structure of the formula in terms of its propositional variables and logical connectives. When formulas are written in infix notation, as above, unique readability is ensured through an appropriate use of parentheses in the definition of formulas. Alternatively, formulas can be written in Polish notation or reverse Polish notation, eliminating the need for parentheses altogether.

The inductive definition of infix formulas in the previous section can be converted to a formal grammar in Backus-Naur form:

It can be shown that any expression matched by the grammar has a balanced number of left and right parentheses, and any nonempty initial segment of a formula has more left than right parentheses. This fact can be used to give an algorithm for parsing formulas. For example, suppose that an expression x begins with $$( \lnot$$. Starting after the second symbol, match the shortest subexpression y of x that has balanced parentheses. If x is a formula, there is exactly one symbol left after this expression, this symbol is a closing parenthesis, and y itself is a formula. This idea can be used to generate a recursive descent parser for formulas.

Example of parenthesis counting:

This method locates as "1" the principal connective the connective under which the overall evaluation of the formula occurs for the outer-most parentheses (which are often omitted). It also locates the inner-most connective where one would begin evaluatation of the formula without the use of a truth table, e.g. at "level 6".

Well-formed formulas versus valid formulas in inferences
The notion of valid argument is usually applied to inferences in arguments, but arguments reduce to propositional formulas and can be evaluated the same as any other propositional formula. Here a valid inference means: "The formula that represents the inference evaluates to "truth" beneath its principal connective, no matter what truth-values are assigned to its variables", i.e. the formula is a tautology. Quite possibly a formula will be well-formed but not valid. Another way of saying this is: "Being well-formed is necessary for a formula to be valid but it is not sufficient." The only way to find out if it is both well-formed and valid is to submit it to verification with a truth table or by use of the "laws":

 * Example 1: What does one make of the following difficult-to-follow assertion? Is it valid? "If it's sunny, but if the frog is croaking then it's not sunny, then it's the same as saying that the frog isn't croaking." Convert this to a propositional formula as follows:
 * " IF (a AND (IF b THEN NOT-a) THEN NOT-a" where " a " represents "its sunny" and " b " represents "the frog is croaking":
 * ( ( (a) & ( (b) → ~(a) ) ≡ ~(b) )
 * This is well-formed, but is it valid? In other words, when evaluated will this yield a tautology (all T) beneath the logical-equivalence symbol ≡ ? The answer is NO, it is not valid. However, if reconstructed as an implication then the argument is valid.
 * "Saying it's sunny, but if the frog is croaking then it's not sunny, implies that the frog isn't croaking."
 * Other circumstances may be preventing the frog from croaking: perhaps a crane ate it.
 * Example 2 (from Reichenbach via Bertrand Russell):
 * "If pigs have wings, some winged animals are good to eat. Some winged animals are good to eat, so pigs have wings."
 * ( ((a) → (b)) & (b) → (a) ) is well formed, but an invalid argument as shown by the red evaluation under the principal implication:

Reduced sets of connectives

A set of logical connectives is called complete if every propositional formula is tautologically equivalent to a formula with just the connectives in that set. There are many complete sets of connectives, including $$\{\land, \lnot\}$$, $$\{\lor, \lnot\}$$, and $$\{\to, \lnot\}$$. There are two binary connectives that are complete on their own, corresponding to NAND and NOR, respectively. Some pairs are not complete, for example $$\{\land, \lor\}$$.

The stroke (NAND)
The binary connective corresponding to NAND is called the Sheffer stroke, and written with a vertical bar | or vertical arrow ↑. The completeness of this connective was noted in Principia Mathematica (1927:xvii). Since it is complete on its own, all other connectives can be expressed using only the stroke. For example, where the symbol " ≡ " represents logical equivalence:
 * ~p ≡ p|p
 * p → q ≡ p|~q
 * p ∨ q ≡ ~p|~q
 * p & q ≡ ~(p|q)

In particular, the zero-ary connectives $$\top$$ (representing truth) and $$\bot$$ (representing falsity) can be expressed using the stroke:
 * $$\top \equiv (a|(a|a))$$
 * $$\bot \equiv (\top | \top)$$

IF ... THEN ... ELSE
This connective together with { 0, 1 }, ( or { F, T } or { $$\bot$$, $$\top$$ } ) forms a complete set. In the following the IF...THEN...ELSE relation (c, b, a) = d represents ( (c → b) ∨ (~c → a) ) ≡ ( (c & b) ∨ (~c & a) ) = d
 * (c, b, a):
 * (c, 0, 1) ≡ ~c
 * (c, b, 1) ≡ (c → b)
 * (c, c, a) ≡ (c ∨ a)
 * (c, b, c) ≡ (c & b)

Example: The following shows how a theorem-based proof of "(c, b, 1) ≡ (c → b)" would proceed, below the proof is its truth-table verification. ( Note: (c → b) is defined to be (~c ∨ b) ):
 * Begin with the reduced form: ( (c & b) ∨ (~c & a) )
 * Substitute "1" for a: ( (c & b) ∨ (~c & 1) )
 * Identity (~c & 1) = ~c: ( (c & b) ∨ (~c) )
 * Law of commutation for V: ( (~c) ∨ (c & b)  )
 * Distribute "~c V" over (c & b): ( ((~c) ∨ c ) & ((~c) ∨ b )
 * Law of excluded middle (((~c) ∨ c ) = 1 ): ( (1) & ((~c) ∨ b ) )
 * Distribute "(1) &" over ((~c) ∨ b): ( ((1) & (~c)) ∨ ((1) & b )) )
 * Commutivity and Identity (( 1 & ~c) = (~c & 1) = ~c, and (( 1 & b) ≡ (b & 1) ≡ b: ( ~c ∨ b )
 * ( ~c ∨ b ) is defined as c → b Q. E. D.

In the following truth table the column labelled "taut" for tautology evaluates logical equivalence (symbolized here by ≡) between the two columns labelled d. Because all four rows under "taut" are 1's, the equivalence indeed represents a tautology.

Normal forms
An arbitrary propositional formula may have a very complicated structure. It is often convenient to work with formulas that have simpler forms, known as normal forms. Some common normal forms include conjunctive normal form and disjunctive normal form. Any propositional formula can be reduced to its conjunctive or disjunctive normal form.

Reduction to normal form

Reduction to normal form is relatively simple once a truth table for the formula is prepared. But further attempts to minimize the number of literals (see below) requires some tools: reduction by De Morgan's laws and truth tables can be unwieldy, but Karnaugh maps are very suitable a small number of variables (5 or less). Some sophisticated tabular methods exist for more complex circuits with multiple outputs but these are beyond the scope of this article; for more see Quine–McCluskey algorithm.

Literal, term and alterm
In electrical engineering, a variable x or its negation ~(x) can be referred to as a literal. A string of literals connected by ANDs is called a term. A string of literals connected by OR is called an alterm. Typically the literal ~(x) is abbreviated ~x. Sometimes the &-symbol is omitted altogether in the manner of algebraic multiplication.

 * Examples
 * a, b, c, d are variables. ((( a & ~(b) ) & ~(c)) & d) is a term. This can be abbreviated as (a & ~b & ~c & d), or a~b~cd.
 * p, q, r, s are variables. (((p ∨ ~(q) ) ∨ r) ∨ ~(s) ) is an alterm. This can be abbreviated as (p ∨ ~q ∨ r ∨ ~s).

Minterms
In the same way that a 2n-row truth table displays the evaluation of a propositional formula for all 2n possible values of its variables, n variables produces a 2n-square Karnaugh map (even though we cannot draw it in its full-dimensional realization). For example, 3 variables produces 23 = 8 rows and 8 Karnaugh squares; 4 variables produces 16 truth-table rows and 16 squares and therefore 16 minterms. Each Karnaugh-map square and its corresponding truth-table evaluation represents one minterm.

Any propositional formula can be reduced to the "logical sum" (OR) of the active (i.e. "1"- or "T"-valued) minterms. When in this form the formula is said to be in disjunctive normal form. But even though it is in this form, it is not necessarily minimized with respect to either the number of terms or the number of literals.

In the following table, observe the peculiar numbering of the rows: (0, 1, 3, 2, 6, 7, 5, 4, 0). The first column is the decimal equivalent of the binary equivalent of the digits "cba", in other words:
 * Example
 * cba2 = c*22 + b*21 + a*20:
 * cba = (c=1, b=0, a=1) = 1012 = 1*22 + 0*21 + 1*20 = 510

This numbering comes about because as one moves down the table from row to row only one variable at a time changes its value. Gray code is derived from this notion. This notion can be extended to three and four-dimensional hypercubes called Hasse diagrams where each corner's variables change only one at a time as one moves around the edges of the cube. Hasse diagrams (hypercubes) flattened into two dimensions are either Veitch diagrams or Karnaugh maps (these are virtually the same thing).

When working with Karnaugh maps one must always keep in mind that the top edge "wrap arounds" to the bottom edge, and the left edge wraps around to the right edge—the Karnaugh diagram is really a three- or four- or n-dimensional flattened object.

Reduction by use of the map method (Veitch, Karnaugh)
Veitch improved the notion of Venn diagrams by converting the circles to abutting squares, and Karnaugh simplified the Veitch diagram by converting the minterms, written in their literal-form (e.g. ~abc~d) into numbers. The method proceeds as follows:

Produce the formula's truth table
Produce the formula's truth table. Number its rows using the binary-equivalents of the variables (usually just sequentially 0 through n-1) for n variables.

 * Technically, the propositional function has been reduced to its (unminimized) conjunctive normal form: each row has its minterm expression and these can be OR'd to produce the formula in its (unminimized) conjunctive normal form.

Example: ((c & d) ∨ (p & ~(c & (~d)))) = q in conjunctive normal form is:
 * ( (~p & d & c ) ∨ (p & d & c) ∨ (p & d & ~c) ∨ (p & ~d & ~c) ) = q

However, this formula be reduced both in the number of terms (from 4 to 3) and in the total count of its literals (12 to 6).

Create the formula's Karnaugh map

Use the values of the formula (e.g. "p") found by the truth-table method and place them in their into their respective (associated) Karnaugh squares (these are numbered per the Gray code convention). If values of "d" for "don't care" appear in the table, this adds flexibility during the reduction phase.

Reduce minterms
Minterms of adjacent (abutting) 1-squares (T-squares) can be reduced with respect to the number of their literals, and the number terms also will be reduced in the process. Two abutting squares (2 x 1 horizontal or 1 x 2 vertical, even the edges represent abutting squares) lose one literal, four squares in a 4 x 1 rectangle (horizontal or vertical) or 2 x 2 square (even the four corners represent abutting squares) lose two literals, eight squares in a rectangle lose 3 literals, etc. (One seeks out the largest square or rectangles and ignores the smaller squares or rectangles contained totally within it. ) This process continues until all abutting squares are accounted for, at which point the propositional formula is minimized.

For example, squares #3 and #7 abut. These two abutting squares can lose one literal (e.g. "p" from squares #3 and #7), four squares in a rectangle or square lose two literals, eight squares in a rectangle lose 3 literals, etc. (One seeks out the largest square or rectangles.) This process continues until all abutting squares are accounted for, at which point the propositional formula is said to be minimized.

Example: The map method usually is done by inspection. The following example expands the algebraic method to show the "trick" behind the combining of terms on a Karnaugh map:
 * Minterms #3 and #7 abut, #7 and #6 abut, and #4 and #6 abut (because the table's edges wrap around). So each of these pairs can be reduced.

Observe that by the Idempotency law (A ∨ A) = A, we can create more terms. Then by association and distributive laws the variables to disappear can be paired, and then "disappeared" with the Law of contradiction (x & ~x)=0. The following uses brackets [ and ] only to keep track of the terms; they have no special significance:
 * Put the formula in conjunctive normal form with the formula to be reduced:
 * q = ( (~p & d & c ) ∨ (p & d & c) ∨ (p & d & ~c) ∨ (p & ~d & ~c) ) = ( #3 ∨ #7 ∨ #6 ∨ #4 )

 * Idempotency (absorption) [ A ∨ A) = A:
 * ( #3 ∨ [ #7 ∨ #7 ] ∨ [ #6 ∨ #6 ] ∨ #4 )

 * Associative law (x ∨ (y ∨ z)) = ( (x ∨ y) ∨ z )
 * ( [ #3 ∨ #7 ] ∨ [ #7 ∨ #6 ] ∨ [ #6 ∨ #4] )
 * [ (~p & d & c ) ∨ (p & d & c) ] ∨ [ (p & d & c) ∨ (p & d & ~c) ] ∨ [ (p & d & ~c) ∨ (p & ~d & ~c) ].

 * Distributive law ( x & (y ∨ z) ) = ( (x & y) ∨ (x & z) ) :
 * ( [ (d & c) ∨ (~p & p) ] ∨ [ (p & d) ∨ (~c & c) ] ∨ [ (p & ~c) ∨ (c & ~c) ] )

 * Commutative law and law of contradiction (x & ~x) = (~x & x) = 0:
 * ( [ (d & c) ∨ (0) ] ∨ [ (p & d) ∨ (0) ] ∨ [ (p & ~c) ∨ (0) ] )

 * Law of identity ( x ∨ 0 ) = x leading to the reduced form of the formula:
 * q = ( (d & c) ∨ (p & d) ∨ (p & ~c) )

Impredicative propositions
Given the following examples-as-definitions, what does one make of the subsequent reasoning:
 * (1) "This sentence is simple." (2) "This sentence is complex, and it is conjoined by AND."

Then assign the variable "s" to the left-most sentence "This sentence is simple". Define "compound" c = "not simple" ~s, and assign c = ~s to "This sentence is compound"; assign "j" to "It [this sentence] is conjoined by AND". The second sentence can be expressed as:
 * ( NOT(s) AND j )

If truth values are to be placed on the sentences c = ~s and j, then all are clearly FALSEHOODS: e.g. "This sentence is complex" is a FALSEHOOD (it is simple, by definition). So their conjunction (AND) is a falsehood. But when taken in its assembled form, the sentence a TRUTH.

This is an example of the paradoxes that result from an impredicative definition—that is, when an object m has a property P, but the object m is defined in terms of property P. The best advice for a rhetorician or one involved in deductive analysis is avoid impredicative definitions but at the same time be on the lookout for them because they can indeed create paradoxes. Engineers, on the other hand, put them to work in the form of propositional formulas with feedback.

Propositional formula with "feedback"
The notion of a propositional formula appearing as one of its own variables requires a formation rule that allows the assignment of the formula to a variable. In general there is no stipulation (either axiomatic or truth-table systems of objects and relations) that forbids this from happening.

The simplest case occurs when an OR formula becomes one its own inputs e.g. p = q. Begin with (p ∨ s) = q, then let p = q. Observe that q's "definition" depends on itself "q" as well as on "s" and the OR connective; this definition of q is thus impredicative. Either of two conditions can result: oscillation or memory.

It helps to think of the formula as a black box. Without knowledge of what is going on "inside" the formula-"box" from the outside it would appear that the output is no longer a function of the inputs alone. That is, sometimes one looks at q and sees 0 and other times 1. To avoid this problem one has to know the state (condition) of the "hidden" variable p inside the box (i.e. the value of q fed back and assigned to p). When this is known the apparent inconsistency goes away.

To understand [predict] the behavior of formulas with feedback requires the more sophisticated analysis of sequential circuits. Propositional formulas with feedback lead, in their simplest form, to state machines; they also lead to memories in the form of Turing tapes and counter-machine counters. From combinations of these elements one can build any sort of bounded computational model (e.g. Turing machines, counter machines, register machines, Macintosh computers, etc.).

Oscillation
In the abstract (ideal) case the simplest oscillating formula is a NOT fed back to itself: ~(~(p=q)) = q. Analysis of an abstract (ideal) propositional formula in a truth-table reveals an inconsistency for both p=1 and p=0 cases: When p=1, q=0, this cannot be because p=q; ditto for when p=0 and q=1.

Oscillation with delay: If a delay (ideal or non-ideal) is inserted in the abstract formula between p and q then p will oscillate between 1 and 0: 101010...101... ad infinitum. If either of the delay and NOT are not abstract (i.e. not ideal), the type of analysis to be used will be dependent upon the exact nature of the objects that make up the oscillator; such things fall outside mathematics and into engineering.

Analysis requires a delay to be inserted and then the loop cut between the delay and the input "p". The delay must be viewed as a kind of proposition that has "qd" (q-delayed) as output for "q" as input. This new proposition adds another column to the truth table. The inconsistency is now between "qd" and "p" as shown in red; two stable states resulting:

Memory

Without delay, inconsistencies must be eliminated from a truth table analysis. With the notion of "delay", this condition presents itself as a momentary inconsistency between the fed-back output variable q and p = qdelayed.

A truth table reveals the rows where inconsistencies occur between p = qdelayed at the input and q at the output. After "breaking" the feed-back, the truth table construction proceeds in the conventional manner. But afterwards, in every row the output q is compared to the now-independent input p and any inconsistencies between p and q are noted (i.e. p=0 together with q=1, or p=1 and q=0); when the "line" is "remade" both are rendered impossible by the Law of contradiction ~(p & ~p)). Rows revealing inconsistencies are either considered transient states or just eliminated as inconsistent and hence "impossible".

Once-flip memory
About the simplest memory results when the output of an OR feeds back to one of its inputs, in this case output "q" feeds back into "p". Given that the formula is first evaluated (initialized) with p=0 & q=0, it will "flip" once when "set" by s=1. Thereafter, output "q" will sustain "q" in the "flipped" condition (state q=1). This behavior, now time-dependent, is shown by the state diagram to the right of the once-flip.

Flip-flop memory
The next simplest case is the "set-reset" flip-flop shown below the once-flip. Given that r=0 & s=0 and q=0 at the outset, it is "set" (s=1) in a manner similar to the once-flip. It however has a provision to "reset" q=0 when "r"=1. And additional complication occurs if both set=1 and reset=1. In this formula, the set=1 forces the output q=1 so when and if (s=0 & r=1) the flip-flop will be reset. Or, if (s=1 & r=0) the flip-flop will be set. In the abstract (ideal) instance in which s=1 ⇒ s=0 & r=1 ⇒ r=0 simultaneously, the formula q will be indeterminate (undecidable). Due to delays in "real" OR, AND and NOT the result will be unknown at the outset but thereafter predicable.

Clocked flip-flop memory
The formula known as "clocked flip-flop" memory ("c" is the "clock" and "d" is the "data") is given below. It works as follows: When c = 0 the data d (either 0 or 1) cannot "get through" to affect output q. When c = 1 the data d "gets through" and output q "follows" d's value. When c goes from 1 to 0 the last value of the data remains "trapped" at output "q". As long as c=0, d can change value without causing q to change.

 * Examples
 * ( ( c & d ) ∨ ( p & ( ~( c & ~( d ) ) ) ) = q, but now let p = q:
 * ( ( c & d ) ∨ ( q & ( ~( c & ~( d ) ) ) ) = q

The state diagram is similar in shape to the flip-flop's state diagram, but with different labelling on the transitions.

Historical development
Bertrand Russell (1912:74) lists three laws of thought that derive from Aristotle: (1) The law of identity: "Whatever is, is.", (2) The law of noncontradiction: "Nothing can both be and not be", and (3) The law of excluded middle: "Everything must be or not be."
 * Example: Here O is an expression about an object's BEING or QUALITY:
 * Law of Identity: O = O
 * Law of contradiction: ~(O & ~(O))
 * Law of excluded middle: (O ∨ ~(O))

The use of the word "everything" in the law of excluded middle renders Russell's expression of this law open to debate. If restricted to an expression about BEING or QUALITY with reference to a finite collection of objects (a finite "universe of discourse") -- the members of which can be investigated one after another for the presence or absence of the assertion—then the law is considered intuitionistically appropriate. Thus an assertion such as: "This object must either BE or NOT BE (in the collection)", or "This object must either have this QUALITY or NOT have this QUALITY (relative to the objects in the collection)" is acceptable. See more at Venn diagram.

Although a propositional calculus originated with Aristotle, the notion of an algebra applied to propositions had to wait until the early 19th century. In an (adverse) reaction to the 2000 year tradition of Aristotle's syllogisms, John Locke's Essay concerning human understanding (1690) used the word semiotics (theory of the use of symbols). By 1826 Richard Whately had critically analyzed the syllogistic logic with a sympathy toward Locke's semiotics. George Bentham's work (1827) resulted in the notion of "quantification of the predicate" (1827) (nowadays symbolized as ∀ ≡ "for all"). A "row" instigated by William Hamilton over a priority dispute with Augustus De Morgan "inspired George Boole to write up his ideas on logic, and to publish them as MAL [Mathematical Analysis of Logic] in 1847" (Grattin-Guinness and Bornet 1997:xxviii).

About his contribution Grattin-Guinness and Bornet comment:
 * "Boole's principal single innovation was [the] law [ xn = x ] for logic: it stated that the mental acts of choosing the property x and choosing x again and again is the same as choosing x once... As consequence of it he formed the equations x•(1-x)=0 and x+(1-x)=1 which for him expressed respectively the law of contradiction and the law of excluded middle" (p. xxviiff). For Boole "1" was the universe of discourse and "0" was nothing.

Gottlob Frege's massive undertaking (1879) resulted in a formal calculus of propositions, but his symbolism is so daunting that it had little influence excepting on one person: Bertrand Russell. First as the student of Alfred North Whitehead he studied Frege's work and suggested a (famous and notorious) emendation with respect to it (1904) around the problem of an antinomy that he discovered in Frege's treatment ( cf Russell's paradox ). Russell's work led to a collaboration with Whitehead that, in the year 1912, produced the first volume of Principia Mathematica (PM). It is here that what we consider "modern" propositional logic first appeared. In particular, PM introduces NOT and OR and the assertion symbol ⊦ as primitives. In terms of these notions they define IMPLICATION → ( def. *1.01: ~p ∨ q ), then AND (def. *3.01: ~(~p ∨ ~q) ), then EQUIVALENCE p ←→ q (*4.01: (p → q) & ( q → p ) ).

 * Henry M. Sheffer (1921) and Jean Nicod demonstrate that only one connective, the "stroke" | is sufficient to express all propositional formulas.
 * Emil Post (1921) develops the truth-table method of analysis in his "Introduction to a general theory of elementary propositions". He notes Nicod's stroke |.
 * Whitehead and Russell add an introduction to their 1927 re-publication of PM adding, in part, a favorable treatment of the "stroke".

Computation and switching logic:
 * William Eccles and F. W. Jordan (1919) describe a "trigger relay" made from a vacuum tube.
 * George Stibitz (1937) invents the binary adder using mechanical relays. He builds this on his kitchen table.
 * Example: Given binary bits ai and bi and carry-in ( c_ini), their summation Σi and carry-out (c_outi) are:
 * ( ( ai XOR bi ) XOR c_ini )= Σi
 * ( ai & bi ) ∨ c_ini ) = c_outi;

 * Alan Turing builds a multiplier using relays (1937–1938). He has to hand-wind his own relay coils to do this.
 * Textbooks about "switching circuits" appear in the early 1950s.
 * Willard Quine 1952 and 1955, E. W. Veitch 1952, and M. Karnaugh (1953) develop map-methods for simplifying propositional functions.
 * George H. Mealy (1955) and Edward F. Moore (1956) address the theory of sequential (i.e. switching-circuit) "machines".
 * E. J. McCluskey and H. Shorr develop a method for simplifying propositional (switching) circuits (1962).

title: Propositional formula


text:
Llanfihangel Nant Brân

Llanfihangel Nant Brân is a small village lying next to the Nant Brân river in Powys, Wales about 7.5 miles (12 km) west of Brecon.

It is largely a farming community. Llanfihangel includes a church, dedicated to St. Michael, which was probably built in the 16th century and was substantially reconstructed in 1882.

Bethel Chapel was built between 1810 and 1811, and later rebuilt or modified between 1865 and 1866. It is in the simple round-headed style, of the long-wall entry type. The walls are rendered and whitewashed, with a slate eaved roof above. The windows are small-paned sashes with intersecting tracery in their heads. The interior of the chapel was gutted in 2000.

The film of On the Black Hill by Bruce Chatwin was shot here.

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

title: Llanfihangel Nant Brân


text:
Talk:Onkyo

from Vfd
On 17 Feb 2005, this article was nominated for deletion. The result was keep. See Votes for deletion/Onkyo for a record of the discussion.

Adding tech support website
Hello, I would like to add a tech support website that has a section about Onkyo called FixYa.com. Let me know if you have any comments.

Fair use rationale for Image:Onkyo.png
Image:Onkyo.png is being used on this article. I notice the image page specifies that the image is being used under fair use but there is no explanation or rationale as to why its use in this Wikipedia article constitutes fair use. In addition to the boilerplate fair use template, you must also write out on the image description page a specific explanation or rationale for why using this image in each article is consistent with fair use.

Please go to the image description page and edit it to include a fair use rationale. Using one of the templates at Fair use rationale guideline is an easy way to insure that your image is in compliance with Wikipedia policy, but remember that you must complete the template. Do not simply insert a blank template on an image page.

If there is other fair use media, consider checking that you have specified the fair use rationale on the other images used on this page. Note that any fair use images uploaded after 4 May, 2006, and lacking such an explanation will be deleted one week after they have been uploaded, as described on criteria for speedy deletion. If you have any questions please ask them at the Media copyright questions page. Thank you.

BetacommandBot 00:36, 2 July 2007 (UTC)

Chinese rendering
Hello there, just a quick question - why does the entry contain info on the Chinese rendering of Onkyo in the header ("traditional Chinese: 安橋; pinyin: ān qiáo; Jyutping: on1 kiu4") - I had a quick skim over the Japanese article and while there is a reference to "上海安橋電気有限公司", this is a subsidiary and maybe should be declared as such in the body of the article. If we started adding foreign renderings for names into all English language articles we'd be here until the cows come home... Now maybe you might say "but this is what their products are marketed under in China", but then, surely this information is only relevant to the Chinese article on Onkyo. After all, I reckon there are probably Arabic or Sanskrit renderings for the company's name, but I don't see those in the article... --84.163.204.7 (talk) 18:20, 25 October 2008 (UTC)

Deleted
This article has been deleted as a copyright violation, taken from Onkyo's website. Keegan talk 07:03, 3 May 2009 (UTC)
 * I have restored the article to its state prior to the addition of violations.  Keegan talk 07:13, 3 May 2009 (UTC)

Incorrect spelling?
The article lists the Japanese name of the corporation as オンキヨー, is there anything that confirms this spelling? The name is (presumably) based on the word 音響, which would be written in katakana as オンキョー　(note the small ヨ).

Pronunciation?
Is it ONK-YO, or ON-KYE-OH? Or something else? 121.216.105.251 (talk) 00:11, 26 April 2011 (UTC)
 * In the Hepburn romanization system, it would normally be spelled Onkyō and pronounced with a long final "o", like "on-kyoh". As the user above noted, it's originally from the word 音響, which is pronounced like that. But according to the company's website the Japanese spelling is オンキヨー, and the romanized spelling is Onkyo, so these are a bit irregular but correct. – Margin1522 (talk) 13:14, 2 November 2014 (UTC)

Merger with Pioneer???
http://www.cnet.com/news/pioneer-electronics-onkyo-combine-to-keep-pace-with-competition/ — Preceding unsigned comment added by 97.86.251.249 (talk) 14:51, 20 April 2015 (UTC)

Unavailable paragraph
A recent edit claims that Onkyo products are not for sale at major retailers last year. In 2021 I see several receivers for sale at Best Buy, contradicting the unsourced edit. I believe this allegation lacks credibility as a major manufacturer would be unlikely to abandon the US and disconnect their phone support. I am an American owner of one of their products, so to avoid an appearance of a conflict I will leave it to another editor to challenge and remove the offending section. 22:12, 9 Jan 2021 (UTC)

My stereo won't stay on for more than 2 seconds how do I keep it on
My stereo won't stay on for more than 2 seconds how do I keep it on — Preceding unsigned comment added by 174.240.67.226 (talk) 21:47, 23 November 2022 (UTC)

 * If you are using a Wikipedia article's talk page for support it is likely consumer electronics are too complicated for you. Perhaps you should stay with a something less complicated like a few rocks and a stick. — Preceding unsigned comment added by 64.72.40.86 (talk) 09:21, 13 December 2022 (UTC)

title: Talk:Onkyo


text: User talk:209.135.123.8

title: User talk:209.135.123.8


text:
Jerramiah Healy

Jerramiah T. Healy (born December 16, 1950 ) is an American local politician who served as the 48th mayor of Jersey City, New Jersey serving from 2004 to 2013. He ran for the unexpired term of the late Glenn D. Cunningham and was elected in November 2004. In the special election, he defeated Acting Mayor L. Harvey Smith. He was subsequently elected to a full term by a record landslide.

Healy entered public service as an assistant prosecutor for the Hudson County Prosecutor's Office in 1977. From 1981 to 1991, he maintained a private law practice in Jersey City. He was appointed Chief Judge in the Jersey City Municipal Court in 1991, and was reappointed in 1995. In 1997, he ran unsuccessfully for Mayor of Jersey City against Bret Schundler, who later ran for Governor of New Jersey against Jim McGreevey. Healy resumed his private law practice until 2004, when he was elected mayor. Healy lost to Councilman Steven Fulop for mayor in 2013.

Early life
Jerramiah Healy was the fourth of five children born to Daniel and Catherine Healy, Irish immigrants who met and married in Jersey City. His father died when Healy was five years old. He attended St. Michael's Grammar School in Union City and Xavier High School in New York City, and is a 1972 graduate of Villanova University. Healy attended Seton Hall University School of Law, and supported himself as a bartender and an ironworker.

Electoral history
The sudden death of Mayor Glenn Cunningham in May 2004 triggered a special election. Among the eleven candidates, Jerramiah Healy won Cunningham's unexpired term with 17,401 votes (27.8%) out of 62,641 cast. Other than the unusually high number of candidates, the election was notable for the rabidly negative nature of the campaign. The attacks included the distribution of a photo taken of Jerramiah Healy on his porch in Jersey City, passed out and naked.

Healy stood for re-election in May 2005, facing only token opposition from Melissa Holloway, a former city councilperson, and Alfred Marc Pine, who had received less than one percent of the votes in the special election. Healy received 18,349 (75%) of the 24,414 votes cast.

Healy sought re-election in 2009, running as an agent of change and promoting his record of putting extra police on the street and reducing violent crime in Jersey City. His critics challenged his claims during the campaign. Nevertheless, on May 12, 2009, Healy was re-elected with nearly 53% of the vote; former New Jersey General Assemblyman Louis Manzo was the runner-up with 26%. Six of Healy's nine running mates for city council won outright on election day, two faced runoffs on June 9 and one lost to incumbent Steven Fulop in Ward E.

Healy lost his bid for another term as mayor on May 14, 2013 to Councilman Steven Fulop.

Arrest and conviction
Healy claimed to have been "roughed up", maced, and arrested outside his sister's bar in Bradley Beach in 2006. Cops allege he was interfering in a police investigation. Healy claimed that he was attempting to intervene in an argument between a couple outside the bar. His claims were rejected by the court and he was found guilty of obstruction of justice on June 22, 2007. Healy appealed the decision while trying to portray himself as having broad public support. On July 2, 2008, Healy's appeal was denied by the state appellate court which upheld Healy's conviction. During his appeal, it was revealed that Healy had attempted to influence the arresting officers. Healy filed suit against the officers in question, alleging that they violated his right to free speech (the case was ultimately denied). Healy appealed to the State Supreme Court and was again denied.

Healy had a similar charge reduced to violation of a noise ordinance on a guilty plea in August 1999.

Gun legislation advocate
He is a member of the Mayors Against Illegal Guns Coalition, a bi-partisan group with a stated goal of "making the public safer by getting illegal guns off the streets." The Coalition is co-chaired by former Boston Mayor Thomas Menino and former New York City Mayor Michael Bloomberg. As part of his efforts at removing guns from Jersey City, Healy pushed an ordinance banning the sale of more than one handgun per month per customer. This ordinance was found unconstitutional in state superior court, and an appellate court affirmed that result. However, the New Jersey government has since enacted legislation creating similar limits statewide.

title: Jerramiah Healy


text: User talk:67.140.44.94

title: User talk:67.140.44.94


text:
Yakovlev Yak-16

The Yakovlev Yak-16 (NATO reporting name Cork) was a Soviet light transport that first flew in 1947. Prototypes were built in both passenger and military cargo versions, but neither was put into production as the Antonov An-2 was felt to be more versatile.

Development
After the end of World War II the GVF (Grazdahnskij Vozdushnyj Flot–Civil Air Fleet) issued a requirement for a passenger aircraft to service low-volume destinations too small to justify a Lisunov Li-2. It wanted an aircraft capable of carrying ten passengers over a distance of 800 km at a cruising speed of 290 km/h that would be powered by a pair of 700 hp Shvetsov ASh-21 radial engines. The Yakovlev OKB was tasked to fulfill this requirement in February 1946 with the first prototype ready for State acceptance trials on 1 November 1946. This proved to be too optimistic considering the amount of work the OKB was already doing and this was delayed to August 1947. The specification was revised at the same time to specify a speed no less than 350 km at sea level and that the military version was to mount a dorsal turret with a single 20 mm gun.

The Yak-16 was a low-winged, twin-engined monoplane that closely resembled the Li-2. The metal-skinned, semi-monocoque fuselage had room for a two-person cockpit and ten passengers plus a toilet and baggage hold. The control surfaces of the tail were fabric-covered although the tail itself was metal-skinned. The two-spar metal wing was built in three sections, a rectangular center section and two trapezoidal outer panels. The main undercarriage legs retracted forward into the engine nacelles, with the wheels remaining semi-exposed, while the tailwheel was fixed. The ASh-21 engines had NACA cowlings and drove two-bladed variable-pitch VISh-11V-20 propellers.

The first prototype, often referred to as the Yak-16-I, made its first flight on 24 September 1947 and proved to have excellent handling characteristics with one engine out and could also climb with one engine inoperable. It passed its State acceptance trials in early 1948 at the NII GVF (Nauchno-Issledovatel'skiy Institut Grazhdanskogo Vozdushnogo Flota—Scientific Test Institute for Civil Air Fleet).

The military transport version, often called the Yak-16-II, differed from the passenger version as it carried a UTK-1 ball turret that mounted a 12.7 mm Berezin UBT machine gun immediately behind the flight deck, the cargo cabin floor was reinforced, the vertical tail was slightly larger and the fuselage was slightly longer. It used three-bladed V-511 feathering propellers with scimitar-shaped blades. It could carry seven paratroopers, ten fully equipped troops or six stretcher cases and a medical attendant. It was fitted with a large clamshell door on the left side of the fuselage to facilitate cargo loading. This door had a smaller, inward-opening door set into its forward half. Three TsDMMM-120 supply containers could be fitted on racks underneath the wing center section and it was fitted with a glider tow hook.

The Yak-16-II passed its manufacturer's trials in April 1948 and was submitted for the State acceptance trials shortly afterwards. These revealed several deficiencies that caused the horizontal tail area to be increased and deicing equipment to be fitted on the leading edges of the wings and tail. It was resubmitted for another round of State acceptance trials which approved it for production. However, it was not selected for production as the Antonov An-2 was thought to be more versatile in both roles. Some effort was made to drum up export sales in Eastern Europe, but no interest was shown because it was not in service with Aeroflot. The prototypes were used for a time by the Yakovlev OKB and Factory No. 464 which had built them.

title: Yakovlev Yak-16


text:
Talk:Clustering coefficient

Just some random feedback here... Many of the references to this article deal with examples that are somewhat complex. As someone who understands graph theory in a very visual way, the graphical example was too simple to be meaningful immediately. A counter-factual visual example would also serve to highlight the nuance of this concept. Thanks to the authors though, overall a good article. Meson537 (talk) 00:44, 8 December 2010 (UTC)

Shouldn't the degree reference (3rd paragraph in formal discussion section) point to Degree_(graph_theory) instead of Degree_(mathematics) ?

I believe the caption below the figure for the local clustering coefficient is either wrong, or misleading. First, there is no light blue node. The (regular) blue node doesn't seem to be related to the edges. It seems like the leftmost node is the one that needs to be painted light blue. —Preceding unsigned comment added by 128.59.65.170 (talk) 21:10, 21 April 2010 (UTC)

—Preceding unsigned comment added by Adonyk (talk • contribs) 15:28, 11 December 2008 (UTC)

Duno is this is the right place to discuss about this but it seems like there is an error on this page. According to other websites and research papers, the maximum of links within the neighbourhood in a directed graph is k_i(k_i-1), not 2k_i(k_i-1).

One of the sources : http://www.elvis.ac.nz/brain?ClusteringCoefficient

 * It is indeed the correct place to discuss it. It was indeed incorrect, I've changed it. Thank you for your correction. --stochata 16:55, 1 Mar 2005 (UTC)

p.s., do not be afraid to be bold and correct it yourself!

Added a few wikilinks to explore for us aspiring math dummies out there. ^^ Zanturaeon 23:21, August 1, 2005 (UTC)

Isn't $$N_i = \{v_j\} : e_{ij} \in E.$$ problematic if $$e_{ij}$$ is $$e_{ii}$$ an edge leading to the vertex whrer it starts? (that was from 83.135.204.222 in June 2006)
 * Indeed. If there is an assumption that i doesn't equal j in the definition of N, it ought to be stated. Or is it not a problem? 72.248.65.171 22:44, 18 March 2007 (UTC)

I think, $$N_i = \{v_j : e_{ij} \in E \land e_{ji} \in E\}.$$ is wrong, too. For directed graphs, $$k_i$$ is defined as the number of vertices leading in _or_ out later on. I think it would make more sense using "and" or "or" both times. Is there any reference for these definitions? --92.224.229.115 (talk) 10:14, 24 September 2010 (UTC)

I agree with the above comment. The neighbourhood in a directed graph should be $$N_i = \{v_j : e_{ij} \in E \lor e_{ji} \in E\}.$$. Otherwise you are only counting nodes where there are 2-cycles between that node and node i. —Preceding unsigned comment added by 81.108.140.67 (talk) 13:56, 17 November 2010 (UTC)

Shouldn't this definition be restricted to vertices with degree greater than or equal to zero? Can you find the clustering coefficient of an isolated vertex? Possie11 20:21, 24 April 2007 (UTC)

 * I think you mean degree strictly greater than one. Yes, you're clearly right, because a vertex with degree zero is isolated, and has an empty neighborhood; one with degree one has a singleton neighborhood, which can have no edges (well, no self-edges, anyway). BrianTung (talk) 21:20, 7 February 2008 (UTC)

The link on the bottom of the page doesn't work anymore. Someone might want to update it. 15:29, 27 May 2007 (UTC)

Does this,
 * $$C_i = \frac{2|\{e_{jk}\}|}{k_i(k_i-1)} : v_j,v_k \in N_i, e_{jk} \in E.$$

mean this?
 * $$ C_i=\frac{2|\{e_{jk} : v_j, v_k \in N_i, e_{jk} \in E\}|}{k_i(k_i-1)}.$$

If not then what does it mean? If it does mean the former then surely that is how it should be written? —Preceding unsigned comment added by 128.232.238.63 (talk) 23:58, 4 November 2008 (UTC)

Sorry but... I think the page is very incomplete. First of all, there is no definition of the concept of clustering coefficient given. A formula is not a concept, is just an expression of a manner to estimate a quantity. Second, Watts and Strogatz did not invent the clustering coefficient, what is a quite old concept. Third, there is no distinction between the global and the local clustering coefficients. The global clustering, C, is the overall conditional probability that any two nodes are connected provided that they share at least one common neighbour. The local clustering Ci of a node i represents the probability of its neighbours to be connected within each other. In directed networks, there is no clear and commonly accepted manner of defining C (at least to my knowledge). However, the local clustering Ci can be applied to individual nodes of a directed network, and then averaged. BUT, if you calculate C of an undirected graph, and the average Ci of all its nodes, C and  are not the same! Please, let me know what you think about my comments. I will be happy to collaborate.

Small World != Clustering Coefficient
I believe the clustering coefficent has nothing to do with the "small-world"-effect, at least not directly. Think of a "big graph", which consists of a lot of throughly connected subgraphs, but the individual subgraphs are not connected to each other. Then the clustering coefficient of the "big graph" will be 1, but there is no small world effect. Most of the networks exhibiting the small world effect will have a high clustering coefficient, but a high clustering coefficient does not mean that the graph exhibits a small world effect. I think "ntroduced the clustering coefficient[1] graph measure to determine whether or not a graph is a small-world network." and "A graph is considered small-world, if its average clustering coefficient \bar{C} is significantly higher than a random graph constructed on the same vertex set." is wrong. 88.65.98.195 14:57, 15 September 2007 (UTC)
 * Please read the paper. It defines the "small world phenomenon" as L slightly greater than Lrnd, while C much greater than Crnd. L is the Average path length, C is the Clustering Coefficient, and the Xrnd values are calculated for a random graph with the same number of edges and vertices. So in a way, you're right, a high clustering coefficient does not suffice for a small world (the paper even states that you can't detect a small world from clustering coefficient alone). The problem is that the clustering coefficient is a local graph measure, while the small world property is a global one. just my 2E-2 Euros. --80.136.95.157 14:58, 2 October 2007 (UTC)
 * I already knew the paper before. I did not find the explicit definition of "small world network" in the paper like you said. I think you mean this passage: "We find that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. We call them ‘small-world’ networks, by ...". I think the meaning is "We call networks with small characteristic path lengths small world networks", not "We call highly clustered networks with small characteristic path lenghts small world models". Anyway, i feel the gist of the paper is: "Is it possible that a network with small path length is highly clustered?" and not "How can we find out whether a network is a small world network?". Besides, defining "small world" through the clustering coefficient is quite illogical IMHO. 88.65.77.185  —Preceding signed but undated comment was added at 15:57, 8 October 2007 (UTC)
 * I agree, the small world property is as indicated by the name, a property of graphs that have a small average distance. The literature is however often interested in real-world small world graphs, they tend to have a large clustering coefficient too. The disregard for trivial small world graphs in literature has confused the author of this article.

'clustering coefficient' has little to do with 'clustering'
If you consider a network with overlapping community structure, then there will be many triangles and hence a reasonably high clustering coefficient. But I suspect many people take 'clustering' to imply a non-overlapping partitioning. A more extreme example is a ring lattice - a ring lattice has high clustering coefficient, but it doesn't have anything that can be reasonably called community structure (overlapping or otherwise).

Is it possible to concisely clear this up at the top of the article? Aaron McDaid (talk - contribs) 10:47, 16 July 2011 (UTC)

 * I agree that it is often overlooked that a network with a high clustering coefficient might have no clusters in it. On the other hand, a network with many clusters, even one that consists entirely of network clusters, could have a low clustering coefficient. Consider a large, undirected graph, say with hundreds of billions of nodes.  Consider that every node belongs to one hundred cliques (i.e., complete subgraphs) of size eleven that are randomly selected.  Thus all edges in the graph are embedded in a clique of size eleven.  Yet the clustering coefficient will be pretty low. To see this, imagine the egocentric neighborhood of any given node.  Each node is connected to ten cliques of ten, so (ignoring the small chance that any of those ten cliques shares members) there is the potential for 500k edges between the alters of any ego, however, only 4500 of these connections actually exist.  This example also illustrates the clustering coefficients of graphs with different sizes should not be compared without some kind of suitable normalization (I'm not aware of one).--Conradl (talk) 23:14, 14 September 2011 (UTC)

Global clustering coefficient vs. Transitivity ratio
The article claims that these are two separate concepts, but the definitions seem to be identical. What am I missing?

Also: why is it called a transitivity ratio? — Preceding unsigned comment added by 84.94.180.144 (talk) 15:30, 13 March 2014 (UTC)
 * Let T = the number of triangles, P = the number of two-edge paths, and C = the number of connected triples of vertices. Then C = P − 2T, because a connected triple that is not a triangle contributes one to the P term while a triangle contributes 3 to the P term and −2 from the other term, so that its contribution is also one. My understanding is that the transitivity ratio is 3T/P and that the clustering coefficient is T/C. So they both give the same information (one is a function of the other) but have different values. But this is not clearly explained in the article and the formula in the transitivity ratio says it is equal to two different things. As for why: because transitivity (a friend of a friend is automatically a friend) would imply that 3T = P, and the transitivity ratio measures how close this is to being true. —David Eppstein (talk) 16:04, 13 March 2014 (UTC)
 * Thanks! That cleared it up. I think I'll try to incorporate all that into the article, as long as I'm here. — Preceding unsigned comment added by 84.94.180.144 (talk) 20:40, 16 March 2014 (UTC)
 * This has me confused. Among the sources i've found that are careful with their definitions, most define the (global) clustering coefficient as 3T/P, while the rest call this the transitivity ratio and define the (global) clustering coefficient as the mean local clustering coefficient. I have not been able to find a source that defines anything as T/C, though some sources (e.g. ) use phrases like "connected triples" but make it clear from examples or further exposition that the calculation they're performing is 3T/P. If anyone has a source for the T/C definition, i would love to see it! In the meantime (as written, though perhaps even if it were written more clearly) i worry that the distinction causes more confusion than clarity. 155.37.131.50 (talk) 21:17, 4 June 2014 (UTC)

Hi everyone! I think the page is a bit confusing currently. On my network software documentation site (http://toreopsahl.com/tnet/weighted-networks/clustering/), some people have reached out to clarify concepts in this article. There are multiple ways of defining the overall level of clustering in a network. The global clustering coefficient which is defined as 3x triangles over triples has been around for a long time (all the way back to Luce and Perry, 1949). In their 1998 paper, Watts and Strogatz introduced the local clustering coefficient, which is a node level metric (studying the number of ties among neighbors were not a new idea, see Granovetter, 1973, Coleman, 1988, and Burt, 1992). To get an overall coefficient, Watts and Strogatz took a simple average of the node-level scores. By using a simple average, you get a different answer than the global clustering coefficient if the nodes do not all have the same number of ties. To get the same answer, you can use a weighted average where each node is weighted by the number of triplets they are the center of, n*(n-1) (see code and references on website).

I have gone ahead and cleared up this article by - removing the paragraph starting with Watts and Strogatz under the Global clustering coefficient heading as it is already mentioned under local clustering coefficient; and their way of computing the simple average is mentioned under Network average clustering coefficient) - removing the heading Transitivity Ratio as this is the Global clustering coefficient.

Tore Opsahl 16:42, 27 July 2014 (UTC) — Preceding unsigned comment added by Tore.opsahl (talk • contribs)
 * Thanks, Tore. However, another source of confusion for me is the Luce–Perry citation. Can you say where in their paper they attempt to compute or describe (using their terms) the proportion of symmetric 3-chains in a matrix that are redundant? I have read through it and have not found such a comment, so i don't understand why the paper is being cited. 155.37.131.50 (talk) 19:10, 7 September 2014 (UTC)

Algorithms to generate clustered networks
I think it would be worth having a section about algorithms to generate clustered networks. If there's agreement: I'd go ahead with the standard small-worlds network algorithm and also the random clustered graphs introduced (separately) by Miller and Newman. Since I'm "Miller", I want to be careful not to be biased on this, so seeking feedback before I do any such changes. If no-one has comments on this, I may go ahead and do the changes (eventually). I'd be interested in including other algorithms as well. Please give suggestions. Joelmiller (talk) 02:39, 19 March 2015 (UTC)

Triplet contradiction
The following two sentences contradict each other:

"The global clustering coefficient is the number of closed triplets (or 3 x triangles) over the total number of triplets (both open and closed)."

"In this formula, a connected triplet is defined to be a connected subgraph consisting of three vertices and two edges."

I had tried editing the latter to read "and either two or three edges", but it was reverted. I don't see how both of these sentences can be true at the same time.

Michaelmalak (talk) 19:32, 5 October 2015 (UTC)
 * A complete graph on three vertices u, v, and w has three triplets, according to the current definition of a triplet: the paths u-v-w, v-w-u, and w-u-v. According to your proposed replacement, it would have four (the whole graph is a subgraph of itself and would also count as a connected triplet) but I expect that what you intended was for it to have only one (the three vertices considered as an unordered set rather than a choice of vertices and edges forming a subgraph). That changes the formula that you need to use to define the clustering coefficient. In particular, it should be a number from 0 to 1, but your proposed replacement turns it into a number from 0 to 2/3 (if you read what you wrote literally) or from 0 to 3 (if you go by what I think you intended). —David Eppstein (talk) 20:16, 5 October 2015 (UTC)

 * I believe my understanding is the same as yours. But just to make sure, let me run through an example. Let G have four nodes. a, b, and c are fully connected with three edges. There is a fourth edge from c to d. There are three closed triplets (a-b-c, b-c-a, and c-a-b) and two open triplets (a-c-d and b-c-d). Therefore the clustering coefficient is 3 / (2+3) = 0.6.

 * My concern is that the definition "In this formula, a connected triplet is defined to be a connected subgraph consisting of three vertices and two edges" suggests (at least to me) that closed triplets are to be excluded from the denominator and thus in my example, with this (in my opinion erroneously worded) definition of triplet, the clustering coefficient would be 3 / 2 = 1.5, which is outside the desired (0,1) range. Michaelmalak (talk) 22:58, 5 October 2015 (UTC)
 * Look at the word "subgraph", and notice that it does not say induced subgraph. —David Eppstein (talk) 23:29, 5 October 2015 (UTC)

 * I suppose that might be technically correct, but it is highly misleading. How about we just completely remove the sentence "In this formula, a connected triplet is defined to be a connected subgraph consisting of three vertices and two edges," since it conflicts apparently (but perhaps not absolutely) with "The global clustering coefficient is the number of closed triplets (or 3 x triangles) over the total number of triplets (both open and closed)"? Michaelmalak (talk) 14:21, 6 October 2015 (UTC)
 * I still don't see the contradiction. If a closed triplet is a triangle with one designated vertex, and an open triplet is an induced two-edge path, then the connected triplets (as defined by this sentence) corresponds one-for-one with the union of closed and open triplets. —David Eppstein (talk) 15:45, 6 October 2015 (UTC)

 * A closed triplet has three edges. "In this formula, a connected triplet is defined to be a connected subgraph consisting of three vertices and two edges" makes it sound like closed triplets are excluded from the denominator. Michaelmalak (talk) 15:54, 6 October 2015 (UTC)
 * Only if you continue to wilfully misunderstand what the word "subgraph" means. —David Eppstein (talk) 16:13, 6 October 2015 (UTC)

 * Was my attempted edit, "In this formula, a connected triplet is defined to be a connected subgraph consisting of three vertices and either two or three edges" incorrect? If so, how? If not, isn't it more clear than the current statment, "In this formula, a connected triplet is defined to be a connected subgraph consisting of three vertices and two edges"? — Preceding unsigned comment added by Michaelmalak (talk • contribs) 16:42, 6 October 2015 (UTC)

title: Talk:Clustering coefficient


text:
Japan Renewal Party

The Japan Renewal Party (新生党) was a Japanese political party that existed in the early 1990s. It was founded in 1993 by 44 members of the Liberal Democratic Party led by Tsutomu Hata and Ichirō Ozawa. It was instrumental in ending the LDP's 38-year dominance of Japanese politics.

Both reformers, Hata and Ozawa had been involved in a difficult leadership struggle within the former Takeshita faction of the LDP. Their opponents, led by Keizo Obuchi and Ryutaro Hashimoto, were using the fallout of the Sagawa Kyubin scandal as a tool to undermine the reformist position. Hata and Ozawa split from the party partly to shift media attention away from the scandal. In doing so, they transformed an internal party dispute to a wide-ranging conflict that led to a decade of shifting allegiances and short-lived parties.

In the elections immediately following the split, the JRP won 55 seats, making it one of the most powerful opposition parties. Most importantly, the party drew off support crucial to the LDP. While several other small parties had split from the LDP, Hata and Ozawa's group was the largest, and was widely considered to have finally broken the back of LDP dominance.

Known for his political organisational skills, Ozawa organised a five-party coalition of the JRP, the Japan Socialist Party, the Democratic Socialist Party, Komeito and the United Social Democratic Party. This coalition held 237 seats in the Diet, and after convincing the Japan New Party and the New Party Sakigake to join, was able to form a government under Morihiro Hosokawa.

As the impetus for the collapse of LDP power, the JRP was able to exert great power in the coalition. While some concessions to other parties were made, the JRP was perhaps overly dominant, eventually forcing some other members out of the coalition through its heavy-handed style. In 1994, the JRP merged into the New Frontier Party.

title: Japan Renewal Party


text:
Landsborough Highway

Landsborough Highway is a highway in western Queensland, Australia, running in the northwest–southeast direction from Morven to Cloncurry. The Landsborough Highway runs through vast tracts of land that was once occupied by William Landsborough, an Australian explorer of the 19th century. It is also the central part of the tourist route known as the Matilda Way after the popular Australian song Waltzing Matilda, which extends from Bourke in central northern New South Wales to Karumba on the Gulf of Carpentaria.

The entire highway is an important part of the National Highway system linking Darwin and Brisbane: formerly National Route 66 (Cloncurry to Barcaldine) and National Route 71 (Barcaldine to Augathella), Queensland began to convert to the alphanumeric system much of Australia had adopted in the early-2000s and is now designated as National Route A2. Its importance also stems from the fact that it is the only sealed link between Flinders Highway and Capricorn Highway apart from Gregory Development Road between Emerald and Charters Towers.

The highway services an important sheep and cattle grazing region, tourist traffic and local properties. The highway is fully sealed but with many sections of substandard width and quality. It is also flood-prone with lengthy closures during floods.

Northern Australia Roads Program upgrade
The Northern Australia Roads Program announced in 2016 included the following project for the Landsborough Highway.

Pavement widening and strengthening
The project for pavement widening and strengthening between Longreach and Winton (Package 1) was completed in early 2020 at a total cost of $27 million.

Roads of strategic importance upgrade
The Roads of Strategic Importance initiative, last updated in March 2022, included the following project for the Landsborough Highway.

Corridor upgrade
A lead project to upgrade the Mount Isa to Rockhampton corridor, including sections of the Landsborough and Capricorn Highways and surrounding state and council roads, at an estimated cost of $237.5 million, was in the planning and scoping stage. Works are expected to include progressive sealing, lane duplications and crossing upgrades.

Pavement strengthening and widening
A project to strengthen and widen pavement 7 km north of Winton, at a cost of $4 million, was completed in June 2021.

A project to strengthen and widen pavement 23 km north-west of Winton, at a cost of $6 million, was completed in December 2021.

Towns
Towns along the highway are listed below:
 * Augathella
 * Tambo
 * Blackall
 * Barcaldine
 * Longreach
 * Winton
 * Kynuna
 * McKinlay
 * Cloncurry

title: Landsborough Highway


text:
Talk:Carla Howell

External links modified
Hello fellow Wikipedians,

I have just modified 2 one external links on Carla Howell. 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/20090902224049/http://thirdpartywatch.com:80/2007/11/20/ending-the-income-tax-in-taxachusetts/ to http://thirdpartywatch.com/2007/11/20/ending-the-income-tax-in-taxachusetts/
 * Added archive https://web.archive.org/web/20100613012514/http://masslpa.org/content/ballot-initiative-filed-roll-back-sales-tax to http://www.masslpa.org/content/ballot-initiative-filed-roll-back-sales-tax
 * Added tag to http://query.nictusa.com/cgi-bin/cancomsrs/?_00+S8MA00185

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at ).

Cheers.— InternetArchiveBot  (Report bug) 10:57, 15 November 2016 (UTC)

title: Talk:Carla Howell