حسبان القضايا

في المنطق الرياضي، منطق القضايا أو منطق الجمل ( Propositional calculus أو sentential calculus ) عبارة عن نظام استنتاج شكلي تتألف صيغه الذرية من متغيرات قضايا propositional variable (عبارات) و هذا ما يميزه عن المنطق الإسنادي predicate calculus الذي تكون صيغه الذرية عبارة عن دوال قضايا propositional functions أما المنطق الطوري الذي يتعامل مع قضايا محتملة .

منطق القضايا أو حسبان القضايا ( Propositional calculus) ينظر إلى الجملة اللغوية المركبة بصفتها قضية منطقية, يقوم بتفكيكها إلى مقولات منطقية بسيطة من قبيل "و"، "أو"، "إذا"، "ومن ثم", وذلك وفقا للمبدأ الذى أرساه فريجه فيلسوف اللغة والذي على أساسه يحسب معنى الجملة على أساس كونه دالة لمعاني العناصر المكونة لها.

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

Basic and derived argument forms

Name	Sequent	Description
Modus Ponens	$((p\to q)\land p)\vdash q$	If $p$ then $q$ ; $p$ ; therefore $q$
Modus Tollens	$((p\to q)\land \neg q)\vdash \neg p$	If $p$ then $q$ ; not $q$ ; therefore not $p$
Hypothetical Syllogism	$((p\to q)\land (q\to r))\vdash (p\to r)$	If $p$ then $q$ ; if $q$ then $r$ ; therefore, if $p$ then $r$
Disjunctive Syllogism	$((p\lor q)\land \neg p)\vdash q$	Either $p$ or $q$ , or both; not $p$ ; therefore, $q$
Constructive Dilemma	$((p\to q)\land (r\to s)\land (p\lor r))\vdash (q\lor s)$	If $p$ then $q$ ; and if $r$ then $s$ ; but $p$ or $r$ ; therefore $q$ or $s$
Destructive Dilemma	$((p\to q)\land (r\to s)\land (\neg q\lor \neg s))\vdash (\neg p\lor \neg r)$	If $p$ then $q$ ; and if $r$ then $s$ ; but not $q$ or not $s$ ; therefore not $p$ or not $r$
Bidirectional Dilemma	$((p\to q)\land (r\to s)\land (p\lor \neg s))\vdash (q\lor \neg r)$	If $p$ then $q$ ; and if $r$ then $s$ ; but $p$ or not $s$ ; therefore $q$ or not $r$
Simplification	$(p\land q)\vdash p$	$p$ and $q$ are true; therefore $p$ is true
Conjunction	$p,q\vdash (p\land q)$	$p$ and $q$ are true separately; therefore they are true conjointly
Addition	$p\vdash (p\lor q)$	$p$ is true; therefore the disjunction ( $p$ or $q$ ) is true
Composition	$((p\to q)\land (p\to r))\vdash (p\to (q\land r))$	If $p$ then $q$ ; and if $p$ then $r$ ; therefore if $p$ is true then $q$ and $r$ are true
De Morgan's Theorem (1)	$\neg (p\land q)\vdash (\neg p\lor \neg q)$	The negation of ( $p$ and $q$ ) is equiv. to (not $p$ or not $q$ )
De Morgan's Theorem (2)	$\neg (p\lor q)\vdash (\neg p\land \neg q)$	The negation of ( $p$ or $q$ ) is equiv. to (not $p$ and not $q$ )
Commutation (1)	$(p\lor q)\vdash (q\lor p)$	( $p$ or $q$ ) is equiv. to ( $q$ or $p$ )
Commutation (2)	$(p\land q)\vdash (q\land p)$	( $p$ and $q$ ) is equiv. to ( $q$ and $p$ )
Commutation (3)	$(p\leftrightarrow q)\vdash (q\leftrightarrow p)$	( $p$ is equiv. to $q$ ) is equiv. to ( $q$ is equiv. to $p$ )
Association (1)	$(p\lor (q\lor r))\vdash ((p\lor q)\lor r)$	$p$ or ( $q$ or $r$ ) is equiv. to ( $p$ or $q$ ) or $r$
Association (2)	$(p\land (q\land r))\vdash ((p\land q)\land r)$	$p$ and ( $q$ and $r$ ) is equiv. to ( $p$ and $q$ ) and $r$
Distribution (1)	$(p\land (q\lor r))\vdash ((p\land q)\lor (p\land r))$	$p$ and ( $q$ or $r$ ) is equiv. to ( $p$ and $q$ ) or ( $p$ and $r$ )
Distribution (2)	$(p\lor (q\land r))\vdash ((p\lor q)\land (p\lor r))$	$p$ or ( $q$ and $r$ ) is equiv. to ( $p$ or $q$ ) and ( $p$ or $r$ )
Double Negation	$p\vdash \neg \neg p$ and $\neg \neg p\vdash p$	$p$ is equivalent to the negation of not $p$
Transposition	$(p\to q)\vdash (\neg q\to \neg p)$	If $p$ then $q$ is equiv. to if not $q$ then not $p$
Material Implication	$(p\to q)\vdash (\neg p\lor q)$	If $p$ then $q$ is equiv. to not $p$ or $q$
Material Equivalence (1)	$(p\leftrightarrow q)\vdash ((p\to q)\land (q\to p))$	( $p$ iff [ك‍] $q$ ) is equiv. to (if $p$ is true then $q$ is true) and (if $q$ is true then $p$ is true)
Material Equivalence (2)	$(p\leftrightarrow q)\vdash ((p\land q)\lor (\neg p\land \neg q))$	( $p$ iff [ك‍] $q$ ) is equiv. to either ( $p$ and $q$ are true) or (both $p$ and $q$ are false)
Material Equivalence (3)	$(p\leftrightarrow q)\vdash ((p\lor \neg q)\land (\neg p\lor q))$	( $p$ iff [ك‍] $q$ ) is equiv to., both ( $p$ or not $q$ is true) and (not $p$ or $q$ is true)
Exportation^[1]	$((p\land q)\to r)\vdash (p\to (q\to r))$	from (if $p$ and $q$ are true then $r$ is true) we can prove (if $q$ is true then $r$ is true, if $p$ is true)
Importation	$(p\to (q\to r))\vdash ((p\land q)\to r)$	If $p$ then (if $q$ then $r$ ) is equivalent to if $p$ and $q$ then $r$
Tautology (1)	$p\vdash (p\lor p)$	$p$ is true is equiv. to $p$ is true or $p$ is true
Tautology (2)	$p\vdash (p\land p)$	$p$ is true is equiv. to $p$ is true and $p$ is true
Tertium non datur (Law of Excluded Middle)	$\vdash (p\lor \neg p)$	$p$ or not $p$ is true
Law of Non-Contradiction	$\vdash \neg (p\land \neg p)$	$p$ and not $p$ is false, is a true statement

