natural deduction

(redirected from Deductive logic)
Also found in: Dictionary.

natural deduction

A set of rules expressing how valid proofs may be constructed in predicate logic.

In the traditional notation, a horizontal line separates premises (above) from conclusions (below). Vertical ellipsis (dots) stand for a series of applications of the rules. "T" is the constant "true" and "F" is the constant "false" (sometimes written with a LaTeX \perp).

"^" is the AND (conjunction) operator, "v" is the inclusive OR (disjunction) operator and "/" is NOT (negation or complement, normally written with a LaTeX \neg).

P, Q, P1, P2, etc. stand for propositions such as "Socrates was a man". P[x] is a proposition possibly containing instances of the variable x, e.g. "x can fly".

A proof (a sequence of applications of the rules) may be enclosed in a box. A boxed proof produces conclusions that are only valid given the assumptions made inside the box, however, the proof demonstrates certain relationships which are valid outside the box. For example, the box below labelled "Implication introduction" starts by assuming P, which need not be a true proposition so long as it can be used to derive Q.

Truth introduction:

- T

(Truth is free).

Binary AND introduction:

----------- | . | . | | . | . | | Q1 | Q2 | ----------- Q1 ^ Q2

(If we can derive both Q1 and Q2 then Q1^Q2 is true).

N-ary AND introduction:

---------------- | . | .. | . | | . | .. | . | | Q1 | .. | Qn | ---------------- Q1^..^Qi^..^Qn

Other n-ary rules follow the binary versions similarly.

Quantified AND introduction:

--------- | x . | | . | | Q[x] | --------- For all x . Q[x]

(If we can prove Q for arbitrary x then Q is true for all x).

Falsity elimination:

F - Q

(Falsity opens the floodgates).

OR elimination:

P1 v P2 ----------- | P1 | P2 | | . | . | | . | . | | Q | Q | ----------- Q

(Given P1 v P2, if Q follows from both then Q is true).

Exists elimination:

Exists x . P[x] ----------- | x P[x] | | . | | . | | Q | ----------- Q

(If Q follows from P[x] for arbitrary x and such an x exists then Q is true).

OR introduction 1:

P1 ------- P1 v P2

(If P1 is true then P1 OR anything is true).

OR introduction 2:

P2 ------- P1 v P2

(If P2 is true then anything OR P2 is true). Similar symmetries apply to ^ rules.

Exists introduction:

P[a] ------------- Exists x.P[x]

(If P is true for "a" then it is true for all x).

AND elimination 1:

P1 ^ P2 ------- P1

(If P1 and P2 are true then P1 is true).

For all elimination:

For all x . P[x] ---------------- P[a]

(If P is true for all x then it is true for "a").

For all implication introduction:

----------- | x P[x] | | . | | . | | Q[x] | ----------- For all x . P[x] -> Q[x]

(If Q follows from P for arbitrary x then Q follows from P for all x).

Implication introduction:

----- | P | | . | | . | | Q | ----- P -> Q

(If Q follows from P then P implies Q).

NOT introduction:

----- | P | | . | | . | | F | ----- / P

(If falsity follows from P then P is false).


//P --- P

(If it is not the case that P is not true then P is true).

For all implies exists:

P[a] For all x . P[x] -> Q[x] ------------------------------- Q[a]

(If P is true for given "a" and P implies Q for all x then Q is true for a).

Implication elimination, modus ponens:

P P -> Q ---------- Q

(If P and P implies Q then Q).

NOT elimination, contradiction:

P /P ------ F

(If P is true and P is not true then false is true).
References in periodicals archive ?
The final format, by using axioms and deductive logic, often presents obscure, hard to understand proofs.
This paper finds support for the view of the quantum logicians who assert quantum logic to be the most comprehensive deductive logic.
This criticism is the common complaint against deductivist and logocentric approaches that all natural language argumentation occurs in a context and that deductive logic 'ignores' context.
Is this just a trifling and insignificant curiosity, or does it reveal a deeper malaise in the way we understand and apply deductive logic, and in the way that we manipulate logical contents?
In a culture infested with fundamentalist Muslims, even theologians, starting from faith-based premises, were in danger for applying deductive logic to religious beliefs.
While some inferences can be made through deductive logic there are also face validity issues with the underlying premise that changes in DCF muscle function are a cause or effect of persisting pain states in the cervical spine.
Following a simple line of deductive logic, the syllogistic conclusion shows that the development of new uranium mines will only be considered once the price exceeds US$75 per pound.
Again, it is a mistaken view that has never presented hard facts, except some priori assumptions and deductive logic.
This book identifies five challenges critical to the nation's future, showing how deductive logic can change how we think about problems and provide win-win solutions that transcend the current Left/Right divide.
Two Reasoners (independent third-party services), DR-Reasoner and R-Reasoner, with a high reputation rating that can conduct inference on defeasible and deductive logic rule bases, accordingly, and produce the results as an RDF file.