PROPOZICIJSKA LOGIKA

Propozicijska logika je veja matematike, ki preučuje logična razmerja med propozicijami (ali izjavami, stavki, trditvami), vzetimi kot celota in povezanimi preko logičnih veziv.

V tem članku smo podrobno obravnavali propozicionalno logiko in sorodne teme.

Kazalo

Kaj je logika?
Propozicijska logika
Tabela resnice

1. Negacija
2. Veznik
3. Disjunkcija
4. Izključni Or
5. Posledica
6. Bipogojna ali dvojna implikacija

Kaj je logika?

Logika je osnova vsega matematičnega sklepanja in vsega avtomatiziranega sklepanja. Pravila logike določajo pomen matematičnih izjav. Ta pravila nam pomagajo razumeti in sklepati izjave, kot so –

exists~x~such~that~x~ eq~a^2~+~b^2,~where~:x,~a,~bin~Z

Kar v preprosti angleščini pomeni Obstaja celo število, ki ni vsota dveh kvadratov .

Pomen matematične logike

Pravila logike dajejo matematičnim izjavam natančen pomen. Ta pravila se uporabljajo za razlikovanje med veljavnimi in neveljavnimi matematičnimi argumenti. Poleg njenega pomena pri razumevanju matematičnega sklepanja ima logika številne aplikacije v računalništvu, ki se razlikujejo od načrtovanja digitalnih vezij do konstruiranja računalniških programov in preverjanja pravilnosti programov.

Kaj je predlog? Predlog je osnovni gradnik logike. Definiran je kot deklarativni stavek, ki je True ali False, vendar ne oboje. The Resnična vrednost predloga je True (označeno kot T), če je resnična izjava, in False (označeno kot F), če je napačna izjava. Na primer,

Sonce vzhaja na vzhodu in zahaja na zahodu.
1 + 1 = 2
'b' je samoglasnik.

Vsi zgornji stavki so predlogi, pri čemer sta prva dva Veljavna(True), tretji pa Neveljaven(False). Nekateri stavki, ki nimajo resničnostne vrednosti ali imajo lahko več kot eno resničnostno vrednost, niso predlogi. Na primer,

Koliko je ura?
Pojdi ven in se igraj
x + 1 = 2

Zgornji stavki niso predlogi, saj prva dva nimata resničnostne vrednosti, tretji pa je lahko resničen ali napačen. Za zastopanje predlogov, propozicionalne spremenljivke so uporabljeni. Po dogovoru so te spremenljivke predstavljene z majhnimi črkami, kot je nprp,:q,:r,:s . Področje logike, ki se ukvarja s propozicijami, se imenuje propozicijski račun oz propozicijska logika . Vključuje tudi izdelavo novih predlogov z uporabo obstoječih. Propozicije, sestavljene z uporabo ene ali več propozicij, imenujemo sestavljeni predlogi . Predlogi so združeni z uporabo Logični vezniki oz Logični operatorji .

Propozicijska logika

naključni vrstni red sql

Tabela resnice

Ker moramo poznati resničnostno vrednost predloga v vseh možnih scenarijih, upoštevamo vse možne kombinacije predlogov, ki so združeni z logičnimi povezovalci, da tvorijo dani sestavljeni predlog. Ta zbirka vseh možnih scenarijev v obliki tabele se imenuje a tabela resnice . Najpogostejši logični vezniki-

1. Negacija

čep je predlog, nato zanikanjep je označen z eg p , kar v prevodu v preprosto angleščino pomeni- Ni tako str ali preprosto ne str . Resnična vrednost -str je nasprotje resnične vrednosti str . Resnična tabela -str je:

str	¬p
T	F
F	T

primer, Negacija od Danes dežuje, ni tako, da danes dežuje ali preprosto Danes ne dežuje.

2. Veznik

Za katera koli dva predlogap inq , njihovo konjunkcijo označujemo zpwedge q , kar pomenip inq . Veznikpwedge q je res, ko obojep inq so True, sicer False. Resnična tabelapwedge q je:

xml komentar

str	q	p ∧ q
T	T	T
T	F	F
F	T	F
F	F	F

primer, Konjunkcija predlogovp – Danes je petek inq – Danes dežuje,pwedge q je Danes je petek in danes dežuje. Ta predlog je resničen le ob deževnih petkih in je napačen ob vseh drugih deževnih dnevih ali ob petkih, ko ne dežuje.

3. Disjunkcija

Za katera koli dva predlogap inq , je njihova disjunkcija označena zpvee q , kar pomenip ozq . Disjunkcijapvee q je True kadar kolip ozq je True, sicer False. Resnična tabelapvee q je:

str	q	p ∨ q
T	T	T
T	F	T
F	T	T
F	F	F

primer, Disjunkcija predlogovp – Danes je petek inq – Danes dežuje,pvee q je danes petek ali pa danes dežuje. Ta predlog je resničen na kateri koli dan, ki je petek ali deževen dan (vključno z deževnimi petki) in je napačen na kateri koli dan razen petka, ko tudi ne dežuje.

