Bevezetés a matematikai logikába (p.

a) Alternatív elhatárolás, mivel feltételezzük, hogy egy feltétel két, de nem mindkettő.

b) Disjunktúra (bár ha a hangszóró "becsületes", akkor alternatív diszjunkció lehetséges).

c) Alternatív elhatárolás.

A kijelentések és képletek ugyanazok:

a) Ha a Föld ütközik a Napdal, akkor esik;

a) Ugyanaz, hiszen az előfeltétel hamis, és a hazugságok mindent követnek.

b) A következmény hamis abban az esetben, ha az igazság hazugságból következik. Ha igaz, akkor P és Q egyenlő igazságértékeket vesz fel. Ezért a következtetés igaz, és a külső következtetés ugyanaz. Ha hamis, akkor a külső következtetés mindig igaz. Tehát az egész képlet azonos módon igaz.

Más módon, a tanulmány elkészíthetõ a képletünkre vonatkozó igazatáblázat megalkotásával. Construct kondenzált igazság táblázat (azaz, az egyes változó osztja csak egy oszlopot, azon a helyen, az első előfordulása a képletben, az egyes diszjunkció - is az egyik oszlopon, így rögzített képlet ..):

Itt van egy rövidített igazságtáblázat a képlet számára: először a P és Q lehetséges értékeinek oszlopai töltődnek fel. ilyen készletek lesznek; akkor a "belső" logikai kapcsolatok oszlopai (egyenértékűség és jobb implikáció), végül a külső (bal) implikáció oszlopa, amely az egész képlet igazságértékét adja. Az alábbi táblázat mutatja az oszlopok kitöltésének sorrendjét. Mivel a változók igazságértékének bármelyik készletén a képlet csak az 1 értéket veszi fel. akkor ugyanaz igaz.

c) Azonnal vegye fontolóra az igazságtáblát:

Mivel a képlet mindkét igazságértéket figyelembe veheti (lásd a kiválasztott oszlopot), ez nem azonos.

Az igazságtáblák létrehozása a képletekhez:

1.2. A képletek egyszerűsítése. Azonos átalakítások.
Az egyenértékűség, az identitás bizonyítása
az igazság és az identitás hamissága
képletek és logikai függvények

Az elmélet összefoglalása

Ha a logikai képlet algebrajának formális definícióját használjuk, akkor a formula rekord gyakran "extra" zárójeleket tartalmaz, amelyek a jelentés értelmét hátrányosan elhanyagolhatók, ha általánosan elfogadott szabályokat alkalmazunk.

Először is, külön képletekben (vagy ha a képlet határai egyértelműek a kontextusból), elhagyhatja a külső zárójeleket.

Másodszor, mint számtani, ínszalagok és kvantifikátorok lehet rendezni az „erő”, azaz a. E. rendezett egy adott sorrendben, kivéve, hogy a karakterek ebben a sorrendben van, „kötődnek erősebb”, azaz a. E először is végre kell hajtani őket:

Így a diszjunkció és a kapcsolódás erősebb, mint az implikáció, de gyengébb, mint a tagadás. A kötődés erősebb, mint a diszjunkció. A leggyengébb kapcsolat az egyenértékűség. A kvantálók egyenlőek a kötéshez képest (ezt részletesen a 2. részben tárgyaljuk), erősebbek, mint bármelyik logikai összeköttetés.

A proposicionális logika formuláinak formális nyelveinek általános meghatározásával (a továbbiakban egyszerű képletek) összehasonlítva a következő finomításokat végezzük:

1) javasló levelekként (egyedi változók), csak egyszerű kifejezéseket veszünk figyelembe x, y. Z ,. B. B = 1, 0>;

2) komplex egyszerű képleteket csak logikai műveletek és zárójelek segítségével fogunk létrehozni.

Ezzel a megközelítéssel bármely képletet teljes mértékben igazolni fogja az igazságtáblája.

A logikai függvény (vagy a logikai algebra funkciója, egy logikai függvény) minden n változó (n = 1. 2.) függvénye, amelynek definíciós tartománya van, és amelynek értékei a B-ban vannak.

Boole-függvényt nyilvánvalóan egy igazságtáblázat határozza meg, amely pontosan ugyanolyan, mint azok a táblázatok, amelyek képletekre vannak leképezve. Ha az igazság táblázat megadja a boolean függvényt f. egybeesik az Φ valamilyen képlet igazatáblájával. akkor azt mondják, hogy a Φ képlet (vagy definiálja vagy megvalósítja) az f függvényt.

Két Φ képlet és egyenértékűnek mondható (amit Φ jelölik), ha ugyanazt a Boole-függvényt képviselik.

Bármelyik két képlet esetében nincs nehéz ellenőrizni, hogy azok egyenértékűek-e: összehasonlítja az igazságtábláikat.

Boole függvények (minden olyan változó közül), amelyek 1 értéket vesznek fel, függetlenül az argumentumok értékétől, (mint a megvalósító képletek) tautológiák (vagy azonos módon igazak).

Boole-függvények (és azok képleteinek megvalósítása), mindig a 0. értéket nevezzük ellentmondásoknak (vagy azonos módon hamisnak).

Egy adott képlet személyazonosságát vagy azonosságát ugyanazon igazságtáblázaton ellenőrizheti (az eredményként kapott táblázat oszlopa csak a megfelelő konstansot tartalmazza).

A formulák egyenértékűségének vagy az azonos igazságnak vagy hamisítványnak az igazolásával egy másik módszer az úgynevezett alapvető logikai törvények (alapvető egyenértékek) használata, amelyek igazolását a megfelelő igazságtáblák megalkotásával lehet elvégezni. Az alábbi összefüggések általában az alapvető logikai törvényekre vonatkoznak:

