Logické rovnice. Systémy logických rovníc v úlohách jednotnej štátnej skúšky z informatiky

Účel služby. Online kalkulačka je určená pre zostavenie pravdivostnej tabuľky pre logický výraz.
Pravdivostná tabuľka – tabuľka obsahujúca všetky možné kombinácie vstupných premenných a im zodpovedajúce výstupné hodnoty.
Pravdivostná tabuľka obsahuje 2n riadkov, kde n je počet vstupných premenných a n+m sú stĺpce, kde m sú výstupné premenné.

Inštrukcie. Pri zadávaní z klávesnice používajte nasledujúce konvencie:

Napríklad logický výraz abc+ab~c+a~bc je potrebné zadať takto: a*b*c+a*b=c+a=b*c
Na zadávanie údajov vo forme logického diagramu použite túto službu.

Pravidlá pre zadávanie logickej funkcie

Namiesto symbolu v (disjunkcia, OR) použite znak +.
Nie je potrebné špecifikovať označenie funkcie pred logickou funkciou. Napríklad namiesto F(x,y)=(x|y)=(x^y) musíte jednoducho zadať (x|y)=(x^y) .
Maximálny počet premenných je 10.

Návrh a analýza počítačových logických obvodov sa vykonáva pomocou špeciálneho odvetvia matematiky - logickej algebry. V algebre logiky možno rozlíšiť tri hlavné logické funkcie: „NOT“ (negácia), „AND“ (konjunkcia), „ALEBO“ (disjunkcia).
Na vytvorenie akéhokoľvek logického zariadenia je potrebné určiť závislosť každej z výstupných premenných od existujúcich vstupných premenných; táto závislosť sa nazýva spínacia funkcia alebo funkcia logickej algebry.
Funkcia logickej algebry sa nazýva úplne definovaná, ak sú zadané všetky jej hodnoty 2n, kde n je počet výstupných premenných.
Ak nie sú definované všetky hodnoty, funkcia sa nazýva čiastočne definovaná.
Zariadenie sa nazýva logické, ak je jeho stav opísaný pomocou funkcie logickej algebry.
Na reprezentáciu funkcie logickej algebry sa používajú nasledujúce metódy:
V algebraickej forme môžete zostaviť obvod logického zariadenia pomocou logických prvkov.

Obrázok 1 - Schéma logického zariadenia

Všetky operácie algebry logiky sú definované pravdivostné tabuľky hodnoty. Pravdivostná tabuľka určuje výsledok operácie pre každý je možný x logické hodnoty pôvodných príkazov. Počet volieb odrážajúcich výsledok aplikovania operácií bude závisieť od počtu príkazov v logickom výraze. Ak je počet výrokov v logickom výraze N, potom pravdivostná tabuľka bude obsahovať 2 N riadkov, keďže existuje 2 N rôznych kombinácií možných hodnôt argumentov.

Operácia NOT - logická negácia (inverzia)

Logická operácia NIE JE aplikovaná na jeden argument, ktorým môže byť jednoduchý alebo zložitý logický výraz. Výsledok operácie NIE JE nasledujúci:

ak je pôvodný výraz pravdivý, potom výsledok jeho negácie bude nepravdivý;
ak je pôvodný výraz nepravdivý, potom výsledok jeho negácie bude pravdivý.

Nasledujúce konvencie nie sú akceptované pre operáciu negácie:
nie A, Ā, nie A, ¬A, !A
Výsledok operácie negácie NIE JE určený nasledujúcou pravdivostnou tabuľkou:

A	nie A
0	1
1	0

Výsledok operácie negácie je pravdivý, keď je pôvodný výrok nepravdivý, a naopak.

Operácia OR - logické sčítanie (rozdelenie, spojenie)

Logická operácia OR vykonáva funkciu spojenia dvoch príkazov, ktoré môžu byť jednoduchým alebo zložitým logickým výrazom. Príkazy, ktoré sú východiskovými bodmi pre logickú operáciu, sa nazývajú argumenty. Výsledkom operácie OR je výraz, ktorý bude pravdivý vtedy a len vtedy, ak bude pravdivý aspoň jeden z pôvodných výrazov.
Použité označenia: A alebo B, A V B, A alebo B, A||B.
Výsledok operácie OR určuje nasledujúca pravdivostná tabuľka:
Výsledok operácie OR je pravdivý, keď A je pravda, alebo B je pravda, alebo A aj B sú pravdivé, a nepravda, keď sú argumenty A a B nepravdivé.

Operácia AND - logické násobenie (konjunkcia)

Logická operácia AND plní funkciu prieniku dvoch tvrdení (argumentov), ktoré môžu byť jednoduchým alebo zložitým logickým výrazom. Výsledkom operácie AND je výraz, ktorý bude pravdivý vtedy a len vtedy, ak sú pravdivé oba pôvodné výrazy.
Použité označenia: A a B, A Λ B, A & B, A a B.
Výsledok operácie AND je určený nasledujúcou pravdivostnou tabuľkou:

A	B	A a B
0	0	0
0	1	0
1	0	0
1	1	1

Výsledok operácie AND je pravdivý vtedy a len vtedy, ak sú výroky A a B pravdivé a nepravdivé vo všetkých ostatných prípadoch.

Operácia „AK-POTOM“ - logický dôsledok (implicita)

Táto operácia spája dva jednoduché logické výrazy, z ktorých prvý je podmienkou a druhý je dôsledkom tejto podmienky.
Použité označenia:
ak A, potom B; A znamená B; ak A, potom B; A→B.
Tabuľka pravdy:

A	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

Výsledok operácie implikácie je nepravdivý iba vtedy, ak je premisa A pravdivá a záver B (dôsledok) nepravdivý.

Operácia „A vtedy a len vtedy, keď B“ (ekvivalencia, ekvivalencia)

Použité označenie: A ↔ B, A ~ B.
Tabuľka pravdy:

A	B	A↔B
0	0	1
0	1	0
1	0	0
1	1	1

Operácia „Addition modulo 2“ (XOR, exkluzívna alebo striktná disjunkcia)

Použitý zápis: A XOR B, A ⊕ B.
Tabuľka pravdy:

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Výsledok operácie ekvivalencie je pravdivý iba vtedy, ak A aj B sú pravdivé alebo nepravdivé súčasne.

Priorita logických operácií

Akcie v zátvorkách
Inverzia
Konjunkcia (&)
Disjunkcia (V), exkluzívne OR (XOR), súčet modulo 2
Implikácia (→)
Ekvivalencia (↔)

Dokonalá disjunktívna normálna forma

Dokonalá disjunktívna normálna forma vzorca(SDNF) je ekvivalentný vzorec, ktorý je disjunkciou elementárnych spojok a má nasledujúce vlastnosti:

Každý logický člen vzorca obsahuje všetky premenné obsiahnuté vo funkcii F(x 1,x 2,...x n).
Všetky logické pojmy vzorca sú odlišné.
Ani jeden logický člen neobsahuje premennú a jej negáciu.
Žiadny logický výraz vo vzorci neobsahuje tú istú premennú dvakrát.

SDNF možno získať buď pomocou pravdivostných tabuliek alebo pomocou ekvivalentných transformácií.
Pre každú funkciu sú SDNF a SCNF jednoznačne definované až do permutácie.

Dokonalá konjunktívna normálna forma

Dokonalá konjunktívna normálna forma vzorca (SCNF) Toto je ekvivalentný vzorec, ktorý je konjunkciou elementárnych disjunkcií a spĺňa vlastnosti:

Všetky elementárne disjunkcie obsahujú všetky premenné obsiahnuté vo funkcii F(x 1 ,x 2 ,...x n).
Všetky elementárne disjunkcie sú odlišné.
Každá elementárna disjunkcia obsahuje raz premennú.
Ani jedna elementárna disjunkcia neobsahuje premennú a jej negáciu.

Používanie rovníc je v našich životoch veľmi rozšírené. Používajú sa pri mnohých výpočtoch, stavbe konštrukcií a dokonca aj v športe. Človek používal rovnice v staroveku a odvtedy sa ich používanie len zvyšuje. V matematike existujú určité problémy, ktoré sa zaoberajú výrokovou logikou. Na vyriešenie tohto druhu rovnice je potrebné mať určité znalosti: znalosť zákonov výrokovej logiky, znalosť pravdivostných tabuliek logických funkcií 1 alebo 2 premenných, metódy na prevod logických výrazov. Okrem toho musíte poznať nasledujúce vlastnosti logických operácií: konjunkcia, disjunkcia, inverzia, implikácia a ekvivalencia.

Akákoľvek logická funkcia \premenných - \môže byť špecifikovaná pravdivostnou tabuľkou.

Poďme vyriešiť niekoľko logických rovníc:

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

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

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

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

Začnime riešenie s \[X1\] a určme, aké hodnoty môže mať táto premenná: 0 a 1. Ďalej zvážime každú z vyššie uvedených hodnôt a uvidíme, čo môže byť \[X2.\].

Ako vidno z tabuľky, naša logická rovnica má 11 riešení.

Kde môžem vyriešiť logickú rovnicu online?

Rovnicu môžete vyriešiť na našej webovej stránke https://site. Bezplatný online riešiteľ vám umožní vyriešiť online rovnice akejkoľvek zložitosti v priebehu niekoľkých sekúnd. Všetko, čo musíte urobiť, je jednoducho zadať svoje údaje do riešiteľa. Na našej stránke si môžete pozrieť aj video návod a naučiť sa riešiť rovnicu. A ak máte stále otázky, môžete sa ich opýtať v našej skupine VKontakte http://vk.com/pocketteacher. Pridajte sa do našej skupiny, vždy vám radi pomôžeme.

Existujú rôzne spôsoby riešenia systémov logických rovníc. Ide o redukciu na jednu rovnicu, zostavenie pravdivostnej tabuľky a rozklad.

Úloha: Vyriešte sústavu logických rovníc:

Uvažujme redukčná metóda na jednu rovnicu . Táto metóda zahŕňa transformáciu logických rovníc tak, aby sa ich pravá strana rovnala pravdivostnej hodnote (tj 1). Na tento účel použite operáciu logickej negácie. Potom, ak rovnice obsahujú zložité logické operácie, nahradíme ich základnými: „A“, „ALEBO“, „NIE“. Ďalším krokom je spojenie rovníc do jednej, ekvivalentnej systému, pomocou logickej operácie „AND“. Potom by ste mali transformovať výslednú rovnicu na základe zákonov logickej algebry a získať konkrétne riešenie systému.

Riešenie 1: Použite inverziu na obe strany prvej rovnice:

Predstavme si implikáciu prostredníctvom základných operácií „ALEBO“ a „NIE“:

Keďže ľavé strany rovníc sú rovné 1, môžeme ich spojiť pomocou operácie „AND“ do jednej rovnice, ktorá je ekvivalentná pôvodnému systému:

Otvoríme prvú zátvorku podľa De Morganovho zákona a transformujeme získaný výsledok:

Výsledná rovnica má jedno riešenie: A =0, B=0 a C=1.

Ďalšia metóda je vytváranie pravdivostných tabuliek . Keďže logické veličiny majú len dve hodnoty, môžete jednoducho prejsť všetky možnosti a nájsť medzi nimi tie, pre ktoré daný systém rovníc vyhovuje. To znamená, že zostavíme jednu spoločnú pravdivostnú tabuľku pre všetky rovnice systému a nájdeme riadok s požadovanými hodnotami.

Riešenie 2: Vytvorme pravdivostnú tabuľku pre systém:








0	0	1	1	0	1

Riadok, pre ktorý sú splnené podmienky úlohy, je zvýraznený tučným písmom. Takže A=0, B=0 a C=1.

spôsob rozklad . Cieľom je zafixovať hodnotu jednej z premenných (nastaviť ju na 0 alebo 1) a tým zjednodušiť rovnice. Potom môžete opraviť hodnotu druhej premennej atď.

Riešenie 3: Nech A = 0, potom:

Z prvej rovnice dostaneme B = 0 a z druhej - C = 1. Riešenie sústavy: A = 0, B = 0 a C = 1.

Na Jednotnej štátnej skúške z informatiky je veľmi často potrebné určiť počet riešení sústavy logických rovníc bez toho, aby sa nachádzali samotné riešenia, existujú na to aj určité metódy. Hlavným spôsobom, ako nájsť počet riešení systému logických rovníc, jenahradenie premenných. Najprv musíte každú z rovníc čo najviac zjednodušiť na základe zákonov logickej algebry a potom nahradiť zložité časti rovníc novými premennými a určiť počet riešení nového systému. Potom sa vráťte k náhrade a určite počet riešení pre ňu.

Úloha: Koľko riešení má rovnica (A →B) + (C →D) = 1? Kde A, B, C, D sú logické premenné.

Riešenie: Zavedme nové premenné: X = A →B a Y = C →D. Ak vezmeme do úvahy nové premenné, rovnica bude napísaná ako: X + Y = 1.

Disjunkcia je pravdivá v troch prípadoch: (0;1), (1;0) a (1;1), zatiaľ čo X a Y sú implikácie, to znamená, že je pravdivá v troch prípadoch a nepravdivá v jednom. Preto prípad (0;1) bude zodpovedať trom možným kombináciám parametrov. Prípad (1;1) – bude zodpovedať deviatim možným kombináciám parametrov pôvodnej rovnice. To znamená, že celkové možné riešenia tejto rovnice sú 3+9=15.

Ďalším spôsobom, ako určiť počet riešení systému logických rovníc, je binárny strom. Pozrime sa na túto metódu pomocou príkladu.

Úloha: Koľko rôznych riešení má systém logických rovníc:

Daný systém rovníc je ekvivalentný rovnici:

(X 1 → X 2 )*(X 2 → X 3 )*…*(x m -1 → x m) = 1.

Predstierajme to X 1 – je pravda, potom to z prvej rovnice dostaneme X 2 tiež pravda, od druhého - X 3 =1 a tak ďalej až do x m= 1. To znamená, že množina (1; 1; …; 1) m jednotiek je riešením systému. Nechaj to teraz X 1 =0, potom z prvej rovnice máme X 2 =0 alebo X 2 =1.

Kedy X 2 true, získame, že zostávajúce premenné sú tiež pravdivé, to znamená, že množina (0; 1; ...; 1) je riešením systému. O X 2 =0 chápeme to X 3 =0 alebo X 3 = a tak ďalej. Pokračovaním k poslednej premennej zistíme, že riešenia rovnice sú nasledujúce množiny premenných (m + 1 riešenie, každé riešenie obsahuje m hodnôt premenných):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Tento prístup je dobre ilustrovaný zostrojením binárneho stromu. Počet možných riešení je počet rôznych vetiev zostrojeného stromu. Je ľahké vidieť, že sa rovná m +1.

	Strom	Počet riešení
x 1
x 2
x 3
		…

V prípade ťažkostí s uvažovaním výskumu a výstavbyriešení, s ktorými môžete hľadať riešenie použitím pravdivostné tabuľky, pre jednu alebo dve rovnice.

Prepíšme sústavu rovníc do tvaru:

A vytvorte pravdivostnú tabuľku samostatne pre jednu rovnicu:

x 1	x 2	(x 1 → x 2)

Vytvorme pravdivostnú tabuľku pre dve rovnice:

x 1	x 2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) (x 2 → x 3)*

Téma lekcie: Riešenie logických rovníc

Vzdelávacie – štúdium metód riešenia logických rovníc, rozvíjanie zručností v riešení logických rovníc a zostrojovanie logického výrazu pomocou pravdivostnej tabuľky;

vývojové - vytvárať podmienky pre rozvoj kognitívneho záujmu žiakov, podporovať rozvoj pamäti, pozornosti a logického myslenia;

Vzdelávacie : podporovať schopnosť počúvať názory iných, pestovanie vôle a vytrvalosti dosiahnuť konečné výsledky.

Typ lekcie: kombinovaná lekcia

Vybavenie: počítač, multimediálny projektor, prezentácia 6.

Počas vyučovania

Opakovanie a aktualizácia základných vedomostí. Kontrola domácich úloh (10 minút)

V predchádzajúcich lekciách sme sa oboznámili so základnými zákonmi logickej algebry a naučili sme sa tieto zákony využívať na zjednodušenie logických výrazov.

Pozrime sa na našu domácu úlohu o zjednodušení logických výrazov:

1. Ktoré z nasledujúcich slov spĺňa logickú podmienku:

(prvopísmenová spoluhláska→druhá písmenová spoluhláska)٨ (posledná samohláska → predposledná samohláska)? Ak existuje niekoľko takýchto slov, uveďte najmenšie z nich.

1) ANNA 2) MARIA 3) OLEG 4) ŠTEPÁN

Predstavme si nasledujúci zápis:

A – spoluhláska prvého písmena

B – spoluhláska druhého písmena

S – samohláska posledného písmena

D – predposledné samohláskové písmeno

Urobme si výraz:

Urobme si tabuľku:

2. Uveďte, ktorý logický výraz je ekvivalentný výrazu

Zjednodušme nahrávanie pôvodného výrazu a navrhovaných možností:

3. Daný fragment pravdivostnej tabuľky výrazu F:

Ktorý výraz sa zhoduje s F?

Určme hodnoty týchto výrazov pre zadané hodnoty argumentov:

Úvod do témy lekcie, prezentácia nového materiálu (30 minút)

Pokračujeme v štúdiu základov logiky a témou našej dnešnej lekcie je „Riešenie logických rovníc“. Po preštudovaní tejto témy sa naučíte základné spôsoby riešenia logických rovníc, získate zručnosti na riešenie týchto rovníc pomocou jazyka logickej algebry a schopnosť zostaviť logický výraz pomocou pravdivostnej tabuľky.

1. Vyriešte logickú rovnicu

(¬K M) → (¬L M N) = 0

Napíšte svoju odpoveď ako reťazec štyroch znakov: hodnoty premenných K, L, M a N (v tomto poradí). Takže napríklad riadok 1101 zodpovedá skutočnosti, že K=1, L=1, M=0, N=1.

Riešenie:

Transformujme výraz(¬K  M) → (¬L  M  N)

Výraz je nepravdivý, keď sú oba pojmy nepravdivé. Druhý člen sa rovná 0, ak M = 0, N = 0, L = 1. V prvom člene K = 0, keďže M = 0, a
.

Odpoveď: 0100

2. Koľko riešení má rovnica (uveďte v odpovedi len číslo)?

Riešenie: transformujte výraz

(A + B)* (C + D) = 1

A + B = 1 a C + D = 1

Metóda 2: zostavenie pravdivostnej tabuľky

3 spôsob: konštrukcia SDNF - dokonalá disjunktívna normálna forma pre funkciu - disjunkcia úplných pravidelných elementárnych konjunkcií.

Transformujme pôvodný výraz, otvorme zátvorky, aby sme získali disjunkciu spojok:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Doplňme spojky na úplné spojky (súčin všetkých argumentov), otvorme zátvorky:

Zoberme do úvahy rovnaké spojky:

Výsledkom je, že získame SDNF obsahujúci 9 konjunkcií. Pravdivostná tabuľka pre túto funkciu má teda hodnotu 1 v 9 riadkoch 2 4 =16 množín hodnôt premenných.

3. Koľko riešení má rovnica (uveďte v odpovedi len číslo)?

Zjednodušme výraz:

3 spôsob: výstavba SDNF

Zoberme do úvahy rovnaké spojky:

Výsledkom je, že získame SDNF obsahujúci 5 konjunkcií. Pravdivostná tabuľka pre túto funkciu má teda hodnotu 1 na 5 riadkoch 2 4 =16 množín hodnôt premenných.

Zostrojenie logického výrazu pomocou pravdivostnej tabuľky:

pre každý riadok pravdivostnej tabuľky obsahujúcej 1 zostavíme súčin argumentov a premenné rovné 0 sú zahrnuté v súčine s negáciou a premenné rovné 1 sú zahrnuté bez negácie. Požadovaný výraz F bude zložený zo súčtu výsledných produktov. Potom, ak je to možné, tento výraz by sa mal zjednodušiť.

Príklad: je uvedená pravdivostná tabuľka výrazu. Zostavte logický výraz.

Riešenie:

3. domáca úloha (5 minút)

Vyriešte rovnicu:

Koľko riešení má rovnica (uveďte v odpovedi iba číslo)?

Pomocou danej pravdivostnej tabuľky zostrojte logický výraz a

zjednodušiť to.