Formula propozicionális algebra

1. Meghatározás és példák a képletek

A rendszer segítségével a logikai műveletek tárgyalt az előző részben, tudjuk, alapján egy egyszerű nyilatkozatot, hogy egy új, bonyolultabb. Például alapján nyilatkozatok R. „Puskin - magyar költő” Q „Gauss - német matematikus”, R. A „”, akkor egy új nyilatkozat :. „Ha Puskin - magyar költő és Gauss - német matematikus, a” Az új nyilatkozat formájában van

(1) kifejezés, eltekintve a konkrét jelentése Q. R. R. nyilatkozatok lehet tekinteni, mint egy program, amely lehetővé teszi, kezdve minden olyan kijelentést R. K. R. építeni az új megnyilatkozást. Hogy az ilyen rendszerek és lesz érdekelt minket ma. Ezek az úgynevezett propozicionális algebra. Persze, hozzá vannak szokva, hogy egy kissé eltérő értelmezése a „képlet”; formula számunkra - ez az egyenlőség a típus (képlet terület egy kör), (képlet kifejezi a Pitagorasz-tétel), stb Mindazonáltal a kifejezés is lehet tekinteni, mint egyfajta formula - .. formula építésére összetett egyszerűbb nyilatkozatokat.

Mielőtt általános meghatározását képlet propozicionális algebra, akkor a következőkben állapodnak meg. Propozicionális változók hívjuk ezeket a változókat, amely akár a következő értékkel külön nyilatkozatot. Mi kell érteni ezeket a változókat nagybetűvel X, Y, Z, U, V .. vagy ugyanaz betűket indexek: Bemutatjuk, továbbá két konkrétabb és propozicionális változók és A; helyett az első, akkor helyettesítheti bármilyen igaz állítás, hanem egy másik - hamis.

Teljes leírás a koncepció képletek, így a következő megállapodások:

1 °. Minden egyes propozicionális változó egy általános képletű.

2 °. Ha - két képlet, ezt a kifejezést. Ők is képleteket.

3 °. Ő nincs más képletek, kivéve azok, amelyek alkalmazásával kapott véges számú alkalommal igénypontok 1 ° és 2 °.

Például, a képlet a következő kifejezések: stb

A jobb áttekinthetőség érdekében megemlítjük példái kifejezések, amelyek nem képleteket.

Az a tény, hogy nem ismerjük a képlet az utolsó írásos kifejezések okozhat eleinte rejtélyes. Azonban, ha követi a fenti meghatározás, a kifejezés - nem egy formula; lesz egy általános képletű, hiányzik belőle merevítők, mivel szerint n. ° 2, a képlet egy kifejezésnek kell állnia. helyette. A különbség a kifejezéseket és válik különösen jelentős, ha tartalmazzák a kifejezést egy résztvevő komponens egy bonyolultabb képlet: összehasonlítani, például expressziós. Ez egy általános képletű a (nem képlet); nem világos, hogyan kell értelmezni a második kifejezés (amely művelet követi: miután vagy után?).

Így, a felvétel külső zárójelben a képlet esetben választható, kivéve, ha ez a képlet nem egy olyan komponenst tartalmaznak egy bonyolultabb képlettel.

2. Az igazság asztalok képletek

Tekintsünk képletű propozicionális algebra, például. Jelöljük ezt a képlet a F (X, Y, Z). Az igazság érték a F képletű (X, Y, Z) teljesen határozza meg az igazság a változók értékeit X, Y, Z. Ez a körülmény lehetővé teszi, hogy dolgozzon ki egy táblázatot, amely megadja az igazság érték F (X, Y, Z), attól függően igazság értékeket az X, Y, Z. Ezt kell áll négy oszlopot: a három - a változók X, Y, Z, és egy - a formula is. Mivel minden egyes változók X, Y, Z feltételezheti két érték (1 vagy 0), akkor megháromszorozza X, Y, Z kapott különböző funkciókat. Ez azt jelenti, hogy az asztalra kellett volna 8 sor. Ahhoz, hogy töltse az utolsó oszlop a táblázatban helyettesítő értékek X, Y és Z a képletben F (X, Y, Z). Például, ha X = 1, Y = 1, Z = 1, van

ha X = 1, Y = 1, Z = 0 találunk

.. stb Ennek eredményeképpen, megtöltjük kapjuk a következő táblázat:

Általában minden formula propozicionális algebra, akkor hozzon létre egy táblázatot, amely megadja az igazság értéke a képlet, attól függően, hogy az igazság-változók értékeit. Egy ilyen táblázatot nevezzük táblázatot

igazság formula

Eljárások az igazság táblázatot lehet egyszerűsíteni néhány trükköt. Hadd illusztráljam ezt a következő példa.