A számítások eredményei igazság táblák mindkét részének ekvivalencia nem attól függ, hogy a változók értékét tartalmazza ezeket a kapcsolatokat, t. E. Nem mindegy, hogy ezek a változók függetlenek, vagy pedig eredményeként kapott bármely számításokat. Ezért a fenti ekvivalensek érvényesek maradnak, ha minden változót lecserélünk bármely logikai függvényre, következésképpen ezekre a függvényekre. Fontos, hogy csak egy változó helyettesítőjének helyettesítse a következő szabályt. ha a Φ képletet az x változó helyettesíti, az eredeti relációban lévő x változó összes előfordulását egyidejűleg a Φ képlet segítségével kell helyettesíteni.

Minden algebra (beleértve a funkció logikai algebraát) a reláció
ФФ azt jelenti, hogy a Ф és Ф képletek ugyanazt a logikai függvényt írják le f. Következésképpen, ha bármelyik Φ képlet Φ β szubformulát tartalmaz, akkor a Φη helyettesítése nem változtatja meg a Boolean algebra elemét. mely műveletek végrehajtása a Φ képletben történik; Ezért Φ ', amelyet ilyen helyettesítéssel Φ-ből kapunk, egyenértékű a Φ-val. Ez az állítás az alformulák helyettesítésére vonatkozó szabály. amely lehetővé teszi a rendelkezésre álló egyenértékűségeknek megfelelő képletek megszerzését.

Vegye figyelembe a helyettesítési és helyettesítési szabályok közötti különbséget. Ha helyettesített, a változó helyébe a képlet lép; a képlet lehet bármely. de a változó minden előfordulására helyettesíteni kell. Az alformulák helyett minden szubformulát helyettesítünk, de nem más, csak azzal egyenértékű. Ebben az esetben nincs szükség az eredeti szubformulák összes előfordulásának helyére.

Tegyük fel, hogy ΦΦ ekvivalenciája van, ahol Φ és Φ tartalmazza az x változót. Ha minden Φ-beli esemény előfordulása helyett Φ, akkor egy tetszőleges Φ képletet helyettesítünk. akkor kapunk új Φ 'és Φ' képleteket, és nem feltétlenül ΦΦ 'és ΦΦ'; Az új képletek azonban egyenértékűek egymással: Φ 'Φ'. Ha az alformulát egy azzal egyenértékű képletre cseréljük, egy új képletet kapunk Φ '. amely egyenértékű az F.

Az ilyen transzformációk, a képletek ekvivalenciáját alkalmazva (amelyek állománya helyettesítési szabálysal bővíthető) és a helyettesítő szabály, azonos átalakulásoknak nevezzük. Azonos átalakítások erős bizonyíték egyenértékűség azonos képletek és igaz vagy hamis volta azonos képletek általában sokkal hatékonyabbak, mint a számítást hármas változók (t. E. rajz, mint az igazság táblázatokat).

Megjegyezzük, hogy az egyenértékűség bizonyításának "taktikája" különböző lehet: vagy átalakítjuk az egyik képletet, vagyis a másik formához vezetünk, vagy mindkét képletet átformáljuk, és ugyanazt a képletet vezetjük át.

Bizonyítsuk be a képletek egyenértékűségét az igazságtábláik segítségével:

a) Hasonlítsa össze az igazság táblázatokat a jobb és a bal oldali részekkel:

1.13. Hozz létre egy U képletet úgy, hogy az adott képlet azonos módon igaz:

1.14. Konstruáljon egy képletet három változóból, ha és csak akkor, ha pontosan két változó hamis.

1.15. Hozz létre egy három változóból álló képletet, amely ugyanazt az értéket veszi fel, mint a változók többségét (kisebbségét).

1.3. A javaslati logikai formulák normál képletei

Az elmélet összefoglalása

Egy elemi összekapcsolódás a változók vagy azok negációinak együttese, amelyben minden változó vagy annak negálása nem fordul elő egyszerre.

Az elemi összekapcsolódások bármely diszjunkcióját diszunktív normális formának (DNF) nevezzük.

Megjegyzendő, hogy a DNF függvény (vagy képlet) nem lehet az egyetlen.

A DNP-re redukálandó algoritmust a fenti egyenértékűségek vagy az alapvető logikai törvények segítségével lehet leírni (lásd 1.2. Szakasz). Először is, a törvény (II.1) és a Morgan törvényei (II.2), (II.3) segítségével minden negáció "leereszkedik" a változókra. Ezután a konzolok által ismertetett logikai törvények (I.7), (I. 8.), (IV.7) és (IV.8) eltávolítja a felesleges összefüggésben és a kiújulás változók kötőszavak, és ezen keresztül a logikai törvények (IV.1. ) - (IV.6) a konstansokat törölni kell.

Egy elemi összekapcsolódás szokásosnak mondható. ha minden változó egyszerre lép be (beleértve a negáló jel alatt szereplő eseményeket is).

A rendszeres elemi összekapcsolódás a változók tekintetében teljesnek mondható, ha mindegyik változó egyszerre és csak egyszer (talán a negatív jel alatt) lép be.

Tökéletes Diszjunktív normál forma (PDNF) a változók nevű DNP, amelyben nincs két egyforma elemi kötőszavak és minden elemi kötőszavak helyes és teljes tekintetében a változókat.

A nagy mennyiség miatt ez az anyag több oldalra kerül:
1 2 3