Proofs in propositional calculus

One of the main uses of a propositional calculus, when interpreted for logical applications, is to determine relations of logical equivalence between propositional formulas. These relationships are determined by means of the available transformation rules, sequences of which are called derivations or proofs.

In the discussion to follow, a proof is presented as a sequence of numbered lines, with each line consisting of a single formula followed by a reason or justification for introducing that formula. Each premise of the argument, that is, an assumption introduced as an hypothesis of the argument, is listed at the beginning of the sequence and is marked as a "premise" in lieu of other justification. The conclusion is listed on the last line. A proof is complete if every line follows from the previous ones by the correct application of a transformation rule. (For a contrasting approach, see proof-trees).

Example of a proof

To be shown that $A \to A$ .
One possible proof of this (which, though valid, happens to contain more steps than are necessary) may be arranged as follows:

Example of a Proof
Number	Formula	Reason
1	$A$	premise
2	$A\lor A$	From (1) by disjunction introduction
3	$(A\lor A)\land A$	From (1) and (2) by conjunction introduction
4	$A$	From (3) by conjunction elimination
5	$A\vdash A$	Summary of (1) through (4)
6	$\vdash A\to A$	From (5) by conditional proof

Interpret $A\vdash A$ as "Assuming $A$ , infer $A$ ". Read $\vdash A\to A$ as "Assuming nothing, infer that $A$ implies $A$ ", or "It is a tautology that $A$ implies $A$ ", or "It is always true that $A$ implies $A$ ".

Alternative calculus

It is possible to define another version of propositional calculus, which defines most of the syntax of the logical operators by means of axioms, and which uses only one inference rule.

Axioms

Let $φ$ , $χ$ , and $ψ$ stand for well-formed formulas. (The well-formed formulas themselves would not contain any Greek letters, but only capital Roman letters, connective operators, and parentheses.) Then the axioms are as follows:

Axioms
Name	Axiom Schema	Description
THEN-1	$\phi \to (\chi \to \phi )$	Add hypothesis $χ$ , implication introduction
THEN-2	$(\phi \to (\chi \to \psi ))\to ((\phi \to \chi )\to (\phi \to \psi ))$	Distribute hypothesis $\phi$ over implication
AND-1	$\phi \land \chi \to \phi$	Eliminate conjunction
AND-2	$\phi \land \chi \to \chi$
AND-3	$\phi \to (\chi \to (\phi \land \chi ))$	Introduce conjunction
OR-1	$\phi \to \phi \lor \chi$	Introduce disjunction
OR-2	$\chi \to \phi \lor \chi$
OR-3	$(\phi \to \psi )\to ((\chi \to \psi )\to (\phi \lor \chi \to \psi ))$	Eliminate disjunction
NOT-1	$(\phi \to \chi )\to ((\phi \to \neg \chi )\to \neg \phi )$	Introduce negation
NOT-2	$\phi \to (\neg \phi \to \chi )$	Eliminate negation
NOT-3	$\phi \lor \neg \phi$	Excluded middle, classical logic
IFF-1	$(\phi \leftrightarrow \chi )\to (\phi \to \chi )$	Eliminate equivalence
IFF-2	$(\phi \leftrightarrow \chi )\to (\chi \to \phi )$
IFF-3	$(\phi \to \chi )\to ((\chi \to \phi )\to (\phi \leftrightarrow \chi ))$	Introduce equivalence

