Výroková logika

Výroková logika , výroková logika ( lat. propositio - „výrok“ [1] ) nebo výrokový počet [2] , také logika nultého řádu , je úsek symbolické logiky , který studuje složité výroky tvořené z jednoduchých a jejich vztahy. Na rozdíl od predikátové logiky výroková logika nezohledňuje vnitřní strukturu jednoduchých výroků, pouze zohledňuje, jakými spojkami a v jakém pořadí se jednoduché výroky spojují do složitých [3] .

Přes svůj význam a široký záběr je výroková logika nejjednodušší logikou a má velmi omezené prostředky pro studium úsudků [2] .

Jazyk výrokové logiky

Jazyk výrokové logiky (výrokový jazyk [4] ) je formalizovaný jazyk určený k analýze logické struktury složitých výroků [1] .

Syntaxe výrokové logiky

Počáteční symboly nebo abeceda jazyka výrokové logiky [5] :

sada výrokových proměnných (výrokových písmen):

Var=\{p,q,r...\}

výrokové spojky (logické spojky):

Symbol	Význam
$\neg$	Negativní znamení
$\přistát$ nebo &	Znak spojky („logický AND“)
$\vee$	Znak disjunkce ("logické OR")
$\šipka doprava$	implikační znak

Pomocné znaky: levá závorka (, pravá závorka ). [6]

Výrokové formule

Výroková formule je slovo v jazyce výrokové logiky [7] , tedy konečná posloupnost abecedních znaků sestavená podle níže uvedených pravidel a tvořící ucelený výraz v jazyce výrokové logiky [1] .

Induktivní definice množiny výrokových logických formulí : [4] [1] $fm$

If , then (každá výroková proměnná je formule); $p\in Var$ $p\in Fm$
jestliže je vzorec, pak je také vzorec; $A$ $\neg A$
jestliže a jsou libovolné formule, pak , , jsou také formule. $A$ $B$ $(A\klín B)$ $(A\vee B)$ $(A\do B)$

V jazyce výrokové logiky nejsou žádné jiné formule.

Backus-Naurova forma , která definuje syntaxi výrokové logiky, má zápis:

$A::=p\;|\;(\neg A)\;|\;(A\land A)\;|\;(A\nebo A)\;|\;(A\to A )$

Velká latinská písmena a další, která se používají při definici vzorce, nepatří do jazyka výrokové logiky, ale do jeho metajazyka, tedy jazyka, který se používá k popisu samotného jazyka výrokové logiky. Výrazy obsahující metalety a další nejsou výrokové formule, ale schémata formulí. Například výraz je schéma, které vyhovuje vzorcům a dalším [1] . $A$ $B$ $\neg A$ $(A\do B)$ $(A\klín B)$ $(p\klín q)$ $(p\wedge (r\vee s))$

S ohledem na libovolnou posloupnost abecedních znaků jazyka výrokové logiky lze rozhodnout, zda se jedná o formuli nebo ne. Pokud lze tuto sekvenci sestavit v souladu s odstavci. 1-3 definice vzorců, pak je to vzorec, pokud ne, pak to není vzorec [1] .

Konvence závorek

Vzhledem k tomu, že ve vzorcích sestavených z definice je příliš mnoho závorek, které někdy nejsou nutné pro jednoznačné pochopení vzorce, existuje konvence o závorkách , podle které lze některé závorky vynechat. Záznamy s vynechanými závorkami se obnovují podle následujících pravidel.

Pokud jsou vnější závorky vynechány, jsou obnoveny.
Pokud existují dvě spojky nebo disjunkce vedle sebe (například ), pak se do závorek nejprve uzavře levá část (to znamená, že tyto spojky jsou ponechány asociativní ). $A\klín B\klín C$
Pokud jsou poblíž různé svazky, pak jsou závorky uspořádány podle priorit: a (od nejvyšší po nejnižší). $\neg ,\klín ,\vee$ $\na$

Když mluvíme o délce vzorce , mají na mysli délku implikovaného (obnoveného) vzorce, nikoli zkrácený zápis.

