Paano malutas ang mga lohikal na formula. Mga sistema ng mga lohikal na equation sa mga problema sa Unified State Exam sa computer science

Ang paggamit ng mga equation ay laganap sa ating buhay. Ginagamit ang mga ito sa maraming mga kalkulasyon, pagtatayo ng mga istruktura at maging sa sports. Gumamit ang tao ng mga equation noong sinaunang panahon, at mula noon ay tumaas lamang ang kanilang paggamit. Sa matematika, may ilang mga problema na tumatalakay sa propositional logic. Upang malutas ang ganitong uri ng equation, kailangan mong magkaroon ng isang tiyak na halaga ng kaalaman: kaalaman sa mga batas ng propositional logic, kaalaman sa mga talahanayan ng katotohanan ng mga lohikal na pag-andar ng 1 o 2 variable, mga pamamaraan para sa pag-convert ng mga lohikal na expression. Bilang karagdagan, kailangan mong malaman ang mga sumusunod na katangian ng mga lohikal na operasyon: conjunction, disjunction, inversion, implication at equivalence.

Anumang lohikal na function ng \variables - \ay maaaring tukuyin ng isang talahanayan ng katotohanan.

Lutasin natin ang ilang lohikal na equation:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Simulan natin ang solusyon sa \[X1\] at tukuyin kung anong mga halaga ang maaaring kunin ng variable na ito: 0 at 1. Susunod, isasaalang-alang natin ang bawat isa sa mga halaga sa itaas at tingnan kung ano ang maaaring maging \[X2.\].

Tulad ng makikita mula sa talahanayan, ang aming lohikal na equation ay may 11 solusyon.

Saan ko malulutas ang isang logic equation online?

Maaari mong lutasin ang equation sa aming website https://site. Ang libreng online solver ay magbibigay-daan sa iyo upang malutas ang mga online na equation ng anumang kumplikado sa loob ng ilang segundo. Ang kailangan mo lang gawin ay ipasok lamang ang iyong data sa solver. Maaari ka ring manood ng mga tagubilin sa video at matutunan kung paano lutasin ang equation sa aming website. At kung mayroon ka pa ring mga katanungan, maaari mong tanungin sila sa aming VKontakte group http://vk.com/pocketteacher. Sumali sa aming grupo, lagi kaming masaya na tulungan ka.

Paglutas ng mga sistema ng mga lohikal na equation sa pamamagitan ng pagbabago ng mga variable

Ang paraan ng pagpapalit ng mga variable ay ginagamit kung ang ilang mga variable ay kasama sa mga equation lamang sa anyo ng isang tiyak na expression, at wala nang iba pa. Pagkatapos ang expression na ito ay maaaring tukuyin ng isang bagong variable.

Halimbawa 1.

Gaano karaming iba't ibang mga hanay ng mga halaga ng mga lohikal na variable x1, x2, x3, x4, x5, x6, x7, x8 ang mayroon na nakakatugon sa lahat ng mga kundisyon na nakalista sa ibaba?

(x1 → x2) → (x3→ x4) = 1

(x3 → x4) → (x5 → x6) = 1

(x5 → x6) → (x7 → x8) = 1

Ang sagot ay hindi kailangang ilista ang lahat ng iba't ibang hanay ng mga halaga ng mga variable na x1, x2, x3, x4, x5, x6, x7, x8, kung saan nasiyahan ang sistemang ito ng pagkakapantay-pantay. Bilang isang sagot, kailangan mong ipahiwatig ang bilang ng mga naturang set.

Solusyon:

(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.

Pagkatapos ay maaari nating isulat ang sistema sa anyo ng isang solong equation:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Ang conjunction ay 1 (true) kapag ang bawat operand ay kumukuha ng value na 1. Iyon ay ang bawat isa sa mga implikasyon ay dapat na totoo, at ito ay totoo para sa lahat ng mga halaga maliban sa (1 → 0). Yung. sa talahanayan ng mga halaga ng mga variable y1, y2, y3, y4, ang isa ay hindi dapat nasa kaliwa ng zero:

Yung. ang mga kondisyon ay nasiyahan para sa 5 set y1-y4.

kasi y1 = x1 → x2, pagkatapos ay ang value na y1 = 0 ay makakamit sa isang set x1, x2: (1, 0), at ang value y1 = 1 – sa tatlong set x1, x2: (0,0) , (0 ,1), (1.1). Gayundin para sa y2, y3, y4.

Dahil ang bawat set (x1,x2) para sa variable na y1 ay pinagsama sa bawat set (x3,x4) para sa variable na y2, atbp., ang mga bilang ng mga set ng mga variable na x ay pinarami:

Pagsamahin natin ang bilang ng mga set: 1 + 3 + 9 + 27 + 81 = 121.

Sagot: 121

Halimbawa 2.

Ilang iba't ibang hanay ng mga halaga ng mga lohikal na variable x1, x2, ... x9, y1, y2, ... y9 mayroon bang nakakatugon sa lahat ng mga kundisyon na nakalista sa ibaba?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

Bilang tugon hindi na kailangan ilista ang lahat ng iba't ibang hanay ng mga halaga ng mga variable na x1, x2, ... x9, y1, y2, ... y9 kung saan nasiyahan ang ibinigay na sistema ng pagkakapantay-pantay. Bilang isang sagot, kailangan mong ipahiwatig ang bilang ng mga naturang set.

Solusyon:

Gumawa tayo ng pagbabago ng mga variable:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Ang sistema ay maaaring isulat bilang isang solong equation:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Ang equivalence ay totoo lamang kung ang parehong operand ay pantay. Mayroong dalawang hanay ng mga solusyon sa equation na ito:

kasi zi = (xi ≡ yi), pagkatapos ay ang value na zi = 0 ay tumutugma sa dalawang set (xi,yi): (0,1) at (1,0), at ang value na zi = 1 ay tumutugma sa dalawang set (xi,yi ): (0 ,0) at (1,1).

Pagkatapos ang unang set z1, z2,…, z9 ay tumutugma sa 2 9 set (x1,y1), (x2,y2),…, (x9,y9).

Ang parehong numero ay tumutugma sa pangalawang set z1, z2,…, z9. Pagkatapos ay mayroong kabuuang 2 9 +2 9 = 1024 set.

Sagot: 1024

Paglutas ng mga sistema ng mga lohikal na equation gamit ang paraan ng visual na pagpapasiya ng recursion.

Ang pamamaraang ito ay ginagamit kung ang sistema ng mga equation ay medyo simple at ang pagkakasunud-sunod ng pagtaas ng bilang ng mga set kapag nagdaragdag ng mga variable ay halata.

Halimbawa 3.

Ilang magkakaibang solusyon mayroon ang sistema ng mga equation?

¬x9 ∨ x10 = 1,

kung saan ang x1, x2, … x10 ay mga lohikal na variable?

Ang sagot ay hindi kailangang ilista ang lahat ng iba't ibang hanay ng mga halaga x1, x2, ... x10 kung saan nasiyahan ang sistemang ito ng pagkakapantay-pantay. Bilang isang sagot, kailangan mong ipahiwatig ang bilang ng mga naturang set.

Solusyon:

Lutasin natin ang unang equation. Ang isang disjunction ay katumbas ng 1 kung hindi bababa sa isa sa mga operand nito ay katumbas ng 1. Iyon ay ang mga solusyon ay ang mga hanay:

Para sa x1=0, mayroong dalawang halaga ng x2 (0 at 1), at para sa x1=1 mayroon lamang isang halaga ng x2 (1), upang ang set (x1,x2) ay isang solusyon sa equation . Mayroong 3 set sa kabuuan.

Idagdag natin ang variable na x3 at isaalang-alang ang pangalawang equation. Ito ay katulad ng una, na nangangahulugan na para sa x2=0 mayroong dalawang halaga ng x3 (0 at 1), at para sa x2=1 mayroon lamang isang halaga x3 (1), upang ang set (x2) ,x3) ay isang solusyon sa equation. Mayroong 4 na set sa kabuuan.

Madaling makita na kapag nagdadagdag ng isa pang variable, isang set ang idinaragdag. Yung. recursive formula para sa bilang ng mga set ng (i+1) variable:

N i +1 = N i + 1. Pagkatapos para sa sampung variable ay makakakuha tayo ng 11 set.

Sagot: 11

Paglutas ng mga sistema ng mga lohikal na equation ng iba't ibang uri

Halimbawa 4.

Ilang iba't ibang hanay ng mga halaga ng mga lohikal na variable x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4 ang naroroon na nakakatugon sa lahat ng mga kondisyong nakalista sa ibaba ?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

Bilang tugon hindi na kailangan ilista ang lahat ng iba't ibang hanay ng mga halaga ng mga variable x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4 kung saan nasiyahan ang sistemang ito ng pagkakapantay-pantay.

Bilang isang sagot, kailangan mong ipahiwatig ang bilang ng mga naturang set.

Solusyon:

Tandaan na ang tatlong equation ng system ay pareho sa iba't ibang independiyenteng hanay ng mga variable.

Tingnan natin ang unang equation. Ang isang conjunction ay totoo (katumbas ng 1) lamang kung ang lahat ng operand nito ay totoo (katumbas ng 1). Ang implikasyon ay 1 sa lahat ng tuple maliban sa (1,0). Nangangahulugan ito na ang solusyon sa unang equation ay ang mga sumusunod na set x1, x2, x3, x4, kung saan ang 1 ay hindi matatagpuan sa kaliwa ng 0 (5 set):

Katulad nito, ang mga solusyon sa pangalawa at pangatlong equation ay magiging ganap na parehong set y1,…,y4 at z1,…, z4.

Ngayon, suriin natin ang ikaapat na equation ng system: x 4 ∧ y 4 ∧ z 4 = 0. Ang solusyon ay magiging lahat ng set x4, y4, z4 kung saan kahit isa sa mga variable ay katumbas ng 0.

Yung. para sa x4 = 0, ang lahat ng posibleng set (y4, z4) ay angkop, at para sa x4 = 1, ang mga set (y4, z4) ay angkop, kung saan mayroong kahit isang zero: (0, 0), (0,1). ), (1, 0).

Ang kabuuang bilang ng mga set ay 25 + 4*9 = 25 + 36 = 61.

Sagot: 61

Paglutas ng mga sistema ng mga lohikal na equation sa pamamagitan ng pagbuo ng mga paulit-ulit na formula

Ang paraan ng pagbuo ng paulit-ulit na mga formula ay ginagamit kapag nilulutas ang mga kumplikadong sistema kung saan ang pagkakasunud-sunod ng pagtaas ng bilang ng mga hanay ay hindi halata, at ang pagtatayo ng isang puno ay imposible dahil sa mga volume.

Halimbawa 5.

Ilang iba't ibang hanay ng mga halaga ng mga lohikal na variable x1, x2, ... x7, y1, y2, ... y7 mayroon bang nakakatugon sa lahat ng mga kundisyon na nakalista sa ibaba?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

Ang sagot ay hindi kailangang ilista ang lahat ng iba't ibang hanay ng mga halaga ng mga variable na x1, x2, ..., x7, y1, y2, ..., y7 kung saan nasiyahan ang sistemang ito ng pagkakapantay-pantay. Bilang isang sagot, kailangan mong ipahiwatig ang bilang ng mga naturang set.

Solusyon:

Tandaan na ang unang anim na equation ng system ay magkapareho at naiiba lamang sa hanay ng mga variable. Tingnan natin ang unang equation. Ang solusyon nito ay ang mga sumusunod na hanay ng mga variable:

Tukuyin natin:

bilang ng mga tuple (0,0) sa mga variable (x1,y1) hanggang A 1,

bilang ng mga tuple (0,1) sa mga variable (x1,y1) hanggang B 1,

bilang ng mga tuple (1,0) sa mga variable (x1,y1) hanggang C 1,

ang bilang ng mga tuple (1,1) sa mga variable (x1,y1) hanggang D 1 .

bilang ng mga tuple (0,0) sa mga variable (x2,y2) hanggang A 2 ,

bilang ng mga tuple (0,1) sa mga variable (x2,y2) hanggang B 2,

bilang ng mga tuple (1,0) sa mga variable (x2,y2) hanggang C 2,

ang bilang ng mga tuple (1,1) sa mga variable (x2,y2) hanggang D 2 .

Mula sa puno ng desisyon ay nakikita natin iyon

A 1 =0, B 1 =1, C 1 =1, D 1 =1.

Tandaan na ang set (0,0) sa mga variable (x2,y2) ay nakuha mula sa set (0,1), (1,0) at (1,1) sa mga variable (x1,y1). Yung. A 2 =B 1 +C 1 +D 1.

Ang set (0,1) sa mga variable (x2,y2) ay nakuha mula sa set (0,1), (1,0) at (1,1) sa mga variable (x1,y1). Yung. B 2 =B 1 +C 1 +D 1.

Sa parehong pagtatalo, napapansin natin na C 2 =B 1 +C 1 +D 1. D2 = D1.

Kaya, nakakakuha kami ng mga paulit-ulit na formula:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i +B i + C i + D i

Gawa tayo ng table

Ang huling equation (x7 ∨ y7) = 1 ay nasiyahan ng lahat ng set maliban sa kung saan ang x7=0 at y7=0. Sa aming talahanayan ang bilang ng mga naturang set ay A 7.

Kung gayon ang kabuuang bilang ng mga set ay B 7 + C 7 + D 7 = 127+127+1 = 255

Sagot: 255

Institusyong pang-edukasyon sa badyet ng munisipyo

"Secondary school No. 18"

urban na distrito ng lungsod ng Salavat ng Republika ng Bashkortostan

Mga sistema ng lohikal na equation

sa Unified State Examination mga problema sa computer science

Ang seksyon na "Mga Pundamental ng Algebra ng Logic" sa mga gawain ng Pinag-isang Estado na Pagsusuri ay itinuturing na isa sa pinakamahirap at mahirap lutasin. Ang average na porsyento ng mga gawaing natapos sa paksang ito ay ang pinakamababa at 43.2.

Batay sa 2018 na detalye ng KIM, ang block na ito ay may kasamang apat na gawain ng iba't ibang antas ng kahirapan.

Ang Gawain 23 ay mataas sa antas ng kahirapan, samakatuwid ito ang may pinakamababang porsyento ng pagkumpleto. Sa mga inihandang nagtapos (81-100 puntos), 49.8% ang nakatapos ng gawain; ang mga nagtapos ng katamtamang paghahanda (61-80 puntos) ay nakakumpleto ng 13.7%; ang natitirang pangkat ng mga mag-aaral ay hindi nakatapos sa gawaing ito.

Ang tagumpay ng paglutas ng isang sistema ng mga lohikal na equation ay nakasalalay sa kaalaman sa mga batas ng lohika at sa tumpak na aplikasyon ng mga pamamaraan para sa paglutas ng sistema.

Isaalang-alang natin ang paglutas ng isang sistema ng mga lohikal na equation gamit ang paraan ng pagmamapa.

(23.154 Polyakov K.Yu.) Ilang magkakaibang solusyon mayroon ang sistema ng mga equation?

((x1  y1 )  (x2  y2 ))  (x1  x2 )  (y1  y2 ) =1

((x2  y2 )  (x3  y3 ))  (x2  x3 )  (y2  y3 ) =1

((x7  y7 )  (x8  y8 ))  (x7  x8 )  (y7  y8 ) =1

saan x1 , x2 ,…, x8, sa1 ,y2 ,…,y8 - mga lohikal na variable? Ang sagot ay hindi kailangang ilista ang lahat ng iba't ibang hanay ng mga variable na halaga kung saan pinanghahawakan ang pagkakapantay-pantay na ito. Bilang isang sagot, kailangan mong ipahiwatig ang bilang ng mga naturang set.

Solusyon. Ang lahat ng mga equation na kasama sa system ay may parehong uri, at ang bawat equation ay may kasamang apat na variable. Alam ang x1 at y1, mahahanap natin ang lahat ng posibleng halaga ng x2 at y2 na nakakatugon sa unang equation. Nangangatuwiran sa katulad na paraan, mula sa kilalang x2 at y2 mahahanap natin ang x3, y3 na nakakatugon sa pangalawang equation. Iyon ay, ang pag-alam sa pares (x1, y1) at pagtukoy sa halaga ng pares (x2, y2), mahahanap natin ang pares (x3, y3), na, naman, ay hahantong sa pares (x4, y4) at iba pa.

Hanapin natin ang lahat ng solusyon sa unang equation. Magagawa ito sa dalawang paraan: bumuo ng talahanayan ng katotohanan, sa pamamagitan ng pangangatwiran at paggamit ng mga batas ng lohika.

Talahanayan ng katotohanan:

Ang pagbuo ng talahanayan ng katotohanan ay masinsinang paggawa at hindi mabisa sa oras, kaya ginagamit namin ang pangalawang paraan - lohikal na pangangatwiran. Ang produkto ay katumbas ng 1 kung at kung ang bawat salik ay katumbas ng 1.

(x1  y1 )  (x2  y2 ))=1

(x1  x2 ) =1

(y1  y2 ) =1

Tingnan natin ang unang equation. Ang kinahinatnan ay katumbas ng 1 kapag 0 0, 0 1, 1 1, na nangangahulugang (x1 y1)=0 para sa (01), (10), pagkatapos ay ang pares (x2  y2 ) maaaring maging anuman (00), (01), (10), (11), at kapag (x1 y1) = 1, ibig sabihin, (00) at (11) ang pares (x2 y2) = 1 ay kumukuha ng parehong mga halaga (00) at (11). Ibukod natin sa solusyon na ito ang mga pares kung saan mali ang pangalawa at pangatlong equation, iyon ay, x1=1, x2=0, y1=1, y2=0.

Kabuuang bilang ng mga pares 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Ilang magkakaibang solusyon mayroon ang sistema ng mga lohikal na equation?

(x 1  (x 2  y 2 ))  (y 1  y 2 ) = 1

(x 2  (x 3  y 3 ))  (y 2  y 3 ) = 1

...

( x 6  ( x 7  y 7 ))  ( y 6  y 7 ) = 1

x 7  y 7 = 1

Solusyon. 1) Ang mga equation ay may parehong uri, kaya gamit ang pangangatwiran ay mahahanap natin ang lahat ng posibleng mga pares (x1,y1), (x2,y2) ng unang equation.

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

Ang solusyon sa pangalawang equation ay ang mga pares (00), (01), (11).

Maghanap tayo ng mga solusyon sa unang equation. Kung x1=0, kung gayon x2, y2 - anuman, kung x1=1, kung gayon ang x2, y2 ay kumukuha ng halaga (11).

Gumawa tayo ng mga koneksyon sa pagitan ng mga pares (x1, y1) at (x2, y2).

Gumawa tayo ng talahanayan upang kalkulahin ang bilang ng mga pares sa bawat yugto.

Isinasaalang-alang ang mga solusyon ng huling equation x 7  y 7 = 1, ibukod natin ang pares (10). Hanapin ang kabuuang bilang ng mga solusyon 1+7+0+34=42

3)(23.180) Ilang magkakaibang solusyon mayroon ang isang sistema ng mga lohikal na equation?

(x1  x2 )  (x3  x4 ) = 1

(x3  x4 )  (x5  x6 ) = 1

(x5  x6 )  (x7  x8 ) = 1

(x7  x8 )  (x9  x10 ) = 1

x1  x3  x5  x7  x9 = 1

Solusyon. 1) Ang mga equation ay may parehong uri, kaya gamit ang pangangatwiran ay mahahanap natin ang lahat ng posibleng mga pares (x1,x2), (x3,x4) ng unang equation.

(x1  x2 )  (x3  x4 ) = 1

Ibukod natin sa solusyon ang mga pares na sa pagkakasunod-sunod ay nagbibigay ng 0 (1 0), ito ang mga pares (01, 00, 11) at (10).

Gumawa tayo ng mga koneksyon sa pagitan ng mga pares (x1,x2), (x3,x4)

Mga tagubilin. Kapag pumapasok mula sa keyboard, gamitin ang mga sumusunod na convention:

Mga panuntunan para sa pagpasok ng isang lohikal na function

1. Sa halip na v (disjunction, OR) na simbolo, gamitin ang + sign.
2. Hindi na kailangang tukuyin ang pagtatalaga ng function bago ang isang lohikal na function. Halimbawa, sa halip na F(x,y)=(x|y)=(x^y) kailangan mong ipasok lamang ang (x|y)=(x^y) .
3. Ang maximum na bilang ng mga variable ay 10.

Ang disenyo at pagsusuri ng mga computer logic circuit ay isinasagawa gamit ang isang espesyal na sangay ng matematika - logic algebra. Sa algebra ng lohika, tatlong pangunahing lohikal na pag-andar ang maaaring makilala: "HINDI" (negation), "AND" (conjunction), "OR" (disjunction).
Upang lumikha ng anumang lohikal na aparato, kinakailangan upang matukoy ang dependence ng bawat isa sa mga output variable sa mga umiiral na input variable; ang dependence na ito ay tinatawag na switching function o isang logic algebra function.
Ang isang lohikal na algebra function ay tinatawag na ganap na tinukoy kung ang lahat ng 2n ng mga halaga nito ay ibinigay, kung saan ang n ay ang bilang ng mga variable ng output.
Kung hindi lahat ng mga halaga ay tinukoy, ang function ay tinatawag na bahagyang tinukoy.
Ang isang aparato ay tinatawag na lohikal kung ang estado nito ay inilalarawan gamit ang isang logic algebra function.
Ang mga sumusunod na pamamaraan ay ginagamit upang kumatawan sa isang lohikal na algebra function:
Sa algebraic form, maaari kang bumuo ng isang circuit ng isang lohikal na aparato gamit ang mga lohikal na elemento.


Figure 1 - Logic device diagram

Ang lahat ng mga operasyon ng algebra ng lohika ay tinukoy mga talahanayan ng katotohanan mga halaga. Tinutukoy ng talahanayan ng katotohanan ang resulta ng isang operasyon para sa lahat ay posible x mga lohikal na halaga ng orihinal na mga pahayag. Ang bilang ng mga opsyon na sumasalamin sa resulta ng paglalapat ng mga operasyon ay depende sa bilang ng mga pahayag sa lohikal na expression. Kung ang bilang ng mga pahayag sa isang lohikal na expression ay N, ang talahanayan ng katotohanan ay maglalaman ng 2 N row, dahil mayroong 2 N magkakaibang kumbinasyon ng mga posibleng halaga ng argumento.

Operation NOT - logical negation (inversion)

• kung totoo ang orihinal na expression, mali ang resulta ng negasyon nito;
• kung mali ang orihinal na expression, magiging totoo ang resulta ng negasyon nito.

O operasyon - lohikal na karagdagan (disjunction, unyon)

Operasyon AT - lohikal na pagpaparami (conjunction)

Operation "IF-THEN" - lohikal na kahihinatnan (implikasyon)

Operasyon "A kung at kung B lamang" (katumbas, katumbas)

Operation "Addition modulo 2" (XOR, eksklusibo o, mahigpit na disjunction)

Priyoridad ng mga lohikal na operasyon

• Mga aksyon sa panaklong
• Pagbabaligtad
• Pang-ugnay (&)
• Disjunction (V), Eksklusibo O (XOR), sum modulo 2
• Implikasyon (→)
• Pagkakatumbas (↔)

Perpektong disjunctive normal na anyo

1. Ang bawat lohikal na termino ng formula ay naglalaman ng lahat ng mga variable na kasama sa function na F(x 1,x 2,...x n).
2. Ang lahat ng mga lohikal na termino ng formula ay iba.
3. Walang isang lohikal na termino ang naglalaman ng variable at ang negasyon nito.
4. Walang lohikal na termino sa isang formula na naglalaman ng parehong variable nang dalawang beses.

Perpektong conjunctive normal na anyo

1. Ang lahat ng elementarya na disjunction ay naglalaman ng lahat ng mga variable na kasama sa function na F(x 1 ,x 2 ,...x n).
2. Ang lahat ng elementarya na disjunction ay iba.
3. Ang bawat elementarya na disjunction ay naglalaman ng isang variable nang isang beses.
4. Walang kahit isang elementarya na disjunction ang naglalaman ng variable at ang negasyon nito.

Mga pamamaraan para sa paglutas ng mga sistema ng mga lohikal na equation

Maaari mong lutasin ang isang sistema ng mga lohikal na equation, halimbawa, gamit ang isang talahanayan ng katotohanan (kung ang bilang ng mga variable ay hindi masyadong malaki) o paggamit ng isang puno ng desisyon, na unang pinasimple ang bawat equation.

1. Paraan ng pagpapalit ng variable.

Ang pagpapakilala ng mga bagong variable ay nagpapahintulot sa iyo na gawing simple ang sistema ng mga equation, na binabawasan ang bilang ng mga hindi alam.Ang mga bagong variable ay dapat na independyente sa bawat isa. Pagkatapos malutas ang pinasimpleng sistema, dapat tayong bumalik sa orihinal na mga variable.

Isaalang-alang natin ang aplikasyon ng paraang ito gamit ang isang partikular na halimbawa.

Halimbawa.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

Solusyon:

Ipakilala natin ang mga bagong variable: A=(X1≡ X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Atensyon! Ang bawat isa sa mga variable na x1, x2, ..., x10 ay dapat isama lamang sa isa sa mga bagong variable na A, B, C, D, E, ibig sabihin, ang mga bagong variable ay independiyente sa bawat isa).

Pagkatapos ang sistema ng mga equation ay magiging ganito:

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

(C ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Bumuo tayo ng decision tree para sa resultang sistema:

Isaalang-alang ang equation A=0, i.e. (X1≡ X2)=0. Ito ay may 2 ugat:

Mula sa parehong talahanayan makikita na ang equation A=1 ay mayroon ding 2 ugat. Ayusin natin ang bilang ng mga ugat sa decision tree:

Upang mahanap ang bilang ng mga solusyon ng isang sangay, kailangan mong i-multiply ang bilang ng mga solusyon sa bawat antas. Ang kaliwang sangay ay may 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 solusyon; ang tamang sangay ay mayroon ding 32 solusyon. Yung. ang buong sistema ay may 32+32=64 na solusyon.

Sagot: 64.

2. Paraan ng pangangatwiran.

Ang kahirapan ng paglutas ng mga sistema ng mga lohikal na equation ay nakasalalay sa pagiging kumplikado ng isang kumpletong puno ng desisyon. Ang paraan ng pangangatwiran ay nagpapahintulot sa iyo na huwag itayo ang buong puno, ngunit upang maunawaan kung gaano karaming mga sanga ang magkakaroon nito. Tingnan natin ang pamamaraang ito gamit ang mga tiyak na halimbawa.

Halimbawa 1. Ilang iba't ibang hanay ng mga halaga ng mga lohikal na variable x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ang naroroon na nakakatugon sa lahat ng mga kundisyon na nakalista sa ibaba?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

x1\/y1 =1

Ang sagot ay hindi kailangang ilista ang lahat ng iba't ibang hanay ng mga halaga ng mga variable na x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 kung saan nasiyahan ang sistemang ito ng pagkakapantay-pantay. Bilang isang sagot, kailangan mong ipahiwatig ang bilang ng mga naturang set.

Solusyon:

Ang una at pangalawang equation ay naglalaman ng mga independiyenteng variable na nauugnay sa ikatlong kondisyon. Bumuo tayo ng puno ng solusyon para sa una at pangalawang equation.

Upang kumatawan sa isang puno ng solusyon para sa isang sistema ng una at pangalawang equation, ang bawat sangay ng unang puno ay dapat ipagpatuloy na may isang puno para sa mga variable. sa . Ang punong itinayo sa ganitong paraan ay maglalaman ng 36 na sanga. Ang ilan sa mga sangay na ito ay hindi nakakatugon sa ikatlong equation ng system. Markahan natin ang bilang ng mga sanga ng puno sa unang puno"y" , na nakakatugon sa ikatlong equation:

Ipaliwanag natin: upang matugunan ang ikatlong kundisyon, kapag x1=0 dapat mayroong y1=1, ibig sabihin, lahat ng sanga ng puno"X" , kung saan ang x1=0 ay maaaring ipagpatuloy na may isang sangay lamang mula sa puno"y" . At para lamang sa isang sanga ng puno"X" (kanan) lahat ng sanga ng puno ay magkasya"y". Kaya, ang kumpletong puno ng buong sistema ay naglalaman ng 11 sanga. Ang bawat sangay ay kumakatawan sa isang solusyon sa orihinal na sistema ng mga equation. Nangangahulugan ito na ang buong sistema ay may 11 solusyon.

Sagot: 11.

Halimbawa 2. Ilang magkakaibang solusyon mayroon ang sistema ng mga equation?

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1

(X1 ≡ X10) = 0

kung saan ang x1, x2, ..., x10 ay mga lohikal na variable? Ang sagot ay hindi kailangang ilista ang lahat ng iba't ibang hanay ng mga variable na halaga kung saan pinanghahawakan ang pagkakapantay-pantay na ito. Bilang isang sagot, kailangan mong ipahiwatig ang bilang ng mga naturang set.

Solusyon: Pasimplehin natin ang sistema. Bumuo tayo ng talahanayan ng katotohanan para sa bahagi ng unang equation:

Bigyang-pansin ang huling column, tumutugma ito sa resulta ng aksyon X1 ≡ X10.

Pagkatapos ng pagpapasimple ay nakukuha namin:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

Isaalang-alang ang huling equation:(X1 ≡ X10) = 0, ibig sabihin. Ang x1 ay hindi dapat tumutugma sa x10. Upang ang unang equation ay maging katumbas ng 1, ang pagkakapantay-pantay ay dapat na totoo(X1 ≡ X2)=1, ibig sabihin. Dapat tumugma ang x1 sa x2.

Bumuo tayo ng puno ng solusyon para sa unang equation:

Isaalang-alang ang pangalawang equation: para sa x10=1 at para sa x2=0 ang bracketdapat katumbas ng 1 (ibig sabihin, ang x2 ay tumutugma sa x3); para sa x10=0 at para sa x2=1 bracket(X2 ≡ X10)=0, na nangangahulugang ang bracket (X2 ≡ X3) dapat ay katumbas ng 1 (ibig sabihin, ang x2 ay tumutugma sa x3):

Nangangatuwiran sa ganitong paraan, bumuo kami ng decision tree para sa lahat ng equation:

Kaya, ang sistema ng mga equation ay may 2 solusyon lamang.

Sagot: 2.

Halimbawa 3.

Ilang iba't ibang hanay ng mga halaga ng mga lohikal na variable x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 ang mayroon na nakakatugon sa lahat ng mga kondisyong nakalista sa ibaba?

(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

Solusyon:

Bumuo tayo ng isang puno ng solusyon para sa 1st equation:

Isaalang-alang ang pangalawang equation:

• Kapag x1=0 : ang pangalawa at pangatlong bracket ay magiging katumbas ng 0; para ang unang bracket ay katumbas ng 1, y1=1, z1=1 (ibig sabihin, sa kasong ito - 1 solusyon)
• Kapag x1=1 : ang unang bracket ay magiging katumbas ng 0; pangalawa o ang ikatlong panaklong ay dapat na katumbas ng 1; ang pangalawang bracket ay magiging katumbas ng 1 kapag y1=0 at z1=1; ang ikatlong bracket ay magiging katumbas ng 1 kapag y1=1 at z1=0 (i.e. sa kasong ito - 2 solusyon).

Katulad din para sa natitirang mga equation. Tandaan natin ang nagresultang bilang ng mga solusyon para sa bawat tree node:

Upang malaman ang bilang ng mga solusyon para sa bawat sangay, i-multiply ang mga resultang numero nang hiwalay para sa bawat sangay (mula kaliwa hanggang kanan).

1 sangay: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 solusyon

Sangay 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 solusyon

3rd branch: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 na solusyon

Ika-4 na sangay: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 solusyon

Ika-5 sangay: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 na solusyon

Pagsamahin natin ang mga resultang numero: mayroong 31 solusyon sa kabuuan.

Sagot: 31.

3. Natural na pagtaas ng bilang ng mga ugat

Sa ilang mga sistema, ang bilang ng mga ugat ng susunod na equation ay nakasalalay sa bilang ng mga ugat ng nakaraang equation.

Halimbawa 1. Ilang iba't ibang hanay ng mga halaga ng mga lohikal na variable x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 ang naroroon na nakakatugon sa lahat ng mga kundisyon na nakalista sa ibaba?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Pasimplehin natin unang equation:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Pagkatapos ang system ay kukuha ng form:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

atbp.

Ang bawat susunod na equation ay may 2 higit pang mga ugat kaysa sa nauna.

4 na equation ay may 12 ugat;

Ang equation 5 ay may 14 na ugat

Ang equation 8 ay may 20 ugat.

Sagot: 20 ugat.

Minsan ang bilang ng mga ugat ay lumalaki ayon sa batas ng Fibonacci.

Ang paglutas ng isang sistema ng mga lohikal na equation ay nangangailangan ng isang malikhaing diskarte.