Axiom THEN-2 may be considered to be a "distributive property of implication with respect to implication."
Axioms AND-1 and AND-2 correspond to "conjunction elimination". The relation between AND-1 and AND-2 reflects the commutativity of the conjunction operator.
Axiom AND-3 corresponds to "conjunction introduction."
Axioms OR-1 and OR-2 correspond to "disjunction introduction." The relation between OR-1 and OR-2 reflects the commutativity of the disjunction operator.
Axiom NOT-1 corresponds to "reductio ad absurdum."
Axiom NOT-2 says that "anything can be deduced from a contradiction."
Axiom NOT-3 is called "tertium non datur" (Latin: "a third is not given") and reflects the semantic valuation of propositional formulas: a formula can have a truth-value of either true or false. There is no third truth-value, at least not in classical logic. Intuitionistic logicians do not accept the axiom NOT-3.

Inference rule

The inference rule is modus ponens:

\phi ,\ \phi \to \chi \vdash \chi

.

Meta-inference rule

Let a demonstration be represented by a sequence, with hypotheses to the left of the turnstile and the conclusion to the right of the turnstile. Then the deduction theorem can be stated as follows:

If the sequence

\phi _{1},\ \phi _{2},\ ...,\ \phi _{n},\ \chi \vdash \psi

has been demonstrated, then it is also possible to demonstrate the sequence

\phi _{1},\ \phi _{2},\ ...,\ \phi _{n}\vdash \chi \to \psi

.

This deduction theorem (DT) is not itself formulated with propositional calculus: it is not a theorem of propositional calculus, but a theorem about propositional calculus. In this sense, it is a meta-theorem, comparable to theorems about the soundness or completeness of propositional calculus.

On the other hand, DT is so useful for simplifying the syntactical proof process that it can be considered and used as another inference rule, accompanying modus ponens. In this sense, DT corresponds to the natural conditional proof inference rule which is part of the first version of propositional calculus introduced in this article.

The converse of DT is also valid:

If the sequence

\phi _{1},\ \phi _{2},\ ...,\ \phi _{n}\vdash \chi \to \psi

has been demonstrated, then it is also possible to demonstrate the sequence

\phi _{1},\ \phi _{2},\ ...,\ \phi _{n},\ \chi \vdash \psi

in fact, the validity of the converse of DT is almost trivial compared to that of DT:

If

\phi _{1},\ ...,\ \phi _{n}\vdash \chi \to \psi

then

1:

\phi _{1},\ ...,\ \phi _{n},\ \chi \vdash \chi \to \psi

2:

\phi _{1},\ ...,\ \phi _{n},\ \chi \vdash \chi

and from (1) and (2) can be deduced

3:

\phi _{1},\ ...,\ \phi _{n},\ \chi \vdash \psi

by means of modus ponens, Q.E.D.

The converse of DT has powerful implications: it can be used to convert an axiom into an inference rule. For example, the axiom AND-1,

\vdash \phi \wedge \chi \to \phi

can be transformed by means of the converse of the deduction theorem into the inference rule

\phi \wedge \chi \vdash \phi

which is conjunction elimination, one of the ten inference rules used in the first version (in this article) of the propositional calculus.

Example of a proof

The following is an example of a (syntactical) demonstration, involving only axioms THEN-1 and THEN-2:

Prove: $A\to A$ (Reflexivity of implication).

البرهان:

$(A\to ((B\to A)\to A))\to ((A\to (B\to A))\to (A\to A))$
Axiom THEN-2 with $\phi =A,\chi =B\to A,\psi =A$
$A\to ((B\to A)\to A)$
Axiom THEN-1 with $\phi =A,\chi =B\to A$
$(A\to (B\to A))\to (A\to A)$
From (1) and (2) by modus ponens.
$A\to (B\to A)$
Axiom THEN-1 with $\phi =A,\chi =B$
$A\to A$
From (3) and (4) by modus ponens.

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

انظر أيضا

Higher logical levels

مواضيع ذات صلة

المصادر

د. نبيل علي و د. نادية حجازي. الفجوة الرقمية، سلسلة عالم المعرفة- غشت -2005 العدد 318. ص. 319.

روابط خارجية

قالب:Classical logic قالب:Formal Fallacy

^ Toida, Shunichi (2 August 2009). "Proof of Implications". CS381 Discrete Structures/Discrete Mathematics Web Course Material. Department Of Computer Science, Old Dominion University. Retrieved 10 March 2010.

[1] Toida, Shunichi (2 August 2009). "Proof of Implications". CS381 Discrete Structures/Discrete Mathematics Web Course Material. Department Of Computer Science, Old Dominion University. Retrieved 10 March 2010.

[1]