Například: položka znamená vzorec a její délka je 12. $A\vee B\wedge\neg C$ $(A\vee (B\wedge (\neg C)))$

Formalizace a interpretace

Jako každý jiný formalizovaný jazyk lze jazyk výrokové logiky považovat za soubor všech slov vytvořených pomocí abecedy tohoto jazyka [8] . Na jazyk výrokové logiky lze pohlížet jako na soubor všemožných výrokových formulí [4] . Věty přirozeného jazyka lze přeložit do symbolického jazyka výrokové logiky, kde se bude jednat o formule výrokové logiky. Proces převodu výroku do formule v jazyce výrokové logiky se nazývá formalizace. Opačný proces dosazování konkrétních výroků za výrokové proměnné se nazývá interpretace [9] .

Axiomy a pravidla odvození formálního systému výrokové logiky

Jednou z možných variant ( Hilbertovské ) axiomatizace výrokové logiky je následující systém axiomů:

$A_{1}:A\šipka doprava (B\šipka doprava A)$ ;

$A_{2}:(A\arrowarrow (B\rightarrow C))\rightarrow ((A\rightarrow B)\rightarrow (A\rightarrow C))$ ;

$A_{3}:A\klín B\šipka doprava A$ ;

$A_{4}:A\klín B\šipka doprava B$ ;

$A_{5}:A\šipka doprava (B\šipka doprava (A\klín B))$ ;

$A_{6}:A\šipka doprava (A\vee B)$ ;

$A_{7}:B\šipka doprava (A\vee B)$ ;

$A_{8}:(A\šipka vpravo C)\šipka vpravo ((B\šipka vpravo C)\šipka vpravo ((A\vee B)\šipka vpravo C))$ ;

$A_{9}:\neg A\šipka doprava (A\šipka doprava B)$ ;

$A_{{10}}:(A\šipka doprava B)\šipka doprava ((A\šipka doprava \neg B)\šipka doprava \neg A)$ ;

$A_{{11}}:A\vee \neg A$ .

s jediným pravidlem:

${\frac {A\quad (A\rightarrow B)}{B}}$ ( modus ponens )

Věta o správnosti výrokového počtu říká, že všechny výše uvedené axiómy jsou tautologie a pomocí pravidla modus ponens lze z pravdivých výroků získat pouze pravdivé výroky. Důkaz této věty je triviální a redukuje se na přímé ověření. Mnohem zajímavější je fakt, že všechny ostatní tautologie lze získat z axiomů pomocí pravidla vyvozování – jde o tzv. větu o úplnosti výrokové logiky.

Pravdivostní tabulky základních operací

Hlavním úkolem výrokové logiky je stanovit pravdivostní hodnotu vzorce, pokud jsou dány pravdivostní hodnoty proměnných v něm obsažených. Pravdivostní hodnota formule je v tomto případě určena induktivně (s kroky, které byly použity při konstrukci formule) pomocí pravdivostních tabulek spojek [10] .

Nechť je množina všech pravdivostních hodnot a nechť je množina výrokových proměnných. Potom lze interpretaci (nebo model) jazyka výrokové logiky reprezentovat jako mapování $\mathbb {B}$ $\{0,1\}$ $Var$

M\colon Var\to \mathbb {B}

který spojuje každou výrokovou proměnnou s pravdivostní hodnotou [10] . $p$ $M(p)$

Negační skóre je dáno tabulkou: $\neg str$

$p$	$\neg str$
$0$	$jeden$
$jeden$	$0$

Hodnoty dvojitých logických spojek (implikace), (disjunkce) a (konjunkce) jsou definovány takto: $\šipka doprava$ $\vee$ $\klín$

$p$	$q$	$p\rightarrow q$	$p\klín q$	$p\vee q$
$0$	$0$	$jeden$	$0$	$0$
$0$	$jeden$	$jeden$	$0$	$jeden$
$jeden$	$0$	$0$	$0$	$jeden$
$jeden$	$jeden$	$jeden$	$jeden$	$jeden$

