Tautologi (logik)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 9. november 2018; checks kræver 4 redigeringer .

En tautologi i logik er en identisk sand proposition .

Det faktum , at formel A er en tautologi, er angivet med . Hver logisk beregning har sit eget sæt af tautologier. $\vDash A$

Konstruktion af tautologier

For at finde ud af, om en given formel er en tautologi, er der en enkel måde i propositionalgebra - at bygge en sandhedstabel . I propositionalregning er tautologier aksiomer (mere præcist aksiomskemaer), såvel som alle formler, der kan opnås fra kendte tautologier ved hjælp af givne inferensregler (oftest er disse Modus ponens og substitutionsreglen ). At kontrollere, om en given formel i propositionsregningen er en tautologi, er mere kompliceret og afhænger også af systemet af aksiomer og tilgængelige slutningsregler.
Problemet med at afgøre, om en vilkårlig formel i prædikatlogik er en tautologi, er algoritmisk uafgørligt.

Eksempler på tautologier

Tautologier af propositional calculus (og propositionalgebra)

$A\højrepil A$ ("Fra A følger A ") - loven om identitet
$(A)\lor (\likke A)$ (" A or not- A ") - loven om den udelukkede midterste
$\neg (P\land \neg P)$ - loven om negation af modsigelse
$\neg \neg P\rightarrow P$ - lov om dobbelt negation
$(P\leftrightarrow Q)\leftrightarrow (\neg Q\leftrightarrow \neg P)$ - lov om modsætninger
$(P\land Q)\leftrightarrow (Q\land P)$ — kommutativitet af konjunktion
$(P\lor Q)\leftrightarrow (Q\lor P)$ — kommutativitet af disjunktion
$[(P\land Q)\land R]\venstrehøjrepil [P\land (Q\land R)]$ - associativitet af konjunktionen
$[(P\lor Q)\lor R]\leftrightarrow [P\lor (Q\lor R)]$ - disjunktionsassociativitet
$(P\land (P\højrepil Q))\højrepil Q$
$A\højrepil (B\højrepil A)$ (sandheden følger af hvad som helst)
$(A\højrepil B)\kile (B\højrepil C)\højrepil (A\højrepil C)$ - kæderegel
$(A\vee B)\kile C\venstrehøjrepil (A\kile C)\vee (B\kile C)$ — fordeling af konjunktion med hensyn til disjunktion
$(A\wedge B)\vee C\leftrightarrow (A\vee C)\wedge (B\vee C)$ — fordeling af disjunktion med hensyn til konjunktion
$(P\land P)\leftrightarrow P$ - idempotent konjunktion
$(P\lor P)\leftrightarrow P$ — idempotens af disjunktionen
$(P\rightarrow Q)\leftrightarrow (\neg P\eller Q)$
$(P\leftrightarrow Q)\leftrightarrow ((P\leftrightarrow Q)\land (Q\leftrightarrow P))$
$(P\land (Q\lor P)\leftrightarrow P$ - den første lov om absorption
$(P\lor (Q\land P)\leftrightarrow P$ - den anden lov om absorption
$\neg (A\kile B)\venstrehøjrepil (\neg A\vee \neg B)$ - De Morgans første lov
$\neg (A\vee B)\venstrehøjrepil (\neg A\kile \neg B)$ - De Morgans anden lov
$(A\højrepil B)\venstrepil (\neg B\højrepil \neg A)$ - lov om modstilling
Hvis og er formler, så ( substitutionsregel ) $\vDash F(X_{1},...,X_{n})$ $H_{1},...,H_{n}$ $\vDash F(H_{1},...,H_{n})$

Tautologier af prædikatregningen (og prædikatalgebraen)

Hvis det er en tautologi i propositionalregning og er prædikater, så er en tautologi i prædikatregning $F(X_{1},...,X_{n})$ $P_{1},...,P_{n}$ $F(P_{1},...,P_{n})$
$\neg (\forall x)P(x)\venstrehøjrepil (\eksisterer x)\neg P(x)$

$\neg (\eksisterer x)P(x)\venstrehøjrepil (\forall x)\neg P(x)$ ( de Morgans lov )

$(\forall x)(P(x)\wedge Q(x))\venstrehøjrepil (\forall x)P(x)\kile (\forall x)Q(x)$
$(\eksisterer x)(P(x)\vee Q(x))\venstrehøjrepil (\eksisterer x)P(x)\vee (\eksisterer x)Q(x)$
$Q\venstrehøjrepil (\eksisterer x)Q$
$Q\venstrehøjrepil (\forall x)Q$
$(\foralt x)P(x)\højrepil P(y)$
$P(y)\højrepil (\eksisterer x)P(x)$
$(\foralt x)(\foralt y)P(x,y)\venstrehøjrepil (\foralt y)(\foralt x)P(x,y)$
$(\eksisterer x)(\eksisterer y)P(x,y)\venstrehøjrepil (\eksisterer y)(\eksisterer x)P(x,y)$
$(\eksisterer x)(\for alt y)P(x,y)\højrepil (\foralt y)(\eksisterer x)P(x,y)$

Se også

Noter

Litteratur

V. Igoshin, Matematisk logik og teori om algoritmer. - Akademiet, 2008.
Karpov Yu. G. "Theory of Automata". - P., 2003. - S. 49, 60.
Mendelsohn E. "Introduktion til matematisk logik". - M. Nauka, 1971.
V. Igoshin «Problembog-værksted om matematisk logik». - Oplysning, 1986.