4. Izključni Or

Za katera koli dva predlogap inq , njihov izključni ali je označen zpoplus q , kar pomeni bodisip ozq vendar ne oboje. Ekskluzivni ozpoplus q je True kadar kolip ozq je True in False, ko sta oba resnična ali sta oba napačna. Resnična tabelapoplus q je:

str	q	p ⊕ q
T	T	F
T	F	T
F	T	T
F	F	F

primer, Ekskluzivno ali od predlogovp – Danes je petek inq – Danes dežuje,poplus q Ali je danes petek ali pa danes dežuje, vendar ne oboje. Ta predlog je resničen na kateri koli dan, ki je petek ali deževen dan (razen deževnih petkov) in je napačen na kateri koli dan razen petka, ko ne dežuje ali so deževni petki.

5. Posledica

Za katera koli dva predlogap inq , izjava čep potemq imenujemo implikacija in jo označujemo zp ightarrow q . V implikacijip ightarrow q ,p se imenuje hipoteza oz predhodnik oz prostor inq se imenuje sklep oz posledica . Posledica jep ightarrow q se imenuje tudi a pogojna izjava . Implikacija je napačna, kop je res inq je napačno, drugače je resnično. Resnična tabelap ightarrow q je:

str	q	p → q
T	T	T
T	F	F
F	T	T
F	F	T

Lahko bi se vprašali, zakaj je takop ightarrow q res kop je napačen. To je zato, ker implikacija zagotavlja, da kdajp inq so resnične, potem je implikacija resnična. Toda implikacija ne zagotavlja ničesar, ko premisap je napačen. Od takrat ni mogoče vedeti, ali je implikacija napačna ali nep ni zgodilo. Ta položaj je podoben stališču Nedolžen, dokler krivda ni dokazana, kar pomeni, da je posledicap ightarrow q velja za resnično, dokler se ne dokaže, da je napačna. Ker ne moremo imenovati implikacijep ightarrow q napačno kop je napačno, je naša edina alternativa, da ga imenujemo resnično.

To izhaja iz Načelo eksplozije ki pravi: Napačna izjava implicira karkoli. Pogojne izjave igrajo zelo pomembno vlogo pri matematičnem sklepanju, zato se za izražanje uporablja različna terminologijap ightarrow q , od katerih so nekateri navedeni spodaj.

Če je p, potem qp zadostuje za qq, ko pa je nujen pogoj za p qp le, če qq, razen če ≠pq sledi iz p

primer, Če je petek, potem danes dežuje je predlog, ki je v oblikip ightarrow q . Zgornji predlog je resničen, če ni petek (premisa je napačna) ali če je petek in dežuje, in je napačen, ko je petek, vendar ne dežuje.

6. Bipogojna ali dvojna implikacija

Za katera koli dva predlogap inq , izjavap če in samo če (če)q imenujemo dvopogojnik in ga označujemo zpleftrightarrow q . Izjavapleftrightarrow q se imenuje tudi a dvojna implikacija .pleftrightarrow q ima enako resničnostno vrednost kot(p ightarrow q) wedge (q ightarrow p) Implikacija je resnična, kop inq imajo enake resničnostne vrednosti in so v nasprotnem primeru napačne. Resnična tabelapleftrightarrow q je:

str	q	p ↔ q
T	T	T
T	F	F
F	T	F
F	F	T

Nekateri drugi običajni načini izražanjapleftrightarrow q so:

p je nujen in zadosten za q, če je p potem q, in obratno p, če je q

Primer, danes dežuje, če in samo če je danes petek. je predlog, ki je oblikepleftrightarrow q . Zgornji predlog je resničen, če ni petek in ne dežuje ali če je petek in dežuje, napačen pa je, če ni petek ali ne dežuje. Vaja:

stopala proti stopalu

1) Upoštevajte naslednje izjave:

P: Dobri mobilni telefoni niso poceni.
V: Poceni mobilni telefoni niso dobri.
L: P implicira Q
M: Q implicira P
N: P je enakovreden Q

Katera od naslednjih trditev o L, M in N je PRAVILNA? (Gate 2014)

(A) Samo L je TRUE.

(B) Samo M je TRUE.

(C) Samo N je TRUE.

(D) L, M in N so TRUE.

Za rešitev glej VRATA | GATE-CS-2014-(Set-3) | vprašanje 11

2) Katera od naslednjih ni enakovredna p?q (Gate 2015)

(A)( eg p vee q)wedge(p vee eg q ) (B)( eg p vee q)wedge(q ightarrow p ) (C)( eg p wedge q)vee(p wedge eg q ) (D)( eg p wedge eg q)vee(p wedge q )

Za rešitev glej VRATA | GATE-CS-2015 (Sklop 1) | 65. vprašanje