Identicky pravdivé formule (tautologie)

Vzorec je stejně pravdivý , pokud platí pro jakékoli hodnoty jeho proměnných (tedy pro jakoukoli interpretaci) [11] . Následuje několik dobře známých příkladů identicky pravdivých výrokových logických formulí:

de Morganovy zákony :

\neg (p\vee q)\leftrightarrow (\neg p\wedge \neg q)

;

\neg (p\wedge q)\leftrightarrow (\neg p\vee \neg q)

;

protikladný zákon :

(p\šipka doprava q)\šipka doleva doprava (\neg q\šipka doprava \neg p)

;

Absorpční zákony :

p\vee (p\klín q)\šipka vlevo vpravo p

;

p\klín (p\vee q)\šipka doleva p

;

distribuční zákony :

p\wedge (q\vee r)\leftrightarrow (p\wedge q)\vee (p\wedge r)

;

p\vee (q\wedge r)\leftrightarrow (p\vee q)\wedge (p\vee r)

Viz také

Poznámky

↑ 1 2 3 4 5 6 Chupakhin, Brodsky, 1977 , str. 203-205.
↑ 1 2 Kondakov, 1971 , článek „Propoziční počet“.
↑ NFE, 2010 .
↑ 1 2 3 Gerasimov, 2011 , str. 13.
↑ Voishvillo, Degtyarev, 2001 , str. 91-94.
↑ Ershov Yu. L. , Palyutin E. A. Matematická logika. - M. , Nauka , 1979. - str. 24
↑ Edelman, 1975 , str. 130.
↑ Edelman, 1975 , str. 128.
↑ Igoshin, 2008 , str. 32.
↑ 1 2 Gerasimov, 2011 , str. 17-19.
↑ Gerasimov, 2011 , str. 19.

Literatura

Kondakov N. I. Logický slovník / Gorsky D. P. - M . : Nauka, 1971. - 656 s.
Edelman S. L. Matematická logika. - M . : Vyšší škola, 1975. - 176 s.
Chupakhin I. Ya., Brodsky IN Formální logika. - Leningrad: Leningrad University Publishing House , 1977. - 357 s.
Voishvillo E. K. , Degtyarev M. G. Logic. - M. : VLADOS-PRESS, 2001. - 528 s. — ISBN 5-305-00001-7 .
Igoshin VI Matematická logika a teorie algoritmů. - 2. vyd., stereotyp .. - M . : Vydavatelské centrum "Akademie", 2008. - 448 s. - ISBN 978-5-7695-4593-1 .
A. S. Karpenko. Výroková logika // Nová filozofická encyklopedie : ve 4 svazcích / předchozí. vědecky vyd. rada V. S. Stepina . — 2. vyd., opraveno. a doplňkové - M . : Myšlenka , 2010. - 2816 s.
Gerasimov AS Kurz matematické logiky a teorie vyčíslitelnosti . - Petrohrad. : Nakladatelství "LEMA", 2011. - 284 s. - ISBN 978-5-98709-292-7 .

Slovníky a encyklopedie	Velký Rus Britannica (online) Britannica (online) Universalis
V bibliografických katalozích	GND : 4136098-9 NKC : ph127455

Logika

Filosofie • Sémantika • Syntaxe • Historie

Logické skupiny

klasická logika	Aristotelská logika výroková logika Logika prvního řádu Logika druhého řádu logika vyššího řádu
matematická logika	teorie množin Teorie modelu Teorie vyčíslitelnosti Důkazová teorie a konstruktivní matematika Lineární logika formální systém přirozený závěr Sekvenční počet Algebra logiky Relevantní logika Deontická logika intuicionistická logika Lambekův počet
Neklasická logika	intuicionismus fuzzy logika Substrukturální logika logika Popisná logika Vícehodnotová logika Logická syntéza Závazná logika Časová logika Modální logika ( Hybrid logic ) epistemická logika
Filosofická logika	Kritické myšlení neformální logika deduktivní uvažování

Komponenty

Seznam booleovských symbolů