Példa. Hozzon létre egy igazság táblázat a képlet

(By megállapodás értelmében külső zárójeles formula elhagyható).

Az első lépés az, hogy létrehoz egy műveleti sorban. Ehhez a jel minden logikai művelet előforduló képlet meghatározott számú, jelezve a sorozatot ez a művelet. Ebben az esetben van lehetőség, például az ilyen számozás:

Az első sorában (fejlécében) a táblázat írunk X, Y, és ebben a képletben. Az X és Y változók, írunk mindenféle készlet logikai értékeket. Aztán kap egy táblázatot

Oszlop száma 5 (előállított utolsó) ad igazság érték a képlet.

Definíció 1. A képlet propozicionális algebra nevezik azonosan igaz (vagy tautológiánál), ha annak igazság érték egyenlő 1 bármelyik értéke igazság.

Tautológiák szerepe elsősorban az, hogy azok az áramkörök igaz állítások, függetlenül a tartalom és valóságtartalmáért nyilatkozatok alkatrészeket.

Például, a képlet tautológia

( «X vagy X»). Valóban, amit egy adott megnyilatkozás lehet helyettesíteni az X, egy állítás igaz, hiszen

Azonban tautológiáknak jelentősége abban rejlik, nem csak az, hogy ezek segítségével épült állítások igazak; Nem kevésbé fontos az a tény, hogy egy tautológia, így a helyes módszerek következtetést. Mi szemléltetik ezt a példa a általános képletű

Ez a képlet a tautológia; hogy könnyű ellenőrizni, hogy write (egy egység lesz az oszlop értékeit a teljes képlet) annak igazság táblázat. Reakcióvázlat logikai következtetések kifejezve ez a tautológia; általánosan használt matematikai: ez a rendszer az úgynevezett „indirekt bizonyítás”. Nevezetesen, hagyjuk, hogy szükség lehet bizonyítani az állítás X. Azt állítják, mint ez: tegyük fel, hogy X hamis (azaz, ez igaz ..). Ezután a segítségével néhány érv (keretében az elmélet, amely tanult) azt állítják, hogy ez következik utverzhdenieY. és - hogy legyen ellentéte állítást. Mivel egyidejű érvényességét állítások és Y nem lehetséges, A fenti megfontolásokból, arra a következtetésre jutunk az érvényesség (igazság) X.

Nézzük rámutatnak néhány nagyon fontos tautológia.

1. A jogszabályok kommutativitás kötőszó és a diszjunkció:

2. A törvények asszociativitása összefüggésben és a diszjunkció:

3. elosztó törvény:

4. A jogszabályok De Morgan :.

5. A törvény a kizárt harmadik :.

6. szembeállítása :.

7. szabály Chain szabadságvesztés (a törvény a szillogizmus):

8. szabály "modus ponens". .

9. A rendszer a bizonyíték „az ellenkezőjére” :.

Bizonyíték arra, hogy az említett képletek tautológia, tartsa a saját egy gyakorlat.

4. Az átszámítási képleteket

2. Definíció Két képletek és propozicionális algebra nevezzük egyenértékű. amennyiben a logikai változók értékét propozicionális logika értékek az F és H azonos. A egyenértékűségét képletek F és H van írva, mint :.

Van egy szoros kapcsolat a ekvivalencia fogalma képlet és a koncepció tautológia. Ez a következő: általános képletű F és H egyenértékűek, ha, és csak akkor, ha az általános képletű tautológia.

Ez az állítás közvetlenül következik a definíciók magukat

egyenértékűség képletek és tautológiánál.

1. Bizonyítsuk egyenértékűségét képletek és.

Minden ilyen képletek alkotják az igazság táblázat:

Összehasonlítva a táblákat, azt látjuk, hogy ezek a képlet egyenértékű.

2. Kísérleti egyenértékűségét képletek és.

Persze, össze tudja hasonlítani az asztalra az igazság ezek a képletek! Azonban, érvelhetünk ilyen módon: képlet hamis csak akkor, ha X = 1, Y = 0 általános képletű, és - csak akkor, ha X = O, Y = 0, azaz, amikor X = 1, Y = 0. Tehát mind .. formula hamis vagy igaz egyszerre.

Számos equipollences lehet elő egy adott n. 3 tautológiánál. Például, képletek egyenértékűek, mivel a formula tautológia (lásd. Tautológia 4 °).

Meg kell jegyezni, hogy ez a kifejezés nem egy formula. Ez egyszerűen egy rekord a tényt, hogy a képletek az F és H-nak egy bizonyos fajta kapcsolat (vagyis, hogy F egyenértékű H).