منطق حدسي

المنطق الحدسي (الإنكليزية: Intuitionistic logic) أو المنطق البنائي (الإنكليزية: constructive logic) هو عبارة عن نظام منطق رمزي يختلف عن نظام المنطق الكلاسيكي في تعريفه لصحة قضية ما. ففي المنطق الكلاسيكي، يفترض بالقضايا أن تكون إما صحيحة أو خاطئة، حتى وإن لم يكن لدينا برهان لذلك. في المنطق البنائي، لا تعتبر القضية صحيحة إلا إذا وجد دليل على صحتها، ولا تعتبر خاطئة إلا إذا وجد دليل على خطئها. فالعمليات في المنطق البنائي تصون التبرير بدلاً من الحقيقة.

من الناحية البنائية يختلف المنطق الحدسي عن المنطق الكلاسيكي في أن كلاً من قانون الوسط المستبعد law of excluded middle واختزال الازدواج السلبي double negation elimination ليسا من بديهيات النظام، ولا يمكن إثباتهما فيه.

Constructive logic is practically useful because its restrictions produce proofs that have the existence property, making it also suitable for other forms of mathematical constructivism. Informally, this means that if you have a constructive proof that an object exists, you can turn that constructive proof into an algorithm for generating an example of it.

It was originally developed by Arend Heyting to provide a formal basis for Brouwer's programme of intuitionism.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

البناء النحوي

The Rieger–Nishimura lattice. Its nodes are the propositional formulas in one variable up to intuitionistic logical equivalence, ordered by intuitionistic logical implication.

The syntax of formulas of intuitionistic logic is similar to propositional logic or first-order logic. However, intuitionistic connectives are not definable in terms of each other in the same way as in classical logic, hence their choice matters. In intuitionistic propositional logic it is customary to use →, ∧, ∨, ⊥ as the basic connectives, treating ¬A as an abbreviation for (A → ⊥). In intuitionistic first-order logic both quantifiers ∃, ∀ are needed.

Many tautologies of classical logic can no longer be proven within intuitionistic logic. Examples include not only the law of excluded middle p ∨ ¬p, but also Peirce's law ((p → q) → p) → p, and even double negation elimination. In classical logic, both p → ¬¬p and also ¬¬p → p are theorems. In intuitionistic logic, only the former is a theorem: double negation can be introduced, but it cannot be eliminated. Rejecting p ∨ ¬p may seem strange to those more familiar with classical logic, but proving this statement in constructive logic would require producing a proof for the truth or falsity of all possible statements, which is impossible for a variety of reasons.

Because many classically valid tautologies are not theorems of intuitionistic logic, but all theorems of intuitionist logic are valid classically, intuitionist logic can be viewed as a weakening of classical logic, albeit one with many useful properties.

Sequent calculus

Gentzen discovered that a simple restriction of his system LK (his sequent calculus for classical logic) results in a system which is sound and complete with respect to intuitionistic logic. He called this system LJ. In LK any number of formulas is allowed to appear on the conclusion side of a sequent; in contrast LJ allows at most one formula in this position.

Other derivatives of LK are limited to intuitionstic derivations but still allow multiple conclusions in a sequent. LJ' ^[1] is one example.

Hilbert-style calculus

Intuitionistic logic can be defined using the following Hilbert-style calculus. Compare with the deduction system at Propositional calculus#Alternative calculus.

In propositional logic, the inference rule is modus ponens

MP: from $\phi$ and $\phi \to \psi$ infer $\psi$

and the axioms are

THEN-1: $\phi \to (\chi \to \phi )$
THEN-2: $(\phi \to (\chi \to \psi ))\to ((\phi \to \chi )\to (\phi \to \psi ))$
AND-1: $\phi \land \chi \to \phi$
AND-2: $\phi \land \chi \to \chi$
AND-3: $\phi \to (\chi \to (\phi \land \chi ))$
OR-1: $\phi \to \phi \lor \chi$
OR-2: $\chi \to \phi \lor \chi$
OR-3: $(\phi \to \psi )\to ((\chi \to \psi )\to (\phi \lor \chi \to \psi ))$
FALSE: $\bot \to \phi$

To make this a system of first-order predicate logic, the generalization rules

$\forall$ -GEN: from $\psi \to \phi$ infer $\psi \to (\forall x\ \phi )$ , if $x$ is not free in $\psi$
$\exists$ -GEN: from $\phi \to \psi$ infer $(\exists x\ \phi )\to \psi$ , if $x$ is not free in $\psi$

are added, along with the axioms

PRED-1: $(\forall x\ \phi (x))\to \phi (t)$ , if the term t is free for substitution for the variable x in $\phi$ (i.e., if no occurrence of any variable in t becomes bound in $\phi (t)$ )
PRED-2: $\phi (t)\to (\exists x\ \phi (x))$ , with the same restriction as for PRED-1

Optional connectives

Negation

If one wishes to include a connective $\lnot$ for negation rather than consider it an abbreviation for $\phi \to \bot$ , it is enough to add:

NOT-1': $(\phi \to \bot )\to \lnot \phi$
NOT-2': $\lnot \phi \to (\phi \to \bot )$

There are a number of alternatives available if one wishes to omit the connective $\bot$ (false). For example, one may replace the three axioms FALSE, NOT-1', and NOT-2' with the two axioms

NOT-1: $(\phi \to \chi )\to ((\phi \to \lnot \chi )\to \lnot \phi )$
NOT-2: $\phi \to (\lnot \phi \to \chi )$

as at Propositional calculus#Axioms. Alternatives to NOT-1 are $(\phi \to \lnot \chi )\to (\chi \to \lnot \phi )$ or $(\phi \to \lnot \phi )\to \lnot \phi$ .

Equivalence

The connective $\leftrightarrow$ for equivalence may be treated as an abbreviation, with $\phi \leftrightarrow \chi$ standing for $(\phi \to \chi )\land (\chi \to \phi )$ . Alternatively, one may add the axioms

IFF-1: $(\phi \leftrightarrow \chi )\to (\phi \to \chi )$
IFF-2: $(\phi \leftrightarrow \chi )\to (\chi \to \phi )$
IFF-3: $(\phi \to \chi )\to ((\chi \to \phi )\to (\phi \leftrightarrow \chi ))$

IFF-1 and IFF-2 can, if desired, be combined into a single axiom $(\phi \leftrightarrow \chi )\to ((\phi \to \chi )\land (\chi \to \phi ))$ using conjunction.

Relation to classical logic

The system of classical logic is obtained by adding any one of the following axioms:

$\phi \lor \lnot \phi$ (Law of the excluded middle. May also be formulated as $(\phi \to \chi )\to ((\lnot \phi \to \chi )\to \chi )$ .)
$\lnot \lnot \phi \to \phi$ (Double negation elimination)
$((\phi \to \chi )\to \phi )\to \phi$ (Peirce's law)

In general, one may take as the extra axiom any classical tautology that is not valid in the two-element Kripke frame $\circ {\longrightarrow }\circ$ (in other words, that is not included in Smetanich's logic).

Another relationship is given by the Gödel–Gentzen negative translation, which provides an embedding of classical first-order logic into intuitionistic logic: a first-order formula is provable in classical logic if and only if its Gödel–Gentzen translation is provable intuitionistically. Therefore intuitionistic logic can instead be seen as a means of extending classical logic with constructive semantics.

Non-interdefinability of operators

In classical propositional logic, it is possible to take one of conjunction, disjunction, or implication as primitive, and define the other two in terms of it together with negation, such as in Łukasiewicz's three axioms of propositional logic. It is even possible to define all four in terms of a sole sufficient operator such as the Peirce arrow (NOR) or Sheffer stroke (NAND). Similarly, in classical first-order logic, one of the quantifiers can be defined in terms of the other and negation.

These are fundamentally consequences of the law of bivalence, which makes all such connectives merely Boolean functions. The law of bivalence does not hold in intuitionistic logic, only the law of non-contradiction. As a result none of the basic connectives can be dispensed with, and the above axioms are all necessary. Most of the classical identities are only theorems of intuitionistic logic in one direction, although some are theorems in both directions. They are as follows:

Conjunction versus disjunction:

$(\phi \wedge \psi )\to \neg (\neg \phi \vee \neg \psi )$
$(\phi \vee \psi )\to \neg (\neg \phi \wedge \neg \psi )$
$(\neg \phi \vee \neg \psi )\to \neg (\phi \wedge \psi )$
$(\neg \phi \wedge \neg \psi )\leftrightarrow \neg (\phi \vee \psi )$

Conjunction versus implication:

$(\phi \wedge \psi )\to \neg (\phi \to \neg \psi )$
$(\phi \to \psi )\to \neg (\phi \wedge \neg \psi )$
$(\phi \wedge \neg \psi )\to \neg (\phi \to \psi )$
$(\phi \to \neg \psi )\leftrightarrow \neg (\phi \wedge \psi )$

Disjunction versus implication:

$(\phi \vee \psi )\to (\neg \phi \to \psi )$
$(\neg \phi \vee \psi )\to (\phi \to \psi )$
$\neg (\phi \to \psi )\to \neg (\neg \phi \vee \psi )$
$\neg (\phi \vee \psi )\leftrightarrow \neg (\neg \phi \to \psi )$

Universal versus existential quantification:

$(\forall x\ \phi (x))\to \neg (\exists x\ \neg \phi (x))$
$(\exists x\ \phi (x))\to \neg (\forall x\ \neg \phi (x))$
$(\exists x\ \neg \phi (x))\to \neg (\forall x\ \phi (x))$
$(\forall x\ \neg \phi (x))\leftrightarrow \neg (\exists x\ \phi (x))$

So, for example, "a or b" is a stronger statement than "if not a, then b", whereas these are classically interchangeable. On the other hand, "neither a nor b" is equivalent to "not a, and also not b".

If we include equivalence in the list of connectives, some of the connectives become definable from others:

$(\phi \leftrightarrow \psi )\leftrightarrow ((\phi \to \psi )\land (\psi \to \phi ))$
$(\phi \to \psi )\leftrightarrow ((\phi \lor \psi )\leftrightarrow \psi )$
$(\phi \to \psi )\leftrightarrow ((\phi \land \psi )\leftrightarrow \phi )$
$(\phi \land \psi )\leftrightarrow ((\phi \to \psi )\leftrightarrow \phi )$
$(\phi \land \psi )\leftrightarrow (((\phi \lor \psi )\leftrightarrow \psi )\leftrightarrow \phi )$

In particular, {∨, ↔, ⊥} and {∨, ↔, ¬} are complete bases of intuitionistic connectives.

As shown by Alexander Kuznetsov, either of the following defined connectives can serve the role of a sole sufficient operator for intuitionistic logic:^[2]

$((p\lor q)\land \neg r)\lor (\neg p\land (q\leftrightarrow r)),$
$p\to (q\land \neg r\land (s\lor t)).$

Semantics

The semantics are rather more complicated than for the classical case. A model theory can be given by Heyting algebras or, equivalently, by Kripke semantics.

Heyting algebra semantics

In classical logic, we often discuss the truth values that a formula can take. The values are usually chosen as the members of a Boolean algebra. The meet and join operations in the Boolean algebra are identified with the ∧ and ∨ logical connectives, so that the value of a formula of the form A ∧ B is the meet of the value of A and the value of B in the Boolean algebra. Then we have the useful theorem that a formula is a valid sentence of classical logic if and only if its value is 1 for every valuation—that is, for any assignment of values to its variables.

A corresponding theorem is true for intuitionistic logic, but instead of assigning each formula a value from a Boolean algebra, one uses values from a Heyting algebra, of which Boolean algebras are a special case. A formula is valid in intuitionistic logic if and only if it receives the value of the top element for any valuation on any Heyting algebra.

It can be shown that to recognize valid formulas, it is sufficient to consider a single Heyting algebra whose elements are the open subsets of the real line R.^[3] In this algebra, the ∧ and ∨ operations correspond to set intersection and union, and the value assigned to a formula A → B is int(A^C ∪ B), the interior of the union of the value of B and the complement of the value of A. The bottom element is the empty set ∅, and the top element is the entire line R. The negation ¬A of a formula A is (as usual) defined to be A → ∅. The value of ¬A then reduces to int(A^C), the interior of the complement of the value of A, also known as the exterior of A. With these assignments, intuitionistically valid formulas are precisely those that are assigned the value of the entire line.^[3]

For example, the formula ¬(A ∧ ¬A) is valid, because no matter what set X is chosen as the value of the formula A, the value of ¬(A ∧ ¬A) can be shown to be the entire line:

Value(¬(A ∧ ¬A)) =

int((Value(A ∧ ¬A))^C) =

int((Value(A) ∩ Value(¬A))^C) =

int((X ∩ int((Value(A))^C))^C) =

int((X ∩ int(X^C))^C)

A theorem of topology tells us that int(X^C) is a subset of X^C, so the intersection is empty, leaving:

int(∅^C) = int(R) = R

So the valuation of this formula is true, and indeed the formula is valid.

But the law of the excluded middle, A ∨ ¬A, can be shown to be invalid by letting the value of A be {y : y > 0 }. Then the value of ¬A is the interior of {y : y ≤ 0 }, which is {y : y < 0 }, and the value of the formula is the union of {y : y > 0 } and {y : y < 0 }, which is {y : y ≠ 0 }, not the entire line.

The interpretation of any intuitionistically valid formula in the infinite Heyting algebra described above results in the top element, representing true, as the valuation of the formula, regardless of what values from the algebra are assigned to the variables of the formula.^[3] Conversely, for every invalid formula, there is an assignment of values to the variables that yields a valuation that differs from the top element.^[4]^[5] No finite Heyting algebra has both these properties.^[3]

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Kripke semantics

Building upon his work on semantics of modal logic, Saul Kripke created another semantics for intuitionistic logic, known as Kripke semantics or relational semantics ^[6].

Relation to other logics

Intutionistic logic is related by duality to a paraconsistent logic known as Brazilian, anti-intuitionistic or dual-intuitionistic logic^[7].

The subsystem of intuitionistic logic with the FALSE axiom removed is known as minimal logic.

انظر أيضاً

ملاحظات

^ Proof Theory by G. Takeuti, ISBN0444104925
^ Alexander Chagrov, Michael Zakharyaschev, Modal Logic, vol. 35 of Oxford Logic Guides, Oxford University Press, 1997, pp. 58–59.
^ ^أ ^ب ^ت ^ث Sørensen, Morten Heine B (2006). Lectures on the Curry-Howard Isomorphism. Studies in Logic and the Foundations of Mathematics. Elsevier. p. 42. ISBN 0444520775. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
^ Alfred Tarski, Der Aussagenkalkül und die Topologie, Fundamenta Mathematicae 31 (1938), 103–134. [1]
^ Rasiowa, Helena (1963). The Mathematics of Metamathematics. Monografie matematyczne. Warsaw: Państwowe Wydawn. Naukowe. pp. 385–386. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
^ Intuitionistic Logic. Written by Joan Moschovakis. Published in Stanford Encyclopedia of Philosophy.
^ Aoyama, Hiroshi (2004). "LK, LJ, Dual Intuitionistic Logic, and Quantum Logic". Notre Dame Journal of Formal Logic. 45 (4): 193–213. doi:10.1305/ndjfl/1099238445.

مراجع

Van Dalen, Dirk, 2001, "Intuitionistic Logic", in Goble, Lou, ed., The Blackwell Guide to Philosophical Logic. Blackwell.
Morten H. Sørensen, Paweł Urzyczyn, 2006, Lectures on the Curry-Howard Isomorphism (chapter 2: "Intuitionistic Logic"). Studies in Logic and the Foundations of Mathematics vol. 149, Elsevier.
W. A. Carnielli (with A. B.M. Brunner)."Anti-intuitionism and paraconsistency". Journal of Applied Logic Volume 3, Issue 1, March 2005, pages 161-184.

وصلات خارجية

Stanford Encyclopedia of Philosophy: "Intuitionistic Logic" -- by Joan Moschovakis.

[1] Proof Theory by G. Takeuti, ISBN0444104925

[2] Alexander Chagrov, Michael Zakharyaschev, Modal Logic, vol. 35 of Oxford Logic Guides, Oxford University Press, 1997, pp. 58–59.

[S-U-3] أ ^ب ^ت ^ث Sørensen, Morten Heine B (2006). Lectures on the Curry-Howard Isomorphism. Studies in Logic and the Foundations of Mathematics. Elsevier. p. 42. ISBN 0444520775. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[4] Alfred Tarski, Der Aussagenkalkül und die Topologie, Fundamenta Mathematicae 31 (1938), 103–134. [1]

[R-S-5] Rasiowa, Helena (1963). The Mathematics of Metamathematics. Monografie matematyczne. Warsaw: Państwowe Wydawn. Naukowe. pp. 385–386. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[Mosch-IntLog-6] Intuitionistic Logic. Written by Joan Moschovakis. Published in Stanford Encyclopedia of Philosophy.

[7] Aoyama, Hiroshi (2004). "LK, LJ, Dual Intuitionistic Logic, and Quantum Logic". Notre Dame Journal of Formal Logic. 45 (4): 193–213. doi:10.1305/ndjfl/1099238445.

[1]

[2]

[3]

[4]

[5]

[6]

[7]