Cum se rezolvă sarcina 2 a științei calculatoarelor

Ordinea de operațiuni:

• dacă nu există paranteze în expresie, mai întâi se fac toate operațiile "NOT", apoi - "AND", apoi - "OR", implicare, echivalență

Mai multe despre operațiile logice:

• produsul logic X ∙ Y ∙ Z ∙ ... este egal cu 1. adică expresia este adevărată numai dacă toți factorii sunt egali cu 1 (și altfel egali cu 0)
• suma logică X + Y + Z + ... este egală cu 0, adică expresia este falsă numai atunci când toți termenii sunt 0 (și în alte cazuri este 1)

Soluția de rezolvare a problemelor 2 USE în domeniul informaticii

Funcția logică F este dată de expresia (y → x) ∧ (y → z) ∧ z. Determinați care coloană a tabelului de adevăr din F corespunde fiecărei variabile x. y. z.

În răspuns, scrieți literele x. y. z în ordinea în care se află coloanele corespunzătoare.

• Pentru o bază, este necesar să luăm o operație logică, pe care o vom efectua la ultima întoarcere - este logică ȘI (conjuncție) sau ∧
• Conjuncția este mai ușor să se uite la acele rânduri ale mesei, unde funcția F = 1
• Deoarece funcția conjuncției este adevărată numai atunci când toate variabilele sunt adevărate, atunci este necesar să se separe fiecare suport a fost adevărat ((y → x) = 1 și (y → z) = 1), iar variabila z a fost de asemenea adevărat (1)
• Deoarece este mai dificil să lucrăm cu paranteze, mai întâi determinăm care coloană corespunde z. Pentru a face acest lucru, selectăm un rând în care F = 1 iar în restul celulei o singură unitate, iar restul de zerouri:

Pentru această linie, y poate fi 0. dacă x = 0. atunci y = 1. și consolă ca rezultat returnează false (0 → 1 = 0). În consecință, y este în prima coloană. Și x înseamnă în al treilea:

• Deoarece există 5 variabile în fiecare dintre aceste expresii, aceste 5 variabile generează un tabel de adevăr de 32 de linii: fiecare dintre variabile poate lua din două valori (0 sau 1), apoi variante diferite cu cinci variabile vor fi 2 5 = 32. și anume 32 de linii.
• Din aceste 32 de linii pentru fiecare expresie (și F și G) știm cu siguranță doar aproximativ 5 linii: în 4 dintre acestea 1, și în unul - 0.
• Întrebarea este despre numărul de rânduri = 1 pentru tabelul de adevăr al expresiei F ∨ G. Această expresie este o disjuncție care este falsă doar într-un caz - dacă F = 0 și simultan G = 0
• În tabelele originale pentru fiecare expresie F și G știm despre existența unui singur 0, adică în liniile rămase poate fi 1. Astfel. pentru fiecare expresie și F și G în linia 31 poate fi una (32-1 = 31), și numai una - zero.
• Apoi pentru expresia F ∨ G numai într-un caz va fi 0, când atât F = 0, cât și G = 0:

Care dintre următoarele expresii poate fi F?
1) ¬x1 ∧ x2 ∧ ¬x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7
2) x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7
4) x1 ∨ ¬x2 ∨ x3 ∨ x4 ∨ ¬x5 ∨ ¬x6 ∨ x7

• În prima expresie, operația principală este o conjuncție. În consecință, verificăm expresia de pe linia a doua, unde funcția = 1. Dacă înlocuim în această linie toate argumentele expresiei, atunci funcția se întoarce la adevărat. Ie această expresie este adecvată.

A doua expresie este verificată pentru prima și a treia linie, deoarece disjuncția este falsă numai dacă toți operanzii sunt false. Verificând prima linie, vedem imediat că x1 în ea este egală cu 1. În acest caz, funcția va fi = 1. Asta este, această expresie nu se potrivește.

A treia expresie este verificată pe a doua linie, deoarece operația principală - conjuncția - va reveni la adevărat numai atunci când toți operanzii sunt egali cu 1. Vom vedea că x1 = 0, respectiv, funcția va fi de asemenea egală cu 0. expresia nu ne convine.

A patra expresie este verificată prin prima și a treia linie. În prima linie x1 = 1, adică funcția trebuie să fie egală cu 1. expresie, de asemenea, nu se potrivește.

Decizia 2 a sarcinii USE privind informatica (K. Polyakov, versiunea 76):

Fragmentul tabelului de adevăr pentru expresia F este dat:

Specificați numărul maxim posibil de linii diferite ale tabelului cu adevărat complet al acestei expresii, în care valoarea lui x3 nu coincide cu F.

• Tabelul complet al adevărului va avea 2 6 = 64 de linii (pentru că 6 variabile).
• 4 linii sunt cunoscute pentru noi: ele x3 de două ori nu coincide cu F.
• Rânduri necunoscute:
• În șirurile necunoscute x3 nu poate coincide cu F. Mai mult, în două linii cunoscute x3 nu coincide cu F. În consecință, numărul maxim posibil de rânduri cu neconcordanță x3 și F. va fi:

Decizia 2 a sarcinii USE privind informatica (K. Polyakov, varianta 89):

Fiecare expresie logică A și B depinde de același set de 7 variabile. În tabelele de adevăr ale fiecăreia dintre aceste expresii, în coloana cu valori există exact 4 unități. Care este numărul maxim de unități din coloana valorilor tabelului de adevăr al expresiei A ∨ B?

• Tabelul cu adevărat complet pentru fiecare dintre expresiile A și B constă din 2 7 = 128 de linii.
• În patru rânduri, rezultatul expresiei este unul, deci în liniile rămase - 0.
• A ∨ B este adevărat când A = 1 sau B = 1 sau ambele A și B = 1.
• Deoarece A = 1 numai în 4 cazuri, obținem numărul de rezultate care returnează adevărul pentru A ∨ B (în care B poate fi 0 sau 1):

Decizia 2 a sarcinii USE privind informatica (K. Polyakov, varianta 91):

Fiecare expresie logică A și B depinde de același set de 8 variabile. În tabelele de adevăr ale fiecăreia dintre aceste expresii, coloana de valori conține exact 6 unități. Care este numărul maxim posibil de zerouri din coloana valorilor tabelului de adevăr al expresiei A ∧ B?

• Tabelul cu adevărat complet pentru fiecare dintre expresiile A și B constă din 2 8 = 256 de linii.
• În 6 rânduri rezultatul expresiei este egal cu unul, apoi în liniile rămase - 0.
• A ∧ B este falsă în cazul în care fie A = 0, fie B = 0. Sau ambele A și B = 0.
• În toate cazurile, unde A = 1 poate rezista B = 0. și apoi rezultatul F = 0. Deoarece avem nevoie să găsim numărul maxim posibil de zerouri, atunci doar pentru toate șase A = 1 asociem B = 0. și viceversa, pentru toate cele șase posibil B = 1 asociem A = 0

Decizia 2 a sarcinii USE privind informatica (K. Polyakov, versiunea 58):

Având o expresie logică, în funcție de 5 variabile logice:

(X ∨ x ∨ x ∨ x ∨ x5) ∧ (x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5)

Cât de multe seturi diferite de valori variabile există pentru care expresia este adevărată?

• Deoarece expresia include cinci variabile, tabelul de adevăr este format din 2 5 = 32 rânduri
• Funcția de bază este o conjuncție (multiplicare logică), iar în paranteze este o disjuncție (adăugare logică)
• Denumim primul bracket de către A. și al doilea bracket pentru B. Obținem expresia A ∧ B.
• Să vedem câți zerouri există pentru tabela de adevăr a acestei expresii:

Luați în considerare fiecare caz separat:

Decizia 2 a sarcinii USE privind informatica (varianta 112 a lui K.Polyakov):

Fragmentul tabelului de adevăr pentru expresia F este dat:

Ce expresie poate fi F?
1) x1 ∧ (x2 → x3) ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7
2) x1 ∨ (¬x2 → x3) ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ ¬x7
3) ¬x1 ∧ (x2 → ¬x3) ∧ x4 ∧ ¬x5 ∧ x6 ∧ x7
4) ¬x1 ∨ (x2 → ¬x3) ∨ x4 ∨ x5 ∨ x6 ∧ x7

• Să luăm în considerare fiecare expresie separat și să găsim ultima operație care trebuie efectuată.

Funcția logică F este dată de expresie

¬a ∧ b ∧ (c ∨ ¬d)

Mai jos este un fragment al tabelului de adevăr al funcției F. care conține toate seturile de argumente pentru care funcția F este adevărată.
Determinați care coloană a tabelului de adevăr din F corespunde fiecărei variabile a. b. c. d.

Articole similare

• Cum să rezolvăm sarcini în informatică - tehnologia informației - lecții - curs școlar și

• Cum de a rezolva sarcina de 4 ege în informatică - analiza sarcinilor

• Informatică - tipul de sarcini 9 - Ege în domeniul informaticii 2018

Trimiteți-le